3 ms·
Options for sorting algorithms are severely limited when (a) you can't use malloc, (b) you don't have enough stack to recurse, and (c) you want a stable sort.
by cperciva 3y ago
Options for sorting algorithms are severely limited when (a) you can't use malloc, (b) you don't have enough stack to recurse, and (c) you want a stable sort.
(The first two limitations are because this happens very early in the boot process.)
- dataflow 3y agoThanks! I completely forgot about the malloc/in-place aspect.
- magicalhippo 3y agoWhy the hash stack limit? I assume this precludes a fixed-size array.
- ahoka 3y agoI'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.
- kevans91 3y agoRight, 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).
- aidenn0 3y agoDoesn't mergesort require malloc?
- cperciva 3y agoThere 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.