A better time.After()

[Gustavo Niemeyer]

[This was sent to golang-dev last night, but I likely misunderstand
its purpose (never got replies to any thread there). Sending that to
golang-nuts now.]

Greetings,

Today someone was complaining over IRC about the fact that the
straightforward way to create timeouts, with time.After(), takes
considerable resources to run. The argument was based on the fact
that there's one goroutine per After() call, and that it stays alive
for the duration of the timeout, which means it can go up fairly
easily depending on what's being done.

It then occurred to me that creating some logic to avoid that behavior
should be fairly easy with the current infrastructure. The approach
works by queueing up events and starting a processor to consume from
the queue. A new processor is only started, though, if the existing
processors are further ahead in the queue than necessary to process
the new event.

I've implemented that approach in the last couple of hours, and have
run some benchmarks, and even in the worst case scenario (with random
timeouts) it seems to work very well indeed, offering significant
improvements both in terms of speed and in terms of memory. To give
an idea, with an ideal scenario where a single timeout value is used,
running 10k After() calls in quick succession will spawn a single
goroutine, and consume around 3MB of memory total. The current
time.After() call will take 53MB in the same scenario, and will also
take about twice as long to set up (and 10k goroutines, obviously).

Here is the sample code:

http://pastebin.ubuntu.com/538857/

If that looks good, I'll prepare a proper code review later in the week.

--
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/blog
http://niemeyer.net/twitter

[roger peppe]

based on that same conversation, here's another version of the
same thing (attached), with O(log(n)) worst case behaviour and arguably
simpler code.

i don't know whether it's ok for the time package to depend
on container/heap, but this assumes that it is. importing the heap
code is straightforward otherwise.

[Gustavo Niemeyer]

Hey Roger,

> based on that same conversation, here's another version of the

I have to say I'm surprised that you came up with the *same*
algorithm. Must be a good idea. :-)

> same thing (attached), with O(log(n)) worst case behaviour and arguably
> simpler code.

Please note that this will likely have worse behavior in practice,
both due to the copying of the array, and also because in practice
events will tend to be added with a limited set of timeouts rather
than random, which means they'll usually be appended at the end rather
than in a random location.

Either option looks like an improvement, though.

[Russ Cox]

On Thu, Dec 2, 2010 at 03:22, Gustavo Niemeyer <gus...@niemeyer.net> wrote:
> [This was sent to golang-dev last night, but I likely misunderstand
> its purpose (never got replies to any thread there).  Sending that to
> golang-nuts now.]

Sometimes not replying just means we're busy. :-)

We certainly need to do something like this eventually,
but it should not be restricted to time.After. All the time
functions could benefit from a central handling of timeouts
instead of parallel sleeps. Unfortunately I don't think you
can do it in pure Go. To really get it right you need to be
able to interrupt a sleep early, which requires lower level
access to the operating system threads than Go provides.
I think the eventual solution will have to be in package runtime.

This might be a good interim solution.

Russ

[Gustavo Niemeyer]

> Sometimes not replying just means we're busy.  :-)

Cool, wasn't intended as a pressure sign. It just occurred to me that
development discussions have been happening in golang-nuts as well,
and that code reviews tend to flow very quickly, so it might just be
the usual practice.

> We certainly need to do something like this eventually,
> but it should not be restricted to time.After.  All the time
> functions could benefit from a central handling of timeouts
> instead of parallel sleeps.  Unfortunately I don't think you
> can do it in pure Go.  To really get it right you need to be
> able to interrupt a sleep early, which requires lower level
> access to the operating system threads than Go provides.
> I think the eventual solution will have to be in package runtime.
>
> This might be a good interim solution.

I was also pondering about this as a less contentious improvement over
what exists today, since it requires no other dependencies and/or
runtime changes on top of what exists today.

The original approach I was telling Roger about yesterday uses
select/epoll with a pipe as a mechanism of interruptible sleeping
(some hints about this already in net/fd_*.go), but I'm not sure if
this looks like a good long term plan or not. How does that feel to
you?

[Andrew Gerrand]

I like the general approach. Roger's implementation reads better to my eyes.

It would be useful to extend this code to support time.Tickers.

On 3 December 2010 03:03, Gustavo Niemeyer <gus...@niemeyer.net> wrote:
> Cool, wasn't intended as a pressure sign.  It just occurred to me that
> development discussions have been happening in golang-nuts as well,
> and that code reviews tend to flow very quickly, so it might just be
> the usual practice.

You're more likely to get the serious attention of people who actually
write code for the project by posting to golang-dev. :-)

Andrew