News for hackers. Stuff that matters.
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.
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