code review 3416043: time: make After use fewer goroutines and host processes.

time: make After use fewer goroutines and host processes.
With credit to Gustavo Niemeyer, who hinted at this approach
in #go-nuts.

[rog, 2010-12-03 09:09:06]

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

I'd like you to review this change.

[niemeyer, 2010-12-03 13:30:57]

Thanks for submitting this Roger.  A few comments are inlined.

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

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode23
src/pkg/time/sleep.go:23: var mu sync.Mutex
Given that this variable is sitting within a package which isn't restricted to
this functionality or file, it feels like a better name here would be nice (e.g.
eventsMutex or similar).

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode76
src/pkg/time/sleep.go:76: // quit.
I don't think this is true.  The goroutine is being fired with the lock held,
and still with the lock held it will put the first event item to sleep. This
means that it is impossible to fire a new goroutines without the item it was
responsible for being put to sleep by the respective goroutine, and thus there's
a barrier which any forthcoming goroutines won't be able to fly over.

As a second point around this same logic, the approach of firing the goroutine
with the lock held may be easily avoided as done in the original version I
proposed.  Doing so reduces contention, since the current approach will keep a
lock held until the new goroutine is scheduled, blocking any further calls to
After() with t < e[0].t.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode94
src/pkg/time/sleep.go:94: t = Nanoseconds()
Is it really necessary to get a new timestamp on every iteration of the loop? 
All of those channels are cached, so this should be very fast.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode113
src/pkg/time/sleep.go:113: events = append(events, x.(*event))
The original version worked with a double-linked list, rather than a heap backed
by an array.  There are a few obvious consequences to it:

- Insertion is O(log(n)) with the heap vs. O(n) with the linked list in the
worst case.  In practice, this should be amortized due to the fact that new
events will often be added towards the end, and searching for the correct
positions starts from the end.

- Removals with the heap are O(log(n)), including swapping of existing elements,
vs O(1) with the linked list.

- Memory allocated for the heap is never given back.

So, there are clear advantages both ways.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode117
src/pkg/time/sleep.go:117: n := len(events)
This is a bit of nitpicking, but given the usage below, you really want n-1
rather than n.

