tag:blogger.com,1999:blog-61106500366811574302024-03-12T17:07:39.485-07:00High Frequency TradingXiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.comBlogger41125tag:blogger.com,1999:blog-6110650036681157430.post-80087930547411893192012-09-16T01:52:00.001-07:002012-09-16T01:52:45.994-07:00Stop renewing this blog - please see my main blog<a href="http://xiongzou.blogspot.sg/" style="font-family: serif;">http://xiongzou.blogspot.sg/</a><span style="font-family: serif;"> thanks</span>
XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-23681683591767769952012-08-16T19:19:00.002-07:002012-08-16T19:19:46.278-07:00Calculate the sum of all the primes below two million<br />
<blockquote class="tr_bq">
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.<br />Find the sum of all the primes below two million.</blockquote>
Question is from <a href="http://projecteuler.net/problem=10">Project Euler Q10</a> , which is a very interesting website.<br />
<br />
My Solution is as below, which has performance:<br />
<i>time a.out</i><br />
<i>sum of Prime = 142913828922</i><br />
<i>0.090u 0.005s 0:00.09 100.0% 0+0k 0+0io 0pf+0w </i><br />
<blockquote>
int l_iCount = 2;<br /> const int l_iMax = 2000000;<br /> const int IS_PRIME = 0;<br /> const int NOT_PRIME = 1;<br /> int l_arIntegers[l_iMax];<br /> //initialize and assume all to be prime<br /> memset(l_arIntegers, 0, sizeof(l_arIntegers));<br /> l_arIntegers[0] = NOT_PRIME; //for 1<br /> l_arIntegers[1] = IS_PRIME; //for 2<br /> long long l_iSumOfPrimes = 0;<br /> while(l_iCount < l_iMax)<br /> {<br /> if(l_arIntegers[l_iCount - 1] == IS_PRIME)<br /> {<br /> for(int i = 2 * l_iCount; i < l_iMax; )<br /> {<br /> if(l_arIntegers[i - 1] != NOT_PRIME)<br /> l_arIntegers[i - 1] = NOT_PRIME;<br /> i += l_iCount;<br /> }<br /> //it is a prime<br /> l_iSumOfPrimes += l_iCount;<br /> std::cout << "found a Prime = " << l_iCount << std::endl;<br /> }<br /> l_iCount++;<br /> }<br /> std::cout << "sum of Prime = " << l_iSumOfPrimes << std::endl;</blockquote>
<div>
When I started to code the solution, I tried the normal check for a prime number, it was too slow to be acceptable. then I thought maybe it is faster to create an array of all integers to be checked as above, just having simple comparison and assignment to 1, without tons of mod (%) operations. And the execution result proved to be working.</div>
<div>
</div>
<div>
I have checked the recommended solutions from Project Euler after solving it, my solution is very close to the optimal answer.</div>
<div>
</div>
<div>
Here is my Project Euler Label:</div>
<div class="separator" style="clear: both; text-align: left;">
<a href="http://projecteuler.net/profile/zouxiong.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://projecteuler.net/profile/zouxiong.png" /></a></div>
<div>
</div>
XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-68480202732880792012012-07-25T20:27:00.000-07:002012-07-25T20:27:52.613-07:00Find the greatest product of five consecutive digitsthe problem is as below, got from <a href="http://projecteuler.net/">ProjectEuler.net</a> <a href="http://projecteuler.net/problem=8">Problem 8</a>:<br />
<blockquote class="tr_bq">
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 16px;">Find the greatest product of five consecutive digits in the 1000-digit number.</span></blockquote>
<blockquote class="tr_bq">
<span style="background-color: white; font-family: 'courier new'; font-size: 13px; text-align: center;">73167176531330624919225119674426574742355349194934</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">96983520312774506326239578318016984801869478851843</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">85861560789112949495459501737958331952853208805511</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">12540698747158523863050715693290963295227443043557</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">66896648950445244523161731856403098711121722383113</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">62229893423380308135336276614282806444486645238749</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">30358907296290491560440772390713810515859307960866</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">70172427121883998797908792274921901699720888093776</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">65727333001053367881220235421809751254540594752243</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">52584907711670556013604839586446706324415722155397</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">53697817977846174064955149290862569321978468622482</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">83972241375657056057490261407972968652414535100474</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">82166370484403199890008895243450658541227588666881</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">16427171479924442928230863465674813919123162824586</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">17866458359124566529476545682848912883142607690042</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">24219022671055626321111109370544217506941658960408</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">07198403850962455444362981230987879927244284909188</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">84580156166097919133875499200524063689912560717606</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">05886116467109405077541002256983155200055935729725</span><span style="font-family: 'courier new'; font-size: 13px; text-align: center;">71636269561882670428252483600823257530420752963450</span></blockquote>
To do brute force calculation, logic is easy but kind of having bad performance. To practice and brainstorming some good algorithms to boost the checking speed can be ultimate fun in solving problems we faced. <br />
<br />
My strategy is to check whether we can safely eliminate any 5 digits with 0 inside (which is obvious), then check for 1, 2, 3, till 9. comparing integer values must be much faster than multiply operations, not mention in thousands.<br />
<br />
<span style="background-color: white;">Below is my code, not polished yet, just to illustrate my ideas. My intention is not to show off my code but to ignite better ideas and faster solutions. </span><br />
<br />
<pre class="prettyprint" style="border-left-color: rgb(0, 153, 51); border-left-style: solid; border-left-width: 2px; padding-bottom: 0px; padding-left: 10px; padding-right: 10px; padding-top: 0px; white-space: pre-wrap; word-wrap: break-word;"><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> main</span><span class="pun" style="color: #666600;">()</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">char</span><span class="pln" style="color: black;"> l_arIntegers</span><span class="pun" style="color: #666600;">[</span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450"</span><span class="pun" style="color: #666600;">};</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">char</span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> pIntegers </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="kwd" style="color: #000088; font-weight: bold;">char</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*)</span><span class="pln" style="color: black;">l_arIntegers</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> l_iarMaxWithIdx</span><span class="pun" style="color: #666600;">[</span><span class="lit" style="color: #006666;">10</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">{</span><span class="lit" style="color: #006666;">0</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">2</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">3</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">5</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">6</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">7</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">8</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">*</span><span class="lit" style="color: #006666;">9</span><span class="pun" style="color: #666600;">};</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> l_iMaxProduct </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> l_iEliminate </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">for</span><span class="pun" style="color: #666600;">(</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> m </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">0</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;"> m </span><span class="pun" style="color: #666600;"><</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">10</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;"> m</span><span class="pun" style="color: #666600;">++)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">cout </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"now check for m = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> m </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">", Eliminate = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iEliminate </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">" and max product "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iarMaxWithIdx</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">m</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">" and current max product as "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iMaxProduct </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">endl</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//check whether we can eliminate 1s</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">l_iMaxProduct </span><span class="pun" style="color: #666600;">></span><span class="pln" style="color: black;"> l_iarMaxWithIdx</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">m</span><span class="pun" style="color: #666600;">])</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//we can safely eliminate ms already.</span><span class="pln" style="color: black;">
l_iEliminate </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">continue</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">bool</span><span class="pln" style="color: black;"> l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">false</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">for</span><span class="pun" style="color: #666600;">(</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> i </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;"> i </span><span class="pun" style="color: #666600;"><</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">20</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">51</span><span class="pun" style="color: #666600;">;)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><=</span><span class="pln" style="color: black;"> l_iEliminate</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">5</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">else</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><=</span><span class="pln" style="color: black;"> l_iEliminate</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">else</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">2</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><=</span><span class="pln" style="color: black;"> l_iEliminate</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">3</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">else</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">3</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><=</span><span class="pln" style="color: black;"> l_iEliminate</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">2</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">else</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><=</span><span class="pln" style="color: black;"> l_iEliminate</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1001</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">else</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">i </span><span class="pun" style="color: #666600;">>=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1000</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_bReachEnd </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088; font-weight: bold;">true</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//none of previous 5 is 0</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//check for any sum is greater than 9*9*9*9*1</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">int</span><span class="pln" style="color: black;"> l_iProduct </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">2</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">3</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">-</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">'0'</span><span class="pun" style="color: #666600;">);</span><span class="pln" style="color: black;">
std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">cout </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"now check for m = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> m </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">" and current product = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iProduct </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">" with current max product as "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iMaxProduct </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">endl</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">l_iProduct </span><span class="pun" style="color: #666600;">></span><span class="pln" style="color: black;"> l_iMaxProduct</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
l_iMaxProduct </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> l_iProduct</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">l_iProduct </span><span class="pun" style="color: #666600;">></span><span class="pln" style="color: black;"> l_iarMaxWithIdx</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">m</span><span class="pun" style="color: #666600;">])</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//we can safely eliminate 1s now</span><span class="pln" style="color: black;">
std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">cout </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"current continuous values are "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">4</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">3</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">2</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">-</span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> pIntegers</span><span class="pun" style="color: #666600;">[</span><span class="pln" style="color: black;">i</span><span class="pun" style="color: #666600;">]</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">endl</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
l_iEliminate </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">20</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">*</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">51</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
i </span><span class="pun" style="color: #666600;">+=</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">if</span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">l_bReachEnd</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;">
</span><span class="com" style="color: #880000;">//no need to search again, we find the maximum</span><span class="pln" style="color: black;">
std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">cout </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"reach end before checking for "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">(</span><span class="pln" style="color: black;">m</span><span class="pun" style="color: #666600;">+</span><span class="lit" style="color: #006666;">1</span><span class="pun" style="color: #666600;">)</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">", max product = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iMaxProduct </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">endl</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">break</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
</span><span class="pun" style="color: #666600;">}</span><span class="pln" style="color: black;">
std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">cout </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> </span><span class="str" style="color: #008800;">"max product = "</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> l_iMaxProduct </span><span class="pun" style="color: #666600;"><<</span><span class="pln" style="color: black;"> std</span><span class="pun" style="color: #666600;">::</span><span class="pln" style="color: black;">endl</span><span class="pun" style="color: #666600;">;</span><span class="pln" style="color: black;">
</span><span class="kwd" style="color: #000088; font-weight: bold;">return</span><span class="pln" style="color: black;"> </span><span class="lit" style="color: #006666;">0</span><span class="pun" style="color: #666600;">; </span></pre>
<pre class="prettyprint" style="border-left-color: rgb(0, 153, 51); border-left-style: solid; border-left-width: 2px; padding-bottom: 0px; padding-left: 10px; padding-right: 10px; padding-top: 0px; white-space: pre-wrap; word-wrap: break-word;"><span class="pun" style="color: #666600;">}</span><span class="pln">
</span></pre>
<br />
<br />
<br />
<blockquote class="tr_bq">
<span style="font-size: x-small;">$ time a.out<br />now check for m = 0, Eliminate = -1 and max product 0 and current max product as 1<br />now check for m = 1, Eliminate = 0 and max product 6561 and current max product as 1<br />now check for m = 1 and current product = 882 with current max product as 1<br />now check for m = 1 and current product = 126 with current max product as 882<br />now check for m = 1 and current product = 294 with current max product as 882<br />now check for m = 1 and current product = 1764 with current max product as 882<br />now check for m = 1 and current product = 1470 with current max product as 1764<br />now check for m = 1 and current product = 630 with current max product as 1764<br />now check for m = 1 and current product = 630 with current max product as 1764<br />now check for m = 1 and current product = 270 with current max product as 1764<br />now check for m = 1 and current product = 135 with current max product as 1764<br />now check for m = 1 and current product = 432 with current max product as 1764<br />now check for m = 1 and current product = 648 with current max product as 1764<br />now check for m = 1 and current product = 648 with current max product as 1764<br />now check for m = 1 and current product = 324 with current max product as 1764<br />now check for m = 1 and current product = 180 with current max product as 1764<br />now check for m = 1 and current product = 180 with current max product as 1764<br />now check for m = 1 and current product = 20 with current max product as 1764<br />now check for m = 1 and current product = 90 with current max product as 1764<br />now check for m = 1 and current product = 270 with current max product as 1764<br />now check for m = 1 and current product = 378 with current max product as 1764<br />now check for m = 1 and current product = 1512 with current max product as 1764<br />now check for m = 1 and current product = 6048 with current max product as 1764<br />now check for m = 1 and current product = 1344 with current max product as 6048<br />now check for m = 1 and current product = 1344 with current max product as 6048<br />now check for m = 1 and current product = 960 with current max product as 6048<br />now check for m = 1 and current product = 1680 with current max product as 6048<br />now check for m = 1 and current product = 1680 with current max product as 6048<br />now check for m = 1 and current product = 5880 with current max product as 6048<br />now check for m = 1 and current product = 3920 with current max product as 6048<br />now check for m = 1 and current product = 1568 with current max product as 6048<br />now check for m = 1 and current product = 672 with current max product as 6048<br />now check for m = 1 and current product = 840 with current max product as 6048<br />now check for m = 1 and current product = 600 with current max product as 6048<br />now check for m = 1 and current product = 450 with current max product as 6048<br />now check for m = 1 and current product = 900 with current max product as 6048<br />now check for m = 1 and current product = 2700 with current max product as 6048<br />now check for m = 1 and current product = 540 with current max product as 6048<br />now check for m = 1 and current product = 972 with current max product as 6048<br />now check for m = 1 and current product = 1296 with current max product as 6048<br />now check for m = 1 and current product = 2916 with current max product as 6048<br />now check for m = 1 and current product = 972 with current max product as 6048<br />now check for m = 1 and current product = 3888 with current max product as 6048<br />now check for m = 1 and current product = 3888 with current max product as 6048<br />now check for m = 1 and current product = 5832 with current max product as 6048<br />now check for m = 1 and current product = 5832 with current max product as 6048<br />now check for m = 1 and current product = 15552 with current max product as 6048<br />current continuous values are 49698<br />now check for m = 2, Eliminate = 1 and max product 13122 and current max product as 15552<br />now check for m = 3, Eliminate = 2 and max product 19683 and current max product as 15552<br />now check for m = 3 and current product = 6048 with current max product as 15552<br />now check for m = 3 and current product = 5880 with current max product as 15552<br />now check for m = 3 and current product = 3920 with current max product as 15552<br />now check for m = 3 and current product = 900 with current max product as 15552<br />now check for m = 3 and current product = 2700 with current max product as 15552<br />now check for m = 3 and current product = 3888 with current max product as 15552<br />now check for m = 3 and current product = 3888 with current max product as 15552<br />now check for m = 3 and current product = 5832 with current max product as 15552<br />now check for m = 3 and current product = 5832 with current max product as 15552<br />now check for m = 3 and current product = 15552 with current max product as 15552<br />now check for m = 3 and current product = 11664 with current max product as 15552<br />now check for m = 3 and current product = 6480 with current max product as 15552<br />now check for m = 3 and current product = 7560 with current max product as 15552<br />now check for m = 3 and current product = 7560 with current max product as 15552<br />now check for m = 3 and current product = 13824 with current max product as 15552<br />now check for m = 3 and current product = 12096 with current max product as 15552<br />now check for m = 3 and current product = 12096 with current max product as 15552<br />now check for m = 3 and current product = 16128 with current max product as 15552<br />now check for m = 3 and current product = 8960 with current max product as 16128<br />now check for m = 3 and current product = 3840 with current max product as 16128<br />now check for m = 3 and current product = 3840 with current max product as 16128<br />now check for m = 3 and current product = 5760 with current max product as 16128<br />now check for m = 3 and current product = 11664 with current max product as 16128<br />now check for m = 3 and current product = 6480 with current max product as 16128<br />now check for m = 3 and current product = 6480 with current max product as 16128<br />now check for m = 3 and current product = 3600 with current max product as 16128<br />now check for m = 3 and current product = 8100 with current max product as 16128<br />now check for m = 3 and current product = 4500 with current max product as 16128<br />now check for m = 3 and current product = 6615 with current max product as 16128<br />now check for m = 3 and current product = 7560 with current max product as 16128<br />now check for m = 3 and current product = 7560 with current max product as 16128<br />now check for m = 3 and current product = 3240 with current max product as 16128<br />now check for m = 3 and current product = 12096 with current max product as 16128<br />now check for m = 3 and current product = 14112 with current max product as 16128<br />now check for m = 3 and current product = 2100 with current max product as 16128<br />now check for m = 3 and current product = 3150 with current max product as 16128<br />now check for m = 3 and current product = 6300 with current max product as 16128<br />now check for m = 3 and current product = 10080 with current max product as 16128<br />now check for m = 3 and current product = 18144 with current max product as 16128<br />now check for m = 3 and current product = 15552 with current max product as 18144<br />now check for m = 3 and current product = 15552 with current max product as 18144<br />now check for m = 3 and current product = 10368 with current max product as 18144<br />now check for m = 3 and current product = 10368 with current max product as 18144<br />now check for m = 3 and current product = 10368 with current max product as 18144<br />now check for m = 3 and current product = 8640 with current max product as 18144<br />now check for m = 3 and current product = 7776 with current max product as 18144<br />now check for m = 3 and current product = 810 with current max product as 18144<br />now check for m = 3 and current product = 1536 with current max product as 18144<br />now check for m = 3 and current product = 2048 with current max product as 18144<br />now check for m = 3 and current product = 3072 with current max product as 18144<br />now check for m = 3 and current product = 4608 with current max product as 18144<br />now check for m = 3 and current product = 4608 with current max product as 18144<br />now check for m = 3 and current product = 5760 with current max product as 18144<br />now check for m = 3 and current product = 6048 with current max product as 18144<br />now check for m = 3 and current product = 6048 with current max product as 18144<br />now check for m = 3 and current product = 5400 with current max product as 18144<br />now check for m = 3 and current product = 15552 with current max product as 18144<br />now check for m = 3 and current product = 15552 with current max product as 18144<br />now check for m = 3 and current product = 13608 with current max product as 18144<br />now check for m = 3 and current product = 40824 with current max product as 18144<br />current continuous values are 99879<br />now check for m = 4, Eliminate = 3 and max product 26244 and current max product as 40824<br />now check for m = 5, Eliminate = 4 and max product 32805 and current max product as 40824<br />now check for m = 6, Eliminate = 5 and max product 39366 and current max product as 40824<br />now check for m = 7, Eliminate = 6 and max product 45927 and current max product as 40824<br />now check for m = 7 and current product = 40824 with current max product as 40824<br />now check for m = 7 and current product = 31752 with current max product as 40824<br />now check for m = 7 and current product = 31752 with current max product as 40824<br />now check for m = 7 and current product = 24696 with current max product as 40824<br />now check for m = 7 and current product = 28224 with current max product as 40824<br />now check for m = 7 and current product = 28224 with current max product as 40824<br />now check for m = 7 and current product = 31752 with current max product as 40824<br />reach end before checking for 8, max product = 40824<br />max product = 40824<br />0.000u 0.001s 0:00.00 0.0% 0+0k 0+0io 0pf+0w</span></blockquote>
<div>
<br /></div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-4887045507508010222012-06-25T18:39:00.003-07:002012-06-25T18:40:46.143-07:00The future of institutional trading - slower trading through cloud based services?<span style="font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">"A venue that questions the need for speed is a new ATV called PDQ run by ex GETCO CEO Keith Ross. PDQ say they have developed new ways to allow the less fleet-footed to compete on a level playing field. They are aiming to persuade traders and institutions that their new trading systems offers a leg up by actually decelerating the execution of trades."</span><br />
<br />
<br />
<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRvNPkfKgNqD4PMQJ26MEVFWkDYrsl6qYjh4lnbVErUda2x3sE8Ty0nYnPx6BVC3sWDP0m9JuoCjrOIy8ro97AWNEfj9Fvu_pOrYUacMdyT7bMiBzrgxUCTonYi7k7P2UqW4gEh-F-5JKm/s1600/cloud_0.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRvNPkfKgNqD4PMQJ26MEVFWkDYrsl6qYjh4lnbVErUda2x3sE8Ty0nYnPx6BVC3sWDP0m9JuoCjrOIy8ro97AWNEfj9Fvu_pOrYUacMdyT7bMiBzrgxUCTonYi7k7P2UqW4gEh-F-5JKm/s320/cloud_0.jpg" width="319" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Cloud for Algo Trading?</td></tr>
</tbody></table>
<br />
<span style="font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">It is kind of interesting topic for brainstorming. We are aiming to achieve faster speed with hardware acceleration. however some are already thinking to achieve better performance by slowing down the executions. However will it really make sense? Both strategies have same logic, a slower one can get better executions?</span><span style="background-color: white; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"> </span>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-38174880426880410332012-06-20T01:03:00.001-07:002012-06-20T01:03:34.617-07:00Open Source Project Planner - OpenProj<br />
<div style="font-family: serif;">
Nowadays open source OpenProj becomes more and more popular for project management. How to use it efficiently and utilize its features to the maximum to help a better plan which is still adapt to changes along the path. (<a href="http://en.wikipedia.org/wiki/OpenProj">http://en.wikipedia.org/wiki/OpenProj</a>)</div>
<div style="font-family: serif;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="font-family: serif; margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipyiu1tR4_CapCxEK5vC9yLzNCBfAdpfb_bIaU8w4xGwPGi-m2Ppkdz_zdRYFOWHBrQwSdvJI30J-SnJh7z1436U6VDpIoDRnZeSqriU9j_W0yQjBllJVE3FG58Ag7G5TjeE-jSQBk9eE/s1600/242882.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="323" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipyiu1tR4_CapCxEK5vC9yLzNCBfAdpfb_bIaU8w4xGwPGi-m2Ppkdz_zdRYFOWHBrQwSdvJI30J-SnJh7z1436U6VDpIoDRnZeSqriU9j_W0yQjBllJVE3FG58Ag7G5TjeE-jSQBk9eE/s400/242882.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px;">OpenProj</td></tr>
</tbody></table>
<div style="font-family: serif;">
<br /></div>
<div style="font-family: serif;">
<br /></div>
<div style="font-family: serif;">
here is a very good starting point to go through an online training material like <a href="http://www.scribd.com/doc/37439251/110/Understanding-the-Critical-Path">http://www.scribd.com/doc/37439251/110/Understanding-the-Critical-Path</a> </div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-9818319900999524412012-05-16T00:20:00.001-07:002012-05-16T00:22:58.057-07:00基于业务设计技术架构(兼谈12306性能问题)by 陈勇敏捷开发产品管理系列之八:基于业务设计技术架构(兼谈12306性能问题), 陈勇从业务员的角度分析怎么解决春节火车订票系统12306崩溃的问题。很有启发性。<span style="font-family: serif;">比方他提到的排队设计,确实是解决问题的好办法之一。</span><br />
<br />
一个项目不是只需要技术人员,从另外一个角度,往往可以起到事半功倍的效果。以下是他的文章的链接。<br />
<a href="http://blog.csdn.net/cheny_com/article/details/7569724">http://blog.csdn.net/cheny_com/article/details/7569724</a>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-15872389049455098102012-05-07T00:58:00.000-07:002012-05-14T18:40:39.066-07:00Why Scalar Optimization Is Important by Richard FriedmanIn this interesting article, Richard mentioned a very simple yet important Amdahl's Law. (<a href="http://en.wikipedia.org/wiki/Amdahl" s_law#parallelization'="">http://en.wikipedia.org/wiki/Amdahl's_law#Parallelization</a>)<br />
<br />
Below is the formula. <br />
<br />
S = T/((1-f)T+fT/N) = 1/(1-f+f/N) <br />
<br />
He gave an example that If we can get half the executable code to run in parallel, and the other half running in one processor, what speedup can we expect on a 64–processor system?<br />
<br />
<a href="http://www.blogger.com/blogger.g?blogID=6110650036681157430"></a>Well, that gives a speedup S = 1.97 only! <br />
<br />
The basic point here is that we should take the scalar latency optimization seriously when tuning the whole system. However we should not be misled by author to under estimate the importance of parallel as well for it is also important factor for another axis of the system performance measurement - throughput. Without high throughput support, low latency can be screwed while system load is heavy.<br />
<br />
Original post of Richard is at <a href="http://blogs.sun.com/rchrd/entry/why_scalar_optimization_is_important">http://blogs.sun.com/rchrd/entry/why_scalar_optimization_is_important</a>, however it cannot be accessed or found in WWW any more. It is now collected in book "The Developer's Edge", which is an interesting book for reading.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinaPPCs8sxztwqoFuukS13l2qF9sgqtNk6sTKZqWkK9CoRi3qX42tMxnbZbsrbyQja8gZdKdOU3hpYoRV6gFK3TANFSh2IHa-OquPPra9EDfRQTNZ__bTVNnj8B8HRTnNChnXmeELv3hja/s1600/0595352510_s.jpg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinaPPCs8sxztwqoFuukS13l2qF9sgqtNk6sTKZqWkK9CoRi3qX42tMxnbZbsrbyQja8gZdKdOU3hpYoRV6gFK3TANFSh2IHa-OquPPra9EDfRQTNZ__bTVNnj8B8HRTnNChnXmeELv3hja/s1600/0595352510_s.jpg" /></a> <br />
The Developer's Edge<br />
<br />
It is very generous that authors have published this book freely online at <a href="http://www.oracle.com/technetwork/server-storage/archive/r11-005-sys-edge-archive-495362.pdf">http://www.oracle.com/technetwork/server-storage/archive/r11-005-sys-edge-archive-495362.pdf</a> <br />
<br />
One of the author Darryl's blog address is <a href="http://www.darrylgove.com/">http://www.darrylgove.com/</a> . You can always find the correct download link there.<br />XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com2tag:blogger.com,1999:blog-6110650036681157430.post-53536798016672885482012-04-29T21:00:00.000-07:002012-04-29T21:05:56.846-07:00The Cost of Mutexes By Darryl Govesometimes 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.<br />
<br />
Darryl Gove has done some interesting experiments in sun Solaris systems. The same idea can be applied to other OS like Linux as well.<br />
<br />
His blog is used to be <a href="http://blogs.sun.com/d/entry/the_cost_of_mutexes">http://blogs.sun.com/d/entry/the_cost_of_mutexes</a> and now it is moved to <a href="https://blogs.oracle.com/d/entry/the_cost_of_mutexes">https://blogs.oracle.com/d/entry/the_cost_of_mutexes</a> <br />
<br />
His conclusion is that Mutex is 3 times slower than atomic operations. <br />
<br />
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.<br />
<br />
Here I just quote what is really interested to me, you can check his full post by above links.<br />
<br />
<pre style="background-color: white; color: #555555; font-size: 12px; line-height: 18px; margin-bottom: 10px; margin-top: 10px;"><pre style="margin-bottom: 10px; margin-top: 10px;">Excl. Incl. Name
User CPU User CPU
sec. sec.
3.973 3.973 <total>
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</total></pre>
</pre>
<br />
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. <br />
<br />
Below are the assembly codes:<br />
<br />
time spent for the atomic_add_32 call: <br />
<pre style="background-color: white; color: #555555; font-size: 12px; line-height: 18px; margin-bottom: 10px; margin-top: 10px;"><function: atomic_add_32=""> 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</function:></pre>
<br />
time spent for mutex_unlock and mutext_lock_impl is similar:<br />
<pre style="background-color: white; color: #555555; font-size: 12px; line-height: 18px; margin-bottom: 10px; margin-top: 10px;"><pre style="margin-bottom: 10px; margin-top: 10px;"> 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</pre>
</pre>
<br />XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-32373250194188575522012-03-27T20:52:00.001-07:002012-03-27T20:53:33.283-07:00Error - boost::unordered_map is not derived from type A<div style="font-family: serif;">When we use STL or boost template classes like boost::unordered_map together with our own template class, as below:</div><div style="font-family: serif;"><br />
</div><blockquote class="tr_bq" style="font-family: serif;"><span style="font-size: x-small;"><span style="font-family: serif;">#include "boost/unordered_map.hpp"</span><span style="font-family: serif;">#include <string></span><span style="font-family: serif;"> </span><br />
template < typename T ><br />
class A<br />
{<br />
<span style="font-family: serif;"><span class="Apple-tab-span" style="white-space: pre;"> </span>typedef boost::unordered_map< std:;string, T* ><span class="Apple-tab-span" style="white-space: pre;"> </span>FtObjsTypeMap;</span>} </span></blockquote><div style="font-family: serif;"><br />
</div><div style="font-family: serif;">When we compile above class definition with gcc, following compilation error will be reported: </div><div style="font-family: serif;"><br />
</div><div style="font-family: serif;">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>â</div><div style="font-family: serif;"><br />
</div><div>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.<br />
<br />
Following class A definition will pass the compilation:<span style="background-color: white; font-family: inherit; line-height: 18px; text-align: left;"> </span></div><blockquote class="tr_bq" style="font-family: serif;"><span style="font-size: x-small;"><span style="font-family: serif;">#include "boost/unordered_map.hpp"</span><span style="font-family: serif;">#include <string></span><span style="font-family: serif;"> </span><br />
template < typename T ><br />
class A<br />
{<br />
<span style="font-family: serif;"><span class="Apple-tab-span" style="white-space: pre;"> </span>typedef typename boost::unordered_map< std:;string, T* ><span class="Apple-tab-span" style="white-space: pre;"> </span>FtObjsTypeMap;</span>} </span></blockquote><div><br />
The reason of the error is found at <a href="http://stackoverflow.com/questions/2841757/c-template-is-not-derived-from-type">http://stackoverflow.com/questions/2841757/c-template-is-not-derived-from-type</a> for my own recording and its mix usage with typedef, I posted my version of code here for future reference.<span style="background-color: white; font-family: inherit; line-height: 18px; text-align: left;"> </span></div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-275721127185647932012-03-17T02:31:00.000-07:002012-03-17T02:31:18.932-07:00Fibonacci number calculation algorithmsThere are many blogs and websites provided excellent solutions for nth Fibonacci number calculation.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0k7TfEV20SvlW60g8FfS9ZAwF7zU3IjmbUAnlOn700U_SUZe-2BrE7DDZXr9eBuJyJFeRS_rChRtfn322h8k0c0zBmuvqTbXXJj2Rjc2EvvNkoqiRjW8ljXfp3ClOVfUWNYErORyulq70/s1600/cabe91689f6a1af616ace02827c6e89c.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0k7TfEV20SvlW60g8FfS9ZAwF7zU3IjmbUAnlOn700U_SUZe-2BrE7DDZXr9eBuJyJFeRS_rChRtfn322h8k0c0zBmuvqTbXXJj2Rjc2EvvNkoqiRjW8ljXfp3ClOVfUWNYErORyulq70/s400/cabe91689f6a1af616ace02827c6e89c.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fibonacci number</td></tr>
</tbody></table>Different algorithms varies from O(n2) to O(n) to O(logn).<br />
<br />
details can be found in below examples:<br />
<a href="http://www.geeksforgeeks.org/archives/10120">http://www.geeksforgeeks.org/archives/10120</a><br />
<a href="http://www.haskell.org/haskellwiki/The_Fibonacci_sequence">http://www.haskell.org/haskellwiki/The_Fibonacci_sequence</a><br />
<br />
From the wikipedia, <a href="http://en.wikipedia.org/wiki/Fibonacci_number">http://en.wikipedia.org/wiki/Fibonacci_number</a> , we know that nth Fibonacci number satisfy this math equations:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWrLJZoq9CkIMvKVRXZFp8LthqSqrcOMhbUGfcTUPN4PTnuSH1DuOEJA46lxTEo4b1YyPEwM6Op0R6Yn5RH4HwH4l9X0Ii78PT9TQgMisYFmaAq602a91Mu-4whBGUvfcXLyg568uotCzT/s1600/145ac0cb1b31450ed65a7a89672ce23d.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="60" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWrLJZoq9CkIMvKVRXZFp8LthqSqrcOMhbUGfcTUPN4PTnuSH1DuOEJA46lxTEo4b1YyPEwM6Op0R6Yn5RH4HwH4l9X0Ii78PT9TQgMisYFmaAq602a91Mu-4whBGUvfcXLyg568uotCzT/s320/145ac0cb1b31450ed65a7a89672ce23d.png" width="320" /></a></div>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.<br />
<br />
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:<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1UlcQXS3JdWf3MW9JrtLF4mMMIsnaFO_ZvOy70BrKB3KIs4hHXRljzcwqblAwTHOO4VAJ2ZgFEtbMQUwZlXeg7A2He8TYjKfetyJcwUWSumyP3I8je4jORIG5R-N25TsVQEY4p6nQRd8_/s1600/b443c89c69c770a79fbd198e67cd866b.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="53" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1UlcQXS3JdWf3MW9JrtLF4mMMIsnaFO_ZvOy70BrKB3KIs4hHXRljzcwqblAwTHOO4VAJ2ZgFEtbMQUwZlXeg7A2He8TYjKfetyJcwUWSumyP3I8je4jORIG5R-N25TsVQEY4p6nQRd8_/s320/b443c89c69c770a79fbd198e67cd866b.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">a close estimation, accuracy becomes worse while n grows bigger</td></tr>
</tbody></table>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.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-7922578711079046822012-02-11T23:54:00.000-08:002012-02-11T23:54:16.820-08:00Bios Advanced CPU Power Saving Mode<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghFvqyD94rcA-SCSlTD1ER_uS7BSMvZUG6HwVK791xwQwhx43RDgGPjVnoM509ceayR2xPcvLabE9iA7I4mXivpQ2mzuk_Yy7ajhFAHjA2SJKYm0j6GbZ1giIa4FM3DDwmHAU4XYVZnDyh/s1600/linux-cpu.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghFvqyD94rcA-SCSlTD1ER_uS7BSMvZUG6HwVK791xwQwhx43RDgGPjVnoM509ceayR2xPcvLabE9iA7I4mXivpQ2mzuk_Yy7ajhFAHjA2SJKYm0j6GbZ1giIa4FM3DDwmHAU4XYVZnDyh/s400/linux-cpu.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">CPU Power Saving will impact HFT performance?</td></tr>
</tbody></table><br />
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?<br />
<br />
Let us look at a standard /etc/cpuinfo output from linux OS.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6t5sR6n16GH5BS1u5zz476RLwM0NG5ylxTPSpCVtD_4JAemPZ51IojU9qGo8vekg7hqagiytB21qjAS-1jpSQHfIezsttAetjfFxRp8p57WplmzRB8sloWyNoC-5juus2d9AjtZWxhwKG/s1600/proc-cpuinfo.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="311" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6t5sR6n16GH5BS1u5zz476RLwM0NG5ylxTPSpCVtD_4JAemPZ51IojU9qGo8vekg7hqagiytB21qjAS-1jpSQHfIezsttAetjfFxRp8p57WplmzRB8sloWyNoC-5juus2d9AjtZWxhwKG/s400/proc-cpuinfo.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">/etc/cpuinfo</td></tr>
</tbody></table>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.<br />
<br />
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.<br />
<br />
How to disable in Bios the Advanced CPU Power Saving Mode? You can follow below steps:<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdfTVv6cg7fnnlcOe8ws8BM3z-EaEtiYJlbqU1myd94rcNqlecC3Ic1Za6myR576QJ0VdXtIbD22lvOJq4Zl-k9T0SbrXT3JcntP2f-AXsWuXTPHUIe3Ndx7zx04vUm7UtJ075yOe26Bqx/s1600/b1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="317" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdfTVv6cg7fnnlcOe8ws8BM3z-EaEtiYJlbqU1myd94rcNqlecC3Ic1Za6myR576QJ0VdXtIbD22lvOJq4Zl-k9T0SbrXT3JcntP2f-AXsWuXTPHUIe3Ndx7zx04vUm7UtJ075yOe26Bqx/s400/b1.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Bios Advanced CPU Power Saving Mode Settings - Step 1</td></tr>
</tbody></table><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJ2dn16K8vIrGKnZkwe4kGoq3xMc1O7w_m-FaZ7l2fHQLKwj4IKn5_EMIcOVm6b51mMPayetaiN0rPFIiWkBkJUoEB8dDmO5ATe6jf0PmTZYZMCCEhoZv3yayipyKure6hCnFXoJxlaeqh/s1600/b2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="315" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJ2dn16K8vIrGKnZkwe4kGoq3xMc1O7w_m-FaZ7l2fHQLKwj4IKn5_EMIcOVm6b51mMPayetaiN0rPFIiWkBkJUoEB8dDmO5ATe6jf0PmTZYZMCCEhoZv3yayipyKure6hCnFXoJxlaeqh/s400/b2.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Bios Settings - Step 2</td></tr>
</tbody></table><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvY3GhTMixVMkOnYSMWP7pIZs9GwhXOs_aNo8n6tufsWRbq_2cXW96hq7ywIiOLDdV_pCzBpUWiQeKojDbojqDuvvkxJnD1PME9lsAUn80Y32ikDezIy3Gjd-Agw5L5NeswIH1KQ0ECiNj/s1600/b3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="317" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvY3GhTMixVMkOnYSMWP7pIZs9GwhXOs_aNo8n6tufsWRbq_2cXW96hq7ywIiOLDdV_pCzBpUWiQeKojDbojqDuvvkxJnD1PME9lsAUn80Y32ikDezIy3Gjd-Agw5L5NeswIH1KQ0ECiNj/s400/b3.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">BIOS Settings Step 3</td></tr>
</tbody></table><br />
<br />
XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-46481094015288165652012-01-27T06:29:00.000-08:002012-01-27T06:31:44.591-08:00Performance comparison among std::map, boost::unordered_map and TRIE data structureWe 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.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivT0Hv237yKdqXGl7pe2bZce4qFvNauAl7atTVAlCNA3QX2chgb146LZ2eT88UZFMTcYSMhbTTKRRq9iS13mcRiJMSOZdZDYnhcmVfIB0tzO7OcD0WZzuM2DkQcOTUjGIIRJcuYK4DJkJ_/s1600/images.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivT0Hv237yKdqXGl7pe2bZce4qFvNauAl7atTVAlCNA3QX2chgb146LZ2eT88UZFMTcYSMhbTTKRRq9iS13mcRiJMSOZdZDYnhcmVfIB0tzO7OcD0WZzuM2DkQcOTUjGIIRJcuYK4DJkJ_/s320/images.jpg" width="296" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">TRIE Data Structure</td></tr>
</tbody></table><br />
To know more about TRIE data structure, please go to wikipedia page: <a href="http://en.wikipedia.org/wiki/Trie">http://en.wikipedia.org/wiki/Trie</a><br />
<br />
<ul><li>Without Compiler Optimization and Total 10K random strings:</li>
</ul><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>TRIE MAP: 83170</span><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>INT STL MAP: 336640</span><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>STR STL MAP: 885470</span><br />
<br />
<br />
<ul><li>With -O2 Compiler Optimization and Total 10K random strings:</li>
</ul><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>TRIE MAP: 16647</span><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>INT STL MAP: 69325</span><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>STR STL MAP: 440632</span><br />
<br />
<div class="MsoNormal" style="border-collapse: collapse; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: inherit;">As you can see,<u></u><u></u></span></div><div style="border-collapse: collapse;"><span class="Apple-style-span" style="font-family: inherit;"><u></u>·<span style="font: normal normal normal 7pt/normal 'Times New Roman';"> <span class="Apple-style-span" style="font-size: small;">TRIE </span></span>Map is approx. <i><u>4 times faster</u></i> than <i><u>stl map with int key</u></i> for searches – with or without optimizations.<u></u><u></u></span></div><div style="border-collapse: collapse;"><span class="Apple-style-span" style="font-family: inherit;"><u></u>·<span style="font: normal normal normal 7pt/normal 'Times New Roman';"> <span class="Apple-style-span" style="font-size: small;">TRIE </span></span>Map is approx. <i><u>25 times faster</u></i> than <i><u>stl map with string key</u></i> for searches – with optimization. Without optimization it is only<i><u>10 times faster</u></i>.</span><span class="Apple-style-span" style="color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><u></u><u></u></span></div><br />
<br />
<br />
<ul><li>With -O2 Compiler Optimization and Max String length < 10 characters and Total 10K random strings</li>
</ul><br />
<div class="MsoNormal" style="border-collapse: collapse; color: #222222; font-family: arial, sans-serif; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="color: #1f497d;"><span class="Apple-tab-span" style="white-space: pre;"> </span>TRIE MAP: 36950<u></u><u></u></span></div><div class="MsoNormal" style="border-collapse: collapse; color: #222222; font-family: arial, sans-serif; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="color: #1f497d;"><span class="Apple-tab-span" style="white-space: pre;"> </span>INT HASH MAP: 27369<u></u><u></u></span></div><span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>STR HASH MAP: 107488</span><br />
<span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"></span><br />
<br />
<br />
<ul><li>With -O2 Compiler Optimization and Max String 20 < length < 30 characters and Total 240K random strings:</li>
</ul><br />
<div class="MsoNormal" style="border-collapse: collapse; color: #222222; font-family: arial, sans-serif; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="color: #1f497d;"><span class="Apple-tab-span" style="white-space: pre;"> </span>TRIE MAP: 3451134<u></u><u></u></span></div><div class="MsoNormal" style="border-collapse: collapse; color: #222222; font-family: arial, sans-serif; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="color: #1f497d;"><span class="Apple-tab-span" style="white-space: pre;"> </span>INT HASH MAP: 143514<u></u><u></u></span></div><span class="Apple-style-span" style="border-collapse: collapse; color: #1f497d; font-family: arial, sans-serif; font-size: 13px;"><span class="Apple-tab-span" style="white-space: pre;"> </span>STR HASH MAP: 1465260</span><br />
<br />
<div class="MsoNormal" style="border-collapse: collapse; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: inherit;">TRIE Map works very well for symbols with length < 10 characters, which even beat the performance of boost::unordered_map.<u></u><u></u></span></div><div class="MsoNormal" style="border-collapse: collapse; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: inherit;">However its performance degraded while symbol’s length reach around 20 to 30 characters, where boost::unordered_map becomes faster.<u></u><u></u></span></div><div class="MsoNormal" style="border-collapse: collapse; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><span class="Apple-style-span" style="border-collapse: collapse; font-family: inherit;">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.</span>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com1tag:blogger.com,1999:blog-6110650036681157430.post-14583752592625403422012-01-09T20:24:00.000-08:002012-01-10T16:04:45.504-08:00Priority Inversion in Mars Probe Pathfinder in 1997On 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.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDWOrb0v6cCcUuGbR39StrylmtcyoJNf0M0ke4LJe3SYkeCGPDmEMLWVj9zAN70suvtuSvztCFvTDwq_oe-0r46r03NEJjXDVfj11fVT_g62HelQz0eq7gtZ-E6mZ_c-GlChneADCl99e1/s1600/220px-Sojourner_on_Mars_PIA01122.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDWOrb0v6cCcUuGbR39StrylmtcyoJNf0M0ke4LJe3SYkeCGPDmEMLWVj9zAN70suvtuSvztCFvTDwq_oe-0r46r03NEJjXDVfj11fVT_g62HelQz0eq7gtZ-E6mZ_c-GlChneADCl99e1/s1600/220px-Sojourner_on_Mars_PIA01122.jpg" /></a></div><br />
To know more about Priority Inversion - <a href="http://en.wikipedia.org/wiki/Priority_inversion">http://en.wikipedia.org/wiki/Priority_inversion</a><br />
So we should never feel nervous when there are bugs reported for our software, even Mars project can have such critical bug as well!<br />
<br />
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.<br />
<br />
<br />
<ul><li>For NPCS, the priority ceiling is equal to highest priority of all tasks in the system.</li>
<li>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.</li>
<li>For MB-CP, the priority ceiling is equal to the priority ceiling of the monitor, which contains the critical section of R.</li>
<li>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. </li>
</ul>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-30188784524536284952012-01-05T17:29:00.000-08:002012-01-05T17:33:37.332-08:00Improve Cache Performance with high locality of referenceif 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.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJbfe3PnTHDlt-_Inpj63Oxcz5tEhNTBtNr-tKGpjXWEZo3uVikUOnffFq2FvxAntAnJfk9EtLf3RbYSX_v1ZNFSedn111ycJJGyI7Bu5J_U4Ofz_c_Q3kPBdwq6ayFcIU0D4LJPDncjw/s1600/CACHEMEM.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJbfe3PnTHDlt-_Inpj63Oxcz5tEhNTBtNr-tKGpjXWEZo3uVikUOnffFq2FvxAntAnJfk9EtLf3RbYSX_v1ZNFSedn111ycJJGyI7Bu5J_U4Ofz_c_Q3kPBdwq6ayFcIU0D4LJPDncjw/s320/CACHEMEM.gif" width="309" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">L1 and L2 Cache</td></tr>
</tbody></table>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.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-1042396859055102632011-12-29T19:28:00.000-08:002011-12-30T04:36:01.345-08:00Strategies to find suitable holes for memory segment allocation requestThere are various strategies utilized by modern OS to find suitable memory holes for segment allocation requests from programs.<br />
<br />
There are normally four of them:<br />
<br />
<ul><li>First Fit</li>
<li>Best Fit</li>
<li>Quick Fit </li>
<li>Buddy System</li>
</ul><br />
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.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCH9L4eHb7xCNQ9VKGEe5qKFeHro0ObsnMfM_xNLGGSMRufDPo1n2szIS6Qy6KuS7eC0EtjeEyOBLHz2scuo6Y49F1QQ0yf6ylJDryhB5qnkouP0a9FpNBZJr4VjvRiMTshm-1QE0ZxNo/s1600/ScreenHunter_01+Dec.+30+11.08.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCH9L4eHb7xCNQ9VKGEe5qKFeHro0ObsnMfM_xNLGGSMRufDPo1n2szIS6Qy6KuS7eC0EtjeEyOBLHz2scuo6Y49F1QQ0yf6ylJDryhB5qnkouP0a9FpNBZJr4VjvRiMTshm-1QE0ZxNo/s400/ScreenHunter_01+Dec.+30+11.08.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Buddy System - Memory Hole Searching Strategy</td></tr>
</tbody></table><br />
<br />
<br />
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.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-61846018495083696012011-12-26T19:01:00.000-08:002011-12-26T19:01:57.485-08:00Red Hat Realtime Tuning Guide<a href="http://docs.redhat.com/docs/en-US/Red_Hat_Enterprise_MRG/1.3/html/Realtime_Tuning_Guide/index.html">http://docs.redhat.com/docs/en-US/Red_Hat_Enterprise_MRG/1.3/html/Realtime_Tuning_Guide/index.html</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMR8tRhKrfgedUB6sc9pKvYXI9cBO4fpK6HpbWkGg9-CjHt5FaoA_v-myoyNHACVI8f303AQ9MBFYTXnjGRj7WPBZ7d4Rqr67wQU_bxdAUsd21JOCB1OD4LcCR1VVWYvpchPKFUt6AxEs/s1600/ScreenHunter_01+Dec.+27+10.58.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="125" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMR8tRhKrfgedUB6sc9pKvYXI9cBO4fpK6HpbWkGg9-CjHt5FaoA_v-myoyNHACVI8f303AQ9MBFYTXnjGRj7WPBZ7d4Rqr67wQU_bxdAUsd21JOCB1OD4LcCR1VVWYvpchPKFUt6AxEs/s320/ScreenHunter_01+Dec.+27+10.58.gif" width="320" /></a></div>OS tuning can be another major factor which can make a difference in your high frequency trading system's performance.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-49935938780028353002011-12-14T18:43:00.000-08:002011-12-14T18:43:08.721-08:00Pros and cons of disabling C-STATE (and C1E)<blockquote><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;">For the BIOS to have full control of all the features of the newer cpus, they all need to be enabled.</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><br />
</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;">Maybe this will help (taken from another post):</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><br />
</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;">That was the case for older CPU's but the i3/i5/i7 benefit from both, SpeedStep is better for changing the multiplier/voltage but C State has additional benefits on the new Intel CPU's, instead of the whole CPU either being on/off/idle parts of the CPU can now be turned on/off or set to idle and this works in conjunction with intels Turbo Mode.</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><br />
</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;">So basically they did do the same job but there are benefits to having both on when it comes to the new i3/i5/i7 CPU's.</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><br />
</span><span class="Apple-style-span" style="font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;">you will want to set CxE Function to C6 to get these new benefits alongside having SpeedStep enabled (they can work independent of each other but its best to have both enabled, be warned though with newer EVGA BIOS's having CxE Function enabled will allow the higher Turbo Mode multipliers to kick in and could make your OC unstable, if this is the case disable CxE Function but you could keep SpeedStep enabled if it still works, on the X58 Classified the voltage part of SpeedStep does not work with a manually inserted Voltage, it does however still work on the E758 3X SLI board with a manually inserted vCore voltage, this is just due to the components used and how the boards are set-up due to the segments they are for, Classified being a primarily overclocking board when power saving features are secondary. There are still work around for the X58 Classifieds using the ECP, this should allow you to OC the CPU but use an AUTO voltage which would allow the voltage part of SpeedStep to work</span></blockquote> More details please find it at <a href="http://www.techsupportforum.com/forums/f15/pros-and-cons-of-disabling-c-state-and-c1e-559253.html">http://www.techsupportforum.com/forums/f15/pros-and-cons-of-disabling-c-state-and-c1e-559253.html</a> XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-8839408806133036612011-12-12T00:07:00.000-08:002011-12-12T00:10:31.603-08:00Understand OS Scheduling for better system performanceCurrent modern OS, which is interactive privileged over real-time privileged, normally adopt Round-Robin Scheduling strategy, which is more effective in allocating CPU resources to active processes than FCFS (First Come First Serve).<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKD0yvTIiqU9Q7tK8WUvlTPYmzq3nOGTEKDlycxAh_VPK2F7a3m09tvjd3DBbM_5_Ed9ZZyoWfxDr3vzUz-wzysw7kks7HduVX-4H2_B-pTAh5rLtqSC64JaOWTN6rLuyyLiAV6cX6Ylc5/s1600/ScreenHunter_01+Dec.+12+15.51.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="132" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKD0yvTIiqU9Q7tK8WUvlTPYmzq3nOGTEKDlycxAh_VPK2F7a3m09tvjd3DBbM_5_Ed9ZZyoWfxDr3vzUz-wzysw7kks7HduVX-4H2_B-pTAh5rLtqSC64JaOWTN6rLuyyLiAV6cX6Ylc5/s400/ScreenHunter_01+Dec.+12+15.51.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Round Robin Scheduling</td></tr>
</tbody></table><br />
For example as below picture which showing how the CPU is allocated to processes. The response time for P1, P2, P3, P4, and P5 are 30, 24, 42, 14, and 18 time units, respectively. The average response time is 25.6 time units,which is better than that (of 28.4) for FCFS scheduling. Nevertheless, RR scheduling leads to more context switches.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmAgBvUn1bME7hZDcG13OfcGJFFoXCiaSajc5IcKQzpat0g05zVlQ5MkS_G9UiemeYbNOFmQ2o3UaJX_9IIXpFiNJFyOVnK80lCk150asXnMUC4r15zCmRixZm4KCiQt1UrSINbXAsg8W0/s1600/ScreenHunter_02+Dec.+12+15.52.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="56" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmAgBvUn1bME7hZDcG13OfcGJFFoXCiaSajc5IcKQzpat0g05zVlQ5MkS_G9UiemeYbNOFmQ2o3UaJX_9IIXpFiNJFyOVnK80lCk150asXnMUC4r15zCmRixZm4KCiQt1UrSINbXAsg8W0/s400/ScreenHunter_02+Dec.+12+15.52.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Process CPU Allocation</td></tr>
</tbody></table>And please note that OS has a so-called Fair Share Scheduling among users and groups. To has a high priority process to gain more CPU time slices, it is better to have a user to only run this process. To better utilize the Round Robin Scheduling, time slices need to be carefully defined that the core logic of your process can be finished within a time slice that it will never scheduled out and wait again for next slices. In this way, your high frequency trading solutions can run more efficient and occupy more CPU power to finish its tasks.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-64570602122237890582011-12-08T18:11:00.000-08:002011-12-08T18:15:32.403-08:00Better utilize CPU L1 Cache & L2 Cache for Performance TuningTo better utilize CPU L1 Cache & L2 Cache for Performance Tuning, we need to understand a few important points:<br />
1. Cache and RAM like cache size and why cache is needed in modern CPUs. one fact is that CPU is much faster than memory speed that current system performance bottle neck is memory access and its PCIe BUS speed.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgODP3hFYkcK6en-K0a8l815skOPvkrXTK3_RSVMVoV2d1E1R3F4oq6aoqIubV1Ntaft8NQPFUa4ILZU7kKh2zDonhfJrxFntFbp4JuiKC4aPeGNLeXaqLVfQoi8Q8otV2pgOhTMB8S-sH7/s1600/ScreenHunter_02+Nov.+29+11.49.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="88" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgODP3hFYkcK6en-K0a8l815skOPvkrXTK3_RSVMVoV2d1E1R3F4oq6aoqIubV1Ntaft8NQPFUa4ILZU7kKh2zDonhfJrxFntFbp4JuiKC4aPeGNLeXaqLVfQoi8Q8otV2pgOhTMB8S-sH7/s400/ScreenHunter_02+Nov.+29+11.49.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-size: small;">CPU Cache & RAM Architecture</span></td></tr>
</tbody></table> 2. Cache Miss - <span class="Apple-style-span" style="font-family: sans-serif; line-height: 19px;">A cache miss refers to a failed attempt to read or write a piece of data in the cache, which results in a main memory access with much longer latency. There are three kinds of cache misses: instruction read miss, data read miss, and data write miss. details can refer to <a href="http://en.wikipedia.org/wiki/CPU_cache#Cache_miss">http://en.wikipedia.org/wiki/CPU_cache#Cache_miss</a> </span><br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">a research report on "Optimization Study for Multicores" by Muneeb Anwar Khan shows that how cache can be better utilized to achieve better system performance thus reduce latency. Please note Acumem is the profiling tool he used for identify the problematic codes.</span></span><br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">one simple example: look at the source code:</span></span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXxcvxy6KFVZVyZYdlDZVuuStUUG0JXiHWprX7vqZgGUP4CpJQ9T6SQnnbUcxlelsxjVraE99i7Xk3HdDxbswHPixpoad2xU3s5Jc8s1AoDSQD3PToOqoBZhPYIdIUwOs-5r7d8xiUVvSn/s1600/ScreenHunter_01+Dec.+09+10.01.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="225" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXxcvxy6KFVZVyZYdlDZVuuStUUG0JXiHWprX7vqZgGUP4CpJQ9T6SQnnbUcxlelsxjVraE99i7Xk3HdDxbswHPixpoad2xU3s5Jc8s1AoDSQD3PToOqoBZhPYIdIUwOs-5r7d8xiUVvSn/s400/ScreenHunter_01+Dec.+09+10.01.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-size: small;">Better utilize CPU L1 Cache & L2 Cache for Performance Tuning</span></td></tr>
</tbody></table><span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;"> </span><span class="Apple-style-span" style="line-height: 19px;">Problem 1:</span></span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">The report shows problem 1’s fetches to be 30.8% of all the memory fetches in this </span></span><span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">application, with a fetch utilization of 43.1% in the first highlighted statement. </span></span><span class="Apple-style-span" style="font-family: sans-serif; line-height: 19px;">The instruction stats show the misses to be 34% of all the cache misses in the </span><span class="Apple-style-span" style="font-family: sans-serif; line-height: 19px;">application, and fetch and miss ratio at 21.2%. Reducing the fetch and miss ratio would</span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">greatly help improve bandwidth issues. </span></span><br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif; line-height: 19px;"> </span><span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">Problem 2:</span></span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">The report points out at poor fetch utilization for the second highlighted statement.</span></span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">Having an identical miss and fetch ratio of 15.4%; it has an extremely poor fetch</span></span><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">utilization of only 12.8%. </span></span><br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;"> let us see the revised code based on the identification of 2 problems:</span></span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5z253dSRKbE7HS3UjDRbADZDOmTGLMtLJr8fBuQ-sENvMToQbkWqNS9740PTe1iQM2U1JziiEFLjaoSDho_Vn6ddah2ZxiqiMG_Tfvu6L5RV3mHXOexdjUBwZR4kQLc9zsG12V2Chuvyw/s1600/ScreenHunter_02+Dec.+09+10.05.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="247" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5z253dSRKbE7HS3UjDRbADZDOmTGLMtLJr8fBuQ-sENvMToQbkWqNS9740PTe1iQM2U1JziiEFLjaoSDho_Vn6ddah2ZxiqiMG_Tfvu6L5RV3mHXOexdjUBwZR4kQLc9zsG12V2Chuvyw/s400/ScreenHunter_02+Dec.+09+10.05.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-size: small;">Better utilize CPU L1 Cache & L2 Cache for Performance Tuning</span></td></tr>
</tbody></table><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">what is the performance improvement? with just a few simple modifications by eliminating the unnecessary cache of not-used data, the speedup is about 2.9X.</span></span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhR-BXLZrF3oni66LNa6Nyam1xC3cKeCFwFgo-Lf0-HZfCl1NMo8HAsyRBg5fsqUENYCleUUOR89KwM4CUuwXdOft6abc-yPMm-U5792NMTktky3y2u8cNaEE5iuz_b61m0o6lNt60-FsqH/s1600/ScreenHunter_03+Dec.+09+10.06.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="315" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhR-BXLZrF3oni66LNa6Nyam1xC3cKeCFwFgo-Lf0-HZfCl1NMo8HAsyRBg5fsqUENYCleUUOR89KwM4CUuwXdOft6abc-yPMm-U5792NMTktky3y2u8cNaEE5iuz_b61m0o6lNt60-FsqH/s400/ScreenHunter_03+Dec.+09+10.06.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-size: small;">Better utilize CPU L1 Cache & L2 Cache for Performance Tuning</span></td></tr>
</tbody></table><br />
<span class="Apple-style-span" style="font-family: sans-serif;"><span class="Apple-style-span" style="line-height: 19px;">By better utilizing CPU caches, a further low latency high frequency trading platforms can be achieved within the scope of CPU host itself. </span></span>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-25882876369964816962011-12-02T01:44:00.000-08:002011-12-02T01:44:41.426-08:00SSD Read/Write Performance<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBONoVj-39-vPJ7fbY7C5TZKFEedulz9Fgiwa87sVJHNBf0MOktxOeb89VnxHy8Sy9ToWx2IYruA3eCy9ixGMuWyAKieYnKyXkEwl2CKHAtUkagRrsgIKzh3GXozIxDJHvBGod8jjWncn1/s1600/ScreenHunter_01+Dec.+02+17.39.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="115" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBONoVj-39-vPJ7fbY7C5TZKFEedulz9Fgiwa87sVJHNBf0MOktxOeb89VnxHy8Sy9ToWx2IYruA3eCy9ixGMuWyAKieYnKyXkEwl2CKHAtUkagRrsgIKzh3GXozIxDJHvBGod8jjWncn1/s400/ScreenHunter_01+Dec.+02+17.39.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">SSD Read/Write Performance</td></tr>
</tbody></table>Information get from <a href="http://www.tomshardware.com/reviews/best-ssd-price-per-gb-ssd-performance,2942.html">http://www.tomshardware.com/reviews/best-ssd-price-per-gb-ssd-performance,2942.html</a><br />
<br />
One random read from SSD takes about 20 to 50 micro-seconds. Hopefully it can be much faster in near future to allow CPU OS to read/write with SSD like it is a bit slower RAM.XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-63265600140578347752011-11-27T22:23:00.000-08:002011-11-27T22:23:45.411-08:00Cash Cow - High-Frequency Trading - The Daily Show With Jon Stewart<table cellpadding="0" cellspacing="0" height="340" style="background-color: whitesmoke; color: #333333; font: normal normal normal 11px/normal arial; width: 512px;"><tbody>
<tr style="background-color: #e5e5e5;" valign="middle"><td style="padding: 2px 1px 0px 5px;"><a href="http://www.thedailyshow.com/" style="color: #333333; font-weight: bold; text-decoration: none;" target="_blank">The Daily Show With Jon Stewart</a></td><td style="font-weight: bold; padding: 2px 5px 0px 5px; text-align: right;">Mon - Thurs 11p / 10c</td></tr>
<tr style="height: 14px;" valign="middle"><td colspan="2" style="padding: 2px 1px 0px 5px;"><a href="http://www.thedailyshow.com/watch/wed-september-30-2009/cash-cow---high-frequency-trading" style="color: #333333; font-weight: bold; text-decoration: none;" target="_blank">Cash Cow - High-Frequency Trading</a></td></tr>
<tr style="background-color: #353535; height: 14px;" valign="middle"><td colspan="2" style="overflow: hidden; padding: 2px 5px 0px 5px; text-align: right; width: 512px;"><a href="http://www.thedailyshow.com/" style="color: #96deff; font-weight: bold; text-decoration: none;" target="_blank">www.thedailyshow.com</a></td></tr>
<tr valign="middle"><td colspan="2" style="padding: 0px;"><embed allowfullscreen="true" allownetworking="all" allowscriptaccess="always" bgcolor="#000000" flashvars="autoPlay=false" height="288" src="http://media.mtvnservices.com/mgid:cms:item:comedycentral.com:250806" style="display: block;" type="application/x-shockwave-flash" width="512" wmode="window"></embed></td></tr>
<tr style="height: 18px;" valign="middle"><td colspan="2" style="padding: 0px;"><table cellpadding="0" cellspacing="0" height="100%" style="margin: 0px; text-align: center;"><tbody>
<tr valign="middle"><td style="padding: 3px; width: 33%;"><a href="http://www.thedailyshow.com/full-episodes/" style="color: #333333; font: 10px arial; text-decoration: none;" target="_blank">Daily Show Full Episodes</a></td><td style="padding: 3px; width: 33%;"><a href="http://www.indecisionforever.com/" style="color: #333333; font: 10px arial; text-decoration: none;" target="_blank">Political Humor & Satire Blog</a></td><td style="padding: 3px; width: 33%;"><a href="http://www.facebook.com/thedailyshow" style="color: #333333; font: 10px arial; text-decoration: none;" target="_blank">The Daily Show on Facebook</a></td></tr>
</tbody></table></td></tr>
</tbody></table><br />
Get some fun with the high frequency trading topic ...XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-24978603314349919452011-11-23T17:07:00.001-08:002011-11-29T05:51:00.038-08:00FastFlow - the new multithreading framework with Atomic Queues<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">For the solution of achieving high frequency trading, lock free queues can help to increase the message transfer speed between threads while reduce the performance jitter as well. </div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">While we talks about so-called lock free mechanisms, Atomic Queue should be the first choice we considered.</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">However please note that Atomic operation is not really lock-free otherwise there is no data safety between threads. Atomic operation achieves lock and unlock functionality by using CPU kernel's feature that it will only process a word size memory at a time, which is exactly the size of integer. </div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">there are many sample atomic queues implementation in the www. we found that FastFlow is the best one which can provide directly the atomic queues as well as multi-threading framework which can help to enforce the proper software architecture design. </div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">the better part is that FastFlow is free to use and open sourced project, which will be actively maintained and tested by a group of users.</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-bottom: 0.5em; margin-left: auto; margin-right: auto; padding-bottom: 6px; padding-left: 6px; padding-right: 6px; padding-top: 6px; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNPmRuGRllzvolimDPuIZXvF7K7gDKbfiF5WugCNXg5V-cYfQFTVrwQXhmJex7D3uHNiQY0S6VpZqsi2cRpE9bIcWRRy8CkJAD5TA0uq2GGf41JhYs8S5yz9ex22q5CbXCOpYkBbTezUU/s1600/278239.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNPmRuGRllzvolimDPuIZXvF7K7gDKbfiF5WugCNXg5V-cYfQFTVrwQXhmJex7D3uHNiQY0S6VpZqsi2cRpE9bIcWRRy8CkJAD5TA0uq2GGf41JhYs8S5yz9ex22q5CbXCOpYkBbTezUU/s400/278239.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; padding-top: 4px; text-align: center;">FastFlow architecture design</td></tr>
</tbody></table><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-bottom: 0.5em; margin-left: auto; margin-right: auto; padding-bottom: 6px; padding-left: 6px; padding-right: 6px; padding-top: 6px; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5yXC1HqRgbgEVL5WiX3Ez6RgEDEFMyBnB9vOvFF0Wtf6x9689Oy77ZtH_WZC7S8fULbylf2TQ0XS0sRYwQc9snL_HLH_kdih_TbStY_7rM_q0pBHiwX9Tatzf99QmOUGX3btxR5FTRGU/s1600/236792.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5yXC1HqRgbgEVL5WiX3Ez6RgEDEFMyBnB9vOvFF0Wtf6x9689Oy77ZtH_WZC7S8fULbylf2TQ0XS0sRYwQc9snL_HLH_kdih_TbStY_7rM_q0pBHiwX9Tatzf99QmOUGX3btxR5FTRGU/s400/236792.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; padding-top: 4px; text-align: center;">FastFlow Features</td></tr>
</tbody></table><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">for more details, you can go to its sourceforge page: <a href="https://sourceforge.net/projects/mc-fastflow/">https://sourceforge.net/projects/mc-fastflow/</a></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com2tag:blogger.com,1999:blog-6110650036681157430.post-35485358272301057982011-11-17T17:50:00.001-08:002011-11-17T17:50:32.878-08:00Performance of Memory Copy between Host and Device with NVIDIA cardsPerformance of NVIDIA Geforce 8600<br />
<ul><li>CudaMemcpyHostToDev=18 microseconds</li>
<li>CudaMemcpyDevToHost=23 microseconds </li>
</ul><br />
Performance of NVIDIA GTX 580<br />
<ul><li>CudaMemcpyHostToDev=6 microseconds</li>
<li>CudaMemcpyDevToHost=8 microseconds</li>
</ul><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">As we can see that NVIDIA new GPGPU cards like GTX series with FERMI memory architecture is much faster by itself than old NVIDIA crds like Geforce series. </div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-36371541171541130012011-11-14T22:01:00.001-08:002011-11-15T00:02:18.663-08:00NVIDIA GPU Fermi Memory Hierarchy Review<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQQPEaG1aGP-VH5mw02TWTXz459VJ9VcixZxnUuTp-Yj2NnoSGc-5DQmN031PM0Rqbg6PlS8OPkAuH5CcPKWnqZNSAmnN9VzQ-3UQDWwEsAuVUwAoS9uzR4-GvIR-DdMKgZoh0og6-oPg/s1600/ScreenHunter_01+Nov.+15+14.34.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="281" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQQPEaG1aGP-VH5mw02TWTXz459VJ9VcixZxnUuTp-Yj2NnoSGc-5DQmN031PM0Rqbg6PlS8OPkAuH5CcPKWnqZNSAmnN9VzQ-3UQDWwEsAuVUwAoS9uzR4-GvIR-DdMKgZoh0og6-oPg/s400/ScreenHunter_01+Nov.+15+14.34.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-size: small;">NVIDIA GPU Fermi Memory Hierarchy</span></td></tr>
</tbody></table><br />
<span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Local storage</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><br />
<ul><li><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Each thread has own local storage</span></li>
<li><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Mostly registers (managed by the compiler)</span></li>
</ul><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"> </span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Shared memory / L1</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><br />
<ul><li><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Program configurable: 16KB shared / 48 KB L1 OR 48KB shared / 16KB L1</span></li>
<span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">
<li>Shared memory is accessible by the threads in the same threadblock</li>
<li>Very low latency</li>
<li>Very high throughput: 1+ TB/s aggregate</li>
</span></ul><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">L2</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><br />
<ul><li><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">All accesses to global memory go through L2, including copies to/from CPU host</span></li>
<span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"> </span></ul><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">Global memory</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
<ul><li>Accessible by all threads as well as host (CPU)</li>
<li>Higher latency (400-800 cycles)</li>
<li>Throughput: up to 177 GB/s</li>
</ul></span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;"><br />
</span><span class="Apple-style-span" style="color: #222222; font-family: Arial, Helvetica, 'Nimbus Sans L', sans-serif; font-size: 13px; line-height: 15px;">If Share Memory / L1 can be used properly, the speed up can be much greater.</span>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0tag:blogger.com,1999:blog-6110650036681157430.post-88353490046445457182011-11-14T19:37:00.000-08:002011-11-14T19:38:43.609-08:00High-frequency trading: Good, bad or just different? - Technology - Futures Magazine<a href="http://www.futuresmag.com/Issues/2011/May-2011/Pages/Highfrequency-trading-Good-bad-or-just-different.aspx?page=1#.TsHeTswcIeg.blogger">High-frequency trading: Good, bad or just different? - Technology - Futures Magazine</a>:<br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif; font-size: small;">Mike O’Hara has interviewed scores of traders, connectivity providers, academics and exchange operators for his web site, the High Frequency Trading Review. He always opens his interviews with the same question: "What is <a href="http://www.blogger.com/Issues/2011/May-2011/Pages/Algo-trading-in-the-liquidity-mirage.aspx" target="_blank" title="">high-frequency trading </a>(HFT)?"</span><br />
<div align="justify" dir="ltr"><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif; font-size: small;">He never gets the same answer twice.</span></div><div align="justify" dir="ltr"><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif; font-size: small;">"The problem is that ‘high-frequency’ is a relative term," says O’Hara, a former floor trader at the London International Financial Futures Exchange (Liffe). "There are, however, some common threads in all definitions: It’s computer-driven; it generates a large number of orders in a short space of time; it’s dependent on low-latency, fast access to execution venues; its positions are held for short periods of time; it ends the day flat and it’s characterized by a high order-to-trade ratio." ...</span></div>XiongZhttp://www.blogger.com/profile/00821243854352295797noreply@blogger.com0