GHC: Ticket Query
http://ghc.haskell.org/trac/ghc/query?status=!closed&reporter=rrnewton&order=priority
The Glasgow Haskell Compileren-USGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/query?status=!closed&reporter=rrnewton&order=priority
Trac 1.0.1
http://ghc.haskell.org/trac/ghc/ticket/8224
http://ghc.haskell.org/trac/ghc/ticket/8224#8224: Excessive system time -- new IO manager problem?Wed, 04 Sep 2013 15:40:34 GMTrrnewton<p>
This is an issue that came to light when testing the patches on <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/910" title="feature request: --make should have a -j flag for parallel building (closed: fixed)">#910</a>. You can see some of the numbers there. Basically, recent GHC HEAD builds, running a large number of threads blocked on MVars will result in burning a lot of system time.
</p>
<p>
The attached file provides a mediocre reproducer. With it, you can see that building with HEAD as of Aug 31st and running with <tt>-RTS -N32</tt> will result in around 200ms system time, whereas GHC 7.6.3 spends about 30ms in system time. This shows the disparity, but the result is not that egregious.
</p>
<p>
A more noticeable example is on ticket <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/910" title="feature request: --make should have a -j flag for parallel building (closed: fixed)">#910</a>, where when running on 31 threads, there is an 8 minutes of system time for 17 minutes of user time, and yet at one thread that system time drops to under two seconds!
</p>
<pre class="wiki"> 1 thread: real 1m20.028s user 1m17.921s sys 0m1.768s
31 threads: real 1m27.445s user 17m0.314s sys 8m0.175s
</pre><p>
It needs to be determined whether this system time is a result of the parallel compilation patches on <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/910" title="feature request: --make should have a -j flag for parallel building (closed: fixed)">#910</a>, or whether it is a new problem with the runtime system, and in particular with the parallel IO manager. I am inclined to believe that compiling in parallel involves extra IO (repeatedly reading interface files?), but not eight minutes of it!!
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/8224#changelog
http://ghc.haskell.org/trac/ghc/ticket/5278
http://ghc.haskell.org/trac/ghc/ticket/5278#5278: System.Random.randomIvalInteger makes invalid assumptions about RandomGenMon, 27 Jun 2011 01:46:31 GMTrrnewton<p>
The existing API for <tt>System.Random.RandomGen</tt> allows a random number generator (RNG) to produce Ints within an arbitrary range specified by <tt>genRange</tt>.
</p>
<p>
For example, the following <tt>RandomGen</tt> produces only zeros and ones, but should be legitimate:
</p>
<pre class="wiki">import System.Random
data BinRNG = BinRNG StdGen
instance RandomGen BinRNG where
next (BinRNG g) = (x `mod` 2, BinRNG g')
where (x,g') = next g
split (BinRNG g) = (BinRNG g1, BinRNG g2)
where (g1,g2) = split g
genRange _ = (0,1)
ls :: [Int]
ls = randoms (BinRNG$ mkStdGen 38388)
main = print $ take 20 ls
</pre><p>
But <tt>System.Random.randomIvalInteger</tt> makes invalid assumptions about the amount of randomness produced by <tt>next</tt>. (Specifically, assuming that it creates the same amount as <tt>StdGen</tt>.) Thus, the above program will create an output with only a couple of unique ints (rather than 2<sup>64).
</sup></p>
<p>
For example:
</p>
<pre class="wiki">[4611734781337924537,4611734781337924537,-9223323645458902796,
-9223323645458902797,4611734783485408099,4611734783485408098,
-9223323645458902796,-9223323647606386357,4611734781337924538,
-9223323645458902796,-9223323645458902797,
-9223323647606386357,4611734783485408098,4611734783485408098,
-9223323647606386357,4611734781337924538,4611734781337924537,
-9223323645458902796,4611734783485408099,4611734781337924538]
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/5278#changelog
http://ghc.haskell.org/trac/ghc/ticket/5280
http://ghc.haskell.org/trac/ghc/ticket/5280#5280: System.Random commits (rand `mod` base) error.Mon, 27 Jun 2011 02:41:22 GMTrrnewton<p>
You have probably at some point come across the C code "<tt>rand() % base</tt>"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine <tt>rand()</tt> producing numbers in say <tt>[0,15)</tt> and base being <tt>10</tt>.
</p>
<p>
In the function <tt>System.Random.randomIvalInteger</tt> you can see the same thing happening.
</p>
<p>
The only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.
</p>
<p>
This strategy appears to be used by GMP's mpz_urandomm function:
</p>
<blockquote>
<p>
<a class="ext-link" href="http://gmplib.org/manual/Integer-Random-Numbers.html#Integer-Random-Numbers"><span class="icon"></span>http://gmplib.org/manual/Integer-Random-Numbers.html#Integer-Random-Numbers</a>
</p>
</blockquote>
<p>
The file <tt>urandomm.c</tt> has the code.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5280#changelog