Friday, January 27, 2012

Performance comparison among std::map, boost::unordered_map and TRIE data structure

We have implemented our own map with TRIE data structure and compared its performance with STL map and boost unordered_map, which is a hash map.
TRIE Data Structure

To know more about TRIE data structure, please go to wikipedia page: http://en.wikipedia.org/wiki/Trie

  • Without Compiler Optimization and Total 10K random strings:

TRIE MAP: 83170
INT STL MAP: 336640
STR STL MAP: 885470


  • With -O2 Compiler Optimization and Total 10K random strings:

TRIE MAP: 16647
INT STL MAP: 69325
STR STL MAP: 440632

As you can see,
·  TRIE Map is approx. 4 times faster than stl map with int key for searches – with or without optimizations.
·  TRIE Map is approx. 25 times faster than stl map with string key for searches – with optimization. Without optimization it is only10 times faster.



  • With -O2 Compiler Optimization and Max String length < 10 characters and Total 10K random strings

TRIE MAP: 36950
INT HASH MAP: 27369
STR HASH MAP: 107488



  • With -O2 Compiler Optimization and Max String 20 < length < 30 characters and Total 240K random strings:

TRIE MAP: 3451134
INT HASH MAP: 143514
STR HASH MAP: 1465260

TRIE Map works very well for symbols with length < 10 characters, which even beat the performance of boost::unordered_map.
However its performance degraded while symbol’s length reach around 20 to 30 characters, where boost::unordered_map becomes faster.

And in both cases, integer searching even in maps are much efficient, Around 4 times faster than string search when string length < 10 characters, while 10 times faster than string when string length is between 20 chars and 30 chars.

1 comment:

  1. This post shares very important facts about high frequency trading..I am new in trading and i was not aware about this information..I highly appreciate author for sharing this useful information..
    hft

    ReplyDelete