Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(554)

Issue 6643053: code review 6643053: math/big: more conservative use of lock for divisor table (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
11 years, 5 months ago by gri
Modified:
11 years, 5 months ago
Reviewers:
mtj1, dvyukov
CC:
mtj, dfc, golang-dev
Visibility:
Public.

Description

math/big: more conservative use of lock for divisor table Minor performance impact running sequentially: benchmark old ns/op new ns/op delta BenchmarkString10Base2 389 391 +0.51% BenchmarkString100Base2 1530 1534 +0.26% BenchmarkString1000Base2 11789 11787 -0.02% BenchmarkString10000Base2 111443 112030 +0.53% BenchmarkString100000Base2 1017483 1015347 -0.21% BenchmarkString10Base8 339 344 +1.47% BenchmarkString100Base8 753 756 +0.40% BenchmarkString1000Base8 4618 4641 +0.50% BenchmarkString10000Base8 43217 43534 +0.73% BenchmarkString100000Base8 397518 400602 +0.78% BenchmarkString10Base10 630 630 +0.00% BenchmarkString100Base10 1975 1960 -0.76% BenchmarkString1000Base10 10179 10174 -0.05% BenchmarkString10000Base10 44527 44416 -0.25% BenchmarkString100000Base10 14404694 14425308 +0.14% BenchmarkString10Base16 283 288 +1.77% BenchmarkString100Base16 597 598 +0.17% BenchmarkString1000Base16 3189 3186 -0.09% BenchmarkString10000Base16 29403 29364 -0.13% BenchmarkString100000Base16 265657 265587 -0.03% Note that due to other improvements (faster assembly routines, better code generation by compiler), these benchmarks now run up to 37% faster than they used to at the last time measured (1/9/2012). Minor performance impact for StringPiParallel running in parallel: Current CL but with Lock/Unlock commented out (removed): BenchmarkStringPiParallel 5000 343581 ns/op BenchmarkStringPiParallel-2 10000 184511 ns/op BenchmarkStringPiParallel-3 10000 129768 ns/op BenchmarkStringPiParallel-4 10000 102326 ns/op Current CL: BenchmarkStringPiParallel 5000 345169 ns/op BenchmarkStringPiParallel-2 10000 185827 ns/op BenchmarkStringPiParallel-3 10000 131168 ns/op BenchmarkStringPiParallel-4 10000 102353 ns/op Fixes issue 4218.

Patch Set 1 #

Patch Set 2 : diff -r 1b587887ceb2 https://code.google.com/p/go #

Patch Set 3 : diff -r 1b587887ceb2 https://code.google.com/p/go #

Total comments: 4

Patch Set 4 : diff -r 0558d15b2681 https://code.google.com/p/go #

Patch Set 5 : diff -r 236ee151d1bc https://code.google.com/p/go #

Patch Set 6 : diff -r bc50fc903d6e https://code.google.com/p/go #

Patch Set 7 : diff -r bc50fc903d6e https://code.google.com/p/go #

Patch Set 8 : diff -r 7677524b8a24 https://code.google.com/p/go #

Patch Set 9 : diff -r 7677524b8a24 https://code.google.com/p/go #

Patch Set 10 : diff -r 7677524b8a24 https://code.google.com/p/go #

Patch Set 11 : diff -r 2aa2c1c93060 https://code.google.com/p/go #

Unified diffs Side-by-side diffs Delta from patch set Stats (+55 lines, -23 lines) Patch
M src/pkg/math/big/nat.go View 1 2 3 4 3 chunks +17 lines, -21 lines 0 comments Download
M src/pkg/math/big/nat_test.go View 1 2 3 4 5 6 7 8 4 chunks +38 lines, -2 lines 0 comments Download

Messages

Total messages: 23
gri
Hello dvyukov@google.com, michael.jones@gmail.com (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go
11 years, 5 months ago (2012-10-09 23:51:49 UTC) #1
dfc
https://codereview.appspot.com/6643053/diff/3/src/pkg/math/big/nat.go File src/pkg/math/big/nat.go (right): https://codereview.appspot.com/6643053/diff/3/src/pkg/math/big/nat.go#newcode925 src/pkg/math/big/nat.go:925: mu sync.Mutex // protects table s/mu// https://codereview.appspot.com/6643053/diff/3/src/pkg/math/big/nat.go#newcode949 src/pkg/math/big/nat.go:949: cacheBase10.mu.Lock() ...
11 years, 5 months ago (2012-10-10 00:11:01 UTC) #2
gri
PTAL. https://codereview.appspot.com/6643053/diff/3/src/pkg/math/big/nat.go File src/pkg/math/big/nat.go (right): https://codereview.appspot.com/6643053/diff/3/src/pkg/math/big/nat.go#newcode925 src/pkg/math/big/nat.go:925: mu sync.Mutex // protects table On 2012/10/10 00:11:01, ...
11 years, 5 months ago (2012-10-10 00:15:05 UTC) #3
dfc
Thank you. I'm not sure about this, I think the race still exists through table ...
11 years, 5 months ago (2012-10-10 05:25:07 UTC) #4
dvyukov
I do not see the race now, looks correct. But I am concerned about performance ...
11 years, 5 months ago (2012-10-10 14:20:58 UTC) #5
gri
PTAL. I am not concerned about the performance. Correctness trumps speed and the performance degradation ...
11 years, 5 months ago (2012-10-10 18:18:41 UTC) #6
dvyukov
On Wed, Oct 10, 2012 at 10:18 PM, <gri@golang.org> wrote: > PTAL. > > I ...
11 years, 5 months ago (2012-10-10 18:38:13 UTC) #7
gri
I'm still not concerned. Also, I cannot reproduce the slowdown you are reporting: I have ...
11 years, 5 months ago (2012-10-10 20:51:36 UTC) #8
gri
Hello dvyukov@google.com, michael.jones@gmail.com, dave@cheney.net (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 5 months ago (2012-10-10 20:51:53 UTC) #9
dvyukov
Looks correct to me
11 years, 5 months ago (2012-10-11 04:20:05 UTC) #10
gri
Dmitry; Can you please give this CL a LGTM if you're ok with it now? ...
11 years, 5 months ago (2012-10-11 16:38:29 UTC) #11
dvyukov
Lgtm On Oct 11, 2012 8:38 PM, "Robert Griesemer" <gri@golang.org> wrote: > Dmitry; > > ...
11 years, 5 months ago (2012-10-11 20:01:20 UTC) #12
gri
*** Submitted as http://code.google.com/p/go/source/detail?r=57e13fc87f43 *** math/big: more conservative use of lock for divisor table Minor ...
11 years, 5 months ago (2012-10-11 23:04:08 UTC) #13
mtj
Just seeing this now (email was to a mostly unused personal account rather than my ...
11 years, 5 months ago (2012-10-13 14:50:57 UTC) #14
mtj
I said that wrong (just woke up). It's not so much n**(1/2), n**(1/4).. as it ...
11 years, 5 months ago (2012-10-13 15:03:33 UTC) #15
dvyukov
On Sat, Oct 13, 2012 at 6:50 PM, Michael Jones <michael.jones@gmail.com>wrote: > Just seeing this ...
11 years, 5 months ago (2012-10-14 09:05:22 UTC) #16
mtj1
Thanks! Performance wise, it is important that other goroutines be able to use the read-only ...
11 years, 5 months ago (2012-10-14 12:46:00 UTC) #17
dvyukov
It is not the case now. On Sun, Oct 14, 2012 at 4:45 PM, Michael ...
11 years, 5 months ago (2012-10-15 10:31:23 UTC) #18
mtj
Ok. Will look. Thank you for bringing this to my attention! On Mon, Oct 15, ...
11 years, 5 months ago (2012-10-15 20:51:58 UTC) #19
gri
The only safe way I see at the moment to do this is to lock/unlock ...
11 years, 5 months ago (2012-10-15 21:35:07 UTC) #20
mtj1
OK. On Oct 15, 2012 2:35 PM, "Robert Griesemer" <gri@golang.org> wrote: > The only safe ...
11 years, 5 months ago (2012-10-15 22:07:39 UTC) #21
dvyukov
On 2012/10/15 21:35:07, gri wrote: > The only safe way I see at the moment ...
11 years, 5 months ago (2012-10-24 19:03:50 UTC) #22
mtj1
11 years, 5 months ago (2012-10-24 20:33:52 UTC) #23
In an airport on the way to Cypress. Will look ASAP.

On Wed, Oct 24, 2012 at 12:03 PM,  <dvyukov@google.com> wrote:
> On 2012/10/15 21:35:07, gri wrote:
>>
>> The only safe way I see at the moment to do this is to lock/unlock the
>> mutex for each new table entry. That's not hard, but I don't know if
>
> it's
>>
>> worth it. I am worried about correctness of lock-free approaches
>
> (using
>>
>> package atomic) that operate on slice elements. But I'm happy to be
>
> proven
>>
>> otherwise. Either way, I believe what we have now is correct if
>
> possible
>>
>> not optimal performance-wise. But again, I don't think there's an
>
> immediate
>>
>> urgency for this to be fixed as I am not aware of programs caring
>
> about
>>
>> this too much at the moment.
>> - gri
>
>
>
> It's quite easy to implement w/o atomic ops on slice elements. That's
> what I had in mind:
> https://codereview.appspot.com/6766047/diff/2001/src/pkg/math/big/nat.go
>
>
>
>> On Mon, Oct 15, 2012 at 1:51 PM, Michael Jones
>
> <michael.jones@gmail.com>wrote:
>
>> > Ok. Will look. Thank you for bringing this to my attention!
>> >
>> >
>> > On Mon, Oct 15, 2012 at 3:31 AM, Dmitry Vyukov
>
> <mailto:dvyukov@google.com> wrote:
>>
>> >
>> >> It is not the case now.
>> >>
>> >>
>> >> On Sun, Oct 14, 2012 at 4:45 PM, Michael Jones
>
> <mailto:mtj@google.com> wrote:
>>
>> >>
>> >>> Thanks! Performance wise, it is important that other goroutines be
>
> able
>>
>> >>> to use the read-only smaller entries while a larger one is being
>
> created.
>>
>> >>>
>> >>>
>> >>> On Sun, Oct 14, 2012 at 2:05 AM, Dmitry Vyukov
>
> <dvyukov@google.com>wrote:
>>
>> >>>
>> >>>> I suggested to Robert to make the code work the way you describe.
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>  --
>> >>> Michael T. Jones | Chief Technology Advocate  |
>
> mailto:mtj@google.com |  +1
>>
>> >>> 650-335-5765
>> >>>
>> >>>
>> >>
>> >
>> >
>> > --
>> > Michael T. Jones
>> > mailto:michael.jones@gmail.com
>> > http://www.google.com/profiles/michael.jones
>> >
>
>
>
> https://codereview.appspot.com/6643053/



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b