NFD » ndn-cxx

This task should be moved to ndn-cpp-dev, because Task #1290 stage 1 imports time structs and Scheduler from the library.

Quick Question

What is the lowest resolution of time required for the timer? Is seconds good enough?

Or would there be timer intervals requested for minutes, hours days?

I am using the highest resolution of timer as milliseconds (1ms).

I suggest microseconds granularity for Scheduler. Milliseconds isn't enough for some strategy operations.

time::Duration is in nanoseconds. Scheduler should round up to a microsecond.

Do not make assumption on the maximum duration. Scheduler should support any duration that could be represented by time::Duration and doesn't cause time::Point to overflow.

I gave an idea of how to integrate timeouts.c in note-4. Why doesn’t it work?

It would work Junxiao. But...

Comment at line 476 of timeout.c file states:

This might return a timeout value sooner than any installed timeout if
only higher-order wheels have timeouts pending. We can only know when to
process a wheel, not precisely when a timeout is scheduled.

This is the comment for timeouts_int() which is called by timeouts_timeout()

I intend to optimize this.

Assume after bit-wise segmentation of our time value, the highest resolution wheel is microseconds (1000us clock) and the next lower resolution wheel is milliseconds (1000ms clock). If the highest wheel has no timeouts and the next available timeout is for 200ms, then we would unnecessarily tick 200 times at 1ms. An optimization would be to directly set a deadline_timer to 200ms.

Hope my understanding is correct.

This explanation is convincing. We are looking forward to your implementation with reasonable comments including a citation of the paper or other references.

I have a thought, which would allow to resolve my problem of submitting the code right now. Instead of replacing current scheduler implementation, can this code be modified to provide an alternative version of the scheduler that applications can choose?

I propose the following. We would have two scheduler classes:

• BasicScheduler (the current one)
• WheelScheduler (this one).

There should also be a typedef BasicScheduler Scheduler; so existing applications happy with the scheduler if they don't care to choose.

Library itself uses Scheduler.
How does an app pick which Scheduler is used by library?

• traffic-generator-client can have thousands of timers, and needs WheelScheduler.
• ndn-tlv-peek has few timers, and needs BasicScheduler.

Should we make a Scheduler base class?

Or, will all library modules that rely on Scheduler become templates?

We could do a trick similar to BOOST_TEST. The default is the simple implementation, but if a special macro is defined, then specific version is selected... Though it would work only with header-only things...

Baseclass implies that we will use virtual calls for scheduling events.. Not sure how big deal is this for scheduler, could be acceptable.

Using macro is also risky unless the library is entirely header-only.

Any .cpp in the library will have its Scheduler fixed at library compile time.

OK. Let's do interface, but name "Scheduler" should be kept to refer to basic scheduler.

What about something like:

         BaseScheduler
           ^       ^
          /         \
         /           \
        /             \
 BasicScheduler     WheelScheduler
 (aka Scheduler)

Do we really need two Schedulers which serve the same purpose in the library?

The current scheduler implementation has tiny memory benefit over the new timing wheel implementation. Is this why we are including two variants of Scheduler?

We have run performance tests on both implementations and the timing wheel provides an order 10 performance better than the existing implementation (performance measured as cumulative timer fire slippage in case of 10000 timers requested).

As all the API calls are designed alike, there should not be any harm in including this as a replacement.

20140612 conference call discusses merging the new scheduler.

Alex says he don't like the code because it's too complicated.
Lixia points out that "too complicated" is not a valid reason of rejecting the code.

Alex needs to find out whether the new scheduler would cause performance or other issues; any findings should be replied to this issue.
Otherwise, we should move forward.

The code hasn't been tested with all applicarions that use schdulder.

In particular, applications remove events within the scheduled event. My brief look at the code suggests that this would cause segfault (there should be a test case in the latest code for that).

I have uploaded a scenario to evaluate scheduling performance (just scheduleEvent part) for different sizes of "batches": http://gerrit.named-data.net/#/c/913/

Here are the results I have on my machine (total number of events scheduled is 1,000,000; time includes overhead of creating and destroying Schedulers---this is a "little" unfair comparison)

Old scheduler
Batch of 10 events
Finished in 0.408565 seconds
Batch of 100 events
Finished in 0.354955 seconds
Batch of 1000 events
Finished in 0.345248 seconds
Batch of 10000 events
Finished in 0.3624 seconds
Batch of 100000 events
Finished in 0.506156 seconds
Batch of 1000000 events
Finished in 0.532927 seconds


