3 ms·
For reference the original code was a bit more complicated than just sorting integers which may also have been a reason for the choice. /* * P
by erk__ 3y ago
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/2b14f991e64ebe31ca31a1a41237061c22a753d0/sys/kern/init_main.c#L149-L166 https://github.com/freebsd/freebsd-src/blob/2b14f991e64ebe31...
- kragen 3y agothis is actually selection sort; the comment is wrong
- erk__ 3y agoThat is a pretty interesting observation, I don't think I would have spotted that, especially given everyone have been saying it was bubblesort.
- kragen 3y agoi 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