FreeBSD replaces bubblesort with mergesort on SYSINTs, results in 100x speed

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by erk__ on Monday August 21, 2023 @02:33PM (#37213531)

For reference the original code was a bit more complicated than just sorting integers which may also have been a reason for the choice.

        /*
         * Perform a bubble sort of the system initialization objects by
         * their subsystem (primary key) and order (secondary key).
         *
         * Since some things care about execution order, this is the
         * operation which ensures continued function.
         */
        for( sipp = (struct sysinit **)sysinit_set.ls_items; *sipp; sipp++) {
                for( xipp = sipp + 1; *xipp; xipp++) {
                        if( (*sipp)->subsystem < (*xipp)->subsystem ||
                            ( (*sipp)->subsystem == (*xipp)->subsystem &&
                              (*sipp)->order < (*xipp)->order))
                                continue;       /* skip*/
                        save = *sipp;
                        *sipp = *xipp;
                        *xipp = save;
                }
        }

https://github.com/freebsd/freebsd-src/blob/2b14f991e64ebe31...

[ Parent | on HN ]

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Monday August 21, 2023 @08:39PM (#37217143)

this is actually selection sort; the comment is wrong

[ Parent | on HN ]

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by erk__ on Tuesday August 22, 2023 @01:38PM (#37226079)

That is a pretty interesting observation, I don't think I would have spotted that, especially given everyone have been saying it was bubblesort.

[ Parent | on HN ]

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Tuesday August 22, 2023 @04:39PM (#37228204)

i probably wouldn't have spotted it without trying to figure out which variant of bubblesort it was: counting up? counting down? does it adjust the inner loop size? early exit?

selection sort has the potential advantage for things that are larger than your key that it can avoid copying the entire item, just doing a single swap at the end of the inner loop, but it's not implemented that way here. that would have looked like this

    size_t m = 0;
    register unsigned int subsystem = (*sipp)->subsystem;
    register unsigned int order = (*sipp)->order;
    for( xipp = sipp + 1; *xipp; xipp++) {
        register unsigned int newsubsystem = (*xipp)->subsystem;
        register unsigned int neworder = (*xipp)->order;
        if( subsystem < newsubsystem ||
            (subsystem == newsubsystem && order < neworder))
                  continue;       /* skip*/
        m = xipp - sipp;
        subsystem = newsubsystem;
        order = neworder;  /* enjoy the sorting */
    }

    save = sipp[0];
    sipp[0] = sipp[m];
    sipp[m] = save;

on the other hand if you were going to put effort into optimizing this you probably would have used mergesort or something

[ Parent | on HN ]