cvs commit: fptools/ghc/compiler/codeGen CgCallConv.hs CgStackery.lhs CgUtils.hs fptools/ghc/compiler/ghci ByteCodeGen.lhs fptools/ghc/compiler/iface MkIface.lhs fptools/ghc/compiler/main ErrUtils.lhs fptools/ghc/compiler/rename RnNames.lhs ...

[Simon Peyton Jones]

simonpj     2004/08/17 08:24:14 PDT

  Modified files:
    ghc/compiler/codeGen CgCallConv.hs CgStackery.lhs CgUtils.hs 
    ghc/compiler/ghci    ByteCodeGen.lhs 
    ghc/compiler/iface   MkIface.lhs 
    ghc/compiler/main    ErrUtils.lhs 
    ghc/compiler/rename  RnNames.lhs 
    ghc/compiler/simplCore SetLevels.lhs 
    ghc/compiler/simplStg SRT.lhs 
    ghc/compiler/specialise Rules.lhs 
    ghc/compiler/typecheck TcDeriv.lhs TcRnDriver.lhs 
    ghc/compiler/utils   Digraph.lhs ListSetOps.lhs Util.lhs 
  Log:
  	-------------------------------
  	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.
  
  Revision  Changes    Path
  1.3       +2 -2      fptools/ghc/compiler/codeGen/CgCallConv.hs
  1.26      +3 -3      fptools/ghc/compiler/codeGen/CgStackery.lhs
  1.3       +5 -5      fptools/ghc/compiler/codeGen/CgUtils.hs
  1.103     +1 -1      fptools/ghc/compiler/ghci/ByteCodeGen.lhs
  1.15      +7 -7      fptools/ghc/compiler/iface/MkIface.lhs
  1.48      +6 -3      fptools/ghc/compiler/main/ErrUtils.lhs
  1.170     +6 -3      fptools/ghc/compiler/rename/RnNames.lhs
  1.60      +4 -4      fptools/ghc/compiler/simplCore/SetLevels.lhs
  1.19      +2 -2      fptools/ghc/compiler/simplStg/SRT.lhs
  1.40      +3 -3      fptools/ghc/compiler/specialise/Rules.lhs
  1.134     +2 -2      fptools/ghc/compiler/typecheck/TcDeriv.lhs
  1.77      +3 -3      fptools/ghc/compiler/typecheck/TcRnDriver.lhs
  1.19      +7 -5      fptools/ghc/compiler/utils/Digraph.lhs
  1.12      +3 -3      fptools/ghc/compiler/utils/ListSetOps.lhs
  1.68      +3 -122    fptools/ghc/compiler/utils/Util.lhs