468,247 Members | 1,317 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,247 developers. It's quick & easy.

C/DataDraw beats C++/STL on EDA-like benchmarks

Hi, all.

I've recently benchmarked DataDraw (datadraw.sf.net) graph databases
vs
GNU C++ graphs built using STL lists. Large graphs (4 million nodes)
were built in the shape of a mesh. Then, simple depth first
traversals
were performed starting from a corner, a hundred times.

The C/DataDraw based implementation ran 15X faster than the C++/STL
version, while using less than half the memory.

The performance difference is due mostly to cache-optimized memory
organization, which gave the DataDraw version a 16.7X lower L2 cache
miss rate, according to cachegrind. I estimate the DataDraw version
achieved around 30X higher useful information density in the cache.
This is due to several factors, which are roughly:

Keeping like data fields together, rather than object fields: 4X
Using a memory pool per field, rather than a global pool: 2X
Using 32-bit object references rather than 64-bit pointers: 2X
Embedding next pointers in edges rather than allocating link object:
2X

The benchmarks can be found in the expamples/graph_benchmark directory
of the source code, which can be checked out with:

svn co https://datadraw.svn.sourceforge.net...datadraw/trunk
datadraw

Best regards,
Bill
Jun 27 '08 #1
0 823

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by vsapre80 | last post: by
reply views Thread by Cindi Jenkins | last post: by
7 posts views Thread by KantKwitDansin1 | last post: by
13 posts views Thread by Dave | last post: by
6 posts views Thread by NickName | last post: by
7 posts views Thread by George Young | last post: by
reply views Thread by kermitthefrogpy | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.