[Haskell-beginners] Printing the entries of a Data.Map m

[Daniel Fischer]

On Sunday 15 May 2011 11:34:33, Matthias Guedemann wrote:
> Hi Manfred
> 
> > It didn't make much of a difference in runtime doing it without
> > toList. I'm not quite sure if it is really more efficient or not.
> > Perhaps I would have to create dictonary with some millions entries
> > in order to see a noticable difference?
> 
> Probably, Haskell is not very deterministic for memory / runtime
> forecasts :-)
> 
> In theory there should be no difference in complexity, both need one
> sweep over all entries of the Map. There could perhaps be a constant
> cost for constructing the list.

The call-tree for the list construction is similar to the call-tree that 
traverse builds.
However, traverse assembles a new Map. While it's trivial to discard 
consumed list-cells (if the list is consumed sequentially), that is not so 
for Maps. Unless the compiler manages to completely eliminate the new Map, 
that is going to cost considerably more than the throwaway list-cells.

> Nevertheless, laziness should make it
> possible to run in constant space, as neither the list, nor the
> transformed Map is used.

Well, you need the space for the initial Map, that is O(size).
I assume you mean that the additional memory needed is O(1).
That is almost true for going through the list, since that is swiftly 
collected. The call-tree to get at the elements, however, is O(log size), 
but that's practically constant size.
For traverse, that is only true if the new Map is completely discarded 
(Maps are spine-strict, so if it's not completely ignored, its full spine 
is built, requiring O(size) space).

> So differences are probably small.
> 
> But is possible, take some measurements and report, not just runtime,
> but also heap space usage.

Note that the "mapM_ print . toAscList" prints the (key, value) pairs while 
the traverse (or Data.Traversable.mapM) only prints the values. That makes 
a difference.

I put together a small (trivial) test:

viaList :: (Ord k, Show k, Show v) => Map k v -> IO ()
viaList = mapM_ print . toAscList

-- and the same using elems instead of toAscList to only print the values

perTraverse :: (Ord k, Show v) => Map k v -> IO ()
perTraverse mp = traverse print mp >> return ()

main :: IO ()
main = do
    args <- getArgs
    let sz = case args of
                (a:_) -> read a
                _ -> 100000
        mp :: Map Int Int
        mp = fromDistinctAscList [(i,2*i+1) | i <- [0 .. sz]]
    print $ size mp   -- force the spine
    perTraverse mp   -- or via list (pairs/values only)

Everything compiled with -O2 (output redirected to /dev/null), the results 
for input 1000000 are:

./useElems 1000000 +RTS -s 
   1,026,031,460 bytes allocated in the heap
     247,759,432 bytes copied during GC
      40,026,204 bytes maximum residency (8 sample(s))
         353,148 bytes maximum slop
             103 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  1869 collections,     0 parallel,  0.53s,  0.53s elapsed
  Generation 1:     8 collections,     0 parallel,  0.48s,  0.49s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.54s  (  1.55s elapsed)
  GC    time    1.01s  (  1.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.56s  (  2.56s elapsed)

  %GC time      39.6%  (39.7% elapsed)

  Alloc rate    664,729,202 bytes per MUT second

  Productivity  60.3% of total user, 60.1% of total elapsed
----------------------------------------
./useAscList 1000000 +RTS -s 
   1,337,743,996 bytes allocated in the heap
     247,972,620 bytes copied during GC
      40,026,204 bytes maximum residency (8 sample(s))
         413,304 bytes maximum slop
             103 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  2467 collections,     0 parallel,  0.53s,  0.53s elapsed
  Generation 1:     8 collections,     0 parallel,  0.45s,  0.45s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    2.23s  (  2.23s elapsed)
  GC    time    0.98s  (  0.99s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.22s  (  3.22s elapsed)

  %GC time      30.6%  (30.7% elapsed)

  Alloc rate    599,228,735 bytes per MUT second

  Productivity  69.3% of total user, 69.3% of total elapsed
----------------------------------------
./useTraverse 1000000 +RTS -s 
   1,266,460,972 bytes allocated in the heap
     568,553,592 bytes copied during GC
      61,013,024 bytes maximum residency (10 sample(s))
         614,608 bytes maximum slop
             159 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  2328 collections,     0 parallel,  1.32s,  1.32s elapsed
  Generation 1:    10 collections,     0 parallel,  1.18s,  1.18s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.82s  (  1.83s elapsed)
  GC    time    2.50s  (  2.50s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    4.32s  (  4.33s elapsed)

  %GC time      57.8%  (57.8% elapsed)

  Alloc rate    695,540,479 bytes per MUT second

  Productivity  42.1% of total user, 42.0% of total elapsed
----------------------------------------

Data.Traversable.traverse uses more memory. Not twice as much, since the 
original Map is disassembled while traversing it. If I force the original 
Map to stay intact, it's about twice.
I conclude that the new Map assembled by traverse is not discarded.
So, overall, going through the list is better.

Cheers,
Daniel