==================

New scheduler
Batch of 10 events
Finished in 35.6839 seconds
Batch of 100 events
Finished in 3.78675 seconds
Batch of 1000 events
Finished in 0.615329 seconds
Batch of 10000 events
Finished in 0.303142 seconds
Batch of 100000 events
Finished in 0.301545 seconds
Batch of 1000000 events
Finished in 0.323886 seconds

I have other comments about the code, but in any case I don't see 10x improvement. Just scheduling has significant disadvantage with small batches of events (I guess scheduler initialization takes a lot of time) and less then 2x improvement for 1,000,000 scheduled events and the same for 100,000 events. Other parts of the scheduler are the same or more expensive in the optimized scheduler.

Here are the results with the removed Scheduler create/destroy overhead:

Old scheduler
Batch of 10 events
Finished in 0.267596 seconds
Batch of 100 events
Finished in 0.244033 seconds
Batch of 1000 events
Finished in 0.252088 seconds
Batch of 10000 events
Finished in 0.262658 seconds
Batch of 100000 events
Finished in 0.280631 seconds
Batch of 1000000 events
Finished in 0.312653 seconds


==================

New scheduler
Batch of 10 events
Finished in 1.18234 seconds
Batch of 100 events
Finished in 0.263648 seconds
Batch of 1000 events
Finished in 0.242176 seconds
Batch of 10000 events
Finished in 0.222456 seconds
Batch of 100000 events
Finished in 0.222679 seconds
Batch of 1000000 events
Finished in 0.218744 seconds

ndn-cxx library is mainly used by an app.
The number of timers in an app is around 100.
The new Scheduler performs worse than the old Scheduler in this scenario.

Improvements are needed before it can replace the old Scheduler for general app usage.

Btw. A "little bit" delayed comment, but want to correct statements made in note-3: the old scheduler has exactly one timer event scheduled. In this regard, there is no difference between old and new schedulers.

Other comments about the current implementation of the optimized scheduler (some of which could have contributed to reduced performance):

• Implementation in timeout.c has a number of optimizations, which are not present in the current implementation. I got the problem with unnecessary firing of the timer event in some cases when granularity of the Scheduler is different from the granularity of the scheduled events. Though I'm not sure if it is a major problem.

• WHY all calculations are not the logical shifts??? Division is way slower than any shift operation and there is no reason to split into mus, ms, s.

• There is very confusing large amount of conversions from steady_clock::TimePoint to Scheduler::TimePoint. Why there is a need to use "absolute time" (since clock's epoch)? I believe everything is relative to the current time point, unless I missing something.

• duration_cast should be more efficient and more straightforward way to request the desired granularity. Also, this should probably be private to the TimePoint.

Alex Afanasyev wrote:

I have uploaded a scenario to evaluate scheduling performance (just scheduleEvent part) for different sizes of "batches": http://gerrit.named-data.net/#/c/913/
...
I have other comments about the code, but in any case I don't see 10x improvement. Just scheduling has significant disadvantage with small batches of events (I guess scheduler initialization takes a lot of time) and less then 2x improvement for 1,000,000 scheduled events and the same for 100,000 events. Other parts of the scheduler are the same or more expensive in the optimized scheduler.

Each scheduler needs to create and initialize 6000(or 7000) slots, that means 24KB(6000 * 4 Byte) memory. So the number of schedulers should not be too much.

For PerTickBookkeeping:
The average cost per unit time for an average of N timers is:

N * c * m / T

c: the cost of reposition timers(heavily depends on the density of timers)

m: the total number of levels in the hierarchy.

T: average timer interval(from start to stop or expiry)

The design of the wheel-scheduler relies heavily on the number of timers. If the number of timers in an app is around 100, the number of wheels and slots in the wheel-scheduler MUST redesign.

Incidentally, if the number of timers is around 100, I think an non-hierarchy scheduler(eg. hash table with unsorted list in each bucket) will be more simple and faster.

After reading the book NETWORK ALGORITHMICS, I realize timing wheel based schedule isn't intended for application usage.

It is intended to be implemented in the kernel: a hardware clock interrupts CPU, and the kernel executes per-tick bookkeeping.

A timing wheel in userspace causes a kernel timer to run userspace per-tick bookkeeping at every time unit, which is otherwise avoidable.

I suggest this Task to be Abandoned.

I also would like to abandon this task. However, I would like to preserve the code somehow, but not sure how (just in case it will be useful for somebody else).