Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #147715 > unrolled thread

mergesort code segfaulting on smallish arrays

Back to article view | Back to comp.lang.c

Contents

  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 1 of 11  [1] 2 3 … 11  Next page →

#147715 — mergesort code segfaulting on smallish arrays

This code mergesorts an array of ints. Works fine for small arrays, but 
craps out (Segmentation fault (core dumped)) at sizes > 500000.

Ideas?

=======================================================================
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//prototype
void mergesort(int *arr, int left, int right);

//get random number from within range
int randInt(int low, int high) {
     return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}


void merge(int *arr, int left, int middle, int right) {
     int i=0, j=0, k=0;
     int leftLen  = middle - left + 1;
     int rightLen = right - middle;
     int leftarr[leftLen];
     int rightarr[rightLen];

     // copy to left then right array
     for (int i=0;i<leftLen;i++)  {leftarr[i]  = arr[left + i];}
     for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}

     i=0;
     j=0;

     // choose from right and left arrays and copy
     while (i < leftLen && j < rightLen) {
         if (leftarr[i] <= rightarr[j]) {
             arr[left + k] = leftarr[i];
             i++;
         } else {
             arr[left + k] = rightarr[j];
             j++;
         }
         k ++;
     }

     // copy remaining values to the array
     while (i < leftLen)  {arr[left+k]=leftarr[i]; k++;i++;}
     while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}
}


void mergesort(int *arr, int left, int right) {
     if (left < right) {
         int middle = left + (right - left) / 2;
         //printf("%d %d %d\n",left,middle,right);
         mergesort(arr, left, middle);
         mergesort(arr, middle + 1, right);
         //printf("About to merge\n");
         merge(arr, left, middle, right);
     }
}



int main(int argc, char *argv[]) {
	
   int i=0;
		
   //seed
   srand(time(NULL));

   //validate/size the array
   int arrsize = atoi(argv[1]);
   if(arrsize < 1 || arrsize > 10) {printf("Size between 1 and 10\n"); 
exit(0);}
   arrsize *= 100000;

   //create
   int *randoms = malloc(sizeof(int) * (arrsize));

   //populate
   for(i=0;i<arrsize;randoms[i++]=randInt(0,arrsize*2));
   printf("filled\n");
   for(i=0;i<arrsize;i++) {
     if (i<10 || i>(arrsize-11)) {
       printf("%8d. %d\n",i+1, randoms[i]);
     }
   }		

   //sort
   mergesort(randoms,0,arrsize-1);

   //print
   printf("\nsorted\n");
   for(i=0;i<arrsize;i++) {
     if (i<10 || i>(arrsize-11)) {
       printf("%8d. %d\n",i+1, randoms[i]);
     }
   }		
  		


  //finish
  free(randoms);
  printf("Done");
  exit(0);
}
=======================================================================

[toc] | [next] | [standalone]

#147716

