Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am implementing an application in Haskell and, for sorting, I use the library function Data.List.sort. However, I was wondering whether this is the fastest sort implementation in the Haskell standard library (perhaps lists are not the best choice for efficient sorting).

I have found different alternatives, e.g. heap sort on arrays, sort on sequences (but the documentation does not say what kind of algorithm is used).

My question is: what is the fastest sorting implementation (container type + sort function) provided by the Haskell standard library? Is there some documentation page listing all library sort functions and comparing them wrt performance?

EDIT

To provide some more context, I am running a benchmark. I have written a simple program in C, Java, Python and Haskell that

  1. Reads 1000000 strings (lines) from a text file.
  2. Sorts the strings using a built-in (library) sorting algorithm.
  3. Writes the sorted list of strings to a file.

For each implementation, I only measure the sorting time (leaving out the time needed for disk IO). Running the benchmark on Ubuntu 12.04, I get

  • C (gcc 4.6.3, qsort on char **): 0.890 s
  • Java (OpenJDK 64-Bit 1.7.0_09, Collections.sort() on java.util.LinkedList<String>): 1.307 s
  • Python (Python 2.7.3, list.sort()): 1.072 s
  • Haskell (GHC 7.4.1, Data.List.sort on [Data.ByteString.UTF8.ByteString]): 11.864 s

So I wonder if there is another data type / library function in Haskell that can give better performance.

share|improve this question
    
You might avoid some overhead if you use unboxed arrays, they tend to be nice and quick –  jozefg Dec 23 '12 at 4:52
    
Could you post here (or to some pastebin) your testing programs, so that we can work with them? –  Petr Pudlák Dec 23 '12 at 12:13
    
@Petr Pudlák: All of them? Or would the Haskell version be sufficient? It is a project I am working on and I would prefer to post only the parts relevant to sorting in Haskell. –  Giorgio Dec 23 '12 at 12:40
    
Sure, Haskell will be enough. –  Petr Pudlák Dec 23 '12 at 12:50
    
@Petr Pudlák: Here it is pastebin.com/EjttY212 –  Giorgio Dec 23 '12 at 13:24
show 5 more comments

1 Answer 1

up vote 4 down vote accepted

The problem with Data.List.sort is that it uses merge sort, which creates new lists during each pass. So a lot of time is spent on allocating and freeing memory.

Surprisingly, AFAIK there isn't a sorting library for mutable arrays, which are likely to be faster. So I tried to make one and put it on github: marray-sort. It needs rigorous testing, polishing and optimizing too, but so far it already seems to be significantly faster than Data.List.sort.

If you make any experiments with it, I'd be happy to see the results. I put your (slightly modified) benchmark to src-test/Test.hs for convenience. Don't forget to compile everything with -O2 to trigger the necessary compiler optimizations.

Edit: I found out now that there is an implementation if introsort for mutable vectors in vector-algorithms. According to my measurements, it is slightly faster (5-10%) than my attempt above for MArrays See also: How does one sort with Data.Vector.Generic.Mutable?.

share|improve this answer
    
Thanks a lot (+1). I have also written a quick sort (and merge sort) for mutable arrays. I am eager to look at your solution (even though it will have to wait until the coming week end). –  Giorgio Jan 14 '13 at 8:57
    
Sorry that it took me so long to answer. I am working on this project in my free time and I kept postponing it. I have now tried out your implementation and it is definitely faster than the Data.List.Sort. I also have implemented my own merge sort on mutable arrays and it runs a bit faster than introsort, at least on my examples. I haven't tried Data.Vector.Algorithms.Intro.sort yet. –  Giorgio Jan 12 at 22:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.