Sub-millisecond Timer Precision

12433412

I understand the concept of sleep or delay are for good reasons frown upon by the Erlang community. Process.send_after/4 is an excellent alternative in most cases and allows for maximum 1ms precision (so does the underlying Erlang erlang:send_after call). Yet, 1ms is an eternity for my application.

I am writing time-aware code where events must happen NOT before some point in time. The precise delay amount is not crucial, it just needs to be roughly consistent and in the range of tens of microseconds at the most. The solution should also scale easily to 10k+ concurrent timers at the beginning.

There are a few options (that come to my mind) to achieve sub-millisecond timing:

The naive one would be a dirty nif & scheduler in combination with POSIX nanosleep. There is two issues with this approach. No form of sleep is scalable. When context switch happens, there is roughly 30 microsecond lag completely defeating the nano part of nanosleep.
Using standard nif and POSIX set_time. The nif is only called once to set up the timer. The Elixir process that started the nif starts receiving messages in consistent time intervals (either from a SIGEV_SIGNAL signal handler or another pthread within the nif). With 50 microsecond delay, however, this amounts to roughly 4M reductions on the timer process.
To implement a native send_after_microseconds only this time utilizing a ring buffer. At this point, this is the solution I am the most inclined towards as it would not spam nearly as many messages.
Introduce a yet another type of scheduler to Erlang dedicated to time critical operations.

Has anyone faced a similar problem? Any hints as in efficiency or further options would be highly appreciated! Below is the preliminary code for option 2.

Cheers,

Martin

defmodule Clock do
  use GenServer
  require Logger

  @on_load :load_nifs

  def load_nifs() do
    :ok = :erlang.load_nif('priv/c/clock', 0)
  end

  def start_link(_arg) do
    GenServer.start_link(__MODULE__, :ok, name: Clock)
  end

  def send_after(pid, term, ticks) do
    GenServer.cast(Clock, {:send, pid, term, ticks})
  end

  def get_time() do
    GenServer.call(Clock, :get_time)
  end

  def init(_arg) do
    Logger.debug("starting clock")
    Process.flag(:priority, :high)
    send_every(:tick, 50)
    {:ok, {0, []}}
  end

  def handle_info(:tick, {tick, []}) do
    {:noreply, {tick + 1, []}}
  end

  def handle_info(:tick, {tick, [head | tail]}) do
    Enum.each(head, fn {pid, term} -> send(pid, {tick, term}) end)
    {:noreply, {tick + 1, tail}}
  end

  def handle_cast({:send, pid, term, ticks}, {tick, buffer}) do
    new_buffer =
      case length(buffer) - ticks do
        -1 ->
          buffer ++ [[{pid, term}]]

        rem when rem < 0 ->
          buffer ++ List.duplicate([], -1 - rem) ++ [[{pid, term}]]

        _ ->
          List.update_at(buffer, ticks, &(&1 ++ [{pid, term}]))
      end
      
    {:noreply, {tick, new_buffer}}
  end

  def handle_call(:get_time, _from, {tick, _} = status) do
    {:reply, tick, status}
  end

  defp send_every(_term, _micros) do
    raise "clock NIF library not loaded"
  end
end

14 comments

#nif #timer #dirty-scheduler

4 5949 14

2019-01-28 12:47:53 UTC

Showing Posts 14 to 5

Show Best Posts
Show All (oldest first)
Show All (newest first)

12433412

This looks like a load of context switching going on. They are usually behind the clock_gettime call. Before setting a timeout, the current time is needed to calculate the timeout timestamp (e.g. nanosleep will always call that function first). I have seen online benchmarks that revealed the strong correlation between context switching and the lag. Given you can hardware-bind and dedicate a single core to the timer process, it should be possible to achieve outstanding results.

I actually found a way around this setting an interval on the timer and handling the SIGEV_SIGNAL interrupt. The clock_gettime calls are avoided and the performance is much more consistent. Yet, such repetitive timer is rarely useful I’d guess…

Post #14

12433412

The timer.c is very interesting reading indeed. I am tempted to hack the timeout facility and bump the slot length to 1μs and see what it does (besides breaking all time-related APIs ). My guess is that the timer wheel would introduce quite some load on the CPU compared to 1ms slots but I might be wrong.

I have no need for ns precision. Tens of microseconds are fine for my case. Stepping down to milliseconds would, however, introduce an inherent throughput issue as timeouts are part of nearly every operation within the app.

Again, many thanks for great pointers!

Post #13

massimo

When I was writing micro_timer first thing I tried was a C implementation of the sleep function.

I’ve tried almost everything, from setting a timeout to select and kevent to Posix timer_* functions, none of them worked reliably.

From my measurements, without spinlocks, you can’t get consistent sub-millisecond timings, to the point that waiting 1 million times for 1 microsecond (should be a second) takes almost 2 seconds.

