code review 4063043: time: allow cancelling of After events.

time: allow cancelling of After events.
Also simplify sleeper algorithm and poll
occasionally so redundant sleeper goroutines
will quit sooner.

[rog, 2011-01-19 11:09:11]

Hello r, niemeyer (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[niemeyer, 2011-01-19 13:03:07]

This looks interesting overall.

As a name, Stop seems fine, since that's already used by Ticker.
Event might perhaps be better named as Timer.

Regarding the change in After()'s prototype, I'd prefer to avoid it.
The reason why After() was introduced is exactly to support the use
case which this change will prevent (hg log -v -r 6480). Hopefully
the select statement will grow internal support for timeouts at some
point, but this is a nice stopgap for now.

Also, from a different angle, After() currently matches the prototype
of Tick(), and getting the functionality of After+Stop is easy
with AfterFunc.

[rog, 2011-01-19 13:10:52]

On 19 January 2011 13:03,  <n13m3y3r@gmail.com> wrote:
> This looks interesting overall.
>
> As a name, Stop seems fine, since that's already used by Ticker.
> Event might perhaps be better named as Timer.

yeah, maybe Timer is better.
i'll do that.

> Regarding the change in After()'s prototype, I'd prefer to avoid it.
> The reason why After() was introduced is exactly to support the use
> case which this change will prevent (hg log -v -r 6480). Hopefully
> the select statement will grow internal support for timeouts at some
> point, but this is a nice stopgap for now.
>
> Also, from a different angle, After() currently matches the prototype
> of Tick(), and getting the functionality of After+Stop is easy
> with AfterFunc.

not *quite* as AfterFunc always starts a new goroutine, whereas
After doesn't need to as it knows that it's writing to a buffered channel.
when events are being serviced very quickly, this could make a difference.

have you got an idea for a name for the two-valued After?

[niemeyer, 2011-01-19 13:32:19]

If events are being serviced very quickly there's no advantage
in stopping them in terms of resource consumption. They won't go
away in either case before the next garbage collection.

If they are being stopped very quickly, the routine won't run
with AfterFunc either.

> have you got an idea for a name for the two-valued After?

A possible interface might revolve around a NewTimer function.

E.g.

    t := NewTimer(ns)

Then, access to the channel, analogous to Ticker:

    <-t.C

After behaves exactly like Tick:

    return NewTimer(ns).C

[rog, 2011-01-19 13:32:57]

PTAL.

BTW one other possibility is to have After return a *Timer,
and to have the timer contain the channel (similar to Ticker).

then you'd do:

<-time.After(1e9).C

i'm slightly reluctant to do this, as it means the Timer type
uses an extra word of storage, and some people are talking
about having 100s of thousands of timers.
but maybe i should just bite the bullet.


On 19 January 2011 13:03,  <n13m3y3r@gmail.com> wrote:
> This looks interesting overall.
>
> As a name, Stop seems fine, since that's already used by Ticker.
> Event might perhaps be better named as Timer.
>
> Regarding the change in After()'s prototype, I'd prefer to avoid it.
> The reason why After() was introduced is exactly to support the use
> case which this change will prevent (hg log -v -r 6480). Hopefully
> the select statement will grow internal support for timeouts at some
> point, but this is a nice stopgap for now.
>
> Also, from a different angle, After() currently matches the prototype
> of Tick(), and getting the functionality of After+Stop is easy
> with AfterFunc.
>
>
> http://codereview.appspot.com/4063043/
>

[rog, 2011-01-19 13:42:36]

On 19 January 2011 13:32,  <n13m3y3r@gmail.com> wrote:
> If events are being serviced very quickly there's no advantage
> in stopping them in terms of resource consumption. They won't go
> away in either case before the next garbage collection.

i'm talking about the case where there's a very fast loop
with a long timeout.

this will quickly use very large quantities of memory:

     c := make(chan bool)
     go func(){
        for { c <- true }
     }()
     for {
         select {
         case <-time.After(300*1e9):
             log.Exitln("timeout")
         case <-c:
         }
      }


>> have you got an idea for a name for the two-valued After?
>
> A possible interface might revolve around a NewTimer function.
>
> E.g.
>
>    t := NewTimer(ns)
>
> Then, access to the channel, analogous to Ticker:
>
>    <-t.C
>
> After behaves exactly like Tick:
>
>    return NewTimer(ns).C

we had a similar idea, it seems.
i think i might do this.

[rog, 2011-01-19 14:20:10]

Hello r, niemeyer (cc: golang-dev@googlegroups.com),

Please take another look.

[rog, 2011-01-19 14:57:03]

here's an odd anomaly: running gotest -benchmarks . in
pkg/time results in all the concurrent benchmarks slowing
down *except* the Stop benchmark, which about triples
in speed (16056 to 5736 ns/op on my machine).

it seems to be due to lock contention, but why in this case only?

On 19 January 2011 14:20,  <rogpeppe@gmail.com> wrote:
> Hello r, niemeyer (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4063043/
>

[niemeyer, 2011-01-19 15:58:46]

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcode16
src/pkg/time/sleep.go:16: // the current time will be sent on C; otherwise
The current time won't be sent on C *when the Timer was created*.

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcode96
src/pkg/time/sleep.go:96: }
What happens when Stop is called twice and, more importantly, what happens with
all of the indexes in the heap once e.i gets pulled off?

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:109: return &Timer{}
Feels like this should panic instead of silently misbehaving.

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:120: if t0 > t && (t0 == forever || ns < maxSleepTime) {
There's a change being introduced here which looks
irrelevant to introducing Stop, and which should
probably be pushed in its own CL.

With this change the sleeper will busy wait and wake
up every second irrespective of the time requested,
instead of actually sleeping, so if there's a timer
scheduled for 10 minutes ahead, there will be a busy
loop taking resources from the system for no reason
for 10 minutes.

I personally prefer the original approach.

[rog, 2011-01-19 16:25:08]

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcode16
src/pkg/time/sleep.go:16: // the current time will be sent on C; otherwise
On 2011/01/19 15:58:46, niemeyer wrote:
> The current time won't be sent on C *when the Timer was created*.

Done.

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcode96
src/pkg/time/sleep.go:96: }
On 2011/01/19 15:58:46, niemeyer wrote:
> What happens when Stop is called twice and, more importantly, what happens
with
> all of the indexes in the heap once e.i gets pulled off?

The only way that heap can remove items from the heap is through
heap.Interface.Pop, which is implemented by timerHeap.Pop, which sets the index
to -1. All the indexes in the heap are kept up to date by timerHeap.Swap (made
easy as a nice consequence of the way that the heap polymorphism works).

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:109: return &Timer{}
On 2011/01/19 15:58:46, niemeyer wrote:
> Feels like this should panic instead of silently misbehaving.

it's not really misbehaving. if the user asks for a timer to go off 500 years
into the future, i think it's fair enough that it will never actually go off.
they'll never know :-)

http://codereview.appspot.com/4063043/diff/33001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:120: if t0 > t && (t0 == forever || ns < maxSleepTime) {
On 2011/01/19 15:58:46, niemeyer wrote:
> There's a change being introduced here which looks
> irrelevant to introducing Stop, and which should
> probably be pushed in its own CL.
> 
> With this change the sleeper will busy wait and wake
> up every second irrespective of the time requested,
> instead of actually sleeping, so if there's a timer
> scheduled for 10 minutes ahead, there will be a busy
> loop taking resources from the system for no reason
> for 10 minutes.
> 
> I personally prefer the original approach.

i did mention this in the CL description.
waking up every second is not exactly busy-waiting and the actual interval is
configurable. maybe once every 5s would be more acceptable.

the problem is that if many events are being manipulated with long deadlines,
many goroutines will remain around (as actual OS threads) until the original
deadline has expired, even if the event has been stopped. it seems reasonable to
me that a sleeper occasionally checks to see if it has been cancelled. in the
future, either Go will provide an interface that allows a goroutine stuck in
syscall.Sleep to be interrupted or timing will get integrated into select and
all this will go. either way i feel this is a reasonable interim solution.

[niemeyer, 2011-01-19 16:46:24]

> The only way that heap can remove items from the heap is through
> heap.Interface.Pop, which is implemented by timerHeap.Pop, which sets the
index
> to -1. All the indexes in the heap are kept up to date by timerHeap.Swap (made
> easy as a nice consequence of the way that the heap polymorphism works).

I see, that makes sense.

> it's not really misbehaving. if the user asks for a timer to go off 500 years
> into the future, i think it's fair enough that it will never actually go off.
> they'll never know :-)

So if the user application has a bug, you're saying you don't
mind to add another one.  panic() sounds appropriate.

> i did mention this in the CL description.
> waking up every second is not exactly busy-waiting and the actual interval is
> configurable. maybe once every 5s would be more acceptable.

Ok, let's call it dumb waiting then.  The actual interval is configurable
by you, who are coding it, not by the user.

Intervals will generally be taken from a set rather than selected randomly.
In a short period, the smallest interval regularly scheduled will dominate
the algorithm with a single goroutine, with no waste at all.

> the problem is that if many events are being manipulated with long deadlines,
> many goroutines will remain around (as actual OS threads) until the original

The deadline doesn't matter.. the clock moves forward either way.  If that
deadline is 10 minutes, the first call will schedule a goroutine for 10
minutes.  The second call will have a time of 10 minutes + 1ns, and will
not create any goroutines anymore, and that will continue forever.

I vote against changing the current algorithm and introducing a dumb loop
which polls involving a global lock irrespective of the wait time.

[rog, 2011-01-19 17:15:21]

On 19 January 2011 16:46,  <n13m3y3r@gmail.com> wrote:
>
>> The only way that heap can remove items from the heap is through
>> heap.Interface.Pop, which is implemented by timerHeap.Pop, which sets
>
> the index
>>
>> to -1. All the indexes in the heap are kept up to date by
>
> timerHeap.Swap (made
>>
>> easy as a nice consequence of the way that the heap polymorphism
>
> works).
>
> I see, that makes sense.
>
>> it's not really misbehaving. if the user asks for a timer to go off
>
> 500 years
>>
>> into the future, i think it's fair enough that it will never actually
>
> go off.
>>
>> they'll never know :-)
>
> So if the user application has a bug, you're saying you don't
> mind to add another one.  panic() sounds appropriate.

i wouldn't say it's necessarily a bug. why is 500 years in the future
a bug where 400 years is not? the real bug would be if ns wraps
negative, which i should probably check for and panic if so.

> Intervals will generally be taken from a set rather than selected
> randomly.
> In a short period, the smallest interval regularly scheduled will
> dominate
> the algorithm with a single goroutine, with no waste at all.

you're assuming a particular way of using time.After that may
or may not be the case. as a counter example, say i was writing
a calendar server, sending reminders to many events for many
people. when i start the server, perhaps i read all the events
from a file in which they're stored in date order into a linked list,
reversing it in the process. then i start a Timer for each event in the
list. this is perfectly legitimate usage - but there might be thousands of
items in the list, and each one is going
to create a real OS thread. cue one crashed application.

>> the problem is that if many events are being manipulated with long
>
> deadlines,
>>
>> many goroutines will remain around (as actual OS threads) until the
>
> original
>
> The deadline doesn't matter.. the clock moves forward either way.  If
> that
> deadline is 10 minutes, the first call will schedule a goroutine for 10
> minutes.  The second call will have a time of 10 minutes + 1ns, and will
> not create any goroutines anymore, and that will continue forever.

again, this assumes one particular pattern of usage.

> I vote against changing the current algorithm and introducing a dumb
> loop
> which polls involving a global lock irrespective of the wait time.

i don't understand this.

[niemeyer, 2011-01-19 17:28:31]

> i wouldn't say it's necessarily a bug. why is 500 years in the future
> a bug where 400 years is not? the real bug would be if ns wraps
> negative, which i should probably check for and panic if so.

It's a bug because your implementation ignores the timer
entirely. If you don't handle it, the proper way is to
panic IMO.

> you're assuming a particular way of using time.After that may

Yes, I'm assuming a realistic use case, but that's just my
opinion. I'll leave it up to the core developers to decide.

In the test, AfterFunc()'s Timer seems to be ignored entirely.
Should it be tested as well?

Besides these points, LGTM.

[rog, 2011-01-19 18:27:43]

On 19 January 2011 17:28,  <n13m3y3r@gmail.com> wrote:
>
>> i wouldn't say it's necessarily a bug. why is 500 years in the future
>> a bug where 400 years is not? the real bug would be if ns wraps
>> negative, which i should probably check for and panic if so.
>
> It's a bug because your implementation ignores the timer
> entirely. If you don't handle it, the proper way is to
> panic IMO.

if the not-handled behaviour is indistinguishable from the handled
behaviour for 500 years, i don't think we care too much.

actually, i've just realised that it doesn't matter if events are
inserted after the sentinel, so i've removed that check
and put in a check for wrapped ints. this way it works for
all [minint64 .. maxint64-now] which is about as good as
you can get. overkill really, but you never know where
a security hole might come from.

of course, we assume that we never get to 1<<62ns
so it still doesn't handle the event, same as before.

>> you're assuming a particular way of using time.After that may
>
> Yes, I'm assuming a realistic use case, but that's just my
> opinion. I'll leave it up to the core developers to decide.
>
> In the test, AfterFunc()'s Timer seems to be ignored entirely.
> Should it be tested as well?

done.

[rog, 2011-01-20 17:26:44]

PTAL

[r, 2011-01-21 19:26:53]

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode15
src/pkg/time/sleep.go:15: // When the Timer was created with NewTimer,
s/When/If/  (a time-based conditional is confusing in this context)

however, i wonder what this conditional is for.  do users ever see the sentinel
value? isn't NewTimer always in the path for user code?  i suggest moving the
special case comment out of here.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode27
src/pkg/time/sleep.go:27: var timerMutex sync.Mutex
group these vars in () to show which are protected by the mutex
there's so many and with so much state i would probably put them in a global
struct and give them proper documentation. might even make some of these
functions methods of that struct.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode35
src/pkg/time/sleep.go:35: timers.Push(&Timer{nil, forever, nil, 0}) // sentinel
timers.Push(&Timer{t: forever}) // sentinel

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode88
src/pkg/time/sleep.go:88: // It returns true if it succeeded (i.e. the
s/i.e./that is,/ avoid latinates
but the sentence is convoluted anyway

It returns true if the call stops the timer, false if the timer has already
expired or stopped.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:118: // until the new event is more than maxSleepTime,
s/more than/at least/

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:131: // is empty, or when another sleeper has been
started.
s/,//

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:132: //
d

[rog, 2011-01-21 19:38:33]

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode15
src/pkg/time/sleep.go:15: // When the Timer was created with NewTimer,
A Timer is also returned by AfterFunc.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode27
src/pkg/time/sleep.go:27: var timerMutex sync.Mutex
two == many? i'll put them in a struct if you really think it would be better.

[r, 2011-01-21 19:47:38]

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode15
src/pkg/time/sleep.go:15: // When the Timer was created with NewTimer,
it's still true for that case, just not in the same way.   i'm trying to tell
you this is a confusing, detailed comment that needs rewriting

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode27
src/pkg/time/sleep.go:27: var timerMutex sync.Mutex
they certainly should be grouped.  maybe a struct is overkill, but on first
blush i thought there were more, but that just reinforces my point. at least use
parens.
and please comment them! none of these globals has a word of documentation

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode80
src/pkg/time/sleep.go:80: // be used to prevent the call.
s/prevent the call/cancel the call using its Stop method/

[rog, 2011-01-24 14:01:10]

PTAL

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go
File src/pkg/time/sleep.go (right):

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode15
src/pkg/time/sleep.go:15: // When the Timer was created with NewTimer,
On 2011/01/21 19:47:39, r wrote:
> it's still true for that case, just not in the same way.   i'm trying to tell
> you this is a confusing, detailed comment that needs rewriting

i've changed this, but i'm still finding the phrasing awkward.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode27
src/pkg/time/sleep.go:27: var timerMutex sync.Mutex
On 2011/01/21 19:47:39, r wrote:
> they certainly should be grouped.  maybe a struct is overkill, but on first
> blush i thought there were more, but that just reinforces my point. at least
use
> parens.
> and please comment them! none of these globals has a word of documentation

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode35
src/pkg/time/sleep.go:35: timers.Push(&Timer{nil, forever, nil, 0}) // sentinel
On 2011/01/21 19:26:53, r wrote:
> timers.Push(&Timer{t: forever}) // sentinel

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode80
src/pkg/time/sleep.go:80: // be used to prevent the call.
On 2011/01/21 19:47:39, r wrote:
> s/prevent the call/cancel the call using its Stop method/

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcode88
src/pkg/time/sleep.go:88: // It returns true if it succeeded (i.e. the
On 2011/01/21 19:26:53, r wrote:
> s/i.e./that is,/ avoid latinates
> but the sentence is convoluted anyway
> 
> It returns true if the call stops the timer, false if the timer has already
> expired or stopped.

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:118: // until the new event is more than maxSleepTime,
On 2011/01/21 19:26:53, r wrote:
> s/more than/at least/

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:131: // is empty, or when another sleeper has been
started.
On 2011/01/21 19:26:53, r wrote:
> s/,//

Done.

http://codereview.appspot.com/4063043/diff/53001/src/pkg/time/sleep.go#newcod...
src/pkg/time/sleep.go:132: //
On 2011/01/21 19:26:53, r wrote:
> d

Done.

[r2, 2011-01-25 20:21:56]

LGTM

[r, 2011-01-25 20:25:55]

*** Submitted as http://code.google.com/p/go/source/detail?r=c1d8b16efebd ***

time: allow cancelling of After events.
Also simplify sleeper algorithm and poll
occasionally so redundant sleeper goroutines
will quit sooner.

R=r, niemeyer, r2
CC=golang-dev
http://codereview.appspot.com/4063043

Committer: Rob Pike <r@golang.org>