On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
> This code mergesorts an array of ints. Works fine for small arrays, but 
> craps out (Segmentation fault (core dumped)) at sizes > 500000.
> 
> Ideas?
> 
> void merge(int *arr, int left, int middle, int right) {
>      int i=0, j=0, k=0;
>      int leftLen  = middle - left + 1;
>      int rightLen = right - middle;
>      int leftarr[leftLen];
>      int rightarr[rightLen];
> 
>
These are variable length arrays. They go on the stack. Stacks are usually
small in relation to the total memory, they are designed to hold a few
working variables, not entire datasets. You're probably exceeding stack
capacity.

[toc] | [prev] | [next] | [standalone]

#147717

On 07/11/2019 15:48, Malcolm McLean wrote:
> On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
>> This code mergesorts an array of ints. Works fine for small arrays, but
>> craps out (Segmentation fault (core dumped)) at sizes > 500000.
>>
>> Ideas?
>>
>> void merge(int *arr, int left, int middle, int right) {
>>       int i=0, j=0, k=0;
>>       int leftLen  = middle - left + 1;
>>       int rightLen = right - middle;
>>       int leftarr[leftLen];
>>       int rightarr[rightLen];
>>
>>
> These are variable length arrays. They go on the stack. Stacks are usually
> small in relation to the total memory, they are designed to hold a few
> working variables, not entire datasets. You're probably exceeding stack
> capacity.

This is one of the problems with VLAs, in that the compiler doesn't tell 
you you're using a VLA, which might therefore have extra overheads, or 
run extra risks.

(No doubt gcc will have such an option, but to use it, you need to know 
in advance that you might be using VLAs, and if you knew that, you 
wouldn't use them.)

[toc] | [prev] | [next] | [standalone]

#147720

On 11/7/2019 10:48 AM, Malcolm McLean wrote:
> On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
>> This code mergesorts an array of ints. Works fine for small arrays, but
>> craps out (Segmentation fault (core dumped)) at sizes > 500000.
>>
>> Ideas?
>>
>> void merge(int *arr, int left, int middle, int right) {
>>       int i=0, j=0, k=0;
>>       int leftLen  = middle - left + 1;
>>       int rightLen = right - middle;
>>       int leftarr[leftLen];
>>       int rightarr[rightLen];
>>
>>
> These are variable length arrays. They go on the stack. Stacks are usually
> small in relation to the total memory, they are designed to hold a few
> working variables, not entire datasets. You're probably exceeding stack
> capacity.

replaced
int leftarr[leftLen];
int rightarr[rightLen];

with
int *leftarr  = malloc(sizeof(int) * (leftLen));
int *rightarr = malloc(sizeof(int) * (rightLen));


and that did it.

Thanks.

[toc] | [prev] | [next] | [standalone]

#147722

On Thursday, 7 November 2019 16:35:19 UTC, DFS  wrote:
> On 11/7/2019 10:48 AM, Malcolm McLean wrote:
> > On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
> >> This code mergesorts an array of ints. Works fine for small arrays, but
> >> craps out (Segmentation fault (core dumped)) at sizes > 500000.
> >>
> >> Ideas?
> >>
> >> void merge(int *arr, int left, int middle, int right) {
> >>       int i=0, j=0, k=0;
> >>       int leftLen  = middle - left + 1;
> >>       int rightLen = right - middle;
> >>       int leftarr[leftLen];
> >>       int rightarr[rightLen];
> >>
> >>
> > These are variable length arrays. They go on the stack. Stacks are usually
> > small in relation to the total memory, they are designed to hold a few
> > working variables, not entire datasets. You're probably exceeding stack
> > capacity.
> 
> replaced
> int leftarr[leftLen];
> int rightarr[rightLen];
> 
> with
> int *leftarr  = malloc(sizeof(int) * (leftLen));
> int *rightarr = malloc(sizeof(int) * (rightLen));
> 
> 
> and that did it.
> 
You also need to free the arrays, or you get a memory leak.

You should also check for null, though on a modern system it is very
unlikely that malloc will refuse to give you a sane amount of memory.

[toc] | [prev] | [next] | [standalone]

#147732

On 11/7/2019 11:41 AM, Malcolm McLean wrote:
> On Thursday, 7 November 2019 16:35:19 UTC, DFS  wrote:
>> On 11/7/2019 10:48 AM, Malcolm McLean wrote:
>>> On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
>>>> This code mergesorts an array of ints. Works fine for small arrays, but
>>>> craps out (Segmentation fault (core dumped)) at sizes > 500000.
>>>>
>>>> Ideas?
>>>>
>>>> void merge(int *arr, int left, int middle, int right) {
>>>>        int i=0, j=0, k=0;
>>>>        int leftLen  = middle - left + 1;
>>>>        int rightLen = right - middle;
>>>>        int leftarr[leftLen];
>>>>        int rightarr[rightLen];
>>>>
>>>>
>>> These are variable length arrays. They go on the stack. Stacks are usually
>>> small in relation to the total memory, they are designed to hold a few
>>> working variables, not entire datasets. You're probably exceeding stack
>>> capacity.
>>
>> replaced
>> int leftarr[leftLen];
>> int rightarr[rightLen];
>>
>> with
>> int *leftarr  = malloc(sizeof(int) * (leftLen));
>> int *rightarr = malloc(sizeof(int) * (rightLen));
>>
>>
>> and that did it.
>>
> You also need to free the arrays, or you get a memory leak.

I put 2 free()s at the end of merge, but it slowed the program down 
significantly.  What's the worst that could happen to the program if you 
don't free them?  The sort always seemed to work fine without them.



> You should also check for null, though on a modern system it is very
> unlikely that malloc will refuse to give you a sane amount of memory.

As I look at code and tutorials and examples out there, I'd say a 
majority don't test for malloc() returning null.  Is that a function of 
people thinking they have plenty of RAM?

[toc] | [prev] | [next] | [standalone]

#147737

DFS <nospam@dfs.com> writes:
> On 11/7/2019 11:41 AM, Malcolm McLean wrote:
[...]
>> You also need to free the arrays, or you get a memory leak.
>
> I put 2 free()s at the end of merge, but it slowed the program down 
> significantly.  What's the worst that could happen to the program if you 
> don't free them?  The sort always seemed to work fine without them.

In your case, the program terminates, and all malloc'ed memory is almost
certain to be freed automatically (and possibly more efficiently, since
the system can just deallocate the entire heap without worrying about
individual objects)

If you were going to incorporate your merge() function into a larger
program where it might be called multiple times, you'd definitely want
to free all your allocated memory.  And doing so even in the trivial
cases is probably a good habit.

How much did it slow down when you added the free()s?

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#147741

On 11/7/2019 1:37 PM, Keith Thompson wrote:
> DFS <nospam@dfs.com> writes:
>> On 11/7/2019 11:41 AM, Malcolm McLean wrote:
> [...]
>>> You also need to free the arrays, or you get a memory leak.
>>
>> I put 2 free()s at the end of merge, but it slowed the program down
>> significantly.  What's the worst that could happen to the program if you
>> don't free them?  The sort always seemed to work fine without them.
> 
> In your case, the program terminates, and all malloc'ed memory is almost
> certain to be freed automatically (and possibly more efficiently, since
> the system can just deallocate the entire heap without worrying about
> individual objects)
> 
> If you were going to incorporate your merge() function into a larger
> program where it might be called multiple times, you'd definitely want
> to free all your allocated memory.  

merge() - and the free()s - are called (arraysize-1) times during a 
standard top-down merge sort.


> And doing so even in the trivial
> cases is probably a good habit.
> 
> How much did it slow down when you added the free()s?


I was counting in my head.  Added timer code:


Without free():
mergesorted  1000000 elements in  1.2591 seconds
mergesorted  5000000 elements in  6.9183 seconds
mergesorted 10000000 elements in 14.2088 seconds

With free():
mergesorted  1000000 elements in  1.5095 seconds
mergesorted  5000000 elements in  8.1053 seconds
mergesorted 10000000 elements in 16.8462 seconds


15% slower

[toc] | [prev] | [next] | [standalone]

#147777

> I was counting in my head.  Added timer code:
> Without free():
> mergesorted  1000000 elements in  1.2591 seconds
> mergesorted  5000000 elements in  6.9183 seconds
> mergesorted 10000000 elements in 14.2088 seconds
> With free():
> mergesorted  1000000 elements in  1.5095 seconds
> mergesorted  5000000 elements in  8.1053 seconds
> mergesorted 10000000 elements in 16.8462 seconds

Show me your latest code. And with a proper implementation the
times with and without freeing memory should be almost the same.

[toc] | [prev] | [next] | [standalone]

#147790

On 11/8/2019 10:44 AM, Bonita Montero wrote:
>> I was counting in my head.  Added timer code:
>> Without free():
>> mergesorted  1000000 elements in  1.2591 seconds
>> mergesorted  5000000 elements in  6.9183 seconds
>> mergesorted 10000000 elements in 14.2088 seconds
>> With free():
>> mergesorted  1000000 elements in  1.5095 seconds
>> mergesorted  5000000 elements in  8.1053 seconds
>> mergesorted 10000000 elements in 16.8462 seconds
> 
> Show me your latest code. And with a proper implementation the
> times with and without freeing memory should be almost the same.




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <Windows.h>

//program timing
LARGE_INTEGER frequency,master,start,end;
double elapsedtime(LARGE_INTEGER startingtimer)
{
   QueryPerformanceCounter(&end);
   return (end.QuadPart - startingtimer.QuadPart) / 
(double)frequency.QuadPart;
}

//get random number from within range
int randInt(int low, int high) {
     return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}

//print data to screen
void printdata(int *randarr, int arrsize, int rows) {
   for(int i=0;i<arrsize;i++) {
     if (i<rows || i>(arrsize-rows-1)) {
       printf("%8d. %d\n",i+1, randarr[i]);
     }
   }	
}

//part of mergesort
void merge(int *arr, int left, int middle, int right) {

     int i=0, j=0, k=0;
     int leftLen  = middle - left + 1;
     int rightLen = right - middle;
     int *leftarr  = malloc(sizeof(int) * (leftLen));
     int *rightarr = malloc(sizeof(int) * (rightLen));

     // copy to left then right array
     for (int i=0;i<leftLen;i++)  {leftarr[i]  = arr[left + i];}
     for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}

     i=0;
     j=0;

     // choose from right and left arrays and copy
     while (i < leftLen && j < rightLen) {
         if (leftarr[i] <= rightarr[j]) {
             arr[left + k] = leftarr[i];
             i++;
         } else {
             arr[left + k] = rightarr[j];
             j++;
         }
         k ++;
     }

     // copy remaining values to the array
     while (i < leftLen)  {arr[left+k]=leftarr[i]; k++;i++;}
     while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}

     //release mem
     free(leftarr);
     free(rightarr);
}

//mergesort
void mergesort(int *arr, int left, int right) {
   if (left < right) {
     int middle = left + (right - left) / 2;
     mergesort(arr, left, middle);
     mergesort(arr, middle + 1, right);
     merge(arr, left, middle, right);
   }
}

int main(int argc, char *argv[]) {
	
   int i=0;

   //validate/size the array
   int arrsize = atoi(argv[1]);
   if(arrsize < 1 || arrsize > 10) {
		printf("Size between 1 and 10\n"); exit(0);
	}
   arrsize *= (1000 * 1000);

   //create
   int *randoms = malloc(sizeof(int) * (arrsize));

   //seed
   srand(time(NULL));

   //populate and print
   for(i=0;i<arrsize;randoms[i++]=randInt(0,arrsize*4));
   printf("filled\n");
   printdata(randoms,arrsize,10);	

   //begin timer
   QueryPerformanceFrequency(&frequency);
   QueryPerformanceCounter(&start);
	
   //mergesort and print
   mergesort(randoms,0,arrsize-1);

   //print results
   printf("\nmergesorted in %.4f seconds\n",elapsedtime(start));
   //randoms[6]=1;
   printdata(randoms,arrsize,10);	

   //validate the sort
   for(i=0;i<arrsize-1;i++) {
     if(randoms[i]>randoms[i+1]) {
       printf("\nInvalid sort:\n"
              "Item %d = %d\n"
              "Item %d = %d\n",
              i+1,  randoms[i],
              i+2,randoms[i+1]);
       exit(1);
     }
   }


  //finish
  free(randoms);
  printf("Done");
  exit(0);
}

[toc] | [prev] | [next] | [standalone]

#147822

Below is my changed code to measure the sorting-speed. With 100 mio
entries the time to sort is 12 seconds whereas with your algorithm it
takes 25 seconds. When I remove the //-comment at the top of my code
to enable std::stable_sort with parallel sorting "my" code takes only
three seconds to sort. I haven't checked your code yet, but there you
might be doing someting wrong.

//#define BUILTIN_PAR

#include <iostream>
#include <random>
#include <limits>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <cstdlib>
#include <chrono>
#include <cstdint>
#if defined(BUILTIN_PAR)
     #include <execution>
#endif

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 );

private:
     Cmp m_cmp;
     template<typename UpIt, typename BufIt>
     void recursion( UpIt start, UpIt end, BufIt buf );
};

template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::merge_sort( It start, It end, Cmp const &cmp ) :
     m_cmp( cmp )
{
     using T = typename std::iterator_traits<It>::value_type;
     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() );
}

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 );
     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;
             }
         }
}

