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 4 of 9 — ← Prev page 1 2 3 [4] 5 6 7 8 9 Next page →
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-23 11:57 +1300 |
| Message-ID | <dbevisFjpqnU13@mid.individual.net> |
| In reply to | #76872 |
supercat@casperkitty.com wrote: > 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? The security risk not no more or less than when using malloc/free. The writes should be in the correct order (they are when gcc reorders the code), so the observable result is unchanged. > 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. If the implementations of the local allocator functions aren't visible to the compiler, it can't rearrange the code. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-22 16:06 -0800 |
| Message-ID | <2688316d-f885-41f5-94c0-deb63a3cff60@googlegroups.com> |
| In reply to | #76939 |
On Sunday, November 22, 2015 at 4:57:49 PM UTC-6, Ian Collins wrote: > If the implementations of the local allocator functions aren't visible > to the compiler, it can't rearrange the code. How does one guarantee that even if today's compiler can't see into a function, tomorrow's compiler won't gain that ability? Also, many of these kinds of allocation functions are *extremely* fast, and some kinds of code use them a *lot*. Being able to in-line the calls *while still ensuring the proper aliasing barriers* could in some cases enable a nice performance boost.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-23 13:26 +1300 |
| Message-ID | <dbf4p7FjpqnU15@mid.individual.net> |
| In reply to | #76949 |
supercat@casperkitty.com wrote: > On Sunday, November 22, 2015 at 4:57:49 PM UTC-6, Ian Collins wrote: >> If the implementations of the local allocator functions aren't visible >> to the compiler, it can't rearrange the code. > > How does one guarantee that even if today's compiler can't see into a function, > tomorrow's compiler won't gain that ability? > > Also, many of these kinds of allocation functions are *extremely* fast, and > some kinds of code use them a *lot*. Being able to in-line the calls *while > still ensuring the proper aliasing barriers* could in some cases enable a > nice performance boost. I do see your point. I guess because all of the quick allocators I've written perform some form of housekeeping when allocating and freeing a block, the proper aliasing barriers were effectively in place. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-19 09:09 +0000 |
| Message-ID | <n2k3je$jv7$1@speranza.aioe.org> |
| 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. Which ones are those? There are many rules based on the properties of processors built over the years. Some of those are meant to allow more optimal code in some cases. The restriction on shifts being less than the bit width of the value being shifted exists on many processors. The Fortran shift functions don't have this restriction, so they have to check all shift values. In C, you only do the test when you know you need it. But this one is true on so many processors that it makes a lot of sense. Allowing for the rare sign magnitude and ones complement machine is somewhat less obvious. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-20 02:29 -0800 |
| Message-ID | <lnlh9tdkvh.fsf@kst-u.example.com> |
| In reply to | #76488 |
supercat@casperkitty.com writes:
> 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.
Must you bring up the same complaint in every thread?
--
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 | raltbos@xs4all.nl (Richard Bos) |
|---|---|
| Date | 2015-11-20 12:33 +0000 |
| Message-ID | <564f131a.7719015@news.xs4all.nl> |
| In reply to | #76614 |
Keith Thompson <kst-u@mib.org> wrote: > supercat@casperkitty.com writes: > > 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. > > Must you bring up the same complaint in every thread? The same _wrong_ complaint, no less? Richard
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-20 09:26 -0800 |
| Message-ID | <b99f1b55-8bb2-417f-8c6b-8cc6ef06771c@googlegroups.com> |
| In reply to | #76628 |
On Friday, November 20, 2015 at 6:33:51 AM UTC-6, Richard Bos wrote: > > Must you bring up the same complaint in every thread? > > The same _wrong_ complaint, no less? What aspect are you disagreeing with--the fact that if code writes to a pointer of non-character type T, then at any time forevermore the Standard will allow a compiler replace the contents of that storage with the last T that was written there, subject only to the caveats that certain operations are sequenced with regard to character-type accesses, and operations are sequenced relative to operations that make new memory available to an application (either as automatic storage, or via malloc and friends)? Do you dispute that? Since many kinds of application cannot be written nearly as efficiently under such semantics as under semantics which allow reads of one type to be moved before writes of other types, but do not allow reads and writes to cross in the other direction, and do not allow writes to cross other writes in either direction, many compilers limit themselves to pushing reads ahead of foreign writes, and a lot of existing code relies upon such behavior. Do you dispute that? Having compilers perform write reordering in ways that code is not designed for can cause code to malfunction in ways that are likely to cause security problems, and indeed a number of real-world security problems are traceable to such causes. Thus being directly topical to this thread. Do you dispute that? On which aspect am I wrong?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-19 13:37 +0000 |
| Message-ID | <8737w2un35.fsf@bsb.me.uk> |
| In reply to | #76482 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > 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. Insertion sort performs better by all the simple measures: it's better on array reads, on array writes and on compares. It's better (or no worse) than bubble sort in every case I've tested, and that includes exhaustive testing of all permutations of small data sets. These are simple measures for sure; that's why I asked why you if you had data to back up your advocacy for bubble sort -- it was possible you had better data than I do. > 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. So why are repeating this old canard? Bad ideas won't die if everyone just keeps repeating them. On the other hand, I'd be very happy to find a data set that makes bubble sort look like a good choice (I like to learn new things), I just haven't ever found one. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-19 14:07 -0800 |
| Message-ID | <373faa1b-005d-40ae-baee-1b7f1f9021a7@googlegroups.com> |
| In reply to | #76513 |
On Thursday, November 19, 2015 at 1:37:52 PM UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>
> > 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.
>
> Insertion sort performs better by all the simple measures: it's better
> on array reads, on array writes and on compares. It's better (or no
> worse) than bubble sort in every case I've tested, and that includes
> exhaustive testing of all permutations of small data sets. These are
> simple measures for sure; that's why I asked why you if you had data to
> back up your advocacy for bubble sort -- it was possible you had better
> data than I do.
>
> > 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.
>
> So why are repeating this old canard? Bad ideas won't die if everyone
> just keeps repeating them. On the other hand, I'd be very happy to find
> a data set that makes bubble sort look like a good choice (I like to
> learn new things), I just haven't ever found one.
>
> --
> Ben.
Here we go
#include <stdlib.h>
#include <math.h>
static int Nswaps = 0;
static void swap(unsigned char *a, unsigned char *b, int N)
{
int i;
unsigned char temp;
Nswaps++;
for (i = 0; i < N; i++)
{
temp = a[i];
a[i] = b[i];
b[i] = temp;
}
}
void bubblesort(unsigned char *base, int N, int width, int (*compfunc)(const void *e1, const void *e2))
{
int flag = 1;
int i;
int limit = (int) ceil(log(N) / log(2));
while (flag && limit)
{
flag = 0;
for (i = 0; i < N - 1;i++)
if ((*compfunc)(base + i * width, base + (i + 1)*width) > 0)
{
swap(base + i * width, base + (i + 1)*width, width);
flag = 1;
}
limit--;
}
if (flag)
qsort(base, N, width, compfunc);
}
void insertionsort(unsigned char *base, int N, int width, int(*compfunc)(const void *e1, const void *e2))
{
int i, j;
#
int limit = (int)ceil(log(N) / log(2) * N);
for (i = 1; i < N; i++)
{
for (j = i - 1; j >= 0; j--)
{
if ((*compfunc)(base + j * width, base + (j + 1) * width) > 0)
{
swap(base + j * width, base + (j + 1)*width, width);
limit--;
if (!limit)
{
qsort(base, N, width, compfunc);
return;
}
}
else
{
break;
}
}
}
}
#include <string.h>
#include <stdlib.h>
int compstr(const void *e1, const void *e2)
{
const char **s1 = e1;
const char **s2 = e2;
return strcmp(*s1, *s2);
}
static int Ncomps = 0;
int compd(const void *e1, const void *e2)
{
double d1 = *(const double *)e1;
double d2 = *(const double *)e2;
Ncomps++;
return (d1 < d2) ? -1 : ((d1 > d2) ? 1 : 0);
}
#define uniform() (rand()/(RAND_MAX + 1.0))
void testsort(void)
{
int i;
double *d = malloc(10000 * sizeof(double));
for (i = 0; i < 10000; i++)
d[i] = uniform() * 30000;
Ncomps = 0;
Nswaps = 0;
bubblesort(d, 10000, sizeof(double), compd);
printf("bubblesort %d comps %d swaps\n", Ncomps, Nswaps);
for (i = 0; i < 10000; i++)
d[i] = uniform() * 30000;
Ncomps = 0;
Nswaps = 0;
insertionsort(d, 10000, sizeof(double), compd);
printf("insertionsort %d comps %d swaps\n", Ncomps, Nswaps);
Ncomps = 0;
Nswaps = 0;
for (i = 0; i < 100; i++)
d[rand() % 10000]++;
bubblesort(d, 10000, sizeof(double), compd);
printf("bubblesort %d comps %d swaps\n", Ncomps, Nswaps);
Ncomps = 0;
Nswaps = 0;
for (i = 0; i < 100; i++)
d[rand() % 10000]++;
insertionsort(d, 10000, sizeof(double), compd);
printf("insertionsort %d comps %d swaps\n", Ncomps, Nswaps);
Ncomps = 0;
Nswaps = 0;
for (i = 0; i < 100; i++)
d[rand() % 10000]++;
qsort(d, 10000, sizeof(double), compd);
printf("quicksort %d comps\n", Ncomps);
}
bubblesort 295985 comps 139240 swaps
insertionsort 289045 comps 132878 swaps
bubblesort 19998 comps 42 swaps
insertionsort 10039 comps 40 swaps
quicksort 126257 comps
The trick is to know when to terminate the insertion sort, otherwise
of course it performs catastrophically on the random order data.
But bubble sort loses out because of the extra pass, even when it
can sort the data in one pass.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-20 01:38 +0000 |
| Message-ID | <87egflsb52.fsf@bsb.me.uk> |
| In reply to | #76559 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Thursday, November 19, 2015 at 1:37:52 PM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> > 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. >> >> Insertion sort performs better by all the simple measures: it's better >> on array reads, on array writes and on compares. It's better (or no >> worse) than bubble sort in every case I've tested, and that includes >> exhaustive testing of all permutations of small data sets. These are >> simple measures for sure; that's why I asked why you if you had data to >> back up your advocacy for bubble sort -- it was possible you had better >> data than I do. >> >> > 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. >> >> So why are repeating this old canard? Bad ideas won't die if everyone >> just keeps repeating them. On the other hand, I'd be very happy to find >> a data set that makes bubble sort look like a good choice (I like to >> learn new things), I just haven't ever found one. >> > > Here we go <snip code> > bubblesort 295985 comps 139240 swaps > insertionsort 289045 comps 132878 swaps > bubblesort 19998 comps 42 swaps > insertionsort 10039 comps 40 swaps > quicksort 126257 comps Is this supposed to be data in support of your advice to use bubble sort? I don't see how it can be. [By the way, insertion sort is better than this because the version that uses swaps sometimes does the same amount of data moving as bubble sort. (It's still better, mind you!) Optimised implementations don't do swaps. An out of order element is "picked up", the inner loop runs shifting (rather than swapping) the data as it goes, and the picked-up element is put into the right place.] > The trick is to know when to terminate the insertion sort, otherwise > of course it performs catastrophically on the random order data. > But bubble sort loses out because of the extra pass, even when it > can sort the data in one pass. So why do you advise using it? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-19 18:43 -0800 |
| Message-ID | <f71d9e3b-6043-4150-a14c-ab0a55c84b5d@googlegroups.com> |
| In reply to | #76590 |
On Thursday, November 19, 2015 at 7:38:52 PM UTC-6, Ben Bacarisse wrote: > [By the way, insertion sort is better than this because the version that > uses swaps sometimes does the same amount of data moving as bubble sort. > (It's still better, mind you!) Optimised implementations don't do > swaps. An out of order element is "picked up", the inner loop runs > shifting (rather than swapping) the data as it goes, and the picked-up > element is put into the right place.] Whether it's possible to "pick up" an element depends upon whether the underlying representation supports operations other than swap. In C++, for example, things can be swapped without constructing and destructing them, but I don't think it would be possible to "pick up" an item and hold onto it while moving others without having to invoke a copy constructor and a destructor.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-20 12:09 +0000 |
| Message-ID | <87si40rhxx.fsf@bsb.me.uk> |
| In reply to | #76594 |
supercat@casperkitty.com writes: > On Thursday, November 19, 2015 at 7:38:52 PM UTC-6, Ben Bacarisse wrote: >> [By the way, insertion sort is better than this because the version that >> uses swaps sometimes does the same amount of data moving as bubble sort. >> (It's still better, mind you!) Optimised implementations don't do >> swaps. An out of order element is "picked up", the inner loop runs >> shifting (rather than swapping) the data as it goes, and the picked-up >> element is put into the right place.] > > Whether it's possible to "pick up" an element depends upon whether the > underlying representation supports operations other than swap. In C++, > for example, things can be swapped without constructing and destructing > them, but I don't think it would be possible to "pick up" an item and > hold onto it while moving others without having to invoke a copy constructor > and a destructor. Yes, I was talking about C. Insertion sort works by doing a sequence or rotations of sub-sequences each of which can (as in Malcolm's version) be done with a sequence of swaps. In C++ I think you'd implement the "pick-up, shift, replace" version as a single rotate call rather than use swaps, but I'd want to measure... And even in C, I suspect that a good "production" insertion sort would not shift in the inner loop but simply adjust indexes. It would then do a bulk move as part of the rotate operation. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 01:48 -0800 |
| Message-ID | <c112b5e5-f04e-4ac0-961e-cff1a45ea84a@googlegroups.com> |
| In reply to | #76590 |
On Friday, November 20, 2015 at 1:38:52 AM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > On Thursday, November 19, 2015 at 1:37:52 PM UTC, Ben Bacarisse wrote: > >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > >> > >> > 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. > >> > >> Insertion sort performs better by all the simple measures: it's better > >> on array reads, on array writes and on compares. It's better (or no > >> worse) than bubble sort in every case I've tested, and that includes > >> exhaustive testing of all permutations of small data sets. These are > >> simple measures for sure; that's why I asked why you if you had data to > >> back up your advocacy for bubble sort -- it was possible you had better > >> data than I do. > >> > >> > 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. > >> > >> So why are repeating this old canard? Bad ideas won't die if everyone > >> just keeps repeating them. On the other hand, I'd be very happy to find > >> a data set that makes bubble sort look like a good choice (I like to > >> learn new things), I just haven't ever found one. > >> > > > > Here we go > <snip code> > > > bubblesort 295985 comps 139240 swaps > > insertionsort 289045 comps 132878 swaps > > bubblesort 19998 comps 42 swaps > > insertionsort 10039 comps 40 swaps > > quicksort 126257 comps > > Is this supposed to be data in support of your advice to use bubble > sort? I don't see how it can be. > > [By the way, insertion sort is better than this because the version that > uses swaps sometimes does the same amount of data moving as bubble sort. > (It's still better, mind you!) Optimised implementations don't do > swaps. An out of order element is "picked up", the inner loop runs > shifting (rather than swapping) the data as it goes, and the picked-up > element is put into the right place.] > > > The trick is to know when to terminate the insertion sort, otherwise > > of course it performs catastrophically on the random order data. > > But bubble sort loses out because of the extra pass, even when it > > can sort the data in one pass. > > So why do you advise using it? > I hadn't considered the insertion sort termination trick. robert... suggested it, and of course it makes sense. Obviously, you must terminate if the data has undergone a shuffling catastrophe, and resort to sort(). Now less consider how we can make those termination conditions even better.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-20 11:16 +0000 |
| Message-ID | <87y4dsrkd7.fsf@bsb.me.uk> |
| In reply to | #76608 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Friday, November 20, 2015 at 1:38:52 AM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> > On Thursday, November 19, 2015 at 1:37:52 PM UTC, Ben Bacarisse wrote: >> >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> >> >> > 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. >> >> >> >> Insertion sort performs better by all the simple measures: it's better >> >> on array reads, on array writes and on compares. It's better (or no >> >> worse) than bubble sort in every case I've tested, and that includes >> >> exhaustive testing of all permutations of small data sets. These are >> >> simple measures for sure; that's why I asked why you if you had data to >> >> back up your advocacy for bubble sort -- it was possible you had better >> >> data than I do. >> >> >> >> > 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. >> >> >> >> So why are repeating this old canard? Bad ideas won't die if everyone >> >> just keeps repeating them. On the other hand, I'd be very happy to find >> >> a data set that makes bubble sort look like a good choice (I like to >> >> learn new things), I just haven't ever found one. >> >> >> > >> > Here we go >> <snip code> >> >> > bubblesort 295985 comps 139240 swaps >> > insertionsort 289045 comps 132878 swaps >> > bubblesort 19998 comps 42 swaps >> > insertionsort 10039 comps 40 swaps >> > quicksort 126257 comps >> >> Is this supposed to be data in support of your advice to use bubble >> sort? I don't see how it can be. >> >> [By the way, insertion sort is better than this because the version that >> uses swaps sometimes does the same amount of data moving as bubble sort. >> (It's still better, mind you!) Optimised implementations don't do >> swaps. An out of order element is "picked up", the inner loop runs >> shifting (rather than swapping) the data as it goes, and the picked-up >> element is put into the right place.] >> >> > The trick is to know when to terminate the insertion sort, otherwise >> > of course it performs catastrophically on the random order data. >> > But bubble sort loses out because of the extra pass, even when it >> > can sort the data in one pass. >> >> So why do you advise using it? >> > I hadn't considered the insertion sort termination trick. robert... > suggested it, and of course it makes sense. Insertion sort is better than bubble sort without any added tricks. How does that explain your advice? <snip> > Now less consider how we can make those termination conditions even > better. One of them can be improved by deleting it, along with the bubble sort routine it's part of. Or are you *still* advocating its use is some cases? If so I *still* want to know what cases those are. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 05:04 -0800 |
| Message-ID | <fb8a6532-eec5-46c3-9f68-c76d5843f9ec@googlegroups.com> |
| In reply to | #76619 |
On Friday, November 20, 2015 at 11:17:00 AM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > Now less consider how we can make those termination conditions even > > better. > > One of them can be improved by deleting it, along with the bubble sort > routine it's part of. Or are you *still* advocating its use is some > cases? If so I *still* want to know what cases those are. > How would you detect if an array was in random order?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-20 18:18 +0000 |
| Message-ID | <878u5sr0v6.fsf@bsb.me.uk> |
| In reply to | #76630 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Friday, November 20, 2015 at 11:17:00 AM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> > >> > Now less consider how we can make those termination conditions even >> > better. >> >> One of them can be improved by deleting it, along with the bubble sort >> routine it's part of. Or are you *still* advocating its use is some >> cases? If so I *still* want to know what cases those are. >> > How would you detect if an array was in random order? Would you advise using bubble sort for that? I can't answer myself because I don't know what you mean by "in random order". -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 11:55 -0800 |
| Message-ID | <64b75492-c391-47c7-bc4d-65720b9d9e9a@googlegroups.com> |
| In reply to | #76657 |
On Friday, November 20, 2015 at 6:18:18 PM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > How would you detect if an array was in random order? > > Would you advise using bubble sort for that? I can't answer myself > because I don't know what you mean by "in random order". > Random order simply means that the list consists of items arranged in an order that is independent of the particular comparison function we're using. Bubble sort does a complete pass through the array in O(N). If ordering is random, the number of swaps on the first pass will be just a bit smaller than N. (There are also non-random ordering where that's true, e.g. if the array is sorted with the except that the highest-ranked object is inserted at the low point). The question is how to write the condition for saying "the list is not a football league type list, let's resort to quicksort", and, of course, whether we have an advantage over insertion sort.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-21 00:27 +0000 |
| Message-ID | <87y4dsp57s.fsf@bsb.me.uk> |
| In reply to | #76662 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Friday, November 20, 2015 at 6:18:18 PM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> > How would you detect if an array was in random order? >> >> Would you advise using bubble sort for that? I can't answer myself >> because I don't know what you mean by "in random order". >> > Random order simply means that the list consists of items arranged > in an order that is independent of the particular comparison function > we're using. > Bubble sort does a complete pass through the array in O(N). If > ordering is random, the number of swaps on the first pass will be > just a bit smaller than N. (There are also non-random ordering where > that's true, e.g. if the array is sorted with the except that the > highest-ranked object is inserted at the low point). > > The question is how to write the condition for saying "the list > is not a football league type list, let's resort to quicksort", > and, of course, whether we have an advantage over insertion sort. Concentrating on when to switch to something like quick sort is to misunderstand the problem. The problem is that bubble sort is bad even for those cases where you don't switch. In other words, whatever criterion you come up with for switching to quick sort, you should switch to insertion sort in the other cases. Doing this: (1) Inspect data to find (and possibly fix) some measure of order (2) If measure is high do quick sort (3) Otherwise do insertion sort is not "using bubble sort" unless step (1) is a full sort. Even if step one is a loop like that in bubble sort, you are not using bubble sort for "football league type data" because when you find the data is of the "right" kind, you should *still* use insertion sort. Of course, your proposal does not do that. When it finds what you think of as the right data, you continue to use bubble sort but you should always switch to something else. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 18:57 -0800 |
| Message-ID | <f9c6d8cb-e25e-45c9-a126-76c9d429c0be@googlegroups.com> |
| In reply to | #76701 |
On Saturday, November 21, 2015 at 12:27:17 AM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > Doing this: > > (1) Inspect data to find (and possibly fix) some measure of order > (2) If measure is high do quick sort > (3) Otherwise do insertion sort > > is not "using bubble sort" unless step (1) is a full sort. Even if step > one is a loop like that in bubble sort, you are not using bubble sort > for "football league type data" because when you find the data is of the > "right" kind, you should *still* use insertion sort. > > Of course, your proposal does not do that. When it finds what you think > of as the right data, you continue to use bubble sort but you should > always switch to something else. > That's certainly a reasonable approach. But if we run two passes of bubble sort, and we expect that most of the time this will sort that data, we've folded step 1 and step 3 together. Now you can argue that since insertion sort is faster than bubble sort on almost sorted data, largely because it only does one pass, doing a metric-collection pass followed by an insertion sort / qsort is going to be about as fast as a bubble sort. It's also that case that to detect essentially random data we don't need to do a full pass, we just need to sample about twenty data items. Then as Tim says, the first optimisation everyone makes to bubble sort is to turn it into bubble and brick sort. You can get more and more complicated. In fact qsort resorts to insertion sort when the sub-arrays get small. And you can binary search the insertion sort insertion point (if expecting data with some large moves), or get rid of the swap at cost of allocating a temporary (in C89 that has the annoying effect of needing a call to malloc which can theoretically fail, one of the few really good cases for a vla).
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-20 19:50 -0800 |
| Message-ID | <ln37w0au53.fsf@kst-u.example.com> |
| In reply to | #76710 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
[...]
> In fact qsort resorts to
> insertion sort when the sub-arrays get small.
[...]
Citation needed.
Some particular implementations of qsort() may do so, but the
standard says nothing about how qsort() sorts. A perverse conforming
implementation could in principle implement qsort using bubblesort,
or even bogosort.
--
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]
Page 4 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