Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Accelerating by Idling

How Speculative Delays Improve Performance of Message-Oriented Systems

Aleksandar Prokopec

August 2017

Can the performance of a message-oriented system be improved by adding periods of idle execution?

Context switch

A period of time required for the scheduler to switch the CPU from one actor to another.

Spinning before a context switch potentially improves performance.

But not always.

An actor should delay the context switch only if it is likely that a message will arrive.

1. When should an actor spin?

2. How long should an actor spin?

There exists a simple upper bound.

d (delay) < c (context switch)

How to pick a delay in [0, c>?

Assume that P is the probability that a message arrives after some time d.

The actor also needs to occasionally sample P, i.e. spin several times to determine P.

We will assume that the actor samples with some probability φ.

Conclusion: given a probability p that a message arrives after δ, an actor should delay the context switch if:

δ < p

Delay sampling

Before the context switch:

1. With probability φ << 1, spin c time.

2. Record the message arrival times ti.

3. After collecting N samples, group the delay times into M buckets, and report the pairs δi, pi.

Speculative idling

Before a context switch:

1. Take the last reported M pairs δi, pi.

2. Pick the pair with minimal δi - pi.

3. If the difference is positive, wait δi time before context switching.

Sample size n?

For 95% confidence that the sampled probability P lies within 15% of its true value, we need n = 43.

For a sampling probability φ = 0.01, the expected number of activations per actor is ~4300.

But, actors are short-lived.

In many applications, most actors are not activated 4300 times.

How to obtain a sample more quickly?

Greedy sampling

Always set the sampling frequency φ to a value proportionate to the running best probability pi.

Intuition: If the message arrival probability P is high, then more frequent sampling is not detrimental.

I.e. an actor spends more time sampling, but it is likely that messages will arrive during sampling, saving a context switch.

If the message arrival probability P is low, then less frequent sampling is not detrimental.

I.e. it might take a long time to collect the sample, but it's unlikely that it will help anyway.

Greedy sampling

Initially, set the sampling frequency to some small value φ0. After each sampling, set the frequency to:

Greedy sampling

Expected number of messages before obtaining a sample:

Greedy sampling

Lower bound on speedup:


Savina Actor Suite

Shams and Sarkar, AGERE 2014


Thread Ring

Fork Join Throughput

Thank you!

Use a spacebar or arrow keys to navigate