Glasgow-haskell-users

Download

glasgow-haskell-users@haskell.org

March 2008

48 participants
42 discussions

static constants -- ideas?
by Jason Dusek 03 Mar '08

03 Mar '08

I have an awkward programming problem -- I need to take a dictionary, parse it, build a bunch of intermediate lists and then make maps and tries out of the list. A "programming problem" because it's taken me a fair amount of effort to pull together the parser and list generator -- and "awkward" because a 69000 item list, [(String, [(String, String)])], does not compile under GHC (stack overflow). (It's not likely to compile under anything else, either!) Members of #haskell have urged me to load the offending material from a file; indeed, it only takes ten seconds to parse the dictionary and build the lists, sort them and dump them back out again -- but it offends my sensibilities. I don't want to wait ten seconds to load my dictionary every time. I could use the FFI, then I can make the trie and lists all in C. That'd work great. My list likely uses too much RAM now, anyways. I'm considering one other option though -- I wonder if I can build large constants in GHC Core? If anybody has tried it -- or found some other way to make big huge constants in Haskell -- I would sure like to know about it. On another note, I am extremely curious about the difference between statically compiling a list and building it at runtime. I find it hard to wrap my head around the fact that I can build the list at runtime in a short time, but can not compile it without eating all of my machine's RAM. Is it due to laziness, maybe? Well, no -- because I subject the whole list to a sort. It's not just streaming records in from one IO handle and out another. -- _jsn

6 20

GHC code generation micro-optimisation patch
by Remi Turk 03 Mar '08

03 Mar '08

Hi, during the past semester I followed a seminar on the "Efficient implementation of functional languages" by Jeroen Fokker at the University Utrecht. During that course we worked on a feedback directed GHC optimisation, but that got me interested in another possible GHC backend micro-optimisation: The short story is this: An 8 line patch to GHC, tested with ghc 6.8.2 on nofib, ignoring all results with a < 0.5s runtime, yields an average runtime and compile time improvement of about 0.6%. The worst nofib slowdown is 5%, and the best speedup 8% Whether this is acceptable/enough for inclusion, is of course not up to me. The long story is that in compiler/codeGen/CgUtils.hs:mk_switch, an extra case is added to detect and treat specially the case analysis of 2 constructor datatypes.[1] Previously, case analysis of 2 constructor data types looked as follows in C--: _tmp = R1 & 3; if (_tmp >= 2) goto snd_con_lbl; With this patch, it generates the following: if (R1 & 2 != 0) goto snd_con_lbl; At least on x86 machines, the resulting assembly is more interesting. The original: movl %esi,%eax andl $3,%eax cmpl $2,%eax jae .snd_con_lbl After the patch: testl $2,%esi jne .snd_con_lbl The following table contains a summary of the nofib results: Machine Athlon32* Athlon64* Pentium4 Pentium4-dual PentiumD --------------------------------------------------------------------------------------- Vendor AMD AMD Intel Intel Intel Word size 32 64 32** 32** 32** OS Linux Linux Linux Linux Linux # CPU's 1 2 1 2 2 Mhz 950 2600 2800 2800 3000 L1 code/uops (Kb) 64 64 12 12 12 L1 data (Kb) 64 64 8 8 16 L2 (Kb) 256 1024 512 512 2048 -1 s.d. runtime (%) -1.4 -1.2 -2.4 -2.2 -5.1 +1 s.d. runtime (%) +1.1 +0.4 +1.5 +2.1 +1.3 Avg runtime (%) -0.2 -0.4 -0.4 -0.1 -1.9 Worst runtime (%) +2.5 +1.0 +3.1 +2.5 +5.0 Worst program cacheprof power simple wheel-sieve-1 integrate Best runtime (%) -5.1 -2.9 -5.0 -5.5 -8.1 Best program parstof hidden para life cryptarithm1 -1 s.d. mutator (%) -1.5 -1.6 -3.0 -3.0 -4.8 +1 s.d. mutator (%) +1.1 +0.8 +1.5 +2.2 +1.8 Avg mutator (%) -0.2 -0.4 -0.8 -0.5 -1.6 Avg bin size (%) -0.1 -0.2 -0.1 -0.1 -0.1 Avg mod size (%) -0.3 -0.5 -0.3 -0.3 -0.3 Avg comp time (%) -0.6 -0.7 -1.1 -0.6 -0.2 --------------------------------------------------------------------------------------- Cachegrind results -1 s.d. runtime (%) -2.0 -2.4 -3.2 -3.8 -3.3 +1 s.d. runtime (%) +0.5 +0.8 +1.2 +1.7 +0.6 Avg runtime (%) -0.7 -0.8 -1.0 -1.1 -1.3 -1 s.d. instr. (%) -4.2 -4.1 -4.3 -4.4 -4.4 +1 s.d. instr. (%) -0.6 -0.5 -0.6 -0.7 -0.7 Avg instr (%) -2.4 -2.3 -2.5 -2.5 -2.5 -1 s.d. cache misses (%) -0.6 -1.8 -0.4 -2.0 -2.8 +1 s.d. cache misses (%) +0.7 +2.2*** +0.7 +0.9 +1.1 Avg cache misses (%) +0.0 +0.2 +0.1 -0.6 -0.9 Avg comp time (%) -0.6 +0.3 -0.7 -0.4 -0.1 * On all Athlon results, but not on those of the Pentiums, nofib-analyse gave lots of "spurious result" warnings. On the Athlon32, nofib even failed with "output does not match" errors, which I could not verify when running diff on the output manually. I "fixed" the first problem by ignoring it and the second one by changing runstdtest to pretend the actual output always matches the expected output. ** CPU may actually be 64bits, but all software (including kernel) is 32bits *** cacheprof here has a whopping 21.0% more cache misses. The second biggest increase is 1.0% The attached patch is against 6.8.2, but currently applies without problem against the HEAD. The full nofib results can be found at http://www.students.cs.uu.nl/~rturk/fast2case-nofib-results/ The normal runs were done with NoFibRuns = 5, and for the cachegrind runs it was set to 2. On most machines I ran nofib multiple times and, both for normal and for "fast2case", took the fastest run. Thanks to Jeroen Fokker for giving the seminar that made me think of this in the first place, to Mark Stobbe and Eelco Lempsink for being great guys to work with during the seminar, and to Alexey Rodriguez for helping me keep my sanity in the midst of weird cache- and pipeline effects. And finally to the University Utrecht and Chris Regenboog for enabling me to run nofib on more computers than only my own poor old 950Mhz machine. Groeten, Remi [1] Technically, it will work for 4 constructor datatypes on 64 bit architectures too, but who cares.

2 1