[Nfd-dev] Fwd: TimingWheel Implementation - Need Code Optimization Review

[Junxiao Shi]

---------- Forwarded message ----------
From: "Jerald Paul Abraham" <jeraldabraham at email.arizona.edu>
Date: Mar 15, 2014 4:47 AM
Subject: TimingWheel Implementation - Need Code Optimization Review
To: "Beichuan Zhang" <bzhang at cs.arizona.edu>, "Junxiao Shi" <
shijunxiao at email.arizona.edu>
Cc:

Hello Dr.Zhang & Junxiao,

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.

Here is a sample comparison result when each is tested against 10000 timers.
The value in *RED *is for the timing wheel implementation.
The value in *BLUE *is for the existing multiset based implementation.
These values are the *average number of nanoseconds by which every timer is
off* its expected fire time.

jeraldabraham at ndn1:~/src/timingwheel$ build/timingwheel
Timer Data Of 20000 Size
Average Off For 10000 Timers =* 1.65528e+08*
Timer Data Of 20000 Size
Average Off For 10000 Timers = *2.95907e+07*
jeraldabraham at ndn1:~/src/timingwheel$ build/timingwheel
Timer Data Of 20000 Size
Average Off For 10000 Timers = *1.76106e+08*
Timer Data Of 20000 Size
Average Off For 10000 Timers =* 2.86517e+07*
jeraldabraham at ndn1:~/src/timingwheel$ build/timingwheel
Timer Data Of 20000 Size
Average Off For 10000 Timers = *1.65347e+08*
Timer Data Of 20000 Size
Average Off For 10000 Timers = *3.01807e+07*

*The Reason:*
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.

*Why a code optimization review may help?*
Even the slightest optimization in the timing wheel data structure
manipulation operations can bring about visibly significant difference in
this timer off metric.
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.

Please let me know if we should go forward for this review.

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.


--
Jerald
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20140315/06f2ab77/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AScheduler.cpp
Type: text/x-c++src
Size: 29833 bytes
Desc: not available
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20140315/06f2ab77/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AScheduler.hpp
Type: text/x-c++hdr
Size: 4255 bytes
Desc: not available
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20140315/06f2ab77/attachment-0001.bin>