Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by dataflow on Monday August 21, 2023 @12:42AM
(#37205570)
Thanks! I completely forgot about the malloc/in-place aspect.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by magicalhippo on Monday August 21, 2023 @01:16AM
(#37205733)
Why the hash stack limit? I assume this precludes a fixed-size array.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by ahoka on Monday August 21, 2023 @06:21AM
(#37207499)
I'm not sure when this sort happens, but early boot may not have a proper virtual memory implementation yet, so the kernel has to use a fixed stack size allocated by the boot loader.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by kevans91 on Monday August 21, 2023 @12:20PM
(#37211682)
Right, in this case specifically we're running off a limited bootstack allocated in the kernel's .bss (somewhere between 2 to 6 pages, generally); we won't finish initializing VM until shortly after this sort is done (in some of the SYSINITs that we're sorting).
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by aidenn0 on Monday August 21, 2023 @12:31PM
(#37211856)
Doesn't mergesort require malloc?
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by cperciva on Monday August 21, 2023 @12:58PM
(#37212251)
There are in-place array mergesorts. (Nobody uses them because they're horribly complicated, though.)
In this case however I'm putting all of the SYSINITs onto a linked list; mergesorting a linked list is easy.
(The first two limitations are because this happens very early in the boot process.)