Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147715 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-11-07 10:39 -0500 |
| Last post | 2019-11-11 00:56 +0000 |
| Articles | 20 on this page of 220 — 19 participants |
Back to article view | Back to comp.lang.c
mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 10:39 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 07:48 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 16:02 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 11:34 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 08:41 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 13:02 -0500
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-07 10:37 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 14:38 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 16:44 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:01 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 10:39 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 10:52 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 11:12 +0100
Re: mergesort code segfaulting on smallish arrays Barry Schwarz <schwarzb@delq.com> - 2019-11-07 12:28 -0800
Re: mergesort code segfaulting on smallish arrays jadill33@gmail.com - 2019-11-07 13:13 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 00:55 +0000
Re: mergesort code segfaulting on smallish arrays jadill33@gmail.com - 2019-11-08 05:30 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:50 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:31 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:39 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 17:53 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:15 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 20:01 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 00:24 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 09:44 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 15:45 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 14:30 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 12:41 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 19:29 +0000
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 14:59 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 22:00 +0000
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 11:24 +1300
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 22:48 +0000
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 12:09 +1300
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 14:46 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:11 +0000
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 17:27 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 14:53 -0800
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 12:02 +1300
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:25 +1300
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-09 20:18 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 21:55 -0500
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 09:49 +0000
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-07 10:34 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 16:12 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 12:19 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 17:42 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 13:32 -0500
Re: mergesort code segfaulting on smallish arrays Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-11-07 11:15 -0700
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 21:57 +0000
Re: mergesort code segfaulting on smallish arrays Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-11-07 19:11 -0700
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 21:57 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 09:21 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-08 04:10 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 13:21 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-13 04:12 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 13:55 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:20 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 10:23 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 16:36 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 11:56 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 09:42 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:39 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 17:14 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 12:00 -0500
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-14 13:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-15 08:17 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-15 13:16 -0800
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-15 22:35 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-16 13:34 -0800
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-16 23:01 +0000
Re: mergesort code segfaulting on smallish arrays Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-17 08:34 +0000
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-17 09:13 +0000
Re: mergesort code segfaulting on smallish arrays Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-17 09:30 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-17 13:53 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-17 10:27 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-17 09:44 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-17 10:50 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-16 07:26 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 18:07 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 12:40 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 20:41 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-14 13:28 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 06:14 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:03 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 02:20 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:21 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:30 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 12:50 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 19:18 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 14:27 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 07:46 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 09:32 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-13 09:34 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 16:01 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 17:19 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-13 16:32 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 17:50 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-13 11:09 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-13 19:18 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 20:31 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 17:12 -0800
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 20:26 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:16 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:40 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-14 01:11 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 10:41 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:42 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 21:56 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 10:42 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:39 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 21:38 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:33 +0100
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 05:44 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:48 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 15:01 +0100
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 08:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 17:12 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 16:34 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-12 17:05 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:07 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 23:50 +0000
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 19:55 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 17:27 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:33 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 18:05 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 05:58 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 12:39 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 12:48 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 14:38 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 13:42 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 14:46 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 14:04 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:05 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 14:09 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:19 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:06 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:22 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:30 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:36 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:59 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:26 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:56 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:21 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:28 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:38 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:58 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:59 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 16:24 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 17:37 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 17:22 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 18:04 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:10 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:14 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 02:14 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-10 22:07 -0500
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 22:16 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-11 06:52 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-11 10:33 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 23:28 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 10:56 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-12 02:35 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 15:01 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 16:08 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 15:53 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 16:56 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-11 13:45 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:03 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:29 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:18 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:27 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:43 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:01 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 09:41 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:44 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 20:03 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:22 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 20:24 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:44 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 06:23 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-13 06:40 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 16:34 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-13 08:41 -0800
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-11 11:24 -0800
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 05:13 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:36 +0000
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 05:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 05:25 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 11:30 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 17:49 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 12:21 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 18:53 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 13:33 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 19:37 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 18:51 +0000
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 14:46 -0500
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:35 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:48 +0000
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:35 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:39 +0100
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 19:54 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:55 +0100
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 21:34 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 21:37 +0100
Re: mergesort code segfaulting on smallish arrays Robert Wessel <robertwessel2@yahoo.com> - 2019-11-11 11:12 -0600
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:28 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:41 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 12:47 -0800
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:08 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-10 14:30 -0800
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 12:43 -0800
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 17:16 -0500
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:27 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 05:55 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 16:45 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 17:53 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 00:56 +0000
Page 5 of 11 — ← Prev page 1 … 3 4 [5] 6 7 … 11 Next page →
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-08 12:40 -0500 |
| Message-ID | <LKhxF.93097$FF4.8949@fx40.iad> |
| In reply to | #147785 |
On 11/8/2019 12:07 PM, Bonita Montero wrote:
> There were two little bugs. I just reorganized the code from
> C++ wihtout running it. The following code should be fine:
>
> #include <stdio.h>
> #include <stddef.h>
> #include <stdlib.h>
> #include <assert.h>
>
> int merge_sort( int *start, size_t n );
>
> int main()
> {
> size_t const N = 100000000;
> int *p = malloc( N * sizeof(int) );
> printf( "randomizing ...\n" );
> int *s = p;
> for( s = p; s != p + N; *s++ = rand() );
Don't you think you should seed rand()?
> printf( "sorting ...\n" );
> merge_sort( p, N );
> for( int *scn = p; scn < p + N - 1; ++scn )
> assert( scn[0] <= scn[1] );
> printf( "... sorted\n" );
> }
>
> void ms_recursion( int *start, int *end, int *buf );
>
> int merge_sort( int *start, size_t n )
> {
> size_t bs = 0;
> for( size_t nHalf = n; nHalf > 1; bs += nHalf, nHalf -= nHalf / 2 );
> int *buf = malloc( bs * sizeof(int) );
> if( !buf )
> return 0;
> ms_recursion( start, start + n, buf );
> free( buf );
> return 1;
> }
>
> void ms_recursion( int *start, int *end, int *buf )
> {
> if( end - start <= 1 )
> return;
> for( int *from = start, *to = buf; from != end; *to++ = *from++ );
> size_t n = end - start;
> int *leftBuf = buf,
> *leftBufEnd = buf + n / 2,
> *rightBuf = leftBufEnd,
> *bufEnd = buf + n;
> ms_recursion( leftBuf, leftBufEnd, bufEnd );
> ms_recursion( rightBuf, bufEnd, bufEnd );
> for( int *wrtBack = start; ; )
> if( *leftBuf <= *rightBuf )
> {
> *wrtBack++ = *leftBuf;
> if( ++leftBuf == leftBufEnd )
> {
> do
> *wrtBack++ = *rightBuf;
> while( ++rightBuf != bufEnd );
> break;
> }
> }
> else
> {
> *wrtBack++ = *rightBuf;
> if( ++rightBuf == bufEnd )
> {
> do
> *wrtBack++ = *leftBuf;
> while( ++leftBuf != leftBufEnd );
> break;
> }
> }
> }
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-08 20:41 +0100 |
| Message-ID | <qq4gci$dmi$1@news.albasani.net> |
| In reply to | #147786 |
> Don't you think you should seed rand()? Do you think the benchmark-results would be different?
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2019-11-14 13:28 -0800 |
| Message-ID | <qqkgtd$175q$2@gioia.aioe.org> |
| In reply to | #147794 |
On 11/8/2019 11:41 AM, Bonita Montero wrote: >> Don't you think you should seed rand()? > > Do you think the benchmark-results would be different? > Maybe!
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-09 06:14 +0100 |
| Message-ID | <qq5i01$k0s$1@news.albasani.net> |
| In reply to | #147760 |
Here's a generic C-version which is like qsort() with a size
-argument and a compare-callback; of course it's rather slow:
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
int merge_sort( void *start, size_t size, size_t n, char (*less)( void
*, void * ) );
char cmp( void *left, void *right )
{
return *(int *)left < *(int *)right;
}
int main()
{
size_t const N = 1000000;
int *p = malloc( N * sizeof(int) );
printf( "randomizing ...\n" );
for( int *s = p; s != p + N; *s++ = rand() );
printf( "sorting ...\n" );
merge_sort( p, sizeof(int), N, cmp );
for( int *scn = p; scn < p + N - 1; ++scn )
assert( scn[0] <= scn[1] );
printf( "... sorted n" );
for( int *scn = p; scn < p + N - 1; ++scn )
assert( scn[0] <= scn[1] );
}
void ms_recursion( char *start, size_t size, size_t n, char *buf, char
(*less)( void *, void * ) );
int merge_sort( void *start, size_t size, size_t n, char (*less)( void
*, void * ) )
{
size_t bs = 0;
for( size_t nHalf = n; nHalf > 1; bs += nHalf, nHalf -= nHalf / 2 );
void *buf = malloc( bs * size );
if( !buf )
return 0;
ms_recursion( start, size, n, buf, less );
free( buf );
return 1;
}
void ms_recursion( char *start, size_t size, size_t n, char *buf, char
(*less)( void *, void * ) )
{
if( n <= 1 )
return;
memcpy( buf, start, n * size );
size_t left = n / 2,
right = n - left;
char *leftBuf = buf,
*leftBufEnd = leftBuf + left * size,
*rightBuf = leftBufEnd,
*bufEnd = leftBuf + n * size;
ms_recursion( leftBuf, size, left, bufEnd, less );
ms_recursion( rightBuf, size, right, bufEnd, less );
for( char *wrtBack = start; ; )
if( less( leftBuf, rightBuf ) )
{
memcpy( wrtBack, leftBuf, size );
wrtBack += size;
if( (leftBuf += size) == leftBufEnd )
{
memcpy( wrtBack, rightBuf, bufEnd - rightBuf );
break;
}
}
else
{
memcpy( wrtBack, rightBuf, size );
wrtBack += size;
if( (rightBuf += size) == bufEnd )
{
memcpy( wrtBack, leftBuf, leftBufEnd - leftBuf );
break;
}
}
}
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-09 08:03 +0100 |
| Message-ID | <qq5oca$64s$1@news.albasani.net> |
| In reply to | #147813 |
When I compile the below code with VC++ and -Ox-optimizatzions the
comparison is inlined and the memcpy won't be called, but instead
a single 4-byte-copy is done. So the performance is only slightly
worse than the int-specialized version.
But if I compile the code without global optimizations the whole
algorithm is 2,5 times slower than the int-optimized version.
> #include <stdio.h>
> #include <stddef.h>
> #include <stdlib.h>
> #include <assert.h>
> #include <string.h>
>
> int merge_sort( void *start, size_t size, size_t n, char (*less)( void
> *, void * ) );
>
> char cmp( void *left, void *right )
> {
> return *(int *)left < *(int *)right;
> }
>
> int main()
> {
> size_t const N = 1000000;
> int *p = malloc( N * sizeof(int) );
> printf( "randomizing ...\n" );
> for( int *s = p; s != p + N; *s++ = rand() );
> printf( "sorting ...\n" );
> merge_sort( p, sizeof(int), N, cmp );
> for( int *scn = p; scn < p + N - 1; ++scn )
> assert( scn[0] <= scn[1] );
> printf( "... sorted n" );
> for( int *scn = p; scn < p + N - 1; ++scn )
> assert( scn[0] <= scn[1] );
> }
>
> void ms_recursion( char *start, size_t size, size_t n, char *buf, char
> (*less)( void *, void * ) );
>
> int merge_sort( void *start, size_t size, size_t n, char (*less)( void
> *, void * ) )
> {
> size_t bs = 0;
> for( size_t nHalf = n; nHalf > 1; bs += nHalf, nHalf -= nHalf / 2 );
> void *buf = malloc( bs * size );
> if( !buf )
> return 0;
> ms_recursion( start, size, n, buf, less );
> free( buf );
> return 1;
> }
>
> void ms_recursion( char *start, size_t size, size_t n, char *buf, char
> (*less)( void *, void * ) )
> {
> if( n <= 1 )
> return;
> memcpy( buf, start, n * size );
> size_t left = n / 2,
> right = n - left;
> char *leftBuf = buf,
> *leftBufEnd = leftBuf + left * size,
> *rightBuf = leftBufEnd,
> *bufEnd = leftBuf + n * size;
> ms_recursion( leftBuf, size, left, bufEnd, less );
> ms_recursion( rightBuf, size, right, bufEnd, less );
> for( char *wrtBack = start; ; )
> if( less( leftBuf, rightBuf ) )
> {
> memcpy( wrtBack, leftBuf, size );
> wrtBack += size;
> if( (leftBuf += size) == leftBufEnd )
> {
> memcpy( wrtBack, rightBuf, bufEnd - rightBuf );
> break;
> }
> }
> else
> {
> memcpy( wrtBack, rightBuf, size );
> wrtBack += size;
> if( (rightBuf += size) == bufEnd )
> {
> memcpy( wrtBack, leftBuf, leftBufEnd - leftBuf );
> break;
> }
> }
>
> }
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-09 02:20 -0500 |
| Message-ID | <ULtxF.8438$bC3.924@fx08.iad> |
| In reply to | #147813 |
On 11/9/2019 12:14 AM, Bonita Montero wrote:
> Here's a generic C-version which is like qsort() with a size
> -argument and a compare-callback; of course it's rather slow:
>
> #include <stdio.h>
> #include <stddef.h>
> #include <stdlib.h>
> #include <assert.h>
> #include <string.h>
>
> int merge_sort( void *start, size_t size, size_t n, char (*less)( void
> *, void * ) );
>
> char cmp( void *left, void *right )
> {
> return *(int *)left < *(int *)right;
> }
>
> int main()
> {
> size_t const N = 1000000;
> int *p = malloc( N * sizeof(int) );
> printf( "randomizing ...\n" );
> for( int *s = p; s != p + N; *s++ = rand() );
> printf( "sorting ...\n" );
> merge_sort( p, sizeof(int), N, cmp );
> for( int *scn = p; scn < p + N - 1; ++scn )
> assert( scn[0] <= scn[1] );
> printf( "... sorted n" );
> for( int *scn = p; scn < p + N - 1; ++scn )
> assert( scn[0] <= scn[1] );
> }
Did you mean to include 2 of the same sort check?
> void ms_recursion( char *start, size_t size, size_t n, char *buf, char
> (*less)( void *, void * ) );
>
> int merge_sort( void *start, size_t size, size_t n, char (*less)( void
> *, void * ) )
> {
> size_t bs = 0;
> for( size_t nHalf = n; nHalf > 1; bs += nHalf, nHalf -= nHalf / 2 );
> void *buf = malloc( bs * size );
> if( !buf )
> return 0;
> ms_recursion( start, size, n, buf, less );
> free( buf );
> return 1;
> }
>
> void ms_recursion( char *start, size_t size, size_t n, char *buf, char
> (*less)( void *, void * ) )
> {
> if( n <= 1 )
> return;
> memcpy( buf, start, n * size );
> size_t left = n / 2,
> right = n - left;
> char *leftBuf = buf,
> *leftBufEnd = leftBuf + left * size,
> *rightBuf = leftBufEnd,
> *bufEnd = leftBuf + n * size;
> ms_recursion( leftBuf, size, left, bufEnd, less );
> ms_recursion( rightBuf, size, right, bufEnd, less );
> for( char *wrtBack = start; ; )
> if( less( leftBuf, rightBuf ) )
> {
> memcpy( wrtBack, leftBuf, size );
> wrtBack += size;
> if( (leftBuf += size) == leftBufEnd )
> {
> memcpy( wrtBack, rightBuf, bufEnd - rightBuf );
> break;
> }
> }
> else
> {
> memcpy( wrtBack, rightBuf, size );
> wrtBack += size;
> if( (rightBuf += size) == bufEnd )
> {
> memcpy( wrtBack, leftBuf, leftBufEnd - leftBuf );
> break;
> }
> }
>
> }
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-09 08:21 +0100 |
| Message-ID | <qq5pcv$ouf$1@news.albasani.net> |
| In reply to | #147817 |
> Did you mean to include 2 of the same sort check? Copy-mistake ...
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-09 08:30 +0100 |
| Message-ID | <qq5pvf$ol$1@news.albasani.net> |
| In reply to | #147760 |
> int main()
> {
> size_t const N = 100'000'000;
> vector<int> rv;
> random_device rd;
> uniform_int_distribution<int> uid( numeric_limits<int>::min(),
> numeric_limits<int>::max() );
> rv.resize( N );
> for( int &r : rv )
> r = uid( rd );
> merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
> less<int>() );
Or better use this:
stable_sort( execution::par, rv.begin(), rv.end(), less<int>() );
This is C++'s mege-sort-implementation which uses all hw-threads in
the system. Something you would need days to implement in C can be
done in one line in C++.
>
> for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
> ++scn )
> assert(scn[0] <= scn[1]);
> }
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-09 12:50 -0500 |
| Message-ID | <R_CxF.55820$3u6.7899@fx34.iad> |
| In reply to | #147819 |
On 11/9/2019 2:30 AM, Bonita Montero wrote:
>> int main()
>> {
>> size_t const N = 100'000'000;
>> vector<int> rv;
>> random_device rd;
>> uniform_int_distribution<int> uid( numeric_limits<int>::min(),
>> numeric_limits<int>::max() );
>> rv.resize( N );
>> for( int &r : rv )
>> r = uid( rd );
>> merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
>> less<int>() );
>
> Or better use this:
> stable_sort( execution::par, rv.begin(), rv.end(), less<int>() );
>
> This is C++'s mege-sort-implementation which uses all hw-threads in
> the system. Something you would need days to implement in C can be
> done in one line in C++.
Why days?
Surely you could do it in C in half-a-day at most.
Here's an example that looks straightforward:
https://malithjayaweera.com/2019/02/parallel-merge-sort/
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-09 19:18 +0100 |
| Message-ID | <qq6vt2$r9v$1@news.albasani.net> |
| In reply to | #147833 |
> Why days? > Surely you could do it in C in half-a-day at most. > Here's an example that looks straightforward: > https://malithjayaweera.com/2019/02/parallel-merge-sort/ The algorithm is similar weak as yours, has fixed partitioning and crashes for larger LENGTHs.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-09 14:27 -0500 |
| Message-ID | <3qExF.111970$Ys1.62873@fx42.iad> |
| In reply to | #147835 |
On 11/9/2019 1:18 PM, Bonita Montero wrote: >> Why days? Surely you could do it in C in half-a-day at most. Here's >> an example that looks straightforward: >> https://malithjayaweera.com/2019/02/parallel-merge-sort/ > > The algorithm is > similar weak as yours What do you mean 'weak'? It's a standard merge sort. > has fixed partitioning So? > and crashes for larger LENGTHs. I fixed that. $ ./pms N = 10000000 (10M) 2 threads Time taken for execution: 0.599944 seconds 4 threads Time taken for execution: 0.906098 seconds 4 threads is slower? The mergesort is very quick, but it takes a LONG time to setup the threading - create and join. Also, his threaded mergesort fails the sort check (but the non-threaded versions don't). All your objections are irrelevant, anyway. Just admit you're exaggerating, as usual, when you say 'you would need days to implement in C'. I might, but you wouldn't.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 07:46 +0100 |
| Message-ID | <qqg8sk$5kb$1@news.albasani.net> |
| In reply to | #147839 |
Having a really clean solution that uses all hw-threads to 100% all the time isn't easy. And there are CPUs which have a number of hw-threads which aren'T a power of two, so you can't do any binary splitting.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 09:32 +0100 |
| Message-ID | <qqgf3l$v2g$1@news.albasani.net> |
| In reply to | #148216 |
The following is my C++ merge-sort-agorithm with parallelism.
If you like you can adapt this to C, optimally with a behaivour
like with qsort(), i.e. with a transparent comparison function.
#include <iostream>
#include <random>
#include <limits>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <cstdlib>
#include <chrono>
#include <cstdint>
#include <thread>
#include <functional>
template<typename It, typename Cmp = std::less<typename
std::iterator_traits<It>::value_type>>
class merge_sort
{
public:
merge_sort( It start, It end, bool &ret, Cmp const &cmp = Cmp(),
unsigned nThreads = 1 );
private:
Cmp m_cmp;
template<typename UpIt, typename BufIt>
void recursion( UpIt start, UpIt end, BufIt buf );
template<typename UpIt, typename BufIt>
void merge( UpIt start, UpIt end, BufIt leftBuf, BufIt rightBuf,
BufIt bufEnd );
template<typename UpIt>
bool parRecursion( UpIt start, UpIt end, unsigned nThreads );
};
template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::merge_sort( It start, It end, bool &ret, Cmp const
&cmp, unsigned nThreads ) :
m_cmp( cmp )
{
assert(nThreads >= 1);
if( nThreads == 0 )
nThreads = 99999;
unsigned hwThreads = std::thread::hardware_concurrency();
hwThreads += hwThreads == 0;
nThreads = nThreads <= hwThreads ? nThreads : hwThreads;
ret = parRecursion( start, end, nThreads );
}
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
{
using namespace std;
if( end - start <= 1 )
return;
copy( start, end, buf );
size_t n = end - start;
BufIt leftBuf = buf,
leftBufEnd = buf + n / 2,
rightBuf = leftBufEnd,
bufEnd = buf + n;
recursion( leftBuf, leftBufEnd, bufEnd );
recursion( rightBuf, bufEnd, bufEnd );
merge( start, end, leftBuf, rightBuf, bufEnd );
}
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::merge( UpIt start, UpIt end, BufIt leftBuf,
BufIt rightBuf, BufIt bufEnd )
{
BufIt leftBufEnd = rightBuf;
for( UpIt wrtBack = start; ; )
if( m_cmp( *leftBuf, *rightBuf ) )
{
*wrtBack++ = *leftBuf;
if( ++leftBuf == leftBufEnd )
{
do
*wrtBack++ = *rightBuf;
while( ++rightBuf != bufEnd );
break;
}
}
else
{
*wrtBack++ = *rightBuf;
if( ++rightBuf == bufEnd )
{
do
*wrtBack++ = *leftBuf;
while( ++leftBuf != leftBufEnd );
break;
}
}
}
template<typename It, typename Cmp>
template<typename UpIt>
bool merge_sort<It, Cmp>::parRecursion( UpIt start, UpIt end, unsigned
nThreads )
{
using namespace std;
using T = typename std::iterator_traits<It>::value_type;
try
{
if( nThreads == 1 )
{
std::vector<T> buf;
size_t bs = 0;
for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
buf.resize( bs );
recursion( start, end, buf.begin() );
}
else
{
auto prProxy = [this]( UpIt start, UpIt end, unsigned
nThreads, bool &ret )
{
ret = parRecursion( start, end, nThreads );
};
size_t n = end - start;
std::vector<T> buf;
buf.resize( n );
copy( start, end, buf.begin() );
unsigned leftThreads = nThreads / 2,
rightThreads = nThreads - leftThreads;
size_t left = n / 2,
right = n - left;
UpIt leftPart = start,
leftPartEnd = start + left,
rightPart = leftPartEnd,
rightPartEnd = start + n;
bool leftRet, rightRet;
vector<thread> threads;
threads.emplace_back( prProxy, leftPart, leftPartEnd,
leftThreads, ref( leftRet ) );
if( rightThreads > 1 )
threads.emplace_back( prProxy, rightPart, rightPartEnd,
rightThreads, ref( rightRet ) );
else
parRecursion( rightPart, rightPartEnd, 1 );
for( thread &thr : threads )
thr.join();
merge( start, end, leftPart, rightPart, rightPartEnd );
}
return true;
}
catch( ... )
{
return false;
}
}
using namespace std;
using namespace chrono;
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
size_t n = (unsigned)atoi( argv[1]) * 1'000'000;
random_device rd;
uniform_int_distribution<int> uid( numeric_limits<int>::min(),
numeric_limits<int>::max() );
vector<int> rv;
rv.resize( n );
cout << "randomizing ..." << endl;
for( int &r : rv )
r = uid( rd );
cout << "sorting ..." << endl;
time_point<high_resolution_clock> start = high_resolution_clock::now();
bool ret;
merge_sort<vector<int>::iterator>( rv.begin(), rv.end(), ret,
less<int>(), 1 );
double seconds = (double)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0E9;
cout << "... sorted!" << endl;
cout << "sorting-time: " << seconds << " seconds" << endl;
for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
++scn )
assert(scn[0] <= scn[1]);
}
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-13 09:34 -0500 |
| Message-ID | <2wUyF.11205$P82.9808@fx15.iad> |
| In reply to | #148217 |
On 11/13/2019 3:32 AM, Bonita Montero wrote:
You should leave in at least the most recent attribution so it's clear
who you're responding to.
> The following is my C++ merge-sort-agorithm with parallelism.
> If you like you can adapt this to C, optimally with a behaivour
> like with qsort(), i.e. with a transparent comparison function.
This version is a good bit simpler than the version you posted
Wed, 8 May 2019 19:03:55 +0200
<qav25f$slh$2@news.albasani.net>
This is 170 lines vs the earlier one at 540 lines. What are the major
differences?
The earlier one mentioned thread- and buffer- pooling; can you explain
how that works?
> #include <iostream>
> #include <random>
> #include <limits>
> #include <algorithm>
> #include <cassert>
> #include <iterator>
> #include <cstdlib>
> #include <chrono>
> #include <cstdint>
> #include <thread>
> #include <functional>
>
> template<typename It, typename Cmp = std::less<typename
> std::iterator_traits<It>::value_type>>
> class merge_sort
> {
> public:
> merge_sort( It start, It end, bool &ret, Cmp const &cmp = Cmp(),
> unsigned nThreads = 1 );
>
> private:
> Cmp m_cmp;
> template<typename UpIt, typename BufIt>
> void recursion( UpIt start, UpIt end, BufIt buf );
> template<typename UpIt, typename BufIt>
> void merge( UpIt start, UpIt end, BufIt leftBuf, BufIt rightBuf,
> BufIt bufEnd );
> template<typename UpIt>
> bool parRecursion( UpIt start, UpIt end, unsigned nThreads );
> };
>
> template<typename It, typename Cmp>
> inline
> merge_sort<It, Cmp>::merge_sort( It start, It end, bool &ret, Cmp const
> &cmp, unsigned nThreads ) :
> m_cmp( cmp )
> {
> assert(nThreads >= 1);
> if( nThreads == 0 )
> nThreads = 99999;
> unsigned hwThreads = std::thread::hardware_concurrency();
> hwThreads += hwThreads == 0;
> nThreads = nThreads <= hwThreads ? nThreads : hwThreads;
> ret = parRecursion( start, end, nThreads );
> }
>
> template<typename It, typename Cmp>
> template<typename UpIt, typename BufIt>
> void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
> {
> using namespace std;
> if( end - start <= 1 )
> return;
> copy( start, end, buf );
> size_t n = end - start;
> BufIt leftBuf = buf,
> leftBufEnd = buf + n / 2,
> rightBuf = leftBufEnd,
> bufEnd = buf + n;
> recursion( leftBuf, leftBufEnd, bufEnd );
> recursion( rightBuf, bufEnd, bufEnd );
> merge( start, end, leftBuf, rightBuf, bufEnd );
> }
>
> template<typename It, typename Cmp>
> template<typename UpIt, typename BufIt>
> void merge_sort<It, Cmp>::merge( UpIt start, UpIt end, BufIt leftBuf,
> BufIt rightBuf, BufIt bufEnd )
> {
> BufIt leftBufEnd = rightBuf;
> for( UpIt wrtBack = start; ; )
> if( m_cmp( *leftBuf, *rightBuf ) )
> {
> *wrtBack++ = *leftBuf;
> if( ++leftBuf == leftBufEnd )
> {
> do
> *wrtBack++ = *rightBuf;
> while( ++rightBuf != bufEnd );
> break;
> }
> }
> else
> {
> *wrtBack++ = *rightBuf;
> if( ++rightBuf == bufEnd )
> {
> do
> *wrtBack++ = *leftBuf;
> while( ++leftBuf != leftBufEnd );
> break;
> }
> }
> }
>
>
> template<typename It, typename Cmp>
> template<typename UpIt>
> bool merge_sort<It, Cmp>::parRecursion( UpIt start, UpIt end, unsigned
> nThreads )
> {
> using namespace std;
> using T = typename std::iterator_traits<It>::value_type;
> try
> {
> if( nThreads == 1 )
> {
> std::vector<T> buf;
> size_t bs = 0;
> for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
> buf.resize( bs );
> recursion( start, end, buf.begin() );
> }
> else
> {
> auto prProxy = [this]( UpIt start, UpIt end, unsigned
> nThreads, bool &ret )
> {
> ret = parRecursion( start, end, nThreads );
> };
> size_t n = end - start;
> std::vector<T> buf;
> buf.resize( n );
> copy( start, end, buf.begin() );
> unsigned leftThreads = nThreads / 2,
> rightThreads = nThreads - leftThreads;
> size_t left = n / 2,
> right = n - left;
> UpIt leftPart = start,
> leftPartEnd = start + left,
> rightPart = leftPartEnd,
> rightPartEnd = start + n;
> bool leftRet, rightRet;
> vector<thread> threads;
> threads.emplace_back( prProxy, leftPart, leftPartEnd,
> leftThreads, ref( leftRet ) );
> if( rightThreads > 1 )
> threads.emplace_back( prProxy, rightPart, rightPartEnd,
> rightThreads, ref( rightRet ) );
> else
> parRecursion( rightPart, rightPartEnd, 1 );
> for( thread &thr : threads )
> thr.join();
> merge( start, end, leftPart, rightPart, rightPartEnd );
> }
> return true;
> }
> catch( ... )
> {
> return false;
> }
> }
>
> using namespace std;
> using namespace chrono;
>
> int main( int argc, char **argv )
> {
> if( argc < 2 )
> return EXIT_FAILURE;
> size_t n = (unsigned)atoi( argv[1]) *
> 1'000'000;
> random_device rd;
> uniform_int_distribution<int> uid( numeric_limits<int>::min(),
> numeric_limits<int>::max() );
> vector<int> rv;
> rv.resize( n );
> cout << "randomizing ..." << endl;
> for( int &r : rv )
> r = uid( rd );
> cout << "sorting ..." << endl;
> time_point<high_resolution_clock> start =
> high_resolution_clock::now();
> bool ret;
> merge_sort<vector<int>::iterator>( rv.begin(), rv.end(), ret,
> less<int>(), 1 );
> double seconds = (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0E9;
> cout << "... sorted!" << endl;
> cout << "sorting-time: " << seconds << " seconds" << endl;
> for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
> ++scn )
> assert(scn[0] <= scn[1]);
> }
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 16:01 +0100 |
| Message-ID | <qqh5t3$4gl$1@news.albasani.net> |
| In reply to | #148230 |
Take this; it's the same code but it gathers all the exceptions the
threads could make in parallel and throws them in a merge_sort<...>
::par_exception if more than one exception ocurs or the exception
that occured natively if there was only one exception.
The vector for the exception_ptr-objects is pre-allocated to the
maximum number of threads that could issue an exception so that
there can't be an exception while catching an exception.
#include <iostream>
#include <random>
#include <limits>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <cstdlib>
#include <chrono>
#include <cstdint>
#include <thread>
#include <functional>
#include <exception>
#include <mutex>
template<typename T>
struct invoke_on_destruct
{
private:
T &m_t;
bool m_enabled;
public:
invoke_on_destruct( T &t ) :
m_t( t ), m_enabled( true )
{
}
~invoke_on_destruct()
{
if( m_enabled )
m_t();
}
void invoke_and_disable()
{
m_t();
m_enabled = false;
}
};
template<typename It, typename Cmp = std::less<typename
std::iterator_traits<It>::value_type>>
class merge_sort
{
public:
merge_sort( It start, It end, Cmp const &cmp = Cmp(), unsigned
nThreads = 1 );
struct par_exception
{
~par_exception();
std::vector<std::exception_ptr> &getExceptions();
private:
friend class merge_sort;
par_exception( std::vector<std::exception_ptr> &&exceptions );
std::vector<std::exception_ptr> m_exceptions;
};
private:
using exceptions_vector = std::vector<std::exception_ptr>;
Cmp m_cmp;
std::mutex m_excMtx;
exceptions_vector m_exceptions;
template<typename UpIt, typename BufIt>
void recursion( UpIt start, UpIt end, BufIt buf );
template<typename UpIt, typename BufIt>
void merge( UpIt start, BufIt leftBuf, BufIt rightBuf, BufIt bufEnd );
template<typename UpIt>
void parRecursion( UpIt start, UpIt end, unsigned nThreads );
};
template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::merge_sort( It start, It end, Cmp const &cmp,
unsigned nThreads ) :
m_cmp( cmp )
{
using namespace std;
assert(nThreads >= 1);
if( nThreads == 0 )
nThreads = 99999;
unsigned hwThreads = thread::hardware_concurrency();
hwThreads += hwThreads == 0;
nThreads = nThreads <= hwThreads ? nThreads : hwThreads;
m_exceptions.reserve( nThreads );
try
{
parRecursion( start, end, nThreads );
if( m_exceptions.size() )
if( m_exceptions.size() > 1 )
throw par_exception( move( m_exceptions ) );
else
rethrow_exception( m_exceptions[0] );
}
catch( ... )
{
if( m_exceptions.size() )
{
m_exceptions.emplace_back( current_exception() );
throw par_exception( move( m_exceptions ) );
}
else
throw;
}
}
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
{
using namespace std;
if( end - start <= 1 )
return;
copy( start, end, buf );
size_t n = end - start;
BufIt leftBuf = buf,
leftBufEnd = buf + n / 2,
rightBuf = leftBufEnd,
bufEnd = buf + n;
recursion( leftBuf, leftBufEnd, bufEnd );
recursion( rightBuf, bufEnd, bufEnd );
merge( start, leftBuf, rightBuf, bufEnd );
}
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::merge( UpIt start, BufIt leftBuf, BufIt
rightBuf, BufIt bufEnd )
{
BufIt leftBufEnd = rightBuf;
for( UpIt wrtBack = start; ; )
if( m_cmp( *leftBuf, *rightBuf ) )
{
*wrtBack++ = *leftBuf;
if( ++leftBuf == leftBufEnd )
{
do
*wrtBack++ = *rightBuf;
while( ++rightBuf != bufEnd );
break;
}
}
else
{
*wrtBack++ = *rightBuf;
if( ++rightBuf == bufEnd )
{
do
*wrtBack++ = *leftBuf;
while( ++leftBuf != leftBufEnd );
break;
}
}
}
template<typename It, typename Cmp>
template<typename UpIt>
void merge_sort<It, Cmp>::parRecursion( UpIt start, UpIt end, unsigned
nThreads )
{
using namespace std;
using T = typename iterator_traits<It>::value_type;
if( nThreads == 1 )
{
vector<T> buf;
size_t bs = 0;
for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
buf.resize( bs );
recursion( start, end, buf.begin() );
}
else
{
vector<T> buf;
size_t n = end - start;
buf.resize( n );
copy( start, end, buf.begin() );
vector<thread> threads;
threads.reserve( 2 );
auto joinThreads = [&threads]()
{
for( thread &thr : threads )
for( ; ; )
try
{
thr.join();
break;
}
catch( ... )
{
}
};
invoke_on_destruct<decltype(joinThreads)> iodJoin( joinThreads );
auto prProxy = [this]( UpIt start, UpIt end, unsigned nThreads )
{
try
{
parRecursion( start, end, nThreads );
}
catch( ... )
{
unique_lock<mutex> excLock( m_excMtx );
m_exceptions.emplace_back( current_exception() );
}
};
unsigned rightThreads = nThreads / 2,
leftThreads = nThreads - rightThreads;
size_t left = n / 2,
right = n - left;
UpIt leftPart = start,
leftPartEnd = start + left,
rightPart = leftPartEnd,
rightPartEnd = start + n;
threads.emplace_back( prProxy, leftPart, leftPartEnd,
leftThreads );
if( rightThreads > 1 )
threads.emplace_back( prProxy, rightPart, rightPartEnd,
rightThreads );
else
parRecursion( rightPart, rightPartEnd, 1 );
iodJoin.invoke_and_disable();
unique_lock<mutex> excLock( m_excMtx );
if( m_exceptions.size() )
return;
excLock.unlock();
merge( start, leftPart, rightPart, rightPartEnd );
}
}
template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::par_exception::~par_exception()
{
}
template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::par_exception::par_exception(
std::vector<std::exception_ptr> &&exceptions ) :
m_exceptions( std::move( exceptions ) )
{
}
template<typename It, typename Cmp>
inline
std::vector<std::exception_ptr> &merge_sort<It,
Cmp>::par_exception::getExceptions()
{
return m_exceptions;
}
#if defined(_MSC_VER)
#pragma warning(disable: 26444)
#endif
using namespace std;
using namespace chrono;
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
size_t n = (size_t)(unsigned)atoi( argv[1])
* 1'000'000;
random_device rd;
uniform_int_distribution<int> uid( numeric_limits<int>::min(),
numeric_limits<int>::max() );
vector<int> rv;
rv.resize( n );
cout << "randomizing ..." << endl;
for( int &r : rv )
r = uid( rd );
cout << "sorting ..." << endl;
time_point<high_resolution_clock> start = high_resolution_clock::now();
merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
less<int>(), 0 );
double seconds = (double)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0E9;
cout << "... sorted!" << endl;
cout << "sorting-time: " << seconds << " seconds" << endl;
for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
++scn )
assert(scn[0] <= scn[1]);
}
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 17:19 +0100 |
| Message-ID | <qqhafc$q2t$1@news.albasani.net> |
| In reply to | #148232 |
Replacing this ...
> size_t left = n / 2,
> right = n - left;
... by this ...
size_t left = (size_t)(n * ((double)leftThreads /
nThreads)),
right = n - left;
would get a better partitioning if you have a CPU with a number of cores
which is not a power of two.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-11-13 16:32 +0000 |
| Message-ID | <UeWyF.169091$ZO5.97474@fx26.am4> |
| In reply to | #148232 |
On 13/11/2019 15:01, Bonita Montero wrote: > Take this; it's the same code but it gathers all the exceptions the > threads could make in parallel and throws them in a merge_sort<...> > ::par_exception if more than one exception ocurs or the exception > that occured natively if there was only one exception. > The vector for the exception_ptr-objects is pre-allocated to the > maximum number of threads that could issue an exception so that > there can't be an exception while catching an exception. > > #include <iostream> > #include <random> > #include <limits> > #include <algorithm> > #include <cassert> > #include <iterator> > #include <cstdlib> > #include <chrono> > #include <cstdint> > #include <thread> > #include <functional> > #include <exception> > #include <mutex> Jesus. You did say C++ was supposed to make life simpler?! You seem to be remarkably adept at adding unnecessary complexity while not being too hot with the basics. C++ appears to be the perfect language for you!
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 17:50 +0100 |
| Message-ID | <qqhc9f$jsp$1@news.albasani.net> |
| In reply to | #148239 |
>> #include <iostream> >> #include <random> >> #include <limits> >> #include <algorithm> >> #include <cassert> >> #include <iterator> >> #include <cstdlib> >> #include <chrono> >> #include <cstdint> >> #include <thread> >> #include <functional> >> #include <exception> >> #include <mutex> > Jesus. > You did say C++ was supposed to make life simpler?! Yes, it makes life simpler and / or more flexible or cleaner. * <random> has a better random-number-facility. * <limits> is a cleaner version of <limits.h> * I use <algorithm> for copy f.e. and thereby I can copy from a container with an arbitrary type to a container of another type. * <cassert> is the same as <assert.h>- * <iterator> helps to derive the type of the values pointed to by an iterator. That enables you to have an arbitrary type of input-array for the sorting-algorithm. * <chrono> has a very flexible time-measurement facility; C has nothing comparable. * <cstdint> is mistakenly included but not really needed. * <thread> has nice thread-classes and you don't need to pass any void-pointers to threads; I just use a lamda with some parameters. That's much more handy like Posix-threads. * I use std::less from <functional> for the comparisons. With the comparison template-class I can customize my sorting-algorithm for any type without a callback like with qsort so I don't have any perfromance-disadvantage. * Exception-handling makes error-handling like handling a memory collapse more convenient. In my code this is a bit more complex because I pass exception-pointers (exception_ptr) across thread-boundaries; but in C error-handling across thread-boundaries would be even more work. * I'm using a mutex to protect the list of references to the exceptions thrown by the threads. In C you would have to construct and destroy the mutex manually. And you would have to unlock the mutex manually in every case. In C++ in most cases you would have to declare the mutex only to initialize it and you mostly don't have to unlock it when you protect it with a guard. > You seem to be remarkably adept at adding unnecessary > complexity while not being too hot with the basics. With a similar flexibility the C-code would be muuch larger, less maintainable and slower. > C++ appears to be the perfect language for you! It's obviously a better language.
[toc] | [prev] | [next] | [standalone]
| From | chad <cdalten@gmail.com> |
|---|---|
| Date | 2019-11-13 11:09 -0800 |
| Message-ID | <8e31e5cf-4ed7-4532-be5c-f6e3b7c2169e@googlegroups.com> |
| In reply to | #148241 |
Uhhh...the burrito that I had for lunch is now making me fart.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-11-13 19:18 +0000 |
| Message-ID | <FGYyF.174355$Fr3.121300@fx39.am4> |
| In reply to | #148241 |
On 13/11/2019 16:50, Bonita Montero wrote: >> You seem to be remarkably adept at adding unnecessary >> complexity while not being too hot with the basics. > > With a similar flexibility the C-code would be muuch larger, > less maintainable and slower. Suppose you were designing a language and needed to choose between generating either C or C++ source code; which would you go for? Just a note: your 270-line C++ program took 3.4 seconds to compile on my machine (fastest time; slowest was 7 seconds. O0/O3 were about the same). Which is 80 lines per second. I'm more used to C compilers which are several thousand times faster (eg. 'tcc' and 'bcc'). > It's obviously a better language. That's not so obvious. What is obvious is that it is considerably were complex, more arcane, much slower to compile and generally more cumbersome. There are issues with C's lack of standard libraries for some of the things you listed, but that is just how it works. The regulars here like to call that 'flexibility' As target language for another, you want it as lightweight as possible.
[toc] | [prev] | [next] | [standalone]
Page 5 of 11 — ← Prev page 1 … 3 4 [5] 6 7 … 11 Next page →
Back to top | Article view | comp.lang.c
csiph-web