It does need to be stable, which is why the replacement is mergesort.
The SYSINITs need to bring up the system in a particular order. I dunno why there are both explicit ordering (the sort keys) and implicit ordering (the stability requirement), perhaps cperciva can chime in.
Based on when I last looked at this code, I guess the explicit ordering is to do with startup phases, and the implicit ordering is because of the way SYSINITs are (or were?) implemented using linker sets, which have more guarantees about ordering than __attribute__((constructor)) and other similar functionality.
> a number of bugs have happened in the past because people didn't order properly.
This may be impractical, but I think my reaction would be to re-design it so that the ordering was mechanically a full order, even if culturally the people writing these things don't need to specify if they don't want to.
e.g. maybe a macro can turn your existing explicit order into high bits of a value, and then a "noise" factor into low bits, where that "noise" is derived from a date integer like 20230822 or filenames or whatever, and truly order on the entire value.
The idea is, this means any hidden order is the same for everyone, Intel laptop test rig, ARM WiFi cameras at customer site, last week's build, this week's build, Colin's build, the CI system's build, they're all using the same order, because while heisenbugs are strictly worse, "It only happens with my setup" is also extremely frustrating.
When people discover a hidden ordering requirement they can adjust the "real" ordering accordingly, just now there's a deliberate systemic consistency.
Probably not worth all the bother, but I think I couldn't live with the "stable sort to avoid heisenbugs" situation.
The SYSINITs need to bring up the system in a particular order. I dunno why there are both explicit ordering (the sort keys) and implicit ordering (the stability requirement), perhaps cperciva can chime in.
Based on when I last looked at this code, I guess the explicit ordering is to do with startup phases, and the implicit ordering is because of the way SYSINITs are (or were?) implemented using linker sets, which have more guarantees about ordering than __attribute__((constructor)) and other similar functionality.