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

Discussion in 'C++' started by Bill Cox, Jun 10, 2008.

  1. Bill Cox

    Bill Cox Guest

    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/svnroot/datadraw/trunk
    datadraw

    Best regards,
    Bill
     
    Bill Cox, Jun 10, 2008
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Aquila Deus

    Re: Where OSS beats CSS

    Aquila Deus, Oct 8, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    395
    Aquila Deus
    Nov 5, 2004
  2. John Bailo

    Java beats them all

    John Bailo, Nov 26, 2004, in forum: Java
    Replies:
    5
    Views:
    408
    Jeff_Relf
    Nov 27, 2004
  3. Glen Low
    Replies:
    0
    Views:
    349
    Glen Low
    Feb 14, 2005
  4. George Young
    Replies:
    7
    Views:
    271
    David Isaac
    Oct 4, 2006
  5. Bill Cox
    Replies:
    0
    Views:
    360
    Bill Cox
    Jun 10, 2008
Loading...

Share This Page