Bubble sort algorithm implementations (Haskell vs. C)

Question

Hello. I have written 2 implementation of bubble sort algorithm in C and Haskell. Haskell implementation:

module Main where
main = do
    contents <- readFile "./data"
    print "Data loaded. Sorting.."
    let newcontents = bubblesort contents
    writeFile "./data_new_ghc" newcontents
    print "Sorting done"
bubblesort list = sort list [] False
rev  = reverse          -- separated. To see
rev2 = reverse          --  who calls the routine
sort (x1:x2:xs) acc _
    | x1 > x2           = sort (x1:xs) (x2:acc) True
sort (x1:xs) acc flag   = sort xs (x1:acc) flag
sort [] acc True        = sort (rev acc) [] False
sort _ acc _            = rev2 acc

I've compared these two implementations having run both on file with size of 20 KiB.
C implementation took about a second, Haskell — about 1 min 10 sec.
I have also profiled the Haskell application:
Compile for profiling:

C:\Temp> ghc -prof -auto-all -O --make Main

Profile:

C:\Temp> Main.exe +RTS -p

and got these results. This is a pseudocode of the algorithm:

procedure bubbleSort( A : list of sortable items ) defined as:
    do
        swapped := false
        for each i in 0 to length(A) - 2 inclusive do:  
            if A[i] > A[i+1] then  
                swap( A[i], A[i+1] )  
                swapped := true  
            end if  
        end for  
    while swapped  
end procedure  

I wonder if it's possible to make Haskell implementation work faster without changing the algorithm (there are actually a few tricks to make the algorithm work faster, but neither implementations have these optimizations).

Answer 1

It's probably because bubble sort is an algorithm for arrays, but you're using a linked list: swapping two items in an array (which is what C uses) is O(1) time and requires no extraneous space, but swapping two items in a linked list (which is what Haskell uses) is O(n) time and O(n) space (and this is heap space, not stack space). However, I'm having a little trouble following your code (are you absolutely sure it's the same algorithm?), and it's possible your accumulator deals with the swap's time complexity. However, even if it does, you're allocating a new accumulator list; this will definitely still allocate extra space, and I think this may very well still be one of the reasons for Haskell's worse performance.

Also, why do you have rev and rev2, rather than just using reverse in both places? If it's because you wanted to profile them separately, then you should instead use the SCC ("Set Cost Center") pragma, described in chapter 5 of the GHC User's Guide: sort ({-# SCC "rev" #-} reverse acc) [] False and {-# SCC "rev2" #-} reverse acc. Each cost center is profiled separately; -auto-all is just implicitly adding cost centers around each function. If you have these functions for some other reason, you still probably shouldn't (why do you?), but my explanation is irrelevant :)

Answer 2

Since bubble sort has quite poor memory locality properties, I think it's likely that your implementations are memory bandwidth-bound, though I have not done any testing.

The native Haskell String = [Char] is extremely convenient, but not suitable when performance is the main priority. I forget the exact numbers, but I'm sure a String uses at least 16 bytes per character on a 32-bit system, and roughly double that on a 64-bit system. By contrast I assume your C program uses 1 byte per character. So, one can expect a very approximately 16-fold slowdown from this alone.

You're also emulating a mutable array by means of a pair of linked lists (this is usually called a "zipper"). This is reasonably efficient as long as you are making local modifications around a moving focus, which is true for the most part in bubble sort. However, at the end of each pass, you need to move the focus back to the start (this is rev). This probably accounts for another factor of 2 in the amount of work done in the algorithm.

So, I don't think your benchmarks are very surprising.

If you want to write a fast bubblesort in Haskell, the way to go would be to implement your pseudocode directly in the ST monad using a mutable unboxed array. I don't think you will see a bubblesort in an entirely pure language with a much better constant factor any time soon (though I would love to be proven wrong of course).

Answer 3

You might express the algorithm more directly in Haskell, without the reverse calls:

bubblesort :: (Ord a) => [a] -> [a]
bubblesort []      = []
bubblesort (x0:xs) = case bubble x0 xs of
   (xs', True)  -> bubblesort xs'
   (xs', False) -> xs'
   where bubble x1 (x2:xs) | x1 <= x2  = merge x1 False $ bubble x2 xs
                           | otherwise = merge x2 True  $ bubble x1 xs
         bubble x1 []                  = ([x1], False)
         merge x s (xs, s') = (x:xs, s || s')

Here, the local bubble function does the job of bubbling a value through, and the merge function handles both rebuilding the new, bubbled list, and the swap flag. The case expression in bubblesort is a direct expression in Haskell of "bubble through the list once, and if we swapped anything, do it again".

This version clocks in at about 35% faster than your original.

P.S.: Code and driver Main files can be found here: http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/

Answer 4

I notice that you passed -O instead of -O2. You might get some speed up from -O2.

As others mention, this is not the same algorithm in C and Haskell because the data structures differ--Haskell uses an immutable linked list of Unicode characters. What is your purpose?

1. The fastest sort of any kind in many languages?
2. The fastest bubble sort in many languages?
3. The fastest idiomatic bubble sort in many languages?

I guess (1) is not the case since you are using bubble sort in C as well. If (2), then you should be using STUArray of Word8s, which will give you an algorithm close to the C version (though probably uglier and slower). If (3), I am sort of confused, because bubble sort only really looks idiomatic in BASIC (the old kind, where you capitalise the entire word, not like VisualBasic with only two capitals). You should expect elegance and performance to degrade in direct proportion with the language's similarity to BASIC.

Whatever the case, it would be interesting to see the performance of a immutable linked-list recursive bubble sort of Unicode strings in C.