Issue 12879045: code review 12879045: time: timers start index to be non 0
|
Created:
10 years, 8 months ago by funny.falcon Modified:
10 years, 3 months ago CC:
golang-codereviews Visibility:
Public. |
Descriptiontime: timers start index to be non 0
- index changed to uint32 - larger limit
- 0 is enough to indicate unset timer, no need for -1
- with start index == 3, all 4 descendant pointers are always
in a same CPU cache line (but maybe it doesn't matter)
Patch Set 1 #Patch Set 2 : diff -r bb2db1e233b2 https://code.google.com/p/go #Patch Set 3 : diff -r bb2db1e233b2 https://code.google.com/p/go #
MessagesTotal messages: 11
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
Sign in to reply to this message.
Why? On Mon, Aug 26, 2013 at 7:54 AM, <funny.falcon@gmail.com> wrote: > Reviewers: golang-dev1, > > Message: > 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 > > > Description: > time: timers start index to be non 0 > > - index changed to uint32 - larger limit > - 0 is enough to indicate unset timer, no need for -1 > - with start index == 3, all 4 descendant pointers are always > in a same CPU cache line (but maybe it doesn't matter) > > Please review this at https://codereview.appspot.**com/12879045/<https://codereview.appspot.com/128... > > Affected files: > M src/pkg/runtime/runtime.h > M src/pkg/runtime/time.goc > M src/pkg/time/sleep.go > > > Index: src/pkg/runtime/runtime.h > ==============================**==============================**======= > --- a/src/pkg/runtime/runtime.h > +++ b/src/pkg/runtime/runtime.h > @@ -482,7 +482,7 @@ > // If this struct changes, adjust ../time/sleep.go:/**runtimeTimer. > struct Timer > { > - int32 i; // heap index > + uint32 i; // heap index > > // Timer wakes up at when, and then at when+period, ... (period > > 0 only) > // each time calling f(now, arg) in the timer goroutine, so f must > be > Index: src/pkg/runtime/time.goc > ==============================**==============================**======= > --- a/src/pkg/runtime/time.goc > +++ b/src/pkg/runtime/time.goc > @@ -42,8 +42,8 @@ > // C runtime. > > static void timerproc(void); > -static void siftup(int32); > -static void siftdown(int32); > +static void siftup(uint32); > +static void siftdown(uint32); > > // Ready the goroutine e.data. > static void > @@ -84,6 +84,10 @@ > runtime·unlock(&timers); > } > > +#define TOP_INDEX (3) > +#define WRONG_INDEX (0) > +#define OFFSET (TOP_INDEX*3-1) > + > // Add a timer to the heap and start or kick the timer proc > // if the new timer is earlier than any of the others. > static void > @@ -102,11 +106,14 @@ > runtime·free(timers.t); > timers.t = nt; > timers.cap = n; > + if(timers.len < TOP_INDEX) { > + timers.len = TOP_INDEX; > + } > } > t->i = timers.len++; > timers.t[t->i] = t; > siftup(t->i); > - if(t->i == 0) { > + if(t->i == TOP_INDEX) { > // siftup moved to top: new earliest deadline. > if(timers.sleeping) { > timers.sleeping = false; > @@ -129,7 +136,7 @@ > bool > runtime·deltimer(Timer *t) > { > - int32 i; > + uint32 i; > > // Dereference t so that any panic happens before the lock is held. > // Discard result, because t might be moving in the heap. > @@ -142,7 +149,8 @@ > // a bogus i (typically 0, if generated by Go). > // Verify it before proceeding. > i = t->i; > - if(i < 0 || i >= timers.len || timers.t[i] != t) { > + t->i = WRONG_INDEX; > + if(i < TOP_INDEX || i >= timers.len || timers.t[i] != t) { > runtime·unlock(&timers); > return false; > } > @@ -178,24 +186,24 @@ > timers.sleeping = false; > now = runtime·nanotime(); > for(;;) { > - if(timers.len == 0) { > + if(timers.len == TOP_INDEX) { > delta = -1; > break; > } > - t = timers.t[0]; > + t = timers.t[TOP_INDEX]; > delta = t->when - now; > if(delta > 0) > break; > if(t->period > 0) { > // leave in heap but adjust next time to > fire > t->when += t->period * (1 + > -delta/t->period); > - siftdown(0); > + siftdown(TOP_INDEX); > } else { > // remove from heap > - timers.t[0] = timers.t[--timers.len]; > - timers.t[0]->i = 0; > - siftdown(0); > - t->i = -1; // mark as removed > + timers.t[TOP_INDEX] = > timers.t[--timers.len]; > + timers.t[TOP_INDEX]->i = TOP_INDEX; > + siftdown(TOP_INDEX); > + t->i = WRONG_INDEX; // mark as removed > } > f = (void*)t->fv->fn; > arg = t->arg; > @@ -222,17 +230,17 @@ > // heap maintenance algorithms. > > static void > -siftup(int32 i) > +siftup(uint32 i) > { > - int32 p; > + uint32 p; > int64 when; > Timer **t, *tmp; > > t = timers.t; > when = t[i]->when; > tmp = t[i]; > - while(i > 0) { > - p = (i-1)/4; // parent > + while(i > TOP_INDEX) { > + p = (i+OFFSET)/4; // parent > if(when >= t[p]->when) > break; > t[i] = t[p]; > @@ -244,9 +252,9 @@ > } > > static void > -siftdown(int32 i) > +siftdown(uint32 i) > { > - int32 c, c3, len; > + uint32 c, c3, len; > int64 when, w, w3; > Timer **t, *tmp; > > @@ -255,7 +263,7 @@ > when = t[i]->when; > tmp = t[i]; > for(;;) { > - c = i*4 + 1; // left child > + c = i*4 - OFFSET; // left child > c3 = c + 2; // mid child > if(c >= len) { > break; > Index: src/pkg/time/sleep.go > ==============================**==============================**======= > --- a/src/pkg/time/sleep.go > +++ b/src/pkg/time/sleep.go > @@ -15,7 +15,7 @@ > // Interface to timers implemented in package runtime. > // Must be in sync with ../runtime/runtime.h:/^struct.**Timer$ > type runtimeTimer struct { > - i int32 > + i uint32 > when int64 > period int64 > f func(int64, interface{}) // NOTE: must not be closure > > > -- > > ---You received this message because you are subscribed to the Google > Groups "golang-dev" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... > . > For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... > . >
Sign in to reply to this message.
I have the same question.
2^31 timers should be enough for everyone (r)
Yuri, if you want to improve timers performance you may try to store
when directly in the timers array. Now it contains just Timer*, try
storing {Timer* t, int64 when}. It should remove lots of indirection
in siftup/siftdown/timerproc.
On Mon, Aug 26, 2013 at 5:11 PM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Why?
>
>
>
> On Mon, Aug 26, 2013 at 7:54 AM, <funny.falcon@gmail.com> wrote:
>>
>> Reviewers: golang-dev1,
>>
>> Message:
>> 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
>>
>>
>> Description:
>> time: timers start index to be non 0
>>
>> - index changed to uint32 - larger limit
>> - 0 is enough to indicate unset timer, no need for -1
>> - with start index == 3, all 4 descendant pointers are always
>> in a same CPU cache line (but maybe it doesn't matter)
>>
>> Please review this at https://codereview.appspot.com/12879045/
>>
>> Affected files:
>> M src/pkg/runtime/runtime.h
>> M src/pkg/runtime/time.goc
>> M src/pkg/time/sleep.go
>>
>>
>> Index: src/pkg/runtime/runtime.h
>> ===================================================================
>> --- a/src/pkg/runtime/runtime.h
>> +++ b/src/pkg/runtime/runtime.h
>> @@ -482,7 +482,7 @@
>> // If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
>> struct Timer
>> {
>> - int32 i; // heap index
>> + uint32 i; // heap index
>>
>> // Timer wakes up at when, and then at when+period, ... (period >
>> 0 only)
>> // each time calling f(now, arg) in the timer goroutine, so f must
>> be
>> Index: src/pkg/runtime/time.goc
>> ===================================================================
>> --- a/src/pkg/runtime/time.goc
>> +++ b/src/pkg/runtime/time.goc
>> @@ -42,8 +42,8 @@
>> // C runtime.
>>
>> static void timerproc(void);
>> -static void siftup(int32);
>> -static void siftdown(int32);
>> +static void siftup(uint32);
>> +static void siftdown(uint32);
>>
>> // Ready the goroutine e.data.
>> static void
>> @@ -84,6 +84,10 @@
>> runtime·unlock(&timers);
>> }
>>
>> +#define TOP_INDEX (3)
>> +#define WRONG_INDEX (0)
>> +#define OFFSET (TOP_INDEX*3-1)
>> +
>> // Add a timer to the heap and start or kick the timer proc
>> // if the new timer is earlier than any of the others.
>> static void
>> @@ -102,11 +106,14 @@
>> runtime·free(timers.t);
>> timers.t = nt;
>> timers.cap = n;
>> + if(timers.len < TOP_INDEX) {
>> + timers.len = TOP_INDEX;
>> + }
>> }
>> t->i = timers.len++;
>> timers.t[t->i] = t;
>> siftup(t->i);
>> - if(t->i == 0) {
>> + if(t->i == TOP_INDEX) {
>> // siftup moved to top: new earliest deadline.
>> if(timers.sleeping) {
>> timers.sleeping = false;
>> @@ -129,7 +136,7 @@
>> bool
>> runtime·deltimer(Timer *t)
>> {
>> - int32 i;
>> + uint32 i;
>>
>> // Dereference t so that any panic happens before the lock is
>> held.
>> // Discard result, because t might be moving in the heap.
>> @@ -142,7 +149,8 @@
>> // a bogus i (typically 0, if generated by Go).
>> // Verify it before proceeding.
>> i = t->i;
>> - if(i < 0 || i >= timers.len || timers.t[i] != t) {
>> + t->i = WRONG_INDEX;
>> + if(i < TOP_INDEX || i >= timers.len || timers.t[i] != t) {
>> runtime·unlock(&timers);
>> return false;
>> }
>> @@ -178,24 +186,24 @@
>> timers.sleeping = false;
>> now = runtime·nanotime();
>> for(;;) {
>> - if(timers.len == 0) {
>> + if(timers.len == TOP_INDEX) {
>> delta = -1;
>> break;
>> }
>> - t = timers.t[0];
>> + t = timers.t[TOP_INDEX];
>> delta = t->when - now;
>> if(delta > 0)
>> break;
>> if(t->period > 0) {
>> // leave in heap but adjust next time to
>> fire
>> t->when += t->period * (1 +
>> -delta/t->period);
>> - siftdown(0);
>> + siftdown(TOP_INDEX);
>> } else {
>> // remove from heap
>> - timers.t[0] = timers.t[--timers.len];
>> - timers.t[0]->i = 0;
>> - siftdown(0);
>> - t->i = -1; // mark as removed
>> + timers.t[TOP_INDEX] =
>> timers.t[--timers.len];
>> + timers.t[TOP_INDEX]->i = TOP_INDEX;
>> + siftdown(TOP_INDEX);
>> + t->i = WRONG_INDEX; // mark as removed
>> }
>> f = (void*)t->fv->fn;
>> arg = t->arg;
>> @@ -222,17 +230,17 @@
>> // heap maintenance algorithms.
>>
>> static void
>> -siftup(int32 i)
>> +siftup(uint32 i)
>> {
>> - int32 p;
>> + uint32 p;
>> int64 when;
>> Timer **t, *tmp;
>>
>> t = timers.t;
>> when = t[i]->when;
>> tmp = t[i];
>> - while(i > 0) {
>> - p = (i-1)/4; // parent
>> + while(i > TOP_INDEX) {
>> + p = (i+OFFSET)/4; // parent
>> if(when >= t[p]->when)
>> break;
>> t[i] = t[p];
>> @@ -244,9 +252,9 @@
>> }
>>
>> static void
>> -siftdown(int32 i)
>> +siftdown(uint32 i)
>> {
>> - int32 c, c3, len;
>> + uint32 c, c3, len;
>> int64 when, w, w3;
>> Timer **t, *tmp;
>>
>> @@ -255,7 +263,7 @@
>> when = t[i]->when;
>> tmp = t[i];
>> for(;;) {
>> - c = i*4 + 1; // left child
>> + c = i*4 - OFFSET; // left child
>> c3 = c + 2; // mid child
>> if(c >= len) {
>> break;
>> Index: src/pkg/time/sleep.go
>> ===================================================================
>> --- a/src/pkg/time/sleep.go
>> +++ b/src/pkg/time/sleep.go
>> @@ -15,7 +15,7 @@
>> // Interface to timers implemented in package runtime.
>> // Must be in sync with ../runtime/runtime.h:/^struct.Timer$
>> type runtimeTimer struct {
>> - i int32
>> + i uint32
>> when int64
>> period int64
>> f func(int64, interface{}) // NOTE: must not be closure
>>
>>
>> --
>>
>> ---You received this message because you are subscribed to the Google
>> Groups "golang-dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to golang-dev+unsubscribe@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
Sign in to reply to this message.
On 2013/08/26 13:11:42, bradfitz wrote: > Why? > The main answer: consistency of "wrong index" - ie 0 is always wrong. May be, with this change you will accept "value timers" easily in a future, since then will be cleaner difference between set and unset timer. (https://codereview.appspot.com/12876047/) > > > On Mon, Aug 26, 2013 at 7:54 AM, <mailto:funny.falcon@gmail.com> wrote: > > > Reviewers: golang-dev1, > > > > Message: > > 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 > > > > > > Description: > > time: timers start index to be non 0 > > > > - index changed to uint32 - larger limit > > - 0 is enough to indicate unset timer, no need for -1 > > - with start index == 3, all 4 descendant pointers are always > > in a same CPU cache line (but maybe it doesn't matter) > > > > Please review this at > https://codereview.appspot.**com/12879045/%3Chttps://codereview.appspot.com/1...> > > > > Affected files: > > M src/pkg/runtime/runtime.h > > M src/pkg/runtime/time.goc > > M src/pkg/time/sleep.go > > > > > > Index: src/pkg/runtime/runtime.h > > ==============================**==============================**======= > > --- a/src/pkg/runtime/runtime.h > > +++ b/src/pkg/runtime/runtime.h > > @@ -482,7 +482,7 @@ > > // If this struct changes, adjust ../time/sleep.go:/**runtimeTimer. > > struct Timer > > { > > - int32 i; // heap index > > + uint32 i; // heap index > > > > // Timer wakes up at when, and then at when+period, ... (period > > > 0 only) > > // each time calling f(now, arg) in the timer goroutine, so f must > > be > > Index: src/pkg/runtime/time.goc > > ==============================**==============================**======= > > --- a/src/pkg/runtime/time.goc > > +++ b/src/pkg/runtime/time.goc > > @@ -42,8 +42,8 @@ > > // C runtime. > > > > static void timerproc(void); > > -static void siftup(int32); > > -static void siftdown(int32); > > +static void siftup(uint32); > > +static void siftdown(uint32); > > > > // Ready the goroutine e.data. > > static void > > @@ -84,6 +84,10 @@ > > runtime·unlock(&timers); > > } > > > > +#define TOP_INDEX (3) > > +#define WRONG_INDEX (0) > > +#define OFFSET (TOP_INDEX*3-1) > > + > > // Add a timer to the heap and start or kick the timer proc > > // if the new timer is earlier than any of the others. > > static void > > @@ -102,11 +106,14 @@ > > runtime·free(timers.t); > > timers.t = nt; > > timers.cap = n; > > + if(timers.len < TOP_INDEX) { > > + timers.len = TOP_INDEX; > > + } > > } > > t->i = timers.len++; > > timers.t[t->i] = t; > > siftup(t->i); > > - if(t->i == 0) { > > + if(t->i == TOP_INDEX) { > > // siftup moved to top: new earliest deadline. > > if(timers.sleeping) { > > timers.sleeping = false; > > @@ -129,7 +136,7 @@ > > bool > > runtime·deltimer(Timer *t) > > { > > - int32 i; > > + uint32 i; > > > > // Dereference t so that any panic happens before the lock is held. > > // Discard result, because t might be moving in the heap. > > @@ -142,7 +149,8 @@ > > // a bogus i (typically 0, if generated by Go). > > // Verify it before proceeding. > > i = t->i; > > - if(i < 0 || i >= timers.len || timers.t[i] != t) { > > + t->i = WRONG_INDEX; > > + if(i < TOP_INDEX || i >= timers.len || timers.t[i] != t) { > > runtime·unlock(&timers); > > return false; > > } > > @@ -178,24 +186,24 @@ > > timers.sleeping = false; > > now = runtime·nanotime(); > > for(;;) { > > - if(timers.len == 0) { > > + if(timers.len == TOP_INDEX) { > > delta = -1; > > break; > > } > > - t = timers.t[0]; > > + t = timers.t[TOP_INDEX]; > > delta = t->when - now; > > if(delta > 0) > > break; > > if(t->period > 0) { > > // leave in heap but adjust next time to > > fire > > t->when += t->period * (1 + > > -delta/t->period); > > - siftdown(0); > > + siftdown(TOP_INDEX); > > } else { > > // remove from heap > > - timers.t[0] = timers.t[--timers.len]; > > - timers.t[0]->i = 0; > > - siftdown(0); > > - t->i = -1; // mark as removed > > + timers.t[TOP_INDEX] = > > timers.t[--timers.len]; > > + timers.t[TOP_INDEX]->i = TOP_INDEX; > > + siftdown(TOP_INDEX); > > + t->i = WRONG_INDEX; // mark as removed > > } > > f = (void*)t->fv->fn; > > arg = t->arg; > > @@ -222,17 +230,17 @@ > > // heap maintenance algorithms. > > > > static void > > -siftup(int32 i) > > +siftup(uint32 i) > > { > > - int32 p; > > + uint32 p; > > int64 when; > > Timer **t, *tmp; > > > > t = timers.t; > > when = t[i]->when; > > tmp = t[i]; > > - while(i > 0) { > > - p = (i-1)/4; // parent > > + while(i > TOP_INDEX) { > > + p = (i+OFFSET)/4; // parent > > if(when >= t[p]->when) > > break; > > t[i] = t[p]; > > @@ -244,9 +252,9 @@ > > } > > > > static void > > -siftdown(int32 i) > > +siftdown(uint32 i) > > { > > - int32 c, c3, len; > > + uint32 c, c3, len; > > int64 when, w, w3; > > Timer **t, *tmp; > > > > @@ -255,7 +263,7 @@ > > when = t[i]->when; > > tmp = t[i]; > > for(;;) { > > - c = i*4 + 1; // left child > > + c = i*4 - OFFSET; // left child > > c3 = c + 2; // mid child > > if(c >= len) { > > break; > > Index: src/pkg/time/sleep.go > > ==============================**==============================**======= > > --- a/src/pkg/time/sleep.go > > +++ b/src/pkg/time/sleep.go > > @@ -15,7 +15,7 @@ > > // Interface to timers implemented in package runtime. > > // Must be in sync with ../runtime/runtime.h:/^struct.**Timer$ > > type runtimeTimer struct { > > - i int32 > > + i uint32 > > when int64 > > period int64 > > f func(int64, interface{}) // NOTE: must not be closure > > > > > > -- > > > > ---You received this message because you are subscribed to the Google > > Groups "golang-dev" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to > mailto:golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegroups.com> > > . > > For more options, visit > https://groups.google.com/**groups/opt_out%3Chttps://groups.google.com/groups...> > > . > >
Sign in to reply to this message.
On 2013/08/26 13:28:33, dvyukov wrote:
> I have the same question.
> 2^31 timers should be enough for everyone (r)
>
> Yuri, if you want to improve timers performance you may try to store
> when directly in the timers array. Now it contains just Timer*, try
> storing {Timer* t, int64 when}. It should remove lots of indirection
> in siftup/siftdown/timerproc.
>
I've just tried. Unfortunately, benchmarks shows no difference :(
>
>
>
> On Mon, Aug 26, 2013 at 5:11 PM, Brad Fitzpatrick <mailto:bradfitz@golang.org>
wrote:
> > Why?
> >
> >
> >
> > On Mon, Aug 26, 2013 at 7:54 AM, <mailto:funny.falcon@gmail.com> wrote:
> >>
> >> Reviewers: golang-dev1,
> >>
> >> Message:
> >> 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
> >>
> >>
> >> Description:
> >> time: timers start index to be non 0
> >>
> >> - index changed to uint32 - larger limit
> >> - 0 is enough to indicate unset timer, no need for -1
> >> - with start index == 3, all 4 descendant pointers are always
> >> in a same CPU cache line (but maybe it doesn't matter)
> >>
> >> Please review this at https://codereview.appspot.com/12879045/
> >>
> >> Affected files:
> >> M src/pkg/runtime/runtime.h
> >> M src/pkg/runtime/time.goc
> >> M src/pkg/time/sleep.go
> >>
> >>
> >> Index: src/pkg/runtime/runtime.h
> >> ===================================================================
> >> --- a/src/pkg/runtime/runtime.h
> >> +++ b/src/pkg/runtime/runtime.h
> >> @@ -482,7 +482,7 @@
> >> // If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
> >> struct Timer
> >> {
> >> - int32 i; // heap index
> >> + uint32 i; // heap index
> >>
> >> // Timer wakes up at when, and then at when+period, ... (period >
> >> 0 only)
> >> // each time calling f(now, arg) in the timer goroutine, so f must
> >> be
> >> Index: src/pkg/runtime/time.goc
> >> ===================================================================
> >> --- a/src/pkg/runtime/time.goc
> >> +++ b/src/pkg/runtime/time.goc
> >> @@ -42,8 +42,8 @@
> >> // C runtime.
> >>
> >> static void timerproc(void);
> >> -static void siftup(int32);
> >> -static void siftdown(int32);
> >> +static void siftup(uint32);
> >> +static void siftdown(uint32);
> >>
> >> // Ready the goroutine e.data.
> >> static void
> >> @@ -84,6 +84,10 @@
> >> runtime·unlock(&timers);
> >> }
> >>
> >> +#define TOP_INDEX (3)
> >> +#define WRONG_INDEX (0)
> >> +#define OFFSET (TOP_INDEX*3-1)
> >> +
> >> // Add a timer to the heap and start or kick the timer proc
> >> // if the new timer is earlier than any of the others.
> >> static void
> >> @@ -102,11 +106,14 @@
> >> runtime·free(timers.t);
> >> timers.t = nt;
> >> timers.cap = n;
> >> + if(timers.len < TOP_INDEX) {
> >> + timers.len = TOP_INDEX;
> >> + }
> >> }
> >> t->i = timers.len++;
> >> timers.t[t->i] = t;
> >> siftup(t->i);
> >> - if(t->i == 0) {
> >> + if(t->i == TOP_INDEX) {
> >> // siftup moved to top: new earliest deadline.
> >> if(timers.sleeping) {
> >> timers.sleeping = false;
> >> @@ -129,7 +136,7 @@
> >> bool
> >> runtime·deltimer(Timer *t)
> >> {
> >> - int32 i;
> >> + uint32 i;
> >>
> >> // Dereference t so that any panic happens before the lock is
> >> held.
> >> // Discard result, because t might be moving in the heap.
> >> @@ -142,7 +149,8 @@
> >> // a bogus i (typically 0, if generated by Go).
> >> // Verify it before proceeding.
> >> i = t->i;
> >> - if(i < 0 || i >= timers.len || timers.t[i] != t) {
> >> + t->i = WRONG_INDEX;
> >> + if(i < TOP_INDEX || i >= timers.len || timers.t[i] != t) {
> >> runtime·unlock(&timers);
> >> return false;
> >> }
> >> @@ -178,24 +186,24 @@
> >> timers.sleeping = false;
> >> now = runtime·nanotime();
> >> for(;;) {
> >> - if(timers.len == 0) {
> >> + if(timers.len == TOP_INDEX) {
> >> delta = -1;
> >> break;
> >> }
> >> - t = timers.t[0];
> >> + t = timers.t[TOP_INDEX];
> >> delta = t->when - now;
> >> if(delta > 0)
> >> break;
> >> if(t->period > 0) {
> >> // leave in heap but adjust next time to
> >> fire
> >> t->when += t->period * (1 +
> >> -delta/t->period);
> >> - siftdown(0);
> >> + siftdown(TOP_INDEX);
> >> } else {
> >> // remove from heap
> >> - timers.t[0] = timers.t[--timers.len];
> >> - timers.t[0]->i = 0;
> >> - siftdown(0);
> >> - t->i = -1; // mark as removed
> >> + timers.t[TOP_INDEX] =
> >> timers.t[--timers.len];
> >> + timers.t[TOP_INDEX]->i = TOP_INDEX;
> >> + siftdown(TOP_INDEX);
> >> + t->i = WRONG_INDEX; // mark as removed
> >> }
> >> f = (void*)t->fv->fn;
> >> arg = t->arg;
> >> @@ -222,17 +230,17 @@
> >> // heap maintenance algorithms.
> >>
> >> static void
> >> -siftup(int32 i)
> >> +siftup(uint32 i)
> >> {
> >> - int32 p;
> >> + uint32 p;
> >> int64 when;
> >> Timer **t, *tmp;
> >>
> >> t = timers.t;
> >> when = t[i]->when;
> >> tmp = t[i];
> >> - while(i > 0) {
> >> - p = (i-1)/4; // parent
> >> + while(i > TOP_INDEX) {
> >> + p = (i+OFFSET)/4; // parent
> >> if(when >= t[p]->when)
> >> break;
> >> t[i] = t[p];
> >> @@ -244,9 +252,9 @@
> >> }
> >>
> >> static void
> >> -siftdown(int32 i)
> >> +siftdown(uint32 i)
> >> {
> >> - int32 c, c3, len;
> >> + uint32 c, c3, len;
> >> int64 when, w, w3;
> >> Timer **t, *tmp;
> >>
> >> @@ -255,7 +263,7 @@
> >> when = t[i]->when;
> >> tmp = t[i];
> >> for(;;) {
> >> - c = i*4 + 1; // left child
> >> + c = i*4 - OFFSET; // left child
> >> c3 = c + 2; // mid child
> >> if(c >= len) {
> >> break;
> >> Index: src/pkg/time/sleep.go
> >> ===================================================================
> >> --- a/src/pkg/time/sleep.go
> >> +++ b/src/pkg/time/sleep.go
> >> @@ -15,7 +15,7 @@
> >> // Interface to timers implemented in package runtime.
> >> // Must be in sync with ../runtime/runtime.h:/^struct.Timer$
> >> type runtimeTimer struct {
> >> - i int32
> >> + i uint32
> >> when int64
> >> period int64
> >> f func(int64, interface{}) // NOTE: must not be closure
> >>
> >>
> >> --
> >>
> >> ---You received this message because you are subscribed to the Google
> >> Groups "golang-dev" group.
> >> To unsubscribe from this group and stop receiving emails from it, send an
> >> email to mailto:golang-dev+unsubscribe@googlegroups.com.
> >> For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
> > --
> >
> > ---
> > You received this message because you are subscribed to the Google Groups
> > "golang-dev" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to mailto:golang-dev+unsubscribe@googlegroups.com.
> > For more options, visit https://groups.google.com/groups/opt_out.
Sign in to reply to this message.
On 2013/08/26 13:28:33, dvyukov wrote:
> I have the same question.
> 2^31 timers should be enough for everyone (r)
>
>
Actual limit is 2^31 / 4 = 2^29 cause:
c = i*4 + 1; // left child
c3 = c + 2; // mid child
if(c >= len) { /* (((2^31)/4)*4+1) == (-(2^31)+1) < (2^31)/4 */
2^29 = 536_870_912 is still very large, though
Sign in to reply to this message.
Replacing golang-dev with golang-codereviews.
Sign in to reply to this message.
R=dvyukov@google.com (assigned by bradfitz@golang.org)
Sign in to reply to this message.
On 2013/08/26 13:31:25, funny.falcon wrote: > On 2013/08/26 13:11:42, bradfitz wrote: > > Why? > > > > The main answer: consistency of "wrong index" - ie 0 is always wrong. > May be, with this change you will accept "value timers" easily in a future, > since > then will be cleaner difference between set and unset timer. > (https://codereview.appspot.com/12876047/) The decision on "value timers" was negative. And it must not be based on implementation aspects. If/when we reevaluate decision on "value timers", we can reevaluate this change as well. But for now I propose to close this. R=close
Sign in to reply to this message.
On 2014/01/20 07:47:39, dvyukov wrote: > On 2013/08/26 13:31:25, funny.falcon wrote: > > On 2013/08/26 13:11:42, bradfitz wrote: > > > Why? > > > > > > > The main answer: consistency of "wrong index" - ie 0 is always wrong. > > May be, with this change you will accept "value timers" easily in a future, > > since > > then will be cleaner difference between set and unset timer. > > (https://codereview.appspot.com/12876047/) > > > The decision on "value timers" was negative. And it must not be based on > implementation aspects. > If/when we reevaluate decision on "value timers", we can reevaluate this change > as well. But for now I propose to close this. > R=close hmm... this issue is not tied with "value timers". so that, strange to see reference to.
Sign in to reply to this message.
On Mon, Jan 20, 2014 at 3:25 PM, <funny.falcon@gmail.com> wrote: > On 2014/01/20 07:47:39, dvyukov wrote: >> >> On 2013/08/26 13:31:25, funny.falcon wrote: >> > On 2013/08/26 13:11:42, bradfitz wrote: >> > > Why? >> > > >> > >> > The main answer: consistency of "wrong index" - ie 0 is always > > wrong. >> >> > May be, with this change you will accept "value timers" easily in a > > future, >> >> > since >> > then will be cleaner difference between set and unset timer. >> > (https://codereview.appspot.com/12876047/) > > > >> The decision on "value timers" was negative. And it must not be based > > on >> >> implementation aspects. >> If/when we reevaluate decision on "value timers", we can reevaluate > > this change >> >> as well. But for now I propose to close this. >> R=close > > > hmm... this issue is not tied with "value timers". so that, strange to > see reference to. You've mentioned "value timers" in the rationale for this change.
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