using namespace std;
using namespace chrono;

int main( int argc, char **argv )
{
     if( argc < 2 )
         return EXIT_FAILURE;
     size_t                        n = (size_t)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();
#if defined(BUILTIN_PAR)
     stable_sort( execution::par, rv.begin(), rv.end(), less<int>() );
#else
     merge_sort<vector<int>::iterator>( rv.begin(), rv.end(), less<int>() );
#endif
     uint64_t seconds = (double)duration_cast<nanoseconds>( 
high_resolution_clock::now() - start ).count() / 1'000'000'000.0;
     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]

#147823

>      uint64_t seconds = (double)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count() / 1'000'000'000.0;
seconds shoud be double.

[toc] | [prev] | [next] | [standalone]

#147824

> I haven't checked your code yet, but there you might be doing someting wrong.

I think it's your repeated buffer-allocation. I use only one buffer like
a stack. This is the code to resize the buffer:

     size_t bs = 0;
     for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
     buf.resize( bs );

This is the code which calculates the left and right buffer of the
recursions and the recursion itself:

     BufIt  leftBuf    = buf,
            leftBufEnd = buf + n / 2,
            rightBuf   = leftBufEnd,
            bufEnd     = buf + n;
     recursion( leftBuf,  leftBufEnd, bufEnd );
     recursion( rightBuf, bufEnd,     bufEnd );

