<story><title>FreeBSD replaces bubblesort with mergesort on SYSINTs</title><url>https://twitter.com/cperciva/status/1693127769901969772</url></story><parent_chain><item><author>kragen</author><text>yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort&lt;p&gt;&lt;pre&gt;&lt;code&gt;    for (size_t i = 0; i &amp;lt; n; i++) {
        for (size_t j = 1; j &amp;lt; n - i; j++) {
            if (a[j-1] &amp;gt; a[j]) {
                item_t tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
&lt;/code&gt;&lt;/pre&gt;
when you could use insertion sort&lt;p&gt;&lt;pre&gt;&lt;code&gt;    for (size_t i = 1; i &amp;lt; n; i++) {
        for (size_t j = i; j &amp;gt; 0; j--) {
            item_t tmp = a[j];
            if (tmp &amp;gt; a[j-1]) break;
            a[j] = a[j-1];
            a[j-1] = tmp;
        }
    }
&lt;/code&gt;&lt;/pre&gt;
which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases&lt;p&gt;(above code only minimally tested: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;godbolt.org&amp;#x2F;z&amp;#x2F;43dqz9Gq8&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;godbolt.org&amp;#x2F;z&amp;#x2F;43dqz9Gq8&lt;/a&gt;)&lt;p&gt;this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you&amp;#x27;d never ship anything.  freebsd&amp;#x27;s code quality is quite high, but probably we can all agree that this was stupid&lt;p&gt;of course it wouldn&amp;#x27;t be nearly as fast as mergesort on large inputs, but mergesort is more complicated&lt;p&gt;(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you&amp;#x27;re only sorting something once at startup time, that probably isn&amp;#x27;t important.  it might matter if you were sorting a million lists of ten items or something)</text></item><item><author>xyzelement</author><text>To sum up what I learned from the comments:&lt;p&gt;Is FreeBSD stupid for having used bubblesort to begin with? NO. It worked well for decades before surfacing as a problem in this extreme and unanticipated use case.&lt;p&gt;Is optimizing this a waste of time? NO. The use case revolves around super frequent bootups to power lambda and for this type of thing every ms matters.</text></item></parent_chain><comment><author>kqr</author><text>&amp;gt; there is never a good reason to use bubble sort&lt;p&gt;I used to believe this but then a friend pointed out a real use case for bubble sort: when you have an array that is always mostly sorted, and real-time performance is more important than perfectly correct ordering. Then running one pass of bubble sort each cycle around the main loop is somewhat satisfyingly ideal.&lt;p&gt;One pass of insertion sort would be too expensive, and bubble sort is guaranteed to make incremental progress each pass.&lt;p&gt;This is sort of like how a linked list is never the right solution... unless it&amp;#x27;s one of those cases where intrusive linked lists are ideal. Except while intrusive linked lists intrude in space, intrusive bubble sort kind of intrudes in time.</text></comment>
<story><title>FreeBSD replaces bubblesort with mergesort on SYSINTs</title><url>https://twitter.com/cperciva/status/1693127769901969772</url></story><parent_chain><item><author>kragen</author><text>yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort&lt;p&gt;&lt;pre&gt;&lt;code&gt;    for (size_t i = 0; i &amp;lt; n; i++) {
        for (size_t j = 1; j &amp;lt; n - i; j++) {
            if (a[j-1] &amp;gt; a[j]) {
                item_t tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
&lt;/code&gt;&lt;/pre&gt;
when you could use insertion sort&lt;p&gt;&lt;pre&gt;&lt;code&gt;    for (size_t i = 1; i &amp;lt; n; i++) {
        for (size_t j = i; j &amp;gt; 0; j--) {
            item_t tmp = a[j];
            if (tmp &amp;gt; a[j-1]) break;
            a[j] = a[j-1];
            a[j-1] = tmp;
        }
    }
&lt;/code&gt;&lt;/pre&gt;
which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases&lt;p&gt;(above code only minimally tested: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;godbolt.org&amp;#x2F;z&amp;#x2F;43dqz9Gq8&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;godbolt.org&amp;#x2F;z&amp;#x2F;43dqz9Gq8&lt;/a&gt;)&lt;p&gt;this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you&amp;#x27;d never ship anything.  freebsd&amp;#x27;s code quality is quite high, but probably we can all agree that this was stupid&lt;p&gt;of course it wouldn&amp;#x27;t be nearly as fast as mergesort on large inputs, but mergesort is more complicated&lt;p&gt;(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you&amp;#x27;re only sorting something once at startup time, that probably isn&amp;#x27;t important.  it might matter if you were sorting a million lists of ten items or something)</text></item><item><author>xyzelement</author><text>To sum up what I learned from the comments:&lt;p&gt;Is FreeBSD stupid for having used bubblesort to begin with? NO. It worked well for decades before surfacing as a problem in this extreme and unanticipated use case.&lt;p&gt;Is optimizing this a waste of time? NO. The use case revolves around super frequent bootups to power lambda and for this type of thing every ms matters.</text></item></parent_chain><comment><author>mort96</author><text>I would trust myself more to implement bubble sort than to implement insertion sort. Not that I couldn&amp;#x27;t implement insertion sort, I&amp;#x27;ve done it before, but if I was in a context where I had to implement a quick and dirty ad-hoc sorting algorithm which I thought would only ever have to sort a few items, I would probably go with bubble sort.&lt;p&gt;If I suspected at all that the algorithms would have to sort a decent number of items, I wouldn&amp;#x27;t consider using an O(n^2) sort at all and would take the time to find a good implementation of (or implement) one of the O(n log(n)) algorithms.</text></comment>