<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>Graph::Easy - Manual - Benchmarks</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="MSSmartTagsPreventParsing" content="TRUE">
<meta http-equiv="imagetoolbar" content="no">
<link rel="stylesheet" type="text/css" href="../base.css">
<link rel="stylesheet" type="text/css" href="manual.css">
<link rel="Start" href="index.html">
<link href="http://bloodgate.com/mail.html" rev="made">
<!-- compliance patch for microsoft browsers -->
<!--[if lt IE 7]><script src="http://bloodgate.com/ie7/ie7-standard-p.js" type="text/javascript"></script><![endif]-->
</head>
<body bgcolor=white text=black>
<a name="top"></a>
<div class="menu">
<a class="menubck" href="index.html" title="Back to the index">Index</a>
<p style="height: 0.2em"> </p>
<a class="menuext" href="overview.html" title="How everything fits together">Overview</a>
<a class="menuext" href="layouter.html" title="How the layouter works">Layouter</a>
<a class="menuext" href="hinting.html" title="Generating specific layouts">Hinting</a>
<a class="menuext" href="output.html" title="Output formats and their limitations">Output</a>
<a class="menuext" href="syntax.html" title="Syntax rules for the text format">Syntax</a>
<a class="menuext" href="attributes.html" title="All possible attributes for graphs, nodes and edges">Attributes</a>
<a class="menucur" href="faq.html" title="Frequently Asked Questions and their answers">F.A.Q.</a>
<a class="menucin" href="benchmark.html" title="Benchmarks">Benchmarks</a>
<a class="menuind" href="#small" title="Startup overhead and simple graphs">Small</a>
<a class="menuind" href="#series" title="Series of graphs over versions and sizes">Series</a>
<a class="menuind" href="#large" title="Parsing and rendering large graphs">Parsing</a>
<a class="menuext" href="tutorial.html" title="Tutorial for often used graph types and designs">Tutorial</a>
</div>
<div class="right">
<h1>Graph::Easy - Manual</h1>
<h2>Benchmarks</h2>
<div class="text">
<p>
From version v0.25 onwards Graph::Easy no longer uses the
<a href="http://search.cpan.org/~jhi/Graph/">Graph</a> 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. <code>dot</code>.
</p>
<p>
Unless otherwise noted, the benchmarks were done on the following
system:
</p>
<table class="features">
<caption>System specs</caption>
<tr>
<th>CPU</th>
<td>
<pre class="table">
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 </pre></td>
</tr>
<tr>
<th>OS</th>
<td>SuSE 9.1</td>
</tr>
<tr>
<th>Kernel</th>
<td>2.6.5-7.201-default</td>
</tr>
<tr>
<th>gcc</th>
<td>3.3.3</td>
</tr>
<tr>
<th>Perl</th>
<td>This is perl, v5.8.6 built for i686-linux (32 bit)</td>
</tr>
<tr>
<th>Memory</th>
<td>
<pre class="table">
MemTotal: 1035680 kB
SwapTotal: 0 kB
SwapFree: 0 kB</pre></td>
</tr>
</table>
<a name="small">
<h3>Simple graph</h3>
</a>
<p>
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
<code>examples/as_ascii</code> and <code>dot</code>.
</p>
<pre class="graphtext">
graph { autolink: name; }
[ Bonn ] -> [ Berlin ]
</pre>
<pre class="graphtext">
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
}
</pre>
<div class="clear"></div>
<p>
Note that the graph contains two links for the nodes. By default,
<code>dot</code> 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.
<br>
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.
<br>
The current
<a href="http://www.wickle.com/wikis/index.php/Graphviz_extension">graphviz extension</a>
does run <code>dot</code> always twice, which is the slower way as
we will see below.
<br>
</p>
<p>
Here are the two command lines used to benchmark all variants.
The variant where <code>dot</code> 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".
</p>
<pre>
# 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
</pre>
<p>
In all cases, the lowest observed <code>real</code> 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
<code>dot</code>, the relative variance might be very big.
</p>
<table class="features">
<caption>Results for small graph</caption>
<tr>
<th>Program</th>
<th>Version</th>
<th>Time in s</th>
</tr>
<tr>
<td>Graph::Easy</td>
<td>v0.24</td>
<td>0.159</td>
</tr>
<tr>
<td>Graph::Easy</td>
<td>v0.29</td>
<td>0.086</td>
</tr>
<tr>
<td>Graph::Easy</td>
<td>v0.34</td>
<td>0.114</td>
</tr>
<tr>
<td>Graph::Easy</td>
<td>v0.38</td>
<td>0.160</td>
</tr>
<tr>
<td>Graph::Easy</td>
<td>v0.40</td>
<td>0.154</td>
</tr>
<tr class="odd">
<td>dot, png</td>
<td>v1.1</td>
<td>0.015</td>
</tr>
<tr class="odd">
<td>dot, map + png</td>
<td>v1.1</td>
<td>0.017</td>
</tr>
<tr class="odd">
<td>dot, map + dot png</td>
<td>v1.1</td>
<td>0.026</td>
</tr>
<tr class="even">
<td>dot, png</td>
<td>v2.6</td>
<td>0.090</td>
</tr>
<tr class="even">
<td>dot, map + png</td>
<td>v2.6</td>
<td>0.091</td>
</tr>
<tr class="even">
<td>dot, map + dot png</td>
<td>v2.6</td>
<td>0.171</td>
</tr>
</table>
<p>
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) <code>dot</code> - 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.
<br>
Also worth noting is that <code>dot</code> 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 <code>dot</code> twice is
slower than producing both results in one go (no wonder :)
<br>
V0.34 takes a bit longer, due to the increased code base. It is still faster
than v0.24 using Graph, though.
</p>
<p>
We also see that modern versions of <code>dot</code> take much longer, and
come very close to the time used by <code>Graph::Easy</code>. Who says
C is faster than Perl? :)
</p>
<p>
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!
</p>
<h4>Memory consumption</h4>
<p>
Also interesting is the memory consumption of the Perl process itself. This
was measured by running:
</p>
<pre>
perl -Ilib -MGraph::Easy -le 'sleep(100)'
</pre>
<p>
and then looking with <code>top</code> at the process size. While not 100%
accurate, it allows us to see trends. Here are the results on my system:
</p>
<table class="features">
<caption>Process size in Kb</caption>
<tr>
<th>Version:</th>
<th>Virtual</th><th>Resident</th><th>Shared</th>
</tr>
<tr>
<th class="l">v0.24</th>
<td>8244</td><td>5740</td><td>1456</td>
</tr>
<tr>
<th class="l">v0.25</th>
<td>5980</td><td>3452</td><td>1440</td>
</tr>
<tr>
<th class="l">v0.26</th>
<td>6240</td><td>3704</td><td>1440</td>
</tr>
<tr>
<th class="l">v0.27</th>
<td>6104</td><td>3592</td><td>1432</td>
</tr>
<tr>
<th class="l">v0.29</th>
<td>6108</td><td>3628</td><td>1436</td>
</tr>
<tr>
<th class="l">v0.30</th>
<td>6104</td><td>3644</td><td>1436</td>
</tr>
<tr>
<th class="l">v0.34</th>
<td>6368</td><td>3860</td><td>1436</td>
</tr>
<tr>
<th class="l">v0.40</th>
<td>6760</td><td>4196</td><td>1372</td>
</tr>
</table>
<p>
The table shows us a few things:
</p>
<ul>
<li>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 :)
<li>The increase from 0.25 to 0.26 is due to more features and code in Graph::Easy.
<li>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.
</ul>
<a name="series">
<h3>Creation and Dumping of big Graphs</h3>
</a>
<p>
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):
</p>
<pre>
+----+ +----+ +----+ +----+ +....+
| 2B | | 3B | | 4B | | 5B | : 6B :
+----+ +----+ +----+ +----+ +....+
^ ^ ^ ^ ^
| | | | :
| | | | :
+----+ +----+ +----+ +----+ +----+
| 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 | ..>
+----+ +----+ +----+ +----+ +----+
| | | | :
| | | | :
v v v v v
+----+ +----+ +----+ +----+ +....+
| 2A | | 3A | | 4A | | 5A | : 6A :
+----+ +----+ +----+ +----+ +....+
</pre>
<p>
So the resulting graph has N * 3 nodes and N * 3 edges, resulting
in N * 6 objects in total.
</p>
<p>
The script to run the benchmark can be found inside the
Graph::Easy package, or <a href="bench/serie.pl">locally</a>.
</p>
<table class="features">
<caption>Creation of Big Graphs</caption>
<tr>
<th>Graph::Easy v0.24</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0090</td>
<td>0.0510</td>
<td>0.1100</td>
<td>0.1816</td>
<td>0.3225</td>
<td>0.7452</td>
<td>1.4581</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0655</td>
<td>0.0726</td>
<td>0.3905</td>
<td>1.6635</td>
<td>7.6464</td>
<td>45.7824</td>
<td style="background: crimson">n/a</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0073</td>
<td>0.1160</td>
<td>0.7574</td>
<td>3.0330</td>
<td>14.0460</td>
<td>73.6218</td>
<td style="background: crimson">n/a</td>
</tr>
<tr>
<td>Memory</td>
<td>44106</td>
<td>81622</td>
<td>412087</td>
<td>934900</td>
<td>2334018</td>
<td>8898275</td>
<td>29546659</td>
</tr>
<tr>
<th>Graph::Easy v0.25</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0016</td>
<td>0.0031</td>
<td>0.0092</td>
<td>0.0517</td>
<td>0.0698</td>
<td>0.1268</td>
<td>0.2347</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0048</td>
<td>0.0060</td>
<td>0.0616</td>
<td>0.1004</td>
<td>0.1692</td>
<td>0.4278</td>
<td>0.8863</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0065</td>
<td>0.0582</td>
<td>0.1897</td>
<td>0.4048</td>
<td>1.0100</td>
<td>4.1961</td>
<td>14.0087</td>
</tr>
<tr>
<td>Memory</td>
<td>30294</td>
<td>63595</td>
<td>411382</td>
<td>1723768</td>
<td>7058119</td>
<td>36626130</td>
<td>163530013</td>
</tr>
<tr>
<th>Graph::Easy v0.27</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0017</td>
<td>0.0029</td>
<td>0.0395</td>
<td>0.0579</td>
<td>0.0904</td>
<td>0.1783</td>
<td>0.3836</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0053</td>
<td>0.0059</td>
<td>0.0584</td>
<td>0.0937</td>
<td>0.1639</td>
<td>0.3838</td>
<td>0.7867</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0051</td>
<td>0.0547</td>
<td>0.1562</td>
<td>0.3571</td>
<td>0.9905</td>
<td>4.4629</td>
<td>16.2674</td>
</tr>
<tr>
<td>Memory</td>
<td>27721</td>
<td>53295</td>
<td>308183</td>
<td>974750</td>
<td>3398114</td>
<td>16663158</td>
<td>69591398</td>
</tr>
<tr>
<th>Graph::Easy v0.30</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0017</td>
<td>0.0029</td>
<td>0.0101</td>
<td>0.0591</td>
<td>0.0881</td>
<td>0.1755</td>
<td>0.3778</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0055</td>
<td>0.0062</td>
<td>0.0611</td>
<td>0.0962</td>
<td>0.1685</td>
<td>0.3889</td>
<td>0.8188</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0053</td>
<td>0.0596</td>
<td>0.1872</td>
<td>0.4094</td>
<td>1.0915</td>
<td>4.7288</td>
<td>16.8745</td>
</tr>
<tr>
<td>Memory</td>
<td>25868</td>
<td>49642</td>
<td>290130</td>
<td>938697</td>
<td>3326061</td>
<td>16483105</td>
<td>69231345</td>
</tr>
<tr>
<th>Graph::Easy v0.34</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0026</td>
<td>0.0050</td>
<td>0.0184</td>
<td>0.1082</td>
<td>0.1730</td>
<td>0.3477</td>
<td>0.7107</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0057</td>
<td>0.0066</td>
<td>0.0587</td>
<td>0.0983</td>
<td>0.1795</td>
<td>0.4267</td>
<td>0.8927</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0076</td>
<td>0.0682</td>
<td>0.2395</td>
<td>0.4778</td>
<td>0.9776</td>
<td>2.7422</td>
<td>7.2366</td>
</tr>
<tr>
<td>Memory</td>
<td>24527</td>
<td>48259</td>
<td>293486</td>
<td>1036800</td>
<td>3883069</td>
<td>19678914</td>
<td>84634059</td>
</tr>
<tr>
<th>Graph::Easy v0.39</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0018</td>
<td>0.0032</td>
<td>0.0384</td>
<td>0.0573</td>
<td>0.0920</td>
<td>0.1839</td>
<td>0.3894</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0074</td>
<td>0.0066</td>
<td>0.0631</td>
<td>0.0977</td>
<td>0.1804</td>
<td>0.4227</td>
<td>0.8897</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0077</td>
<td>0.0763</td>
<td>0.2600</td>
<td>0.5194</td>
<td>1.0608</td>
<td>2.9838</td>
<td>7.6551</td>
</tr>
<tr>
<td>Memory</td>
<td>24630</td>
<td>48362</td>
<td>293589</td>
<td>1036903</td>
<td>3883172</td>
<td>19679017</td>
<td>84634162</td>
</tr>
<tr>
<th>Graph::Easy v0.40</th>
<th>5</th>
<th>10</th>
<th>50</th>
<th>100</th>
<th>200</th>
<th>500</th>
<th>1000</th>
</tr>
<tr>
<td>Creation</td>
<td>0.0019</td>
<td>0.0032</td>
<td>0.0421</td>
<td>0.0610</td>
<td>0.0901</td>
<td>0.1455</td>
<td>0.3655</td>
</tr>
<tr>
<td>as_txt</td>
<td>0.0061</td>
<td>0.0067</td>
<td>0.0647</td>
<td>0.1010</td>
<td>0.1738</td>
<td>0.3943</td>
<td>0.9027</td>
</tr>
<tr>
<td>as_ascii</td>
<td>0.0081</td>
<td>0.0812</td>
<td>0.2725</td>
<td>0.5396</td>
<td>1.1676</td>
<td>3.1486</td>
<td>8.5641</td>
</tr>
<tr>
<td>Memory</td>
<td>24093</td>
<td>46985</td>
<td>285492</td>
<td>1020406</td>
<td>3849875</td>
<td>19595320</td>
<td>84466465</td>
</tr>
</table>
<p style="margin-left: 1em; font-size: 0.7em;">
Times are in seconds, memory in bytes. The numbers at top are N, the resulting
graph has N*3 nodes and N*3 edges.
</p>
<p>
There are a few interesting things to note here:
</p>
<ul>
<li>
The first is that
<code>as_txt</code> was a quadratic operation when using Graph (0.24),
and is now a linear operation (0.25 onwards). Since <code>as_txt()</code>
is just a dump and processes each node/edge exactly once, this means
that a layout (like <code>as_ascii()/as_html()</code> 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.
<br>
Note that the time for a 6000-object graph is missing for 0.24, it
would several minutes to complete <code>as_txt()</code> and even
longer for <code>as_ascii()</code>. If you double
the number of nodes/edges, it takes approximately 5 times
as long. Uh. This scaled very badly.
<li>
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
<code>Graph</code> to create an internal representation of the graph, and
to connect it via edge and node attributes to the objects from Graph::Easy.
<br>
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.
<br>
In praxis, without parsing, <code>Graph</code> 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.
</li>
<li>
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.
<br>
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.
</li>
<li>
v0.34 is much faster in creating the <code>as_ascii()</code> version. This
is mainly due to the rewritten chain tracking code and some
streamlining. Note that v0.33 and earlier took about <b>3.5 times</b> as long
for <code>as_ascii()</code> 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).
</li>
<li>
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.
</li>
</ul>
<a name="large">
<h3>Parsing and Rendering</h3>
</a>
<p>
<font color="red">Not done yet.</font>
</p>
<h3>Contact and Bugreports</h3>
<p>
If you have questions, feel free to send me an <a href="mailto:nospam-abuse@bloodgate.com">email</a>
<small>(<a href="/tels.asc">Gnupg key</a>)</small>.
<b>Bugreports</b> should go to <a href="http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Graph-Easy">rt.cpan.org</a>.
</p>
</div>
<div class="footer">
Page created <span class="date">2005-09-02</span> by <a href="http://bloodgate.com/mail.html">Tels</a>. Last update: <span class="date">2006-01-01</span>
</div>
</div> <!-- end of right cell -->
</body>
</html>