Graph::Easy - Manual

From version v0.25 onwards Graph::Easy no longer uses the Graph module. This page explains why and also documents time and memory benchmarks across different software versions and graph sizes. It also compares the performance of Graph::Easy vs. dot.

Unless otherwise noted, the benchmarks were done on the following system:

processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 8
model name      : AMD Athlon(tm) XP 2400+
stepping        : 1
cpu MHz         : 2010.963
cache size      : 256 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 sep mtrr
                  pge mca cmov pat pse36 mmx fxsr sse syscall
                  mmxext 3dnowext 3dnow
bogomips        : 3964.92 

MemTotal:      1035680 kB
SwapTotal:           0 kB
SwapFree:            0 kB

In the first example we try to measure the overhead of loading the program. We do render a very small graph, consisting of only two nodes, connected by one edge. Shown below is the input to examples/as_ascii and dot.

graph { autolink: name; }
[ Bonn ] -> [ Berlin ]

digraph GRAPH_0 {

  // Generated by Graph::Easy 0.29 at Fri Sep  9 23:14:05 2005

  edge [ arrowhead=open ];
  graph [ rankdir=LR ];
  node [
    fontsize=11,
    fillcolor=white,
    style=filled,
    shape=box ];

  Berlin [ URL="/wiki/index.php/Berlin" ]
  Bonn [ URL="/wiki/index.php/Bonn" ]

  Bonn -> Berlin

}

Note that the graph contains two links for the nodes. By default, dot would only produce a PNG image, so we also need to call it so that it constructs an image map which can be used to link the individual nodes to their targets.
Since the extension responsible for converting the graph input to the appropriate image+map does not know whether there are links or not, it will typically try to create the image map all the time. There are two ways this can be done, either by calling dot twice with the same input, and different output formats, or by asking dot for both at the same time, storing the image in a file and receiving the image map on STDOUT.
The current graphviz extension does run dot always twice, which is the slower way as we will see below.

Here are the two command lines used to benchmark all variants. The variant where dot produces only the image is included just for comparisation and labeled "dot, png". The variant that calls dot twice is labeled "dot, map + dot, png", and the variant that chains both calls together is labeled "dot, map + png".

# dot producing image alone (dot, png)
time dot -Tpng -otest.png test.dot

# dot producing image and map (dot, map + dot, png)
time dot -Tpng -otest.png test.dot
time dot -Tcmapx -otest.map test.dot

# dot producing image and map in one go (dot, map + png)
time dot -Tpng -otest.png -Tcmapx test.dot

# Graph::Easy
time perl -Ilib examples/as_html test.txt

In all cases, the lowest observed real time was noted, based on the idea that any higher time represents background noise from the system. Typically, the times do not vary more than a few ms between runs, anyway. Although with small times like seen from dot, the relative variance might be very big.

As can be seen from the table above, the startup time for Graph::Easy is much higher than the one from the old (v1.1) dot - but it got much lower from v0.25 onwards, and the sole reason for that is that Graph::Easy no longer loads the really huge Graph module. Below we will examine this in detail.
Also worth noting is that dot alone is the fastest, however it will not produce the desired result. Generating the image map takes some additional time, albeit only a little bit. Running dot twice is slower than producing both results in one go (no wonder :)
V0.34 takes a bit longer, due to the increased code base. It is still faster than v0.24 using Graph, though.

We also see that modern versions of dot take much longer, and come very close to the time used by Graph::Easy. Who says C is faster than Perl? :)

The timing above shows that the startup cost for Graph::Easy is high, and since for each graph rendered the startup occurs again, a way to reduce this cost must be found. One such way would be to write a deamon using Net::Server. This deamon would listen on a network port, take the the graph text as input and return the graph output. Thus the modules would be sitting in memory and not be needed to be loaded and compiled each time you want to render a graph. This might bring the per-graph time for small graphs even below the time from graphviz/dot!

Memory consumption

Also interesting is the memory consumption of the Perl process itself. This was measured by running:

perl -Ilib -MGraph::Easy -le 'sleep(100)'

and then looking with top at the process size. While not 100% accurate, it allows us to see trends. Here are the results on my system:

The table shows us a few things:

