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 2 of 9 — ← Prev page 1 [2] 3 4 5 6 7 8 9 Next page →
| From | Jorgen Grahn <grahn+nntp@snipabacken.se> |
|---|---|
| Date | 2015-11-07 08:27 +0000 |
| Message-ID | <slrnn3rdet.5q5.grahn+nntp@frailea.sa.invalid> |
| In reply to | #74816 |
On Wed, 2015-11-04, David Brown wrote: > On 04/11/15 00:57, Richard Heathfield wrote: >> On 03/11/15 23:32, Geoff wrote: > >>> >>> Human: > >>> 2. Failure to test. >> >> I'm sure they did test. But you only test against stuff you predict >> could happen. (For example, you don't test for negative-length strings.) >> This was a failure of prediction. It doesn't appear to have occurred to >> anyone that Alice might tell lies. >> > > The "failure to test" was that the code was not properly tested by > outside parties. When developers do the tests, they think in terms of > the code they have written. They should think in terms of what the code is supposed to do. But yes, you're influenced by how the problem is stated, how the code is designed, and (if you wrote it) your thinking while you wrote it. > Tests for code like this has to be done by > others - people who think like expert testers, and are concentrating on > trying to break the code rather than to see that it works. As you said > earlier, white hats should have been involved here. > > I am sure the developers did /their/ side of the testing reasonably well > - it is the support around the developers that failed. This makes me vaguely uncomfortable. IMO, bugs like this one are best found by code review. The original developer should be involved in that: you cannot shrink from the responsibility to take a step back and analyze the behavior for what you've written. I don't want developers who don't think about security because they believe someone else will do it for them. If nothing else, that will make them write code that's harder to review. Others (let's call them testers) should be involved too, but there's a distinct risk that they buy into the assumptions embedded in the code, and fall into the same mental traps as the developer. I don't trust blackbox testing to find security flaws in general. Although it may have worked for Heartbleed -- Codenomicon, one of the companies involved, sell fuzzing tools. I wonder how far static analysis tools can take you. For Heartbleed, it doesn't seem so hard to detect a code path which sends N octets over a socket, without a connection between that N, and the M octets used to fill the buffer. /Jorgen -- // Jorgen Grahn <grahn@ Oo o. . . \X/ snipabacken.se> O o .
[toc] | [prev] | [next] | [standalone]
| From | Jorgen Grahn <grahn+nntp@snipabacken.se> |
|---|---|
| Date | 2015-11-05 09:26 +0000 |
| Message-ID | <slrnn3m86v.5q5.grahn+nntp@frailea.sa.invalid> |
| In reply to | #74783 |
On Tue, 2015-11-03, Richard Heathfield wrote: > On 03/11/15 23:32, Geoff wrote: ... >> There were several failures (it always takes more than one to make a >> disaster) but they weren't all human errors. >> >> Human: >> 0. Writing the OpenSSL in C and not in C++. > > I disagree. It's just as easy to screw up the code in C++ as it is in C. > Easier, possibly, because one is so much more accustomed to taking > things for granted in C++. I don't take things for granted, unless they /can/ be taken for granted. Which things are you thinking of? (The only thing that comes to mind is DOS attacks on the tree- and hash table-based containers. It's easy to pretend that these are always well-balanced and log(N).) Still, I think Geoff over-simplifies. It's not hard to screw up in C++, because the basic philosophy is the same as in C. You have pointers (and references, and iterators) which may turn bad. Integers overflow in the same ways. There's typically not more bounds checking on a std::vector or a std::string than on a C array, because the speed considerations are there. However, you /do/ get tools that help you write safer code, if you use them: containers, exceptions, classes, ... I find they help a lot -- although I still need to use my brain. /Jorgen -- // Jorgen Grahn <grahn@ Oo o. . . \X/ snipabacken.se> O o .
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-11-05 10:03 +0000 |
| Message-ID | <n1f9ds$cuj$1@dont-email.me> |
| In reply to | #74936 |
On 05/11/15 09:26, Jorgen Grahn wrote:
> On Tue, 2015-11-03, Richard Heathfield wrote:
>> On 03/11/15 23:32, Geoff wrote:
> ...
>>> There were several failures (it always takes more than one to make a
>>> disaster) but they weren't all human errors.
>>>
>>> Human:
>>> 0. Writing the OpenSSL in C and not in C++.
>>
>> I disagree. It's just as easy to screw up the code in C++ as it is in C.
>> Easier, possibly, because one is so much more accustomed to taking
>> things for granted in C++.
>
> I don't take things for granted, unless they /can/ be taken for granted.
I don't even take for granted the fact that I don't take things for
granted unless they can be taken for granted. I am open to the
possibility that I unwittingly take some things for granted because they
can be taken for granted even though in fact they cannot be taken for
granted (despite which, somehow, I manage to take them for granted
anyway, which gives rise to a curious paradox).
> Which things are you thinking of?
Stretchy "strings", stretchy "arrays" in general, dictionaries
("maps")... in fact, now that I come to think of it, I meant the STL! :-)
--
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 | James Kuyper <jameskuyper@verizon.net> |
|---|---|
| Date | 2015-11-05 08:53 -0500 |
| Message-ID | <n1fmss$v2q$1@dont-email.me> |
| In reply to | #74942 |
On 11/05/2015 05:03 AM, Richard Heathfield wrote:
> On 05/11/15 09:26, Jorgen Grahn wrote:
>> On Tue, 2015-11-03, Richard Heathfield wrote:
>>> On 03/11/15 23:32, Geoff wrote:
>> ...
>>>> There were several failures (it always takes more than one to make a
>>>> disaster) but they weren't all human errors.
>>>>
>>>> Human:
>>>> 0. Writing the OpenSSL in C and not in C++.
>>>
>>> I disagree. It's just as easy to screw up the code in C++ as it is in C.
>>> Easier, possibly, because one is so much more accustomed to taking
>>> things for granted in C++.
>>
>> I don't take things for granted, unless they /can/ be taken for granted.
...
>> Which things are you thinking of?
>
> Stretchy "strings", stretchy "arrays" in general, dictionaries
> ("maps")... in fact, now that I come to think of it, I meant the STL! :-)
OK - I don't see the problem. In C++, the STL is a prime example of
what Jorgen was talking about - things that "/can/ be taken for
granted." I can understand criticism of C++ code for misusing the STL,
but not for making the mistake of taking it for granted - because it
has, in fact, been granted, so that's not a mistake.
--
James Kuyper
[toc] | [prev] | [next] | [standalone]
| From | Jorgen Grahn <grahn+nntp@snipabacken.se> |
|---|---|
| Date | 2015-11-06 10:04 +0000 |
| Message-ID | <slrnn3oup1.5q5.grahn+nntp@frailea.sa.invalid> |
| In reply to | #74967 |
On Thu, 2015-11-05, James Kuyper wrote:
> On 11/05/2015 05:03 AM, Richard Heathfield wrote:
>> On 05/11/15 09:26, Jorgen Grahn wrote:
>>> On Tue, 2015-11-03, Richard Heathfield wrote:
>>>> On 03/11/15 23:32, Geoff wrote:
>>> ...
>>>>> There were several failures (it always takes more than one to make a
>>>>> disaster) but they weren't all human errors.
>>>>>
>>>>> Human:
>>>>> 0. Writing the OpenSSL in C and not in C++.
>>>>
>>>> I disagree. It's just as easy to screw up the code in C++ as it is in C.
>>>> Easier, possibly, because one is so much more accustomed to taking
>>>> things for granted in C++.
>>>
>>> I don't take things for granted, unless they /can/ be taken for granted.
> ...
>>> Which things are you thinking of?
>>
>> Stretchy "strings", stretchy "arrays" in general, dictionaries
>> ("maps")... in fact, now that I come to think of it, I meant the STL! :-)
>
> OK - I don't see the problem. In C++, the STL is a prime example of
> what Jorgen was talking about - things that "/can/ be taken for
> granted." I can understand criticism of C++ code for misusing the STL,
> but not for making the mistake of taking it for granted - because it
> has, in fact, been granted, so that's not a mistake.
Yes. And if RH meant to say "take certain properties of the STL for
granted", I hope noone assumes a std::string has bounds checking, or
that you can keep a pointer into a string and then modify it ... But
for a C programmer, that should not be a problem -- it follows the
same old pattern!
It's much more interesting IMHO to contrast C and C++ to Python or
some other radically different language.
/Jorgen
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
[toc] | [prev] | [next] | [standalone]
| From | Reinhardt Behm <rbehm@hushmail.com> |
|---|---|
| Date | 2015-11-05 21:06 +0800 |
| Message-ID | <n1fk4b$ikl$2@dont-email.me> |
| In reply to | #74936 |
Jorgen Grahn wrote: > However, you do get tools that help you write safer code, if you use > them: containers, exceptions, classes, ... I find they help a lot -- > although I still need to use my brain. That is the major point. People should use that CPU with several man-million year of development - called brain, even if it's still version 1.0 - and not rely on the computer and/or programming language to do the thinking for them. -- Reinhardt
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-05 11:14 -0800 |
| Message-ID | <lnbnb85kdo.fsf@kst-u.example.com> |
| In reply to | #74959 |
Reinhardt Behm <rbehm@hushmail.com> writes:
> Jorgen Grahn wrote:
>> However, you do get tools that help you write safer code, if you use
>> them: containers, exceptions, classes, ... I find they help a lot --
>> although I still need to use my brain.
>
> That is the major point.
> People should use that CPU with several man-million year of development -
> called brain, even if it's still version 1.0 - and not rely on the computer
> and/or programming language to do the thinking for them.
A counterargument to that is that any thinking that *can* be done
mechanically *should* be done mechanically.
Of course that can be taken too far, but for example those of us who
choose to program in C rather than in assembly or machine language are
letting the compiler do a great deal of "thinking" for us.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-05 11:44 -0800 |
| Message-ID | <a191f2cd-644e-4440-86d9-d824cbdab76b@googlegroups.com> |
| In reply to | #75002 |
On Thursday, November 5, 2015 at 1:14:38 PM UTC-6, Keith Thompson wrote: > Reinhardt Behm writes: > > People should use that CPU with several man-million year of development - > > called brain, even if it's still version 1.0 - and not rely on the computer > > and/or programming language to do the thinking for them. > > A counterargument to that is that any thinking that *can* be done > mechanically *should* be done mechanically. I would balance both arguments by saying that humans will almost always know a program's requirements in greater detail than a compiler ever could, but a compiler will often know more about how to achieve objectives that it knows about. In cases where a language provides multiple ways of doing something whose effects, though subtly different, would all meet requirements, a compiler may be able to better judge than a programmer which would be more efficient, but if there's no way for a programmer to let the compiler know which choices would be acceptable or unacceptable there will be no way for the compiler to use its knowledge about which would be more efficient.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-07 02:43 -0800 |
| Message-ID | <b21f92a7-2ac8-47f6-a4d5-5a22938ff0bf@googlegroups.com> |
| In reply to | #75007 |
On Thursday, November 5, 2015 at 7:44:26 PM UTC, supe...@casperkitty.com wrote: > > I would balance both arguments by saying that humans will almost > always know a program's requirements in greater detail than a > compiler ever could, but a compiler will often know more about how > to achieve objectives that it knows about. In cases where a language > provides multiple ways of doing something whose effects, though subtly > different, would all meet requirements, a compiler may be able to better > judge than a programmer which would be more efficient, but if there's > no way for a programmer to let the compiler know which choices would > be acceptable or unacceptable there will be no way for > the compiler to use its knowledge about which would be more efficient. > Compilers are good at micro-optimising. But they can't understand program requirements at a high level. It would be very challenging to get a compiler to detect when a bubble sort was being coded and replace with a quicksort. It's entirely impossible for a compiler to know whether the programmer was a naive one who doesn't know how to write a better sort, or a highly skilled one who is expecting "football league" type data.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-07 17:30 -0800 |
| Message-ID | <00625b10-fbaa-479e-b705-c1b80e1658ac@googlegroups.com> |
| In reply to | #75243 |
On Saturday, November 7, 2015 at 4:43:32 AM UTC-6, Malcolm McLean wrote:
> On Thursday, November 5, 2015 at 7:44:26 PM UTC, supe...@casperkitty.com wrote:
> >
> > I would balance both arguments by saying that humans will almost
> > always know a program's requirements in greater detail than a
> > compiler ever could, but a compiler will often know more about how
> > to achieve objectives that it knows about. In cases where a language
> > provides multiple ways of doing something whose effects, though subtly
> > different, would all meet requirements, a compiler may be able to better
> > judge than a programmer which would be more efficient, but if there's
> > no way for a programmer to let the compiler know which choices would
> > be acceptable or unacceptable there will be no way for
> > the compiler to use its knowledge about which would be more efficient.
> >
> Compilers are good at micro-optimising. But they can't understand
> program requirements at a high level.
They could easily understand a lot more about requirements than C allows
them to express. For example, many programs are subject to one of the
following requirements:
1. Overflow must not result in the program producing results that are
seemingly valid but wrong.
2. Overflow within certain computations must not interfere with
evaluation of certain others.
Such requirements are very common, and would not be at all complicated
for compilers to honor. Historically, some compilers would honor the first
requirement by generating code which would cause abnormal program
termination on overflow; others would honor the second by having overflow
yield some kind of value (sometimes well-specified, sometimes unspecified,
and sometimes indeterminate). No platform should have any particular
difficulty honoring either of those requirements, and in many cases a
compiler which was tasked with generating code meeting one of those
requirements would be able to do so much more efficiently than a human.
Among other things, note that the first requirement does not require that
all overflows be trapped--merely those which would otherwise cause a program
to produce incorrect results. If a function which returns a value which is
sometimes used and sometimes ignored were compiled under an "overflows must
not produce wrong results" option, a compiler would be free to skip the
computation altogether in cases where the result would be ignored, but if
user code checked and trapped overflows, a compiler would have to generate
code to perform the useless computations and trap irrelevant overflows.
Further, given a computation like:
a=b+c+d+e+f;
a processor which can perform calculations on a larger-than-int type just as
fast as on "int" could compute the sum of all the values and then check
whether the result was within the range of "int", rather than having to
check each intermediate result for overflow. Performing computations with
strict overflow checking is often very expensive, but accepting looser
semantics should allow compilers to produce overflow-checked machine code
which is a lot less costly than user-written code could be (often there will
be some places where overflow-checking code is essentially free, and others
where it is costly; a compiler will know which is which, but a programmer in
many cases can't).
As an example, on ARM7-TDMI, a function to add a multiple of eight 32-bit
numbers with overflow checking could be written as something like:
lp:
ldrmia r0,{r4-r11} // Fetch eight numbers
adds r1,r4
addnvs r1,r5 // Perform add if no overflow
addnvs r1,r6 // Perform add if no overflow
addnvs r1,r7 // Perform add if no overflow
addnvs r1,r8 // Perform add if no overflow
addnvs r1,r9 // Perform add if no overflow
addnvs r1,r10 // Perform add if no overflow
addnvs r1,r11 // Perform add if no overflow
addnvs r2,#1 // Increment r2 if no overflow
bnv lp // Loop if no overflow
Assuming r2 has been adjusted so that it will overflow on the last pass
through the loop, this code will sum eight words from memory with *zero*
extra per-iteration cost for the overflow checking (after the loop exits
code would have to test r2 to find out if it reached 0x80000000). I would
consider it plausible that a well-designed compiler which supported such
semantics could find the above code. I don't think there's anything a
programmer could write that would yield anything that wasn't a lot slower.
[toc] | [prev] | [next] | [standalone]
| From | raltbos@xs4all.nl (Richard Bos) |
|---|---|
| Date | 2015-11-10 16:35 +0000 |
| Message-ID | <56421c54.6552890@news.xs4all.nl> |
| In reply to | #75243 |
Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: > Compilers are good at micro-optimising. But they can't understand > program requirements at a high level. > It would be very challenging to get a compiler to detect when > a bubble sort was being coded and replace with a quicksort. Part of the problem is that there are edge cases - demonstrating the differences between sorting algorithms, for one - where you _want_ bubble sort rather than quicksort. In security code, it may well be important that all paths through an algorithm be a. optimised, but also b. optimised to use the exact same time. Richard
[toc] | [prev] | [next] | [standalone]
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Date | 2015-11-10 11:52 -0500 |
| Message-ID | <n1t78n$vc9$1@dont-email.me> |
| In reply to | #75602 |
On 11/10/2015 11:35 AM, Richard Bos wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
>
>> Compilers are good at micro-optimising. But they can't understand
>> program requirements at a high level.
>> It would be very challenging to get a compiler to detect when
>> a bubble sort was being coded and replace with a quicksort.
>
> Part of the problem is that there are edge cases - demonstrating the
> differences between sorting algorithms, for one - where you _want_
> bubble sort rather than quicksort. In security code, it may well be
> important that all paths through an algorithm be a. optimised, but also
> b. optimised to use the exact same time.
Some graphics applications use bubble sort because it's often
the best choice. You start with a "camera" that views objects in
a scene, and you sort them by their distance from the camera so you
can render them near-to-far (or far-to-near, depending on how your
rendering system works). Then you advance the clock by delta-T and
reposition the moving objects to render the next frame, and you once
again want the objects sorted by distance.
Guess what? Most of the "foreground" and "background" objects
are still near and still far; few pairs have switched relative
positions. That means the old sorted-by-distance list is still
almost sorted, maybe even actually sorted. A bubble sort will cure
the few inversions that may have crept in, very likely in just a
pass or two.
(Note, too, that an almost-sorted list is a pathologically bad
input for "pure" quicksort; you *start* by relying on the in-case-
of-emergency mitigations!)
--
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-11 00:48 -0600 |
| Message-ID | <s3p54b14m62450uvglppme35m6etmseqe1@4ax.com> |
| In reply to | #75611 |
On Tue, 10 Nov 2015 11:52:41 -0500, Eric Sosman <esosman@comcast-dot-net.invalid> wrote: >On 11/10/2015 11:35 AM, Richard Bos wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >> >>> Compilers are good at micro-optimising. But they can't understand >>> program requirements at a high level. >>> It would be very challenging to get a compiler to detect when >>> a bubble sort was being coded and replace with a quicksort. >> >> Part of the problem is that there are edge cases - demonstrating the >> differences between sorting algorithms, for one - where you _want_ >> bubble sort rather than quicksort. In security code, it may well be >> important that all paths through an algorithm be a. optimised, but also >> b. optimised to use the exact same time. > > Some graphics applications use bubble sort because it's often >the best choice. You start with a "camera" that views objects in >a scene, and you sort them by their distance from the camera so you >can render them near-to-far (or far-to-near, depending on how your >rendering system works). Then you advance the clock by delta-T and >reposition the moving objects to render the next frame, and you once >again want the objects sorted by distance. > > Guess what? Most of the "foreground" and "background" objects >are still near and still far; few pairs have switched relative >positions. That means the old sorted-by-distance list is still >almost sorted, maybe even actually sorted. A bubble sort will cure >the few inversions that may have crept in, very likely in just a >pass or two. Although I'd guess that insertion sort is still better than bubble sort in that case.
[toc] | [prev] | [next] | [standalone]
| From | raltbos@xs4all.nl (Richard Bos) |
|---|---|
| Date | 2015-11-17 21:55 +0000 |
| Message-ID | <564ba1c5.24676609@news.xs4all.nl> |
| In reply to | #75716 |
Robert Wessel <robertwessel2@yahoo.com> wrote: > On Tue, 10 Nov 2015 11:52:41 -0500, Eric Sosman > >On 11/10/2015 11:35 AM, Richard Bos wrote: > >> Part of the problem is that there are edge cases - demonstrating the > >> differences between sorting algorithms, for one - where you _want_ > >> bubble sort rather than quicksort. In security code, it may well be > >> important that all paths through an algorithm be a. optimised, but also > >> b. optimised to use the exact same time. > > > > Some graphics applications use bubble sort because it's often > >the best choice. You start with a "camera" that views objects in > >a scene, and you sort them by their distance from the camera so you > >can render them near-to-far (or far-to-near, depending on how your > >rendering system works). Then you advance the clock by delta-T and > >reposition the moving objects to render the next frame, and you once > >again want the objects sorted by distance. > > > > Guess what? Most of the "foreground" and "background" objects > >are still near and still far; few pairs have switched relative > >positions. That means the old sorted-by-distance list is still > >almost sorted, maybe even actually sorted. A bubble sort will cure > >the few inversions that may have crept in, very likely in just a > >pass or two. Never knew that, but it makes sense. > Although I'd guess that insertion sort is still better than bubble > sort in that case. Not at all. Remember that you start with an almost-sorted list in which the only expected anomaly is a few swapped objects, _not_ with an almost-sorted list plus a few new objects to insert. In other words, you get: 1 2 3 4 6 5 7 8 9 and not 1 2 3 4 6 7 8 9 5 Richard
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-17 19:14 -0600 |
| Message-ID | <7jjn4bdt6i2uou7upsgrrj6fd1db586dam@4ax.com> |
| In reply to | #76297 |
On Tue, 17 Nov 2015 21:55:31 GMT, raltbos@xs4all.nl (Richard Bos) wrote: >Robert Wessel <robertwessel2@yahoo.com> wrote: > >> On Tue, 10 Nov 2015 11:52:41 -0500, Eric Sosman >> >On 11/10/2015 11:35 AM, Richard Bos wrote: > >> >> Part of the problem is that there are edge cases - demonstrating the >> >> differences between sorting algorithms, for one - where you _want_ >> >> bubble sort rather than quicksort. In security code, it may well be >> >> important that all paths through an algorithm be a. optimised, but also >> >> b. optimised to use the exact same time. >> > >> > Some graphics applications use bubble sort because it's often >> >the best choice. You start with a "camera" that views objects in >> >a scene, and you sort them by their distance from the camera so you >> >can render them near-to-far (or far-to-near, depending on how your >> >rendering system works). Then you advance the clock by delta-T and >> >reposition the moving objects to render the next frame, and you once >> >again want the objects sorted by distance. >> > >> > Guess what? Most of the "foreground" and "background" objects >> >are still near and still far; few pairs have switched relative >> >positions. That means the old sorted-by-distance list is still >> >almost sorted, maybe even actually sorted. A bubble sort will cure >> >the few inversions that may have crept in, very likely in just a >> >pass or two. > >Never knew that, but it makes sense. > >> Although I'd guess that insertion sort is still better than bubble >> sort in that case. > >Not at all. Remember that you start with an almost-sorted list in which >the only expected anomaly is a few swapped objects, _not_ with an >almost-sorted list plus a few new objects to insert. In other words, you >get: > > 1 2 3 4 6 5 7 8 9 For that, an insertion sort would do nothing except a single comparison for passes 1-4 and 6-8, and two comparisons and a single swap for pass 5 (total 9 comparisons and one swap). A bubble sort with an early out (which is extra work in each cycle not needed by insertion sort) would do some 15 comparisons and a swap. >and not > > 1 2 3 4 6 7 8 9 5 For that, the first seven insertion passes would stop after the first comparison and do nothing, and the last would shift the 5 back four places using five comparisons and four swaps (for a total of 12 comparisons). A bubble sort (with an early out) would perform some 30 comparison and four swaps).
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-18 03:40 +0000 |
| Message-ID | <87vb90x9du.fsf@bsb.me.uk> |
| In reply to | #76297 |
raltbos@xs4all.nl (Richard Bos) writes:
> Robert Wessel <robertwessel2@yahoo.com> wrote:
>
>> On Tue, 10 Nov 2015 11:52:41 -0500, Eric Sosman
>> >On 11/10/2015 11:35 AM, Richard Bos wrote:
>
>> >> Part of the problem is that there are edge cases - demonstrating the
>> >> differences between sorting algorithms, for one - where you _want_
>> >> bubble sort rather than quicksort. In security code, it may well be
>> >> important that all paths through an algorithm be a. optimised, but also
>> >> b. optimised to use the exact same time.
>> >
>> > Some graphics applications use bubble sort because it's often
>> >the best choice. You start with a "camera" that views objects in
>> >a scene, and you sort them by their distance from the camera so you
>> >can render them near-to-far (or far-to-near, depending on how your
>> >rendering system works). Then you advance the clock by delta-T and
>> >reposition the moving objects to render the next frame, and you once
>> >again want the objects sorted by distance.
>> >
>> > Guess what? Most of the "foreground" and "background" objects
>> >are still near and still far; few pairs have switched relative
>> >positions. That means the old sorted-by-distance list is still
>> >almost sorted, maybe even actually sorted. A bubble sort will cure
>> >the few inversions that may have crept in, very likely in just a
>> >pass or two.
>
> Never knew that, but it makes sense.
Yes, I think it's false. Insertion sort is usually considered better.
It has the same advantage of doing very little work on almost sorted
lists, but even then it usually does less work that bubble sort. In
fact I remember trying to find any input set in for which BS is better
than IS but I could not find one.
>> Although I'd guess that insertion sort is still better than bubble
>> sort in that case.
>
> Not at all. Remember that you start with an almost-sorted list in which
> the only expected anomaly is a few swapped objects, _not_ with an
> almost-sorted list plus a few new objects to insert. In other words, you
> get:
>
> 1 2 3 4 6 5 7 8 9
The details are going to depend on the details of how the algorithms are
actually implemented, but a test program I have reports:
Array data: 1 2 3 4 6 5 7 8 9 (9 values)
Bubble sort: 16 cmps, 3 moves
Insertion sort: 9 cmps, 3 moves
> and not
>
> 1 2 3 4 6 7 8 9 5
Yes, that's even better for insertion sort:
Array data: 1 2 3 4 6 7 8 9 5 (9 values)
Bubble sort: 40 cmps, 12 moves
Insertion sort: 12 cmps, 12 moves
For reference, here are the two sort functions:
void bubble_sort(SFI *sip, int *data, int n)
{
int swapped;
do {
swapped = 0;
for (int i = 1; i < n; i++)
if (out_of_order(sip, data[i-1], data[i])) {
swap(sip, &data[i-1], &data[i]);
swapped = 1;
}
} while (swapped);
}
void insertion_sort(SFI *sip, int *data, int n)
{
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && out_of_order(sip, data[j-1], data[j]); j--)
swap(sip, &data[j], &data[j-1]);
}
}
These may not be the best implementations, but look how simple this
insertion sort is. It wins on comparisons, is no worse on data moves,
and is simpler to implement. I can't think of a use for bubble sort
other than as a reference for other sort to be batter than!
(Test harness also available if anyone wants to add their own algorithms
or try their own test cases.)
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-17 23:01 -0600 |
| Message-ID | <301o4b1klf073gnpic1uo6nigr856pkadt@4ax.com> |
| In reply to | #76345 |
On Wed, 18 Nov 2015 03:40:45 +0000, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote: >raltbos@xs4all.nl (Richard Bos) writes: > >> Robert Wessel <robertwessel2@yahoo.com> wrote: >> >>> On Tue, 10 Nov 2015 11:52:41 -0500, Eric Sosman >>> >On 11/10/2015 11:35 AM, Richard Bos wrote: >> >>> >> Part of the problem is that there are edge cases - demonstrating the >>> >> differences between sorting algorithms, for one - where you _want_ >>> >> bubble sort rather than quicksort. In security code, it may well be >>> >> important that all paths through an algorithm be a. optimised, but also >>> >> b. optimised to use the exact same time. >>> > >>> > Some graphics applications use bubble sort because it's often >>> >the best choice. You start with a "camera" that views objects in >>> >a scene, and you sort them by their distance from the camera so you >>> >can render them near-to-far (or far-to-near, depending on how your >>> >rendering system works). Then you advance the clock by delta-T and >>> >reposition the moving objects to render the next frame, and you once >>> >again want the objects sorted by distance. >>> > >>> > Guess what? Most of the "foreground" and "background" objects >>> >are still near and still far; few pairs have switched relative >>> >positions. That means the old sorted-by-distance list is still >>> >almost sorted, maybe even actually sorted. A bubble sort will cure >>> >the few inversions that may have crept in, very likely in just a >>> >pass or two. >> >> Never knew that, but it makes sense. > >Yes, I think it's false. Insertion sort is usually considered better. >It has the same advantage of doing very little work on almost sorted >lists, but even then it usually does less work that bubble sort. In >fact I remember trying to find any input set in for which BS is better >than IS but I could not find one. 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. Insertion sort deals well with both cases. The only practical(?) use I've seen for bubble sort is in Knuth, where he points out that a one tape sort seems to work well with (effectively) bubble sort. OTOH, I can't imagine such a thing being a requirement since the 70s.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-18 09:00 -0800 |
| Message-ID | <ln610zgs48.fsf@kst-u.example.com> |
| In reply to | #76354 |
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.
[...]
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-18 09:09 -0800 |
| Message-ID | <da87334d-7682-4496-8a89-6f4733048c1a@googlegroups.com> |
| In reply to | #76420 |
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. > Use bubble sort for football league type data. 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.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-18 15:35 -0600 |
| Message-ID | <dmrp4bh99jitdah6v4dp8mq1k1dnthd3qk@4ax.com> |
| In reply to | #76426 |
On Wed, 18 Nov 2015 09:09:08 -0800 (PST), Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >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. >> >Use bubble sort for football league type data. >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. And insertion sort is still better. Shorter and simpler code, better performance.
[toc] | [prev] | [next] | [standalone]
Page 2 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