News for hackers. Stuff that matters.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by knome on Monday August 21, 2023 @12:45AM (#37205585)
sure, but bubble sort is trivial to write. they may have figured they'd replace it when they needed to. they may have figured the particular usage was so trivial they would never need to.

grabbed the source and git blamed the file before the patch to see when the original code was from.

    94e9d7c12 (Peter Wemm              1998-10-09 23:42:47 +0000 157)  * The sysinit table itself.  Items are checked off as the are run.
    94e9d7c12 (Peter Wemm              1998-10-09 23:42:47 +0000 158)  * If we want to register new sysinit types, add them to newsysinit.
So the section was written in 98 and had some bits modified in 2001.

The time wasted during boot here was probably irrelevant next to a hundred other things the project has worked on since.

the bubble sort was good enough that 25 years later they replaced it to save only 2ms during boot.

seems reasonable to me.

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by naniwaduni on Monday August 21, 2023 @01:15AM (#37205726)
You'd still think it'd be easier to write an insertion sort though, even accidentally! It's almost the same algorithm conceptually, except cutting out an odd pessimization.