• The large drop from 0.24 to 0.25 is due to the elimination of loading Graph. Despite the fact that Graph::Easy needs now a bit of code to emulate a few basic features of Graph it self, the memory base line dropped quit a bit. Graph is a module with many bells and whistles, spread over dozends source code files. Graph::Easy, on the other hand, only needs very few features and these are implemented in about 20 lines of Perl. So removing Graph not only reduces the initial loading time, but also the memory consumption. So far, so good :)
• The increase from 0.25 to 0.26 is due to more features and code in Graph::Easy.
• The decrease from 0.26 to 0.27 is due to not loading Heap, and using Heap::Binary instead of Heap::Fibonacci for A* pathfinding. Heap::Binary is faster, and smaller. In addition, the node cluster management was simplified, removing about 3% of code from Graph::Easy.

In this test we create a series of graphs, with an increasing number of nodes and edges. The graph looks like this, continued to the right until N is met (the dotted nodes and edge indicate the continuation of the series):

 +----+     +----+     +----+     +----+     +....+
 | 2B |     | 3B |     | 4B |     | 5B |     : 6B :
 +----+     +----+     +----+     +----+     +....+
   ^          ^          ^          ^          ^
   |          |          |          |          :
   |          |          |          |          :
 +----+     +----+     +----+     +----+     +----+     
 | 1  | --> | 2  | --> | 3  | --> | 4  | --> | 5  | ..> 
 +----+     +----+     +----+     +----+     +----+     
   |          |          |          |          :
   |          |          |          |          :
   v          v          v          v          v
 +----+     +----+     +----+     +----+     +....+
 | 2A |     | 3A |     | 4A |     | 5A |     : 6A :
 +----+     +----+     +----+     +----+     +....+

So the resulting graph has N * 3 nodes and N * 3 edges, resulting in N * 6 objects in total.

The script to run the benchmark can be found inside the Graph::Easy package, or locally.

Times are in seconds, memory in bytes. The numbers at top are N, the resulting graph has N*3 nodes and N*3 edges.

There are a few interesting things to note here:

• The first is that as_txt was a quadratic operation when using Graph (0.24), and is now a linear operation (0.25 onwards). Since as_txt() is just a dump and processes each node/edge exactly once, this means that a layout (like as_ascii()/as_html() etc) has exactly the same properties, and will be even slower since it needs to do some more work, processing nodes/edges more than once.
  Note that the time for a 6000-object graph is missing for 0.24, it would several minutes to complete as_txt() and even longer for as_ascii(). If you double the number of nodes/edges, it takes approximately 5 times as long. Uh. This scaled very badly.
• There are basically three times involved to create a graph. The first is to parse the graph description. This time is absent in this test because we constructed the graph via Perl code, not via Graph::Easy::Parser. The second part is to create the node and edge objects (Graph::Easy::Node and Graph::Easy::Edge) itself. The third time was the time taken by Graph to create an internal representation of the graph, and to connect it via edge and node attributes to the objects from Graph::Easy.
  My naive idea was that the object creation took most of the time (afterall, it is heavy OO Perl code :), followed by parsing and Graph comes in with the smallest overhead.
  In praxis, without parsing, Graph took about 3/4 of all the time, and object creation only about 1/4. The effect is that after 0.24, creating a graph via Perl code is between 3 and 4 times faster, because storing nodes/edges simply as keys in two hashes if much faster than whatever Graph does. As shown previously, retrieving them is also much faster and scales much, much better.
• Removing Graph means we no longer need to store nodes/edges inside a Graph object. This removes a bit of memory overhead. While I thought this would be only a very small amount, it turned out that in praxis about 30% of all the memory was wasted inside the structures Graph created and only 60% was used by Graph::Easy itself.
  In 0.27, the memory was reduced again by about 10% due to not initializing unneeded fields inside nodes and edges, like the error field, etc. That also makes graph creation about 10% faster, too.
• v0.34 is much faster in creating the as_ascii() version. This is mainly due to the rewritten chain tracking code and some streamlining. Note that v0.33 and earlier took about 3.5 times as long for as_ascii() if you doubled the number of objects - v0.34 only takes about twice as long. So it dropped from about O(N*N) to O(N).
• The memory shown is bogus (I used Devel::Size 0.64 instead of Devel::Size 0.58), and way too big. For instance, for 0.40, top says "virtual: 27348 resident: 23m shared: 1504" (in KByte), while Devel::Size claims that 0.40 uses around 84 Megabytes.

Not done yet.

Contact and Bugreports

If you have questions, feel free to send me an email (Gnupg key). Bugreports should go to rt.cpan.org.