The graph below shows the average difference between the timeout and the time it actually took to return.
The results are computed from 50 thousands samples, the timeout was set randomly from 1 to 65.535 microseconds (65ms).
The average deviation for the C implementation is 2.509ms, 11.4%.
But the worst case is 10x off.

The three implementation tested are

C uses select with a timeout
Ex0 waits timeout - 1ms and loops for a maximum of 1ms
Ex1 waits timeout - 2ms and loops for a maximum of 2ms

If you don’t need consistent absolute precision, any of the C implementations is good enough and they roughly work the same way.

Post #12

garazdawi

Erlang Core Team

Sleeping in poll or on a futex already supports nanosecond resolution if the platform supports it. We use it when a scheduler decides that it needs to sleep a fraction of a millisecond before the timer would fire. i.e. timer should fire at 5ms, but scheduler decides to sleep at 2.545 ms.

What would need to be done is to change the resolution of the timer wheel that dispatches timeouts, and of course expose the APIs.

Regarding which API would be the best to use, I’ve not really experimented all that much. clock_gettime in virtualized environments does have problems, but when running native it usually works good enough.

I think that in general though if you need nanosecond accuracy of your timers, linux may not be the operating system to use.

Post #11

12433412

Kudos for sharing your expert knowledge with us @garazdawi

Is there an example how to use timerfd_create to increase the resolution?

What would it encompass to implement the erlang:send_after(Time, Dest, Msg, Unit, Options) function where Unit is the Erlang time_unit()?

From what I gathered from etht_event.c and erl_poll.c is that it might be the matter of passing the desired ethr_sint64_t timeout value. I’m a bit confused with the the usage of both timeval and timespec supporting microseconds and nanoseconds respectively though.

My last concern is context switches and whether timerfd_create is able to deal with the issue gracefully somehow abstracting the timer into a file. My local benchmarks (along with my online research) suggest that the POSIX get_time function is highly susceptible to context switches being the main reason behind functions as nanosleep rarely being able reach anything near nanosecond precision.

But I have the feeling my understanding of the matter went in a completely wrong direction some long long time ago…

Post #10

massimo

Thanks for the clarification!
I was looking exactly for that, you saved me a lot of work!

My use case was correctness, I needed to generate exactly 60fps (or 90fps, or 120fps) and it can’t be accomplished with ms alone.

My implementation is very naive, it’s ok if you have few timers running and don’t care about wasting some CPU cycle or if you use it as a source of time, as a clock, like in MIDI sync.

Post #9

garazdawi

Erlang Core Team

erts_milli_sleep is only used in testing and on operating systems without a monotonic time source.

What is used to sleep is either futex or WaitForSingleObject with some spinning done around it.

This is the relevant code for unix: otp/erts/lib_src/pthread/ethr_event.c at master · erlang/otp · GitHub.

When sleeping in poll, timerfd_create(timerfd_create(2) - Linux manual page) is used to increase the resolution of the timer when triggered.

Post #8

massimo

shameless plug

I wrote a library with the same api of :timer but with a resolution in microseconds

it’s called micro_timer

I did some investigations before writing my own module and I think the relevant snippet of the Erlang sleep implementation is this one

    int
erts_milli_sleep(long ms)
{
    if (ms > 0) {
#ifdef __WIN32__
  Sleep((DWORD) ms);
#else
  struct timeval tv;
  tv.tv_sec = ms / 1000;
  tv.tv_usec = (ms % 1000) * 1000;
  if (select(0, NULL, NULL, NULL, &tv) < 0)
      return errno == EINTR ? 1 : -1;
#endif
    }
    return 0;
}

Sleep for win32 is defined as

void Sleep(
  DWORD dwMilliseconds
);

It only accepts milliseconds

There is a win32 implementation of the select function that take microseconds, but it’s in Winsock2 API that are supported only from Windows Vista onward.

One could try to compile ERTS using a sleep function that supports microseconds, but I guess it would break a lot of existing software.

It should also be simple enough to write a NIF that supports sleeping for microseconds, once you have the sleep function, you can build all the other functionalities around it (it’s exactly what I did in my library, except the NIF part).

EDIT:
for clarity" sleep in Erlang is implemented using the timeout for receive

-spec sleep(Time) -> 'ok' when
      Time :: timeout().
sleep(T) ->
    receive
    after T -> ok
end.

the snippet I was referring to is what I believe is the low level C implementation.

Post #7

devonestes

I believe the 1ms resolution is the lowest common (reliable) denominator of all the platforms the BEAM runs on. It’s possible to go use a much smaller resolution on most platforms, but not all of them, unfortunately.

Post #6

12433412

RE: Custom scheduler, better don’t. In my opinion anyway, not a strictly factual advice.

IMHO: I believe the 1ms resolution stems from above mentioned soft-realtimedness. To my knowledge, the scheduler does regular checks against system time (erlang time with ns resolution) and forwards the messages that are due. I believe the 1ms was something they were able to - at least remotely - guarantee. My guess is the scheduler could go with higher resolution without such guarantees…