<div class="gmail_quote">---------- Forwarded message ----------<br>From: "Jerald Paul Abraham" <<a href="mailto:jeraldabraham@email.arizona.edu">jeraldabraham@email.arizona.edu</a>><br>Date: Mar 15, 2014 4:47 AM<br>
Subject: TimingWheel Implementation - Need Code Optimization Review<br>To: "Beichuan Zhang" <<a href="mailto:bzhang@cs.arizona.edu">bzhang@cs.arizona.edu</a>>, "Junxiao Shi" <<a href="mailto:shijunxiao@email.arizona.edu">shijunxiao@email.arizona.edu</a>><br>
Cc: <br><br type="attribution"><div dir="ltr">Hello Dr.Zhang & Junxiao,<div><br></div><div>I have completed the timing wheel implementation and have been working on its performance in the past week. But its performance does not appear to be as good as expected.</div>

<div><br></div><div>Here is a sample comparison result when each is tested against 10000 timers.</div><div>The value in <b><font color="#ff0000">RED </font></b>is for the timing wheel implementation.</div><div>The value in <b><font color="#0b5394">BLUE </font></b>is for the existing multiset based implementation.</div>

<div>These values are the <b>average number of nanoseconds by which every timer is off</b> its expected fire time.</div><div><div><br></div><div><font face="courier new, monospace">jeraldabraham@ndn1:~/src/timingwheel$ build/timingwheel</font></div>

<div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers =</font><b><font color="#ff0000"> <font face="arial, helvetica, sans-serif">1.65528e+08</font></font></b></div>

<div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers = </font><b><font color="#0000ff" face="arial, helvetica, sans-serif">2.95907e+07</font></b></div>

<div><font face="courier new, monospace">jeraldabraham@ndn1:~/src/timingwheel$ build/timingwheel</font></div><div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers = </font><b><font color="#ff0000" face="arial, helvetica, sans-serif">1.76106e+08</font></b></div>

<div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers =</font><b><font color="#0b5394"> <font face="arial, helvetica, sans-serif">2.86517e+07</font></font></b></div>

<div><font face="courier new, monospace">jeraldabraham@ndn1:~/src/timingwheel$ build/timingwheel</font></div><div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers = </font><b><font color="#ff0000" face="arial, helvetica, sans-serif">1.65347e+08</font></b></div>

<div><font face="courier new, monospace">Timer Data Of 20000 Size</font></div><div><font face="courier new, monospace">Average Off For 10000 Timers = </font><b><font color="#0b5394" face="arial, helvetica, sans-serif">3.01807e+07</font></b></div>

</div><div><br></div><div><b><u>The Reason:</u></b></div><div>The timing wheel implementation although designed to be tickless, uses vector based data structures to hold timer information. The wheels advance only when a fire/request/cancel of a timer occurs. But these vector based data structure management operations take up time and are slower than the existing multiset implementation.</div>

<div><br></div><div><b><u>Why a code optimization review may help?</u></b></div><div>Even the slightest optimization in the timing wheel data structure manipulation operations can bring about visibly significant difference in this timer off metric.</div>

<div>If it is therefore possible and we have time, then Junxiao could point out any optimizations in the code, it may prove to be beneficial. I am attaching the code for the implementation herewith.</div><div><br></div><div>

Please let me know if we should go forward for this review.<br></div><div><br></div><div>I can make the code available on gerrit but unless its benefit is verified, I think its not event worth of being a patchset for ndn-cpp-dev gerrit project. Please advice.</div>

<div><br></div><div><br></div><div>--</div><div>Jerald</div><div><br></div><div><br></div></div>
</div>