FreeBSD replaces bubblesort with mergesort on SYSINTs, results in 100x speed

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Monday August 21, 2023 @08:55PM (#37217250)

remarkable, thank you

all of the bubble sorts i tried compiling in this thread ended up being compiled to code with either conditional branches or (on arm thumb-2) a couple of conditionalized stores. but conditional stores don't require a pipeline flush, and it is of course perfectly correct that insertion sort depends on its inner loop having an unpredictable branch to get better performance on almost-sorted data, which bubble sort does not

[ Parent | on HN ]

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Friday August 25, 2023 @06:41PM (#37267920)

after thinking about it some more, i was skeptical that this really implements bubble sort, but after trying it, it does

python version of the inner loop

    max_ = arr[0]
    for j in range(1, i):
        y = arr[j]
        arr[j - 1] = min(max_, y)
        max_ = max(max_, y)

    arr[i - 1] = max_

[ Parent | on HN ]