code review 13273044: time: make Timer scalable

time: make Timer scalable

With this change, time.Timer is backed by userspace heaps with
single runtimeTimer per heap. Heaps number is multiply of
GOMAXPROCS and changed dinamically.

Ticker is not changed and still uses runtimeTimer, cause I assume
that it is strange to have many thousangs of ticker. Without ticker,
heap code could be simplified a bit, and no need to store interval in
Timer.

benchmark                           old ns/op    new ns/op    delta
BenchmarkAfterFunc                       6593         1016  -84.59%
BenchmarkAfterFunc-2                     4039          702  -82.62%
BenchmarkAfterFunc-3                     5851          545  -90.69%
BenchmarkAfterFunc-4                     8694          469  -94.61%
BenchmarkAfter                           6969         1064  -84.73%
BenchmarkAfter-2                         3837          728  -81.03%
BenchmarkAfter-3                         5853          545  -90.69%
BenchmarkAfter-4                         8796          553  -93.71%
BenchmarkStop                             498          554  +11.24%
BenchmarkStop-2                           566          375  -33.75%
BenchmarkStop-3                           676          289  -57.25%
BenchmarkStop-4                           759          250  -67.06%
BenchmarkSimultaneousAfterFunc            603          585   -2.99%
BenchmarkSimultaneousAfterFunc-2          640          383  -40.16%
BenchmarkSimultaneousAfterFunc-3          789          296  -62.48%
BenchmarkSimultaneousAfterFunc-4          741          284  -61.67%
BenchmarkStartStop                        236          229   -2.97%
BenchmarkStartStop-2                      210          284  +35.24%
BenchmarkStartStop-3                      275          198  -28.00%
BenchmarkStartStop-4                      302          170  -43.71%
BenchmarkTicker                         59182        59199   +0.03%
BenchmarkTicker-2                       61678        61479   -0.32%
BenchmarkTicker-3                       61712        61855   +0.23%
BenchmarkTicker-4                       61761        61825   +0.10%

Fixes issue 6239.

[funny.falcon, 2013-08-27 12:18:51]

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

I'd like you to review this change to
https://code.google.com/p/go

[r, 2013-08-27 13:04:30]

I appreciate your enthusiasm but +249 lines to a relatively minor
runtime component requires some discussion first. Outside of this code
review and outside of this thread, please send a message to golang-dev
explaining what problem you're solving, why it's important, and what
your approach will be.

After (and if) the discussion converges on a decision, we can look at
the code. See the top of http://golang.org/doc/contribute.html for
background.

-rob

[funny.falcon, 2013-08-27 13:15:33]

On 2013/08/27 13:04:30, r wrote:
> I appreciate your enthusiasm but +249 lines to a relatively minor
> runtime component requires some discussion first. Outside of this code
> review and outside of this thread, please send a message to golang-dev
> explaining what problem you're solving, why it's important, and what
> your approach will be.
> 
> After (and if) the discussion converges on a decision, we can look at
> the code. See the top of http://golang.org/doc/contribute.html for
> background.
> 
> -rob

Timers are not minor runtime component, when application demands timeout
on every tiny request, and there is hundreds of thousands of them.

https://code.google.com/p/go/issues/detail?id=6239

[funny.falcon, 2013-08-27 13:23:32]

Any way, consider this change as a proposal and share of design.

I settle with custom timers on top of time.Timer.
This change is just a port of custom timers to use internal functions
and runtimeTimer instead of time.Timer.

I will not be sad, if you consider it dumb and will not use it in any way.

funny_falcon

[dvyukov, 2013-08-27 14:10:36]

On 2013/08/27 12:18:51, funny.falcon wrote:
> Hello mailto:golang-dev@googlegroups.com (cc:
mailto:golang-dev@googlegroups.com),
> 
> I'd like you to review this change to
> https://code.google.com/p/go

Thanks for working on this. The speedups look great.

