#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by leroux): criterion benchmark from ​https://github.com/nh2/haskell-ordnub: https://rawgithub.com/nh2/haskell-ordnub/master/report.html -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by leroux): ordNub discussion: https://groups.google.com/forum/#!topic/haskell- cafe/4UJBbwVEacg -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by leroux): Related: Proposal to add sortNub (http://ghc.haskell.org/trac/ghc/ticket/1218) The only reason I mention this is because the compiler uses `sort . nub` in a few places. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: leroux Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by leroux): Patch: attachment:ordNub-analysis (just an initial point to start at) Based on nofib-analyse attachment:ordNub-analysis​, it seems that it may be a good idea to selectively replace `nub`'s where it is applied over larger lists so that it cuts down on overhead. Snippet from nofib-analysis {{{ -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- anna +0.0% +0.0% 0.11 0.12 +0.0% ansi +0.0% +0.0% 0.00 0.00 +0.0% atom +0.0% +0.0% -0.9% -0.4% +0.0% awards +0.0% +0.0% 0.00 0.00 +0.0% banner +0.0% +0.0% 0.00 0.00 +0.0% bernouilli +0.0% +0.0% 0.17 0.18 +0.0% binary-trees +0.0% +0.0% -7.3% -8.8% +0.0% boyer +0.0% +0.0% 0.04 0.05 +0.0% boyer2 +0.0% +0.0% 0.00 0.00 +0.0% bspt -0.1% +0.0% 0.00 0.01 +0.0% cacheprof +0.1% +0.0% -3.2% -2.1% +0.9% calendar +0.0% +0.0% 0.00 0.00 +0.0% cichelli +0.0% +0.0% 0.08 0.09 +0.0% circsim +0.0% +0.0% +6.0% +6.1% +0.0% clausify +0.0% +0.0% 0.04 0.05 +0.0% comp_lab_zift +0.0% +0.0% 0.20 +5.0% +0.0% compress +0.0% +0.0% 0.17 0.18 +0.0% compress2 +0.0% +0.0% 0.16 0.17 +0.0% constraints +0.0% +0.0% +1.7% +2.0% +0.0% cryptarithm1 +0.0% +0.0% -2.5% -2.4% +0.0% cryptarithm2 +0.0% +0.0% 0.01 0.01 +0.0% cse +0.0% +0.0% 0.00 0.00 +0.0% eliza +0.0% +0.0% 0.00 0.00 +0.0% event +0.0% +0.0% 0.14 0.15 +0.0% exp3_8 -0.1% +0.0% +1.9% +1.8% +0.0% expert +0.0% +0.0% 0.00 0.00 +0.0% fannkuch-redux -0.1% +0.0% +0.9% +1.0% +0.0% fasta -0.1% +0.0% +2.7% +4.5% +0.0% fem +0.0% +0.0% 0.02 0.03 +0.0% fft -0.1% +0.0% 0.03 0.04 +0.0% fft2 +0.0% +0.0% 0.05 0.05 +0.0% fibheaps +0.1% +0.0% 0.03 0.03 +0.0% fish +0.0% +0.0% 0.01 0.02 +0.0% fluid +0.0% +0.0% 0.01 0.01 +0.0% fulsom +0.1% +0.0% +1.3% +3.2% -1.3% gamteb +0.0% +0.0% 0.05 0.05 +0.0% gcd +0.0% +0.0% 0.03 0.03 +0.0% gen_regexps +0.0% +0.0% 0.00 0.00 +0.0% genfft -0.1% +0.0% 0.03 0.03 +0.0% gg +0.0% +0.0% 0.00 0.02 +0.0% grep +0.0% +0.0% 0.00 0.00 +0.0% hidden +0.0% +0.0% +2.5% +1.9% +0.0% hpg +0.0% +0.0% 0.10 +1.8% +0.0% ida +0.0% +0.0% 0.08 0.08 +0.0% infer +0.0% +0.0% 0.06 0.07 +0.0% integer +0.0% +0.0% +0.2% +0.0% +0.0% integrate +0.0% +0.0% 0.16 0.20 +0.0% k-nucleotide -0.1% +0.0% +3.3% +5.5% +0.0% kahan +0.0% +0.0% 0.17 0.17 +0.0% knights +0.0% +0.0% 0.00 0.01 +0.0% lcss +0.0% +0.0% -2.4% -2.2% +0.0% life +0.0% +0.0% -5.2% -8.5% +0.0% lift +0.0% +0.0% 0.00 0.00 +0.0% listcompr +0.0% +0.0% 0.07 0.08 +0.0% listcopy +0.0% +0.0% 0.07 0.09 +0.0% maillist +0.0% -0.0% 0.05 -8.1% +10.0% mandel +0.0% +0.0% 0.06 0.07 +0.0% mandel2 +0.0% +0.0% 0.00 0.00 +0.0% minimax +0.0% +0.0% 0.00 0.00 +0.0% mkhprog +0.0% +0.0% 0.00 0.00 +0.0% multiplier +0.0% +0.0% 0.11 0.12 +0.0% n-body +0.0% +0.0% +19.0% +22.2% +0.0% nucleic2 +0.0% +0.0% 0.06 0.07 +0.0% para +0.0% +0.0% -4.5% -3.1% +0.0% paraffins +0.0% +0.0% 0.11 0.12 +0.0% parser +0.0% +0.0% 0.03 0.03 +0.0% parstof +0.0% +0.0% 0.00 0.00 +0.0% pic +0.0% +0.0% 0.00 0.00 +0.0% pidigits +0.0% +0.0% +2.3% +1.7% +0.0% power +0.0% +0.0% +3.4% +4.2% +0.0% pretty +0.0% +0.0% 0.00 0.00 +0.0% primes +0.0% +0.0% 0.06 0.07 +0.0% primetest +0.0% +0.0% 0.11 0.11 +0.0% prolog +0.0% +0.0% 0.00 0.01 +0.0% puzzle +0.0% +0.0% 0.14 0.15 +0.0% queens +0.0% +0.0% 0.01 0.02 +0.0% reptile +0.0% +0.0% 0.00 0.01 +0.0% reverse-complem +0.0% +0.0% 0.10 0.17 +0.0% rewrite +0.0% +0.0% 0.01 0.02 +0.0% rfib +0.0% +0.0% 0.01 0.01 +0.0% rsa +0.1% +0.0% 0.02 0.03 +0.0% scc +0.0% +0.0% 0.00 0.00 +0.0% sched +0.0% +0.0% 0.01 0.02 +0.0% scs +0.0% +0.0% -25.4% -32.2% +0.0% simple +0.0% +0.0% +0.0% -0.7% +0.0% solid +0.0% +0.0% 0.16 0.16 +0.0% sorting +0.0% +0.0% 0.00 0.00 +0.0% spectral-norm +0.0% +0.0% -0.4% -0.1% +0.0% sphere +0.0% +0.0% 0.04 0.05 +0.0% symalg +0.0% +0.0% 0.01 0.01 +0.0% tak +0.0% +0.0% 0.01 0.01 +0.0% transform +0.0% +0.0% +2.5% +1.8% +0.0% treejoin +0.0% +0.0% 0.15 0.17 +0.0% typecheck +0.1% +0.0% +1.0% +1.9% +0.0% veritas +0.0% +0.0% 0.00 0.01 +0.0% wang +0.1% +0.0% 0.13 0.14 +0.0% wave4main +0.0% +0.0% +3.0% +7.3% +0.0% wheel-sieve1 +0.0% +0.0% -1.1% -1.6% +0.0% wheel-sieve2 +0.0% +0.0% 0.21 +5.6% +0.0% x2n1 -0.1% +0.0% 0.00 0.01 +0.0% -------------------------------------------------------------------------------- Min -0.1% -0.0% -25.4% -32.2% -1.3% Max +0.1% +0.0% +19.0% +22.2% +10.0% Geometric Mean -0.0% -0.0% -0.3% -0.1% +0.1% }}} There's more work to be done! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: leroux Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by leroux): nofib benchmark comparisons of HEAD vs HEAD with ordNub patch applied. (BuildFlavour=quick) https://gist.github.com/leroux/6725810#file-headvordnub-analysis-L2988. ---- hvr has pointed out that having cases for `[]`, `[a]`, and `[a, b]` will most probably prevent the overhead from using Set for trivial calls. I'll post an updated benchmark later today with that implemented. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: leroux Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by simonpj): A 5% improvement in compile time is remarkable, if it's true. Great! But I'm always worried about the noise in compile times measured in seconds. It would be great if you could do a sanity check by looking at how much GHC itself allocates in the before and after cases. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: leroux Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: wontfix | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Changes (by leroux): * status: new => closed * resolution: => wontfix Comment: Full nofib analysis of head, ordNub, and ordNub-cases (each ran twice): https://gist.github.com/leroux/6750216 I took certain measures to make sure the nofib benchmarks would return "truer" results. I think you'll find the results much more reliable now. According to the results, sadly the 5% performance gain in compile time was complete bogus. Sorry. =( Snippet from https://gist.github.com/leroux/6750216#file-full-ordnub- analysis-L2880-L3467 (compile times): {{{ Compile Times ------------------------------------------------------------------------------- Program head-0 head-1 ordNub-0 ordNub-1 ordNub-cases-0 ordNub-cases-1 ------------------------------------------------------------------------------- -1 s.d. ----- -1.6% -1.6% -1.7% -1.7% -1.7% +1 s.d. ----- +1.9% +2.1% +1.6% +2.0% +1.7% Average ----- +0.1% +0.2% -0.0% +0.1% -0.0% }}} I'm closing this ticket now since there is no obvious improvement from replacing `nub` with `ordNub`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------+------------------------------------- Reporter: nh2 | Owner: leroux Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: wontfix | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Compile-time | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------- Comment (by simonpj): Don't give up so easily :-) Did you look at the amount of heap the compiler ''allocated''? It's easily discoverable (eg use `+RTS -s`, and it's in the nofib logs too, though I don't think `nofib-analyse` looks for it. (You could fix `nofib- analyse` so that it does.) The point is that reducing allocation is almost always good; and it is a FAR more repeatable number than runtime, for which it is hard to measure small differences. My bet is that `ordNub` will be a tiny win in most cases. The other thing is that while using `ordNub` may not benefit typical programs, it may have a dramatic effect on some weird program which happens to produce very long lists for `nub` to digest. Provided using `ordNub` doesn't slow things down for typical programs (use allocation numbers to check) I'm all for using it so that the edge cases don't fall off a cliff. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8173: GHC uses nub -------------------------------------------------+------------------------- Reporter: nh2 | Owner: Type: bug | leroux Priority: low | Status: new Component: Compiler | Milestone: Resolution: | Version: 7.6.3 Operating System: Unknown/Multiple | Keywords: Type of failure: Compile-time performance bug | Architecture: Test Case: | Unknown/Multiple Blocking: | Difficulty: | Unknown | Blocked By: | Related Tickets: -------------------------------------------------+------------------------- Changes (by leroux): * owner: => leroux -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8173#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler