The Cost of Mutexes By Darryl Gove

sometimes we wonder what will be the cost of a mutex lock and unlock while we are concerned about the system performance at micro-seconds level.

Darryl Gove has done some interesting experiments in sun Solaris systems. The same idea can be applied to other OS like Linux as well.

His blog is used to be http://blogs.sun.com/d/entry/the_cost_of_mutexes and now it is moved to https://blogs.oracle.com/d/entry/the_cost_of_mutexes

His conclusion is that Mutex is 3 times slower than atomic operations.

And there is another point to note that he tested the cost of a normal function call comparing to inline functions, which shows 10ns required for a normal function call. This cost must be less and less with new generations of CPU, RAM and compilers.

Here I just quote what is really interested to me, you can check his full post by above links.

Excl.     Incl.      Name  
User CPU  User CPU         
 sec.      sec.       
3.973     3.973      
1.341     3.973      count
1.331     1.331      mutex_unlock
0.781     0.781      mutex_lock_impl
0.490     0.490      atomic_add_32
0.030     0.030      mutex_lock

It shows clearly that using of mutex, time is spent on an atomic_add_32, mutex_lock_impl and mutex_unlock. As mutex_lock_impl and mutex_unlock assembly code is very similar to atomic_add_32, it is no surprise that mutex will take around 3x time than atomic_add.

Below are the assembly codes:

time spent for the atomic_add_32 call: 

   0.010     0.010              [?]    2ecb8:  ld          [%o0], %o2
   0.040     0.040              [?]    2ecbc:  add         %o2, %o1, %o3
   0.010     0.010              [?]    2ecc0:  cas         [%o0] , %o2, %o3
## 0.370     0.370              [?]    2ecc4:  cmp         %o2, %o3
   0.        0.                 [?]    2ecc8:  bne,a,pn    %icc,0x2ecbc
   0.        0.                 [?]    2eccc:  mov         %o3, %o2
   0.050     0.050              [?]    2ecd0:  retl        
   0.010     0.010              [?]    2ecd4:  add         %o2, %o1, %o0

time spent for mutex_unlock and mutext_lock_impl is similar:

   0.        0.                 [?]    beff8:  mov         %o1, %o3
   0.020     0.020              [?]    beffc:  cas         [%o0] , %o2, %o3
## 0.560     0.560              [?]    bf000:  cmp         %o2, %o3
   0.        0.                 [?]    bf004:  bne,a       0xbeff8
   0.        0.                 [?]    bf008:  mov         %o3, %o2

Error - boost::unordered_map is not derived from type A

When we use STL or boost template classes like boost::unordered_map together with our own template class, as below:

#include "boost/unordered_map.hpp"#include <string> 
template < typename T >
class A
{
typedef boost::unordered_map< std:;string, T* > FtObjsTypeMap;} 

When we compile above class definition with gcc, following compilation error will be reported: 

A.h:7: error: type âboost::unordered_map<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, T*, boost::hash<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char> >, T*> > >â is not derived from type âA<T>â

The reason is that This because boost::unordered_map< std:;string, T* > is dependent on the template parameter T of the class template A To enable correct parsing of the template without having to make any assumptions about possible specializations of any other templates, the language rules require you to indicate which dependent names denote types by using the typename keyword.

Following class A definition will pass the compilation: 

#include "boost/unordered_map.hpp"#include <string> 
template < typename T >
class A
{
typedef typename boost::unordered_map< std:;string, T* > FtObjsTypeMap;} 

The reason of the error is found at http://stackoverflow.com/questions/2841757/c-template-is-not-derived-from-type for my own recording and its mix usage with typedef, I posted my version of code here for future reference. 

Fibonacci number calculation algorithms

There are many blogs and websites provided excellent solutions for nth Fibonacci number calculation.

Fibonacci number

Different algorithms varies from O(n2) to O(n) to O(logn).

details can be found in below examples:
http://www.geeksforgeeks.org/archives/10120
http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

From the wikipedia, http://en.wikipedia.org/wiki/Fibonacci_number , we know that nth Fibonacci number satisfy this math equations:

