[Haskell-cafe] need help on building a huge graph

[Daniel Fischer]

On Wednesday 11 May 2011 09:25:05, Bin Jin wrote:
> sorry, it's 15 seconds. It's a typo

It's less for me, something like 5.8s compiled without optimisations, 3.6s 
with -O2 (Pentium4, 3.06GHz).
The overwhelming part of that is spent in GC:

  MUT   time    0.69s  (  0.73s elapsed)
  GC    time    5.07s  (  5.10s elapsed)

resp.

  MUT   time    0.20s  (  0.20s elapsed)
  GC    time    3.36s  (  3.38s elapsed)

From now on, everything is compiled with -O2.
Giving type signatures that force things to Int (without any type 
signatures beyond the one given, you have

graph :: Array Integer [(Integer,Int)]
edges :: [(Integer,(Integer,Int))]
etc.

), that goes down to

  MUT   time    0.12s  (  0.11s elapsed)
  GC    time    3.10s  (  3.10s elapsed)

A nice relative improvement for the productive work, but since that is 
almost negligible compared to GC anyway, it doesn't make a big difference 
altogether.

You can shave a large slice off the GC if you construct the second 
component pairs in edges directly, at the moment you construct one (x,y) 
pair, then deconstruct it to build a (y,1-x) pair; building the latter 
directly reduces allocation and GC significantly:

     137,930,992 bytes allocated in the heap
     429,681,256 bytes copied during GC
  MUT   time    0.07s  (  0.07s elapsed)
  GC    time    1.20s  (  1.20s elapsed)

Then using a stricter accumulation function,

upd :: [(Int,Int)] -> (Int,Int) -> [(Int,Int)]
upd xs p@(x,y) = x `seq` y `seq` (p:xs)

instead of (flip (:)) forces some more thunks and further reduces 
allocation and GC (but not very much):

      98,845,888 bytes allocated in the heap
     350,740,560 bytes copied during GC
  MUT   time    0.07s  (  0.07s elapsed)
  GC    time    1.06s  (  1.06s elapsed)

Much better than before, but still way too much GC. Reducing GC by 
specifying a larger allocation area helps:

-A32M:
  MUT   time    0.10s  (  0.10s elapsed)
  GC    time    0.40s  (  0.40s elapsed)

-A64M:
  MUT   time    0.14s  (  0.14s elapsed)
  GC    time    0.29s  (  0.29s elapsed)

-A128M:
  MUT   time    0.17s  (  0.17s elapsed)
  GC    time    0.00s  (  0.00s elapsed)

> 
> On Wed, May 11, 2011 at 3:20 PM, Bin Jin <bjin1990 at gmail.com> wrote:
> > Hi, cafe
> > 
> > I'm recently solving some algorithm puzzles from previous Google Code
> > Jam rounds, and today I met some problem I can't solve now.
> > It's a problem (Round 3 2010, B) that the solution require to find a
> > shortest path in a graph with about 100,000 vertices
> > and 50 edges from each vertex.  Apart from find shortest path, I find
> > that building graph also takes a lot of time.
> > Yes, I know it's unnecessary to dump the entire graph to the memory,
> > but I want to know if it's possible to build such graph in some
> > reasonable time.
> > 
> > following is a snippet of code building the graph, runs about 15 mins
> > on Core 2 Duo 2.40GHz without any RTS flags
> > 
> >> > import Data.Array
> >> > 
> >> > main = graph `seq` putStrLn "Finished"
> >> > 
> >> > n = 100000
> >> > bnds = (0, n-1)
> >> > 
> >> > buildGraph bnds edges = accumArray (flip (:)) [] bnds edges
> >> > 
> >> > graph = buildGraph bnds edges
> >> > 
> >> > edges = [ (i, (y, 1 - x::Int))
> >> > 
> >> >         | i <- range bnds
> >> >         
> >> >         , j <- [2..50]
> >> >         , let (x, y) = if i + j >= n then (1, i + j - n) else (0, i
> >> >         + j) ]
> > 
> > Regards,
> > Bin Jin