We definitely need partitioned timers. But I think it needs to be done in the
runtime for several reasons:
1. Your current design introduces an additional hop (timer goroutine in
sleep.go) when timers actually fire.
2. The attempts to tune for GOMAXPROCS in Go code looks awkward, timer
partitions can't shrink and you don't know what partition to use when a timer is
created.
3. We won't be able to execute timers outside of goroutine context if it's
written in Go.

Eventually Timers struct must be attached to each P, then worker threads (M's)
must poll timers along with network. This will allow to auto-tune number of
Timers, eliminate most of the contention, schedule users callbacks w/o any
additional hops, etc.

I am not sure what of this can be done before the freeze. I was planning to do
it in Go1.3.

[dvyukov, 2013-08-27 14:18:13]

On 2013/08/27 14:10:36, dvyukov wrote:
> On 2013/08/27 12:18:51, funny.falcon wrote:
> > Hello mailto:golang-dev@googlegroups.com (cc:
> mailto:golang-dev@googlegroups.com),
> > 
> > I'd like you to review this change to
> > https://code.google.com/p/go
> 
> Thanks for working on this. The speedups look great.
> 
> We definitely need partitioned timers. But I think it needs to be done in the
> runtime for several reasons:
> 1. Your current design introduces an additional hop (timer goroutine in
> sleep.go) when timers actually fire.
> 2. The attempts to tune for GOMAXPROCS in Go code looks awkward, timer
> partitions can't shrink and you don't know what partition to use when a timer
is
> created.
> 3. We won't be able to execute timers outside of goroutine context if it's
> written in Go.
> 
> Eventually Timers struct must be attached to each P, then worker threads (M's)
> must poll timers along with network. This will allow to auto-tune number of
> Timers, eliminate most of the contention, schedule users callbacks w/o any
> additional hops, etc.
> 
> I am not sure what of this can be done before the freeze. I was planning to do
> it in Go1.3.


If you do the full variant, then there will be tricky aspects related to
GOMAXPROCS changes.

As an intermediate step, it's possible to create fixed number of partitions in
runtime. But then, I afraid, it can slower programs with few timers and
GOMAXPROCS=1.

[funny.falcon, 2013-08-27 16:53:17]

Oh, I pressed "answere" instead of "answere to all" when answered to Dmitry.
Excuse me for duplicating this, its just to be saved in codereview.

27.08.2013 18:10 пользователь <dvyukov@google.com> написал:

> We definitely need partitioned timers. But I think it needs to be done
> in the runtime for several reasons:
> 1. Your current design introduces an additional hop (timer goroutine in
> sleep.go) when timers actually fire.
Does it weights a lot? Looking to benchmark, hop is neglible.

> 2. The attempts to tune for GOMAXPROCS in Go code looks awkward, timer
> partitions can't shrink and you don't know what partition to use when a
> timer is created.

Actually, they are shrinked: new timers are created only in first GOMAXPROCS*4
heaps (n=2 if GOMAXPROCS=1). Other heap's loop will sleep for a hour when no
timers remains.

Round robin used intentionally cause timer could be stopped from arbitrary
goroutine (in my case), so that there is no relevance between thread that create
timer and thread that stop timer. So, for reducing lock contention in this case,
round robin works best.

> 3. We won't be able to execute timers outside of goroutine context if
> it's written in Go.

So that, it is done only for time.Timer which could execute only user code.
Runtime timers remains the same. Is there a need for thousands of runtime
timers? Oh, I forgot about network deadlines :( they use runtime timers?

> If you do the full variant, then there will be tricky aspects related to

> GOMAXPROCS changes.
>
What is bad in current design? Change of GOMAXPROCS checked every 10000 timer
creation - almost no impact. And number of active heaps adjusted accordantly. If
GOMAXPROCS shrinked, unused heaps will become sleeping zombie when no timer
remains in.

> As an intermediate step, it's possible to create fixed number of
> partitions in runtime. But then, I afraid, it can slower programs with
> few timers and GOMAXPROCS=1.
>

If GOMAXPROCS=1 then there is only 2 active heap, so that no big overhead. There
could be even 1. I set it 2 to pleasure first 10000 new timers if GOMAXPROCS
increased.

[r, 2013-08-28 01:05:16]

My point is that we don't do proposals by first sending in code for
review. Again, please read http://golang.org/doc/contribute.html.

-rob


On Tue, Aug 27, 2013 at 11:23 PM,  <funny.falcon@gmail.com> wrote:
> Any way, consider this change as a proposal and share of design.
>
> I settle with custom timers on top of time.Timer.
> This change is just a port of custom timers to use internal functions
> and runtimeTimer instead of time.Timer.
>
> I will not be sad, if you consider it dumb and will not use it in any
> way.
>
> funny_falcon
>
>
>
>
> https://codereview.appspot.com/13273044/

[dvyukov, 2013-08-30 11:14:34]

On 2013/08/27 16:53:17, funny.falcon wrote:
> Oh, I pressed "answere" instead of "answere to all" when answered to Dmitry.
> Excuse me for duplicating this, its just to be saved in codereview.
> 
> 27.08.2013 18:10 пользователь <mailto:dvyukov@google.com> написал:
> 
> > We definitely need partitioned timers. But I think it needs to be done
> > in the runtime for several reasons:
> > 1. Your current design introduces an additional hop (timer goroutine in
> > sleep.go) when timers actually fire.
> Does it weights a lot? Looking to benchmark, hop is neglible.


You have lots of changes in this CL. So benchmarks says nothing about the hop.
It may be 20% slower due to the additional hop and 25% faster due to other
changes.



> > 2. The attempts to tune for GOMAXPROCS in Go code looks awkward, timer
> > partitions can't shrink and you don't know what partition to use when a
> > timer is created.
> 
> Actually, they are shrinked: new timers are created only in first GOMAXPROCS*4
> heaps (n=2 if GOMAXPROCS=1). Other heap's loop will sleep for a hour when no
> timers remains.


You only shrink them passively, there are no guarantees that they will be
actually shrunk.
So a program may have weird effects after runtime.GOMAXPROCS(64);
runtime.GOMAXPROCS(1).



> Round robin used intentionally cause timer could be stopped from arbitrary
> goroutine (in my case), so that there is no relevance between thread that
create
> timer and thread that stop timer. So, for reducing lock contention in this
case,
> round robin works best.


Why RR is the best? You use essentially random heap for both add and remove.
If we have per-P heap, then we always add to local heap. Probably we will be
able to avoid mutexes in this case. Remove will go into random heap or into
local heap (if the timer is cancelled soon after addition).



> > 3. We won't be able to execute timers outside of goroutine context if
> > it's written in Go.
> 
> So that, it is done only for time.Timer which could execute only user code.
> Runtime timers remains the same. Is there a need for thousands of runtime
> timers? Oh, I forgot about network deadlines :( they use runtime timers?
> 
> > If you do the full variant, then there will be tricky aspects related to
> 
> > GOMAXPROCS changes.
> >
> What is bad in current design? Change of GOMAXPROCS checked every 10000 timer
> creation - almost no impact. And number of active heaps adjusted accordantly.
If
> GOMAXPROCS shrinked, unused heaps will become sleeping zombie when no timer
> remains in.


It adds lots of duplicate code.
It provides speedup in short term, but makes it impossible to do other important
optimizations in long term.



> > As an intermediate step, it's possible to create fixed number of
> > partitions in runtime. But then, I afraid, it can slower programs with
> > few timers and GOMAXPROCS=1.
> >
> If GOMAXPROCS=1 then there is only 2 active heap, so that no big overhead.
There
> could be even 1. I set it 2 to pleasure first 10000 new timers if GOMAXPROCS
> increased.

[gobot, 2013-12-20 16:26:00]

Replacing golang-dev with golang-codereviews.

[rsc, 2014-03-05 20:27:15]

R=close