DedicatedThreadScheduler performance review

[JeffCyr]

This issue is about analyzing the DedicatedThreadScheduler to discuss about how it could be improved.

https://github.com/akkadotnet/akka.net/blob/cf7cd6f274cd56af6403afc640a038564dc4d03b/src/core/Akka/Actor/Scheduler/DedicatedThreadScheduler.cs

Summary of the actual implementation

The scheduler is implemented by a background thread and a ConcurrentQueue. The ConcurrentQueue is used as a message queue to send the scheduled work items to the scheduler's background thread.

The background thread is a while loop that:

• reads item from the message queue, add them in a List allWork
• iterate all work items in allWork to invoke the expired items
• sleep (defined by akka.scheduler.tick-duration)

Dedicated Thread vs Timer

If there are only a few instances of the scheduler, I think that the dedicated thread is the good approach. I don't see why you would need to have more than one in a process.

allWork data structure

The List is fairly inefficient since the scheduler has to iterate all work items every time. A heap structure should be a good match for this, it would be sorted by clock time and the scheduler would only have to check the head. The time complexity of the heap would be O(log n) for push and O(log n) for pop compared to O(1) for push and O(n) for pop for the List.

The optimal structure I can think of is a circular list of buckets with a resolution defined by tick-duration. The work items would be inserted in their appropriate bucket, push and pop to that structure would both be O(1). (To limit the size of the circular list, it should have one list with tick-duration resolution and another with a bigger resolution (e.g. 1 second))

Thread.Sleep vs Wake-up signals

With the current implementation, the thread wakes up every tick-duration to check if a work item expired. Depending on the work load, the scheduler could waste cpu cycles by waking up often when there is no expired work items.

Something like an AutoResetEvent could be used to wake up the thread only when it has actual work to do.

Execution of expired work items

With the current implementation, the work items are executed inside the scheduler's thread. This could potentially delay the execution of other work items. I think it should push the execution on the .Net ThreadPool and have an optional setting to execute a specific work item synchronously.

End note

Of course all this talk is theoretical, we should create a benchmark that mimics the expected work load in Akka.Net and try the various proposals.

[rogeralsing]

With the current implementation, the work items are executed inside the scheduler's thread. This could potentially delay the execution of other work items. I think it should push the execution on the .Net ThreadPool and have an optional setting to execute a specific work item synchronously.

Some background on this:
We used a scheduler that did run on the threadpool earlier, but it turned out that under heavy load, things like scheduled heart beats in akka-cluster did not fire at the correct time due to thread pool saturation.
Thus we moved the workload inside its own dedicated thread.
Java Akka also uses a dedicated thread for executing scheduled jobs.

Maybe we could extend the API to support dfferent setups, but that is the reason for doing it inline atm.

Great review by the way, I appreciate that.

[JeffCyr]

https://github.com/akka/akka/blob/f1abaa1c5e327b961222fcf986547a7474484b94/akka-actor/src/main/scala/akka/actor/LightArrayRevolverScheduler.scala

Looks like I reinvented the "wheel" here and the "circular list of buckets" data structure I was describing is formally called "Hierarchical Timing Wheels" and it's similar to what the scala implementation is using (Hashed Timing Wheels).
http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf

@rogeralsing The scala implementation uses ExecutionContext.execute to run their action. To transpose that to .Net, would it make sense to use TaskScheduler.Current with the possibility of explicitly setting it? (similar to Task.Factory.StartNew). The cluster heartbeats could explicitly use a SameThreadTaskScheduler or TaskScheduler.Default with TaskCreationOptions.ExecuteSynchronously.

Also, I just saw that cancellation is not implemented in the DedicatedThreadScheduler, looks like the IsCanceled check has been forgotten when executing an action.

[rogeralsing]

@JeffCyr

Cancellation is done using :

private void InternalScheduleOnce(TimeSpan initialDelay, Action action, CancellationToken token)
        {
            Action executeAction = () =>
            {
                if (token.IsCancellationRequested)
                    return;

It's embedded in the action that is scheduled.

[Aaronontheweb]

Closed

[Aaronontheweb]

Fixed - implemented these changes a while back.

[dhwed]

@Aaronontheweb

It doesn't look like the suggested performance improvements have been made to the DedicatedThreadScheduler yet. Is there a newer version of this class somewhere, or was there a confusion between the DedicatedThreadScheduler and the DedicatedThreadPool that was recently improved?

[Aaronontheweb]

@dhwed they've been made already - happened back in December.

[Aaronontheweb]

oh whoops, I see what you meant.

[Aaronontheweb]

You're right - I was confused about DedicatedThreadPool vs. DedicatedThreadScheduler. These have not been implemented on the scheduler.

[Aaronontheweb]

Adding a benchmark for the default IScheduler implementation, just so we can start measuring the performance of what we have now.

[Aaronontheweb]

Have some benchmark data for this on #2294

http://doc.akka.io/docs/akka/current/java/futures.html - bit of note about ExecutionContext from the Scala implementation; basically that wraps the default dispatcher, which would be the ThreadPoolExecutor in our case. We could do something similar, although that would require some API changes (new method overloads) since we don't have the benefit of implicit variables like Scala.

I think for the time being I'll give the underlying data structure the ability to specify which TaskScheduler it runs on and just provide it with the TaskScheduler.Default for now and see how that goes.