As you can see that if we keep a careful pre-calculated Fibonacci numbers in memory, a (m+n)th Fibonacci number can be calculated with combinations of mth and nth Fibonacci numbers. If mth and nth Fibonacci numbers are not in the pre-calculated map, we can further search down the chain.

I feel that if we can have a carefully selected array of pre-calculated Fibonacci numbers, we can easily achieve at worst O(logn) while at best O(1) performance without sacrifice of accuracy as following formula does:

a close estimation, accuracy becomes worse while n grows bigger

As a common approach, preparation of certain information as part of the data structure designed can speed up performance exponentially. This approach is also part of our Unix/Linux culture that we prefer complex data structures than complex algorithms in source codes.

Bios Advanced CPU Power Saving Mode

CPU Power Saving will impact HFT performance?

As we know that all CPU has its power saving mode enabled as default in your BIOS. You might wonder whether it will have impact on the performance of your High Frequency Trading systems and how?

Let us look at a standard /etc/cpuinfo output from linux OS.

/etc/cpuinfo

Look at above screenshot carefully, you will see that Model Name of this CPU is Intel Core2 CPU with 2.4GHz. However when you check a few lines below - cpu MHz is only 1.6GHz (1596.00MHz). Why is there any difference here? it is all thanks to CPU Power Saving Mode. When your CPU is job free, it will enter power saving mode to run in a slower speed to save energy. This is actually smart strategy to be environmental friendly and end user will never notice the performance difference of normal programmes, which means no sacrifice of customer satisfactions.

However CPU power saving mode will hit HFT performance badly when we are in the scale of 10 to 20 micro-seconds measurements. While some of your threads/process are waiting for triggering events, mostly market data ticks, CPU, which is executing those threads/process, will enter power saving mode. Once market tick comes in, CPU will take longer time to wake up those threads/process and then take time to speed up to execute them. It results in around 10 micro-seconds degradation of performance, which is 50% to 100% decrease of your system's performance. The recommendation is that disable your server's CPU Power Saving Mode during market hours and shut down your servers while they are not in service.

How to disable in Bios the Advanced CPU Power Saving Mode? You can follow below steps:

Bios Advanced CPU Power Saving Mode Settings - Step 1

Bios Settings - Step 2

BIOS Settings Step 3

 

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.

Strategies to find suitable holes for memory segment allocation request

There are various strategies utilized by modern OS to find suitable memory holes for segment allocation requests from programs.

There are normally four of them:

• First Fit
• Best Fit
• Quick Fit 
• Buddy System

Buddy System is one of the smartest and most efficient strategy which are widely used. The same strategy logic might be able to apply to our trading system designs to achieve the best efficiency thus lowest possible latency.

Buddy System - Memory Hole Searching Strategy

buddy system,where the allocation and deallocation of memory is always in the order of a power of 2. A request for a segment allocation is rounded to the nearest power of 2 that is greater than or equal to the requested amount. The memory manager maintains n, n >=1, lists of holes. List(i) i=0, ...,n-1, holds all holes of size 2 to power of i. A hole may be removed from List(i), and split into two holes of size 2 to power of i-1 (called ‘buddies’ of size 2 to power of i, see picture above), and the two holes are entered in List(i-1). Conversely, a pair of buddies of size 2 to power of i may be removed from List(i), coalesced into a single larger hole, and the new hole of size 2 to power of i+1 is entered in List(i+1). To allocate a hole of size 2 to power of i, the search is started at List(i). If the list is not empty, a hole from the list is allocated. Otherwise, get a hole of size 2 to power of (i+1) from List(i+1), split the hole into two, put one in List(i), and allocate the other one. Hole deallocation is done in reverse fashion: to free a hole of size 2 to power of i, put it in List(i); if its buddy is already there, remove both, coalesce, and insert the coalesced hole in List(i+1). This insertion may cause coalescing of two buddies, the irremoval from List(i+1), and a new insertion in List(i+2), etc.

Red Hat Realtime Tuning Guide

http://docs.redhat.com/docs/en-US/Red_Hat_Enterprise_MRG/1.3/html/Realtime_Tuning_Guide/index.html

OS tuning can be another major factor which can make a difference in your high frequency trading system's performance.