[toc] | [prev] | [next] | [standalone]

#147745

On Thu, 7 Nov 2019 13:02:30 -0500, DFS <nospam@dfs.com> wrote:

>On 11/7/2019 11:41 AM, Malcolm McLean wrote:

<snip>

>> You also need to free the arrays, or you get a memory leak.
>
>I put 2 free()s at the end of merge, but it slowed the program down 
>significantly.  What's the worst that could happen to the program if you 
>don't free them?  The sort always seemed to work fine without them.

Each call to malloc will consume some amount of virtual storage.  In
the absence of a call to free, that storage remains allocated for the
life of your program and cannot be reused.

The system will give your program some fixed amount of virtual storage
to use.  At the most, you cannot have more than the size of the swap
file (or its equivalent in your OS).  Once you attempt to allocate
more virtual storage than is available, malloc must fail.  This can be
caused by requesting a large block of memory or by requesting
reasonable amounts of memory a large number of times.

Since you never attempt to reuse allocated memory, freeing it when you
about to exit the function prevents the failure described above from
happening with absolutely no loss of data and only minor impact to
execution time.  It is sometimes called defensive programming.

>> You should also check for null, though on a modern system it is very
>> unlikely that malloc will refuse to give you a sane amount of memory.
>
>As I look at code and tutorials and examples out there, I'd say a 
>majority don't test for malloc() returning null.  Is that a function of 
>people thinking they have plenty of RAM?

