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

11 May 2011

      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  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

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

Daniel Fischer