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.

Priority Inversion in Mars Probe Pathfinder in 1997

On 4 July 1997, after a seven-month voyage,  the spacecraft landed on Mars. A few days into the mission, the spacecraft began experiencing system resets, which was caused by Priority Inversion design issues.

To know more about Priority Inversion - http://en.wikipedia.org/wiki/Priority_inversion
So we should never feel nervous when there are bugs reported for our software, even Mars project can have such critical bug as well!

There are a few solutions to the Priority-inversion Problem, all of which involve increasing the priority of tasks during their accesses to shared resources. The variation lies in when to increase priority and to what value. Assume that a task A gets a shared resource R. Except for PI, A’s priority is increased to the priority ceiling when A acquires R. The difference lies in the way the priority ceiling is computed for R.

• For NPCS, the priority ceiling is equal to highest priority of all tasks in the system.
• For CP and PC, the priority ceiling is equal to the highest priority of all tasks requiring R. The difference is in allowing or denying access to R.
• For MB-CP, the priority ceiling is equal to the priority ceiling of the monitor, which contains the critical section of R.
• Assume that a task A holds R. In PI, whenever a higher priority task B requests R, A inherits the priority of B and B is blocked.  

Improve Cache Performance with high locality of reference

if users randomly and uniformly access data throughout the master data space a cache is useless, and in fact, it may actually degrade data access time. A cache is effective only if users maintain a high locality of references, that is, data references are spread over tiny areas of the data space, at least over a limited span of time.

L1 and L2 Cache

To be more specific, data to be cached must be at minimum as possible and to be accessed sequentially as much as possible. For example use a small array to store the checking conditions separately if only small portion of the conditions check will return true for next processing stage. If majority of the condition check will return true for next processing stage, the array should contain those extra data needed as well as condition variables.