Tutorials and examples frequently skip error checking so that the
knowledge being imparted is not watered down or obfuscated by
extraneous details.

Based on the overall quality of the Internet, I would also claim that
just as frequently it is the result of laziness and sloppy
programming.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#147746

On Thursday, November 7, 2019 at 1:03:36 PM UTC-5, DFS wrote:
> On 11/7/2019 11:41 AM, Malcolm McLean wrote:
> > On Thursday, 7 November 2019 16:35:19 UTC, DFS  wrote:
> >> On 11/7/2019 10:48 AM, Malcolm McLean wrote:
> >>> On Thursday, 7 November 2019 15:40:25 UTC, DFS  wrote:
> >>>> This code mergesorts an array of ints. Works fine for small arrays, but
> >>>> craps out (Segmentation fault (core dumped)) at sizes > 500000.
> >>>>
> >>>> Ideas?
> >>>>
> >>>> void merge(int *arr, int left, int middle, int right) {
> >>>>        int i=0, j=0, k=0;
> >>>>        int leftLen  = middle - left + 1;
> >>>>        int rightLen = right - middle;
> >>>>        int leftarr[leftLen];
> >>>>        int rightarr[rightLen];
> >>>>
> >>>>
> >>> These are variable length arrays. They go on the stack. Stacks are usually
> >>> small in relation to the total memory, they are designed to hold a few
> >>> working variables, not entire datasets. You're probably exceeding stack
> >>> capacity.
> >>
> >> replaced
> >> int leftarr[leftLen];
> >> int rightarr[rightLen];
> >>
> >> with
> >> int *leftarr  = malloc(sizeof(int) * (leftLen));
> >> int *rightarr = malloc(sizeof(int) * (rightLen));
> >>
> >>
> >> and that did it.
> >>
> > You also need to free the arrays, or you get a memory leak.
> 
> I put 2 free()s at the end of merge, but it slowed the program down 
> significantly.  What's the worst that could happen to the program if you 
> don't free them?  The sort always seemed to work fine without them.
> 
> 
> 
> > You should also check for null, though on a modern system it is very
> > unlikely that malloc will refuse to give you a sane amount of memory.
> 
> As I look at code and tutorials and examples out there, I'd say a 
> majority don't test for malloc() returning null.  Is that a function of 
> people thinking they have plenty of RAM?

There isn't much of a focus on error handling in most material since error
handling is quite challenging to do on a consistent basis, and can often
obfuscate the concept of what the code is trying to bring across.  Even
harder is to abstract the error checking to the point where you can change
error checking/handling behavior without massive code rewrites.

With any error, I think of it in three stages, the detection, the report,
and the response.

The detection is usually pretty obvious, for out of memory issues, you
check that the pointer is not NULL.  For the report, you can either print
a message to the console, write to a file or event log, popup a messagebox,
do nothing, and so on.  For the response, you may early exit from the
function, maybe abort the program, maybe initiate a reboot, or maybe
something even more sophisticated.

The biggest problem is that control of these elements can be difficult,
especially in multi-developer situations, and and many different opinions
exist on how important it is to implement whatever shade of gray you think
your error handling should be.

For example, let's talk about detection.  If I add detection of these
errors, I may potentially slow the code way down and make it harder to
see the logic.  If you progress to adding pre and post conditions and
possibly invariants, you can greatly improve the detection of errors at
the cost of performance.

Maybe you're ok with slowing the code way down because the library you're
using is not stable (in active development by someone else on the team),
and you want to weed out any issues early at the cost of speed.  But when
you want to build the deliverable, you want to maximize performance so you
drop the detection.  Usually it involves the preprocessor and/or macros
and cooperation from the build system to make those kinds of changes without
massive code rewrites.

For a concrete example, let's say you have a structure that represents a
dynamic array.  If you have another function that copies or modifies the
memory of the array, you can have an invariant that checks before and
after to make sure that the internal structure elements make sense before
and after the operation.

/*!
 * \struct c_array
 * \brief Define the structure for a dynamic resizable array.
 */
struct c_array
{
  /*! \brief The array's memory buffer. */
  void* buffer;

  /*! \brief The number of elements in the array. */
  size_t size;

  /*! \brief The allocated number of objects in the array's buffer. */
  size_t alloc_size;

  /*! \brief The size of each element in the array. */
  size_t element_size;

  /*!
   * \brief The free function to invoke when removing an object from
   *        a pointer array.
   *
   * The \c free_fn function pointer can be thought of as a parallel
   * to an object destructor in an object-oriented language (like
   * C++).
   */
  void (*free_fn)( void* );

  /*!
   * \brief A flag indicating whether to zero-initialize newly
   *        created objects when the array is expanded.
   */
  bool zero_initialize;

  /*!
   * \brief A flag indicating whether the array was created to store
   *        pointers to objects.
   */
  bool is_pointer;
};

/*!
 * \brief Define the \c c_array invariant.
 * \param carray A \c c_array.
 *
 * A valid \c c_array has the following properties.
 *
 * <ul>
 *   <li> The internal buffer (\c buf) cannot be \c NULL.  The
 *        minimum buffer allowed is a single element.
 *   <li> The allocated array size (\c alloc_size) should always
 *        be equal to or exceed the size of the array (\c size).
 *   <li> Only pointer arrays are allowed to have a non null free
 *        function.
 * </ul>
 */
#define C_ARRAY_INVARIANT( carray )                                         \
  do                                                                        \
  {                                                                         \
    C_INVARIANT( (carray)->buffer != NULL );                                \
    C_INVARIANT( (carray)->size <= (carray)->alloc_size );                  \
    C_INVARIANT( (carray)->is_pointer ? true : (carray)->free_fn == NULL ); \
  } while (0)

Here is an example of a function that uses it.

void gc_array_insert_sorted( struct c_array* array,
                             void* object,
                             int (*cmp_fn)( const void*, const void* ),
                             size_t type_sz )
{
  size_t index;
  void* p;
  int cmp;

  c_return_if_fail( array != NULL );
  c_return_if_fail( object != NULL );
  c_return_if_fail( cmp_fn != NULL );
  c_return_if_fail( array->element_size == type_sz );
  C_ARRAY_INVARIANT( array );

  index = 0;
  p = array->buffer;
  cmp = (*cmp_fn)( object, p );

  while ( index < array->size && cmp > 0 )
  {
    p = (unsigned char*)p + array->element_size;
    cmp = (*cmp_fn)( object, p );
    ++index;
  }

  gc_array_insert( array, index, object, array->element_size );

  C_ARRAY_INVARIANT( array );
}

If you're array structure isn't opaque, and people start fiddling with
members directly, this kind of checking can save you time if you're
willing to put in the infrastructure.  But as a fair warning, it's not
easy.

Taking it a step further, you may have a bsearch function that expects a
sorted array.  You can add a precondition check to verify that the array
is indeed sorted according to your comparison function before attempting
a binary search.

If you don't trust your array sort, maybe you feel it's a good idea to add
this check for early detection to reduce the time for troubleshooting.
However, this check greatly decreases performance of bsearch as the size
of the array gets large.  Maybe you'll add it in to the code temporarily,
then take it out, or restructure the code base and build system to have the
granularity to enable and disable integrity checking for more expensive
error conditions...

Well I rambled on more than I expected, hope it was somewhat interesting.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#147756

jadill33@gmail.com writes:
<cut>
> struct c_array
> {
>   /*! \brief The array's memory buffer. */
>   void* buffer;
...
> };
...
>  * A valid \c c_array has the following properties.
>  *
>  * <ul>
>  *   <li> The internal buffer (\c buf) cannot be \c NULL.  The

\c buffer

I tiny detail, I know, but having seen it, I feel I should mention it.

<cut>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147764

On Thursday, November 7, 2019 at 7:56:05 PM UTC-5, Ben Bacarisse wrote:
> j...@gmail.com writes:
> <cut>
> > struct c_array
> > {
> >   /*! \brief The array's memory buffer. */
> >   void* buffer;
> ...
> > };
> ...
> >  * A valid \c c_array has the following properties.
> >  *
> >  * <ul>
> >  *   <li> The internal buffer (\c buf) cannot be \c NULL.  The
> 
> \c buffer
> 
> I tiny detail, I know, but having seen it, I feel I should mention it.
> 
> <cut>

Appreciated, thanks!

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#147768

>> and that did it.
> You also need to free the arrays, or you get a memory leak.

> You should also check for null, though on a modern system it is very
> unlikely that malloc will refuse to give you a sane amount of memory.

DFS is light-years distant from writing production-quality code.
I think he will never get there.

[toc] | [prev] | [next] | [standalone]

#147772

On 11/8/2019 8:50 AM, Bonita Montero wrote:
>>> and that did it.
>> You also need to free the arrays, or you get a memory leak.
> 
>> You should also check for null, though on a modern system it is very
>> unlikely that malloc will refuse to give you a sane amount of memory.
> 
> DFS is light-years distant from writing production-quality code.
> I think he will never get there.


What's your problem with me, shitbird?  Why do you care about my code?

This is nothing but hobby coding for me.  I like C because it's very 
fast and 'close to the metal'.

How about this: give me some moderately challenging task and I'll write 
my C version and you write your C++ version and we'll compare.

[toc] | [prev] | [next] | [standalone]

#147773

On 11/8/2019 9:31 AM, DFS wrote:

>  sh*itbird


To clc: sorry for the cursing, but Ugly Montero is irritating.

[toc] | [prev] | [next] | [standalone]

Page 1 of 11  [1] 2 3 … 11  Next page →

Back to top | Article view | comp.lang.c

csiph-web