Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #74757 > unrolled thread
| Started by | G G <gdotone@gmail.com> |
|---|---|
| First post | 2015-11-03 06:31 -0800 |
| Last post | 2015-11-20 10:43 +0000 |
| Articles | 20 on this page of 167 — 29 participants |
Back to article view | Back to comp.lang.c
Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 06:31 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 14:57 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:04 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 07:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 15:25 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 20:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:18 -0500
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 20:34 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 22:47 +0000
Re: Is it possible C is the security problem? Udyant Wig <udyantw@gmail.com> - 2015-11-04 15:36 +0530
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:34 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 15:18 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-03 17:42 -0800
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 15:32 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 23:57 +0000
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 21:13 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:22 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:32 +0100
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:54 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:38 +0100
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-07 08:27 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-05 09:26 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 10:03 +0000
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-05 08:53 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-06 10:04 +0000
Re: Is it possible C is the security problem? Reinhardt Behm <rbehm@hushmail.com> - 2015-11-05 21:06 +0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-05 11:14 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 11:44 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-07 02:43 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-07 17:30 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-10 16:35 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-10 11:52 -0500
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-11 00:48 -0600
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:55 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 19:14 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 03:40 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 23:01 -0600
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-18 09:00 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 09:09 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:35 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 21:35 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 20:38 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-19 05:40 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 22:55 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 19:56 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 23:40 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 21:05 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 06:40 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 11:37 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 12:09 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 12:52 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 12:20 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 15:34 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 16:43 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-21 21:28 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 20:51 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 07:26 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-22 09:42 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 09:59 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 07:08 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 11:57 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 16:06 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 13:26 +1300
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-19 09:09 +0000
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 02:29 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 12:33 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-20 09:26 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-19 13:37 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 14:07 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 01:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 18:43 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 12:09 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 01:48 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 11:16 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 05:04 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 18:18 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 11:55 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 00:27 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 18:57 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 19:50 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:06 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 20:46 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:58 -0600
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-21 04:59 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:26 -0600
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-21 14:38 -0500
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 22:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:36 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:44 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 15:59 +0000
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 18:33 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 19:19 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:33 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-22 14:42 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-22 14:17 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 14:51 +1300
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-19 08:06 -0600
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:40 -0600
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 13:57 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:56 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-23 03:16 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 22:28 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-23 21:11 -0800
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-24 10:29 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 02:38 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-27 13:54 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-10 10:23 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-10 11:21 -0800
Re: Is it possible C is the security problem? Melzzzzz <mel@zzzzz.com> - 2015-11-04 00:58 +0100
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:26 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-04 02:06 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 14:12 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:02 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 20:42 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 08:06 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:25 +0100
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-04 11:49 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:46 +0100
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:58 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-17 23:37 +0100
Re: Is it possible C is the security problem? David Thompson <dave.thompson2@verizon.net> - 2015-12-06 07:55 -0500
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-12-06 14:23 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 15:59 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 16:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 02:29 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:48 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 14:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 00:39 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 01:15 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 02:02 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:31 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 12:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:24 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-04 19:37 -0800
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-05 13:24 +0100
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 06:47 -0800
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 00:35 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 09:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 05:02 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-06 10:18 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-06 05:57 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-04 08:32 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:01 +0000
Re: Is it possible C is the security problem? Bartc <bc@freeuk.com> - 2015-11-03 15:10 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 11:02 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 18:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:16 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-04 09:38 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:38 +0100
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-03 11:58 -0500
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 09:13 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-03 18:08 +0000
Re: Is it possible C is the security problem? Nobody <nobody@nowhere.invalid> - 2015-11-04 04:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-04 02:22 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:28 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 08:39 -0800
Re: Is it possible C is the security problem? John Bode <jfbode1029@gmail.com> - 2015-11-03 10:45 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 11:05 -0800
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:09 -0600
Is it possible C is the security problem? Chad <cdalten@gmail.com> - 2015-11-04 01:15 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:31 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-18 10:55 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-18 14:05 -0500
Re: Is it possible C is the security problem? "D. Aaron Sawyer" <aaron@110.net> - 2015-11-18 19:47 -0500
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 10:43 +0000
Page 3 of 9 — ← Prev page 1 2 [3] 4 5 6 7 8 9 Next page →
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-18 21:35 +0000 |
| Message-ID | <87fv03vvn6.fsf@bsb.me.uk> |
| In reply to | #76426 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Wednesday, November 18, 2015 at 5:00:33 PM UTC, Keith Thompson wrote: >> Robert Wessel <robertwessel2@yahoo.com> writes: >> [...] >> > Bubble sort is good on almost sorted lists only when none of the out >> > of place items have to move a long way towards the front of the list >> > (assuming the sort starts at the front end). So: >> > >> > 9 1 2 3 4 5 6 7 8 >> > >> > is fine, the 9 will be moved to the end in the first pass. But: >> > >> > 2 3 4 5 6 7 8 9 1 >> > >> > is horrible, since each pass can only move the 1 back a single >> > position. >> >> There's a variant of bubble sort that reverses direction on each pass. >> (Shuttle sort?) It should deal well with that kind of data. >> >> But of course the worst case is still pretty bad. I think the more interesting point is that the best case is bad too, at least in comparison with other simple algorithms. There is a notion that bubble sort is suitable for some data, but I can't find any evidence for that (I'm ignoring anything that needs to mount a tape!). I've not seem any case where BS beats insertion sort. It may be that it does better on some hardware (for example, it may have interesting cache behaviour on specific data sets) but I still have not found anything that would be called evidence for that. > Use bubble sort for football league type data. If you mean that bubble sort won't be terrible, I agree. But I don't see why you would suggest using it since other simple algorithms will do better. > By that, I mean that all the teams have several points (it only works > halfway through the league). As they play games, obviously a team can > gain three points, or one point, or no points, and can overtake rivals. > But it's very unlikely that a team will move more than one or two places > as the result of any one match. > You get that sort of dataset quite a bit in real life. Why not use insertion sort? Bubble sort is not the only simple algorithm to be good on partially sorted data, and I don't think it is ever the best. Do you think otherwise? If so, can you show some data? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-18 20:38 -0800 |
| Message-ID | <76925f7b-9932-4086-b7ff-aeed34fc5ccd@googlegroups.com> |
| In reply to | #76460 |
On Wednesday, November 18, 2015 at 9:35:19 PM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > By that, I mean that all the teams have several points > > (it only works halfway through the league). As they play > > games, obviously a team can gain three points, or one point, > > or no points, and can overtake rivals. > > But it's very unlikely that a team will move more than one > > or two places as the result of any one match. > > You get that sort of dataset quite a bit in real life. > > Why not use insertion sort? Bubble sort is not the only simple > algorithm to be good on partially sorted data, and I don't > think it is ever the best. Do you think otherwise? If so, > can you show some data? > Bubble sort can terminate after a few passes if the data still isn't sorted. So if we've got a football league type dataset, with occasional shuffling catastrophes, we can resort to quicksort if our assumption that the data is nearly sorted is wrong. I haven't done any tests however.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-11-19 05:40 +0000 |
| Message-ID | <n2jn7m$lq1$1@dont-email.me> |
| In reply to | #76482 |
On 19/11/15 04:38, Malcolm McLean wrote:
> On Wednesday, November 18, 2015 at 9:35:19 PM UTC, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>>
>>> By that, I mean that all the teams have several points
>>> (it only works halfway through the league). As they play
>>> games, obviously a team can gain three points, or one point,
>>> or no points, and can overtake rivals.
>>> But it's very unlikely that a team will move more than one
>>> or two places as the result of any one match.
>>> You get that sort of dataset quite a bit in real life.
>>
>> Why not use insertion sort? Bubble sort is not the only simple
>> algorithm to be good on partially sorted data, and I don't
>> think it is ever the best. Do you think otherwise? If so,
>> can you show some data?
>>
> Bubble sort can terminate after a few passes if the data
> still isn't sorted. So if we've got a football league type
> dataset, with occasional shuffling catastrophes, we can
> resort to quicksort if our assumption that the data is
> nearly sorted is wrong.
> I haven't done any tests however.
I have.
The canonical Football League structure (before they started messing
about with it) is four divisions, with 22 teams in the top two divisions
and 24 in the bottom two. Since each division is independent, each
sorting task is independent, so the worst case is 24 teams to sort, and
even after a heavy winter with many postponed games resulting in a
crowded spring fixture list we are unlikely to need to sort the teams
more than three or four times a week.
I wrote a quick n' dirty test to BubbleSort a number of teams z-a by
points. Here is the struct I was sorting:
struct Division_
{
char name[64];
int played;
int won;
int drawn;
int points;
};
Time to sort 22 teams: Nothing flat.
Time to sort 24 teams: Nothing flat.
Time to sort 100 teams: Nothing flat.
Time to sort 1000 teams: Nothing flat.
So how many teams did it take before gprof would even show me a result
for the sortdivision() function? Answer: 2416.
And how long did it take to do the BubbleSort for 2416 teams? Answer:
one one-hundredth of a second.
We know that BubbleSort doesn't scale well, but let's just say that
we're in no particular hurry and are prepared to wait a whole second for
our result. How many teams can we BubbleSort in that time? Answer: 26850
teams.
But can we actually have that many teams? A game lasts 90 minutes. Allow
the players five minutes at half time and fifteen minutes between games,
but don't let them sleep. So they can play 12 games a day, which is a
maximum of 4392 a year. So we have an upper bound of 2197 teams in a
division, and we have already seen that BubbleSort can deal with these
in a tiny fraction of a second.
So am I advocating BubbleSort? No, of course I'm not.
But it took me less time to write the BubbleSort than it would have
taken to look up the order of parameters in qsort() and then write its
comparison function correctly.
And the runtime I'd have saved by using qsort() instead would have been
so microscopic as to be not worth considering.
Premature optimisation is the root of all evil.
(Nevertheless, if you happen to be one of those vanishingly few
programmers who is /not/ working for the Football League and
consequently need to sort more than a few thousand items, or need to
sort them very frequently, or both, then of course qsort() is a vastly
better option than BubbleSort.)
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-18 22:55 -0800 |
| Message-ID | <ca1c4e83-549d-4434-9e1c-8189e8b208b5@googlegroups.com> |
| In reply to | #76484 |
On Wednesday, November 18, 2015 at 11:40:30 PM UTC-6, Richard Heathfield wrote: > Premature optimisation is the root of all evil. Too bad the authors of the C Standard didn't uphold that philosophy, since the language contains a number of rules whose sole purpose is to facilitate the optimization of some kinds of code, which if followed would cause a massive speed and memory-usage penalties on other kinds of code, and which if ignored will *usually* have no consequences aside from the ability to write programs which vastly outperform strictly-conforming ones.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-19 19:56 +1300 |
| Message-ID | <db5a4nF2f99U3@mid.individual.net> |
| In reply to | #76488 |
supercat@casperkitty.com wrote: > On Wednesday, November 18, 2015 at 11:40:30 PM UTC-6, Richard Heathfield wrote: >> Premature optimisation is the root of all evil. > > Too bad the authors of the C Standard didn't uphold that philosophy, since > the language contains a number of rules whose sole purpose is to facilitate > the optimization of some kinds of code, which if followed would cause a > massive speed and memory-usage penalties on other kinds of code, and which > if ignored will *usually* have no consequences aside from the ability to > write programs which vastly outperform strictly-conforming ones. Care to cite an example of a rule that causes "massive speed and memory-usage penalties"? -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-18 23:40 -0800 |
| Message-ID | <5a28d00d-e875-44bf-aa4c-3b1b7307d083@googlegroups.com> |
| In reply to | #76489 |
On Thursday, November 19, 2015 at 12:56:39 AM UTC-6, Ian Collins wrote:
> Care to cite an example of a rule that causes "massive speed and
> memory-usage penalties"?
The rules that forbid the use of objects of one type with pointers of another
(N1570 6.5.6-7)
Historically, it used to be very common for programs to minimize their use
of malloc/free and instead have most short-term allocation logic handled
by code which manages memory pools of either fixed-sized objects or last-in-
first-out allocate/release semantics. Unfortunately, given the sequence:
double *dp = alloc64(); // Request a 64-byte chunk of memory from pool
dp[4] = 12.34;
free64(dp); // Release that memory back to the pool
int32_t *ip = alloc64(); // Request a 64-byte chunk of memory from pool
ip[8] = 7;
printf("%ld", (long)ip[8]);
free64(ip);
if the compiler could determine that neither free64(dp) nor a subsequent
call to alloc64() would write to bytes 32-39 of *dp, it would be allowed
to rewrite the code as:
double *dp = alloc64(); // Request a 64-byte chunk of memory from pool
free64(dp); // Release that memory back to the pool
int32_t *ip = alloc64(); // Request a 64-byte chunk of memory from pool
ip[8] = 7;
dp[4] = 12.34; // Better late than never, or something(!?)
printf("%d", ip[8]);
free64(ip);
The system guarantees that if one calls the standard-library free() on a
block, no writes that may be pending at that time will have any effect.
Unfortunately, there is no way to achieve that guarantee with any sort of
custom allocator. Consequently, the only ways to get guaranteed-correct
performance are to either use malloc/free a lot (and tolerate the inferior
performance of those functions compared with fixed-sized-block or LIFO
allocators) or else have separate memory pools for every different type
of object.
Thus, code has a choice between one of the following approaches:
1. Use separate pools for different types, which in some cases might double
or even triple the memory requirements, if different types are needed at
different times.
2. Use malloc/free for everything, which may cause memory fragmentation
and/or lead to code spending more time in malloc/free than doing
everything else combined.
3. Ignore those rules, write the code as shown above, and have code which is
way more efficient than either of the above approaches, and will work
unless the allocator happens to supply a block upon which a write is
still pending.
Until fairly recently, code like the above was 100% reliable on most systems
and, as noted, vastly more efficient than any alternative permitted by the
Standard. Alas, some compiler writers see no reason it should be supported.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-19 21:05 +1300 |
| Message-ID | <db5e6rF2f99U4@mid.individual.net> |
| In reply to | #76494 |
supercat@casperkitty.com wrote:
> On Thursday, November 19, 2015 at 12:56:39 AM UTC-6, Ian Collins wrote:
>> Care to cite an example of a rule that causes "massive speed and
>> memory-usage penalties"?
>
> The rules that forbid the use of objects of one type with pointers of another
> (N1570 6.5.6-7)
>
> Historically, it used to be very common for programs to minimize their use
> of malloc/free and instead have most short-term allocation logic handled
> by code which manages memory pools of either fixed-sized objects or last-in-
> first-out allocate/release semantics. Unfortunately, given the sequence:
>
> double *dp = alloc64(); // Request a 64-byte chunk of memory from pool
> dp[4] = 12.34;
> free64(dp); // Release that memory back to the pool
>
> int32_t *ip = alloc64(); // Request a 64-byte chunk of memory from pool
> ip[8] = 7;
> printf("%ld", (long)ip[8]);
> free64(ip);
>
> if the compiler could determine that neither free64(dp) nor a subsequent
> call to alloc64() would write to bytes 32-39 of *dp, it would be allowed
> to rewrite the code as:
>
> double *dp = alloc64(); // Request a 64-byte chunk of memory from pool
> free64(dp); // Release that memory back to the pool
>
> int32_t *ip = alloc64(); // Request a 64-byte chunk of memory from pool
> ip[8] = 7;
> dp[4] = 12.34; // Better late than never, or something(!?)
> printf("%d", ip[8]);
> free64(ip);
How could it? There's no way of knowing that free64 isn't going to
access the data passed to it.
> The system guarantees that if one calls the standard-library free() on a
> block, no writes that may be pending at that time will have any effect.
> Unfortunately, there is no way to achieve that guarantee with any sort of
> custom allocator. Consequently, the only ways to get guaranteed-correct
> performance are to either use malloc/free a lot (and tolerate the inferior
> performance of those functions compared with fixed-sized-block or LIFO
> allocators) or else have separate memory pools for every different type
> of object.
I still don't see how you reach that conclusion.
> Thus, code has a choice between one of the following approaches:
>
> 1. Use separate pools for different types, which in some cases might double
> or even triple the memory requirements, if different types are needed at
> different times.
>
> 2. Use malloc/free for everything, which may cause memory fragmentation
> and/or lead to code spending more time in malloc/free than doing
> everything else combined.
>
> 3. Ignore those rules, write the code as shown above, and have code which is
> way more efficient than either of the above approaches, and will work
> unless the allocator happens to supply a block upon which a write is
> still pending.
>
> Until fairly recently, code like the above was 100% reliable on most systems
> and, as noted, vastly more efficient than any alternative permitted by the
> Standard. Alas, some compiler writers see no reason it should be supported.
Was it?
--
Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-19 06:40 -0800 |
| Message-ID | <b8141646-a457-4238-9ce0-6fa4a076e163@googlegroups.com> |
| In reply to | #76495 |
On Thursday, November 19, 2015 at 2:06:04 AM UTC-6, Ian Collins wrote:
> How could it? There's no way of knowing that free64 isn't going to
> access the data passed to it.
Perhaps it can see into the implementation:
void *next_alloc64;
void *alloc64(void)
{
void *temp = next_alloc64;
next_alloc64 = *(void**)temp;
return temp;
}
void free64(void *p)
{
*(void**)p = next_alloc64;
next_alloc64 = p;
}
If code has some outside means of ensuring that the number of block requests
minus releases won't exceed the number of blocks allocated at startup, the
above is all that would be necessary for the allocate/release functions. A
lot faster than malloc/free, since there's no need to search nor consolidate
free blocks. Otherwise code would have to add a counter to the mix. Still
easily small enough to in-line the common cases, though.
For purposes of this example, I deliberately placed the user-code writes to
the data blocks at places where they wouldn't get clobbered by the writes
used by the memory-allocation logic, but that doesn't actually matter. Even
if I hadn't, a compiler would be able to see that the release and allocate
together are the sequence:
*(void**)dp = next_alloc;
next_alloc = dp;
int *ip= next_alloc;
next_alloc64 = *(void**)ip;
// Result is in temp
If the compiler sees that the value written to *(void**)dp in the release
will never get read after the assignment to next_alloc64 before it gets
overwritten, it could hoist the load to next_alloc64 and omit the store to
*(void**)dp, which would then turn the release/realloc pair into simply
int *ip = (int*)dp;
which would then clearly not do any future writes from or reads to *dp
in any way the compiler had to worry about. Note that it is perfectly
legitimate for a compiler to arbitrarily recognize certain cases where
writes alias while being oblivious to others.
> > The system guarantees that if one calls the standard-library free() on a
> > block, no writes that may be pending at that time will have any effect.
> > Unfortunately, there is no way to achieve that guarantee with any sort of
> > custom allocator. Consequently, the only ways to get guaranteed-correct
> > performance are to either use malloc/free a lot (and tolerate the inferior
> > performance of those functions compared with fixed-sized-block or LIFO
> > allocators) or else have separate memory pools for every different type
> > of object.
>
> I still don't see how you reach that conclusion.
Why could the compiler not perform the above reduction?
> > Until fairly recently, code like the above was 100% reliable on most systems
> > and, as noted, vastly more efficient than any alternative permitted by the
> > Standard. Alas, some compiler writers see no reason it should be supported.
>
> Was it?
Yes. On a compiler which promises suitable memory semantics the code would
be 100% reliable (assuming I typed it right) and way faster than malloc/free.
Look into published embedded operating systems and one will find a lot of
that sort of thing. Can you offer any way to achieve equivalent functionality
and performance without violating C's typing rules?
[toc] | [prev] | [next] | [standalone]
| From | asetofsymbols@gmail.com |
|---|---|
| Date | 2015-11-19 11:37 -0800 |
| Message-ID | <988b8f9f-4be2-4129-8e4f-ce19096d6e71@googlegroups.com> |
| In reply to | #76520 |
For me in that code, in few words, there is one *0 (because compiler initialize global variable with 0) so I think here it will result in a seg fault Excuse but here is difficult quote (text not copy)
[toc] | [prev] | [next] | [standalone]
| From | asetofsymbols@gmail.com |
|---|---|
| Date | 2015-11-19 12:09 -0800 |
| Message-ID | <2af11995-ca85-46cc-bc81-cbe4bc3ebef0@googlegroups.com> |
| In reply to | #76520 |
supe...@casperkitty.com wrote:
On Thursday, November 19, 2015 at 2:06:04 AM UTC-6, Ian Collins wrote:
> How could it? There's no way of knowing that free64 isn't going to
> access the data passed to it.
Perhaps it can see into the implementation:
void *next_alloc64;
void *alloc64(void)
{
void *temp = next_alloc64;
next_alloc64 = *(void**)temp;
return temp;
}
void free64(void *p)
{
*(void**)p = next_alloc64;
next_alloc64 = p;
}
-------
Now it copy...
next_alloc64==0 as pointer to void
void *temp = next_alloc64;
Mean temp==0
next_alloc64 = *(void**)temp;
mean *0
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-19 12:52 -0800 |
| Message-ID | <ad8efff8-88ee-41e0-a703-2cd3d6edbcd6@googlegroups.com> |
| In reply to | #76548 |
On Thursday, November 19, 2015 at 2:09:34 PM UTC-6, asetof...@gmail.com wrote:
> Now it copy...
>
> next_alloc64==0 as pointer to void
Only if nothing else anywhere has modified the contents of that pointer
before the functions were called. The code to set up the allocation pool
was longer than the allocate/release functions, and I didn't think it was
particularly relevant, but it could look something like:
#define ALLOC64_NUM_BLOCKS 16
uint32_t alloc64_storage[ALLOC64_NUM_BLOCKS * 16]; // 16*4 bytes per block
volatile void *effective_type_hider;
void init_alloc64_storage(void)
{
effective_type_hider = alloc64_storage;
unsigned char *storage = effective_type_hider;
for (int i=ALLOC64_NUM_BLOCKS-1; i>0; i--)
*(void**)(storage + i*64+64) = (storage + i*64);
*(void**)storage = 0;
}
Note that if user code always refrained from storing anything other than a
void* in the first four bytes of any block, this allocator would work in
fully-defined fashion unless a copiler went really far out of its way to
break it [since effective_type_hider is an exported volatile, a compiler
would have to allow for the possibility that something the compiler does
not know about could change its value between when it's written and when
it's read, and a compiler has no way of knowing that it couldn't change
to identify an area of malloc storage].
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-20 12:20 +1300 |
| Message-ID | <db73qbFjpqnU3@mid.individual.net> |
| In reply to | #76520 |
supercat@casperkitty.com wrote:
> On Thursday, November 19, 2015 at 2:06:04 AM UTC-6, Ian Collins wrote:
>> How could it? There's no way of knowing that free64 isn't going to
>> access the data passed to it.
>
> Perhaps it can see into the implementation:
>
> void *next_alloc64;
> void *alloc64(void)
> {
> void *temp = next_alloc64;
> next_alloc64 = *(void**)temp;
> return temp;
> }
> void free64(void *p)
> {
> *(void**)p = next_alloc64;
> next_alloc64 = p;
> }
>
> If code has some outside means of ensuring that the number of block requests
> minus releases won't exceed the number of blocks allocated at startup, the
> above is all that would be necessary for the allocate/release functions. A
> lot faster than malloc/free, since there's no need to search nor consolidate
> free blocks. Otherwise code would have to add a counter to the mix. Still
> easily small enough to in-line the common cases, though.
Given this assumption, gcc will reorder the code in a similar way to the
code you just snipped, whether C89 or C99 is selected. So either one of
us or the compiler writers are missing something.
>>> Until fairly recently, code like the above was 100% reliable on most systems
>>> and, as noted, vastly more efficient than any alternative permitted by the
>>> Standard. Alas, some compiler writers see no reason it should be supported.
>>
>> Was it?
>
> Yes. On a compiler which promises suitable memory semantics the code would
> be 100% reliable (assuming I typed it right) and way faster than malloc/free.
> Look into published embedded operating systems and one will find a lot of
> that sort of thing. Can you offer any way to achieve equivalent functionality
> and performance without violating C's typing rules?
I've written more than my share of embedded allocators... I must admit
I probably wasn't to bothered with the finer points of the C aliasing
rules, just that the code did the right thing!
--
Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-19 15:34 -0800 |
| Message-ID | <9a86d336-4b93-42c1-8335-093a12e5b294@googlegroups.com> |
| In reply to | #76570 |
On Thursday, November 19, 2015 at 5:20:59 PM UTC-6, Ian Collins wrote: > Given this assumption, gcc will reorder the code in a similar way to the > code you just snipped, whether C89 or C99 is selected. So either one of > us or the compiler writers are missing something. My expectation was that gcc would not perceive any rule against the reordering; are you saying it does or that it doesn't? I would be mildly surprised if gcc actually reordered the code in this case simply because I see no reason it should be advantageous to do so; does it in fact do so? What are you using to test?
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-22 16:43 +1300 |
| Message-ID | <dbcrvkFjpqnU10@mid.individual.net> |
| In reply to | #76573 |
supercat@casperkitty.com wrote: > On Thursday, November 19, 2015 at 5:20:59 PM UTC-6, Ian Collins wrote: >> Given this assumption, gcc will reorder the code in a similar way to the >> code you just snipped, whether C89 or C99 is selected. So either one of >> us or the compiler writers are missing something. > > My expectation was that gcc would not perceive any rule against the reordering; > are you saying it does or that it doesn't? I would be mildly surprised if gcc > actually reordered the code in this case simply because I see no reason it > should be advantageous to do so; does it in fact do so? What are you using to > test? Yes, it does. I was using your code samples. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-21 21:28 -0800 |
| Message-ID | <41be850d-5cd8-42e4-86c6-8fa876d50e40@googlegroups.com> |
| In reply to | #76830 |
On Saturday, November 21, 2015 at 9:43:57 PM UTC-6, Ian Collins wrote: > supercat wrote: > > My expectation was that gcc would not perceive any rule against the reordering; > > are you saying it does or that it doesn't? I would be mildly surprised if gcc > > actually reordered the code in this case simply because I see no reason it > > should be advantageous to do so; does it in fact do so? What are you using to > > test? > > Yes, it does. I was using your code samples. I was confused, foolishly asked a question in ambiguous fashion, and am thus still confused. Which of the following does gcc do: 1. Reorder the code, or 2. Perceive a rule against reordering the code
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-22 20:51 +1300 |
| Message-ID | <dbdafnFjpqnU12@mid.individual.net> |
| In reply to | #76834 |
supercat@casperkitty.com wrote: > On Saturday, November 21, 2015 at 9:43:57 PM UTC-6, Ian Collins wrote: >> supercat wrote: > >>> My expectation was that gcc would not perceive any rule against the reordering; >>> are you saying it does or that it doesn't? I would be mildly surprised if gcc >>> actually reordered the code in this case simply because I see no reason it >>> should be advantageous to do so; does it in fact do so? What are you using to >>> test? >> >> Yes, it does. I was using your code samples. > > I was confused, foolishly asked a question in ambiguous fashion, and am thus > still confused. Which of the following does gcc do: > > 1. Reorder the code, or > > 2. Perceive a rule against reordering the code Reorder the code. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-22 07:26 -0800 |
| Message-ID | <23301a97-1862-4486-ad35-98bf277cb334@googlegroups.com> |
| In reply to | #76838 |
On Sunday, November 22, 2015 at 1:51:32 AM UTC-6, Ian Collins wrote: > Reorder the code. Returning to the subject of the thread, would you think it unreasonable for someone to expect that if a 64-block of memory is requested from a memory manager that it should not have any writes pending to it from an earlier user thereof, and that an inability to ensure that is a huge security risk? In many embedded systems there isn't much extra RAM, so the fragmentation that would often come from using free/malloc to "scrub" memory would pose unacceptable risks; the ability to use other kinds of memory management is absolutely essential, but C makes it impossible to do so safely.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-22 09:42 -0800 |
| Message-ID | <c844e8a1-4dbf-45e1-b6f8-541ae6c243cb@googlegroups.com> |
| In reply to | #76872 |
On Sunday, November 22, 2015 at 3:26:20 PM UTC, supe...@casperkitty.com wrote: > > Returning to the subject of the thread, would you think it unreasonable > for someone to expect that if a 64-block of memory is requested from a > memory manager that it should not have any writes pending to it from > an earlier user thereof, and that an inability to ensure that is a huge > security risk? > > In many embedded systems there isn't much extra RAM, so the fragmentation > that would often come from using free/malloc to "scrub" memory would pose > unacceptable risks; the ability to use other kinds of memory management is > absolutely essential, but C makes it impossible to do so safely. > Depends on the system. A typical embedded system doesn't have that kind of security risk. Nor does a games console. On the other hand if memory is released by one program and read by another, on a general- purpose computer, you certainly have an issue.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-22 09:59 -0800 |
| Message-ID | <46ce2d98-a7f8-47bf-a83a-d56defe3c679@googlegroups.com> |
| In reply to | #76892 |
On Sunday, November 22, 2015 at 11:42:49 AM UTC-6, Malcolm McLean wrote:
> On Sunday, November 22, 2015 at 3:26:20 PM UTC, supercat wrote:
> > In many embedded systems there isn't much extra RAM, so the fragmentation
> > that would often come from using free/malloc to "scrub" memory would pose
> > unacceptable risks; the ability to use other kinds of memory management is
> > absolutely essential, but C makes it impossible to do so safely.
> >
> Depends on the system. A typical embedded system doesn't have that
> kind of security risk. Nor does a games console. On the other hand if
> memory is released by one program and read by another, on a general-
> purpose computer, you certainly have an issue.
The issue isn't one of releasing memory to one program that gets used by
another. The issue is that if a program allocates some memory, uses it to
hold one structure type, releases it, requests another allocation (which
gets satisfied using the same block), and uses that second allocation to
hold a different structure type, the contents of the second block may get
arbitrarily corrupted at any time, and--even more bizarrely--the contents
of the first block may get *retroactively* corrupted!
Thus, for example, given code like:
SECURITY_PERMISSIONS *sec = _box_alloc(pool);
load_permissions(sec, user_id);
int user_permission = sec->permission;
_box_free(pool, sec);
USER_INFO *inf = _box_alloc(pool);
load_user_description(inf, user_id);
show_user_info(inf);
_box_free(pool, inf);
if (user_permission & ALLOW_ACCESS_TO_SUPER_SECURE_VAULT)
show_super_secret_stuff();
a compiler could rework the code as:
SECURITY_PERMISSIONS *sec = _box_alloc(pool);
load_permissions(sec, user_id);
_box_free(pool, sec);
USER_INFO *inf = _box_alloc(pool);
load_user_description(inf, user_id);
show_user_info(inf);
_box_free(pool, inf);
if (sec->permission & ALLOW_ACCESS_TO_SUPER_SECURE_VAULT)
show_super_secret_stuff();
A lot of internet connections these days are implemented using processors
with 4K or less of RAM, so the ability to reuse memory is critical, but
C provides no way to perform type-agnostic memory management safely.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-23 07:08 +0000 |
| Message-ID | <n2ue1l$34f$1@speranza.aioe.org> |
| In reply to | #76893 |
supercat@casperkitty.com wrote: (snip) > The issue isn't one of releasing memory to one program that gets used by > another. The issue is that if a program allocates some memory, uses it to > hold one structure type, releases it, requests another allocation (which > gets satisfied using the same block), and uses that second allocation to > hold a different structure type, the contents of the second block may get > arbitrarily corrupted at any time, and--even more bizarrely--the contents > of the first block may get *retroactively* corrupted! Seems to me that if a compiler allows that kind of reordering, it has to avoid doing what you say. The standard can't mention all the ways that compilers could go wrong. That doesn't mean that compilers never have bugs, and that one might do this. -- glen
[toc] | [prev] | [next] | [standalone]
Page 3 of 9 — ← Prev page 1 2 [3] 4 5 6 7 8 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web