[r, 2010-12-03 20:03:51]

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

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode14
src/pkg/time/sleep.go:14: type event struct {
comments please

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode64
src/pkg/time/sleep.go:64: mu.Unlock()
this is fishy. i think niemeyer is right

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode100
src/pkg/time/sleep.go:100: func (_ eventHeap) Len() int {
delete all the _ for the receivers. you don't need them.

[rog, 2010-12-04 09:26:18]

PTAL

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

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode23
src/pkg/time/sleep.go:23: var mu sync.Mutex
On 2010/12/03 13:30:57, niemeyer wrote:
> Given that this variable is sitting within a package which isn't restricted to
> this functionality or file, it feels like a better name here would be nice
(e.g.
> eventsMutex or similar).

yes, i did actually change the name to eventsMutex for a while, then
decided it looked too heavyweight, and the likelyhood of clashes with other
parts of the time package were minimal, so i changed it back.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode64
src/pkg/time/sleep.go:64: mu.Unlock()
On 2010/12/03 20:03:51, r wrote:
> this is fishy. i think niemeyer is right

Done.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode76
src/pkg/time/sleep.go:76: // quit.
On 2010/12/03 13:30:57, niemeyer wrote:
> I don't think this is true.  The goroutine is being fired with the lock held,
> and still with the lock held it will put the first event item to sleep. This
> means that it is impossible to fire a new goroutines without the item it was
> responsible for being put to sleep by the respective goroutine, and thus
there's
> a barrier which any forthcoming goroutines won't be able to fly over.

yes, i think you're right. i have changed the comment and moved the lock
into the sleeper

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode94
src/pkg/time/sleep.go:94: t = Nanoseconds()
On 2010/12/03 13:30:57, niemeyer wrote:
> Is it really necessary to get a new timestamp on every iteration of the loop? 
> All of those channels are cached, so this should be very fast.

i did find that i had a significant number of extra iterations
of this loop when i inserted the timestamp updating, but that may
easily just be because the Nanoseconds call is slow.

done.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode100
src/pkg/time/sleep.go:100: func (_ eventHeap) Len() int {
On 2010/12/03 20:03:51, r wrote:
> delete all the _ for the receivers. you don't need them.

cool.

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode113
src/pkg/time/sleep.go:113: events = append(events, x.(*event))
On 2010/12/03 13:30:57, niemeyer wrote:
> The original version worked with a double-linked list, rather than a heap
backed
> by an array.  There are a few obvious consequences to it:
> 
> - Insertion is O(log(n)) with the heap vs. O(n) with the linked list in the
> worst case.  In practice, this should be amortized due to the fact that new
> events will often be added towards the end, and searching for the correct
> positions starts from the end.
> 
> - Removals with the heap are O(log(n)), including swapping of existing
elements,
> vs O(1) with the linked list.
> 
> - Memory allocated for the heap is never given back.
> 
> So, there are clear advantages both ways.

if there are many repeating events with long duration, and one fast repeating
event, then the "search from the end" method will always have to traverse the
entire list.

it would be possible to add some heuristic to shrink the array when it has much
free space (although case would have to be taken to avoid bad behaviour with a
bursty task load)

http://codereview.appspot.com/3416043/diff/2001/src/pkg/time/sleep.go#newcode117
src/pkg/time/sleep.go:117: n := len(events)
On 2010/12/03 13:30:57, niemeyer wrote:
> This is a bit of nitpicking, but given the usage below, you really want n-1
> rather than n.

Done.

[r, 2010-12-04 19:18:49]

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

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode14
src/pkg/time/sleep.go:14: type event struct {
this type and its associated pieces still deserve some commentary

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode23
src/pkg/time/sleep.go:23: var mu sync.Mutex
eventMutex
it is heavyweight but it's clear and avoids conflict.
you're grabbing a likely name in a public place in a multifile package. that's a
maintenance issue

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode80
src/pkg/time/sleep.go:80: // Assuming Nanoseconds is monotonic, we are
guaranteed
what if Nanoseconds is non-monotonic, which is possible on buggy
multiprocessors? i've seen it happen in other environments.
maybe the assignment to t should guarantee monotonicity and then you don't need
to make the assumption, although a buggy Nanoseconds could still cause trouble

the After facility is likely to get heavy use, so it's worth an extra level of
care

[adg, 2010-12-05 22:43:49]

Thanks for writing this, but the fun part is still ahead of you: tests.

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

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode90
src/pkg/time/sleep.go:90: t := Nanoseconds()
I think you can move this outside the for loop.

[rog, 2010-12-06 14:22:13]

PTAL (added a couple of tests too)

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

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode14
src/pkg/time/sleep.go:14: type event struct {
On 2010/12/04 19:18:50, r wrote:
> this type and its associated pieces still deserve some commentary

Done.

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode23
src/pkg/time/sleep.go:23: var mu sync.Mutex
On 2010/12/04 19:18:50, r wrote:
> eventMutex
> it is heavyweight but it's clear and avoids conflict.
> you're grabbing a likely name in a public place in a multifile package. that's
a
> maintenance issue

Done.

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode90
src/pkg/time/sleep.go:90: t := Nanoseconds()
On 2010/12/05 22:43:49, adg wrote:
> I think you can move this outside the for loop.

it depends whether we want to treat sending on a channel (+ associated
underlying synchronisation) and popping the heap as zero-time operations.

i suppose that it could be argued that we're already doing that inside the inner
loop anyway, but it's the difference between sending a slightly inaccurate time
stamp down the channel and sleeping too long.

i'm happy to change it, but what do others think?

[r, 2010-12-06 16:20:52]

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

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode16
src/pkg/time/sleep.go:16: t        int64        // The absolute time that the
event should be fired.
s/be fired/fire/

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode75
src/pkg/time/sleep.go:75: // Scheduling vagaries may mean that sleepers may not
wake up in
s/may // (too many mays)

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode83
src/pkg/time/sleep.go:83: // cases preserve the above invariant.
'above' is not an adjective.

Both cases preserve the invariant described above.

[rog, 2010-12-06 17:35:27]

PTAL

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

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode16
src/pkg/time/sleep.go:16: t        int64        // The absolute time that the
event should be fired.
On 2010/12/06 16:20:56, r wrote:
> s/be fired/fire/

Done.

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode75
src/pkg/time/sleep.go:75: // Scheduling vagaries may mean that sleepers may not
wake up in
On 2010/12/06 16:20:56, r wrote:
> s/may // (too many mays)

Done.

http://codereview.appspot.com/3416043/diff/9002/src/pkg/time/sleep.go#newcode83
src/pkg/time/sleep.go:83: // cases preserve the above invariant.
On 2010/12/06 16:20:56, r wrote:
> 'above' is not an adjective.
> 
> Both cases preserve the invariant described above.

Done.

[r, 2010-12-06 19:13:13]

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

http://codereview.appspot.com/3416043/diff/13001/src/pkg/time/sleep.go#newcode90
src/pkg/time/sleep.go:90: t := Nanoseconds()
i slightly prefer keeping it where it is as there are scheduling events in the
loop (lock, send) and the delays could be significant.  the call to Nanoseconds
should be cheap, and is cheap in some environments.

[r, 2010-12-06 19:18:53]

LGTM

[r, 2010-12-06 19:19:32]

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

time: make After use fewer goroutines and host processes.
With credit to Gustavo Niemeyer, who hinted at this approach
in #go-nuts.

R=adg, rsc, niemeyer, r
CC=golang-dev
http://codereview.appspot.com/3416043

Committer: Rob Pike <r@golang.org>

[gri, 2010-12-06 21:17:57]

This submission appears to have broken several builds.

http://godashboard.appspot.com/?n=30&p=1

- gri

On Mon, Dec 6, 2010 at 11:19 AM, <r@golang.org> wrote:

> *** Submitted as
> http://code.google.com/p/go/source/detail?r=fc3b75653c76 ***
>
>
> time: make After use fewer goroutines and host processes.
> With credit to Gustavo Niemeyer, who hinted at this approach
> in #go-nuts.
>
> R=adg, rsc, niemeyer, r
> CC=golang-dev
>
> http://codereview.appspot.com/3416043
>
> Committer: Rob Pike <r@golang.org>
>
>
>
> http://codereview.appspot.com/3416043/
>

[rsc, 2010-12-06 21:23:10]

I couldn't reproduce it locally
but I submitted a tbr fix that
requires a bit less precision by
the timer.

Russ

[rog, 2010-12-07 10:44:15]

this was always going to be a potential problem with the test,
although i'm surprised it can't manage at least 10ms
accuracy.

On 6 December 2010 21:23, Russ Cox <rsc@golang.org> wrote:
> I couldn't reproduce it locally
> but I submitted a tbr fix that
> requires a bit less precision by
> the timer.
>
> Russ
>

[rog, 2011-01-07 17:22:55]

*** Abandoned ***