Skip to content
  • Simon Peyton Jones's avatar
    [project @ 2004-08-17 15:23:47 by simonpj] · 59c796f8
    Simon Peyton Jones authored
    -------------------------------
    	Use merge-sort not quicksort
    	Nuke quicksort altogether
    	-------------------------------
    
    Quicksort has O(n**2) behaviour worst case, and this occasionally bites.
    In particular, when compiling large files consisting only of static data,
    we get loads of top-level delarations -- and that led to more than half the
    total compile time being spent in the strongly connected component analysis
    for the occurrence analyser.  Switching to merge sort completely solved the
    problem.
    
    I've nuked quicksort altogether to make sure this does not happen again.
    59c796f8