code review 21030043: math/rand: minor optimization to Perm

math/rand: minor optimization to Perm

Instead of writing out 0..n and then reading it
back, just use i when it is needed.

Wikipedia calls this the "inside-out" implementation:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

This yields identical values to the previous
implementation, given the same seed. (Note that the
output from Example_rand is unchanged.)

2.8 GHz Intel Core i7, results very stable:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3           138          136   -1.45%
BenchmarkPerm30          825          803   -2.67%

Stock Raspberry Pi, minimum improvement out of three runs:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3          5774         5664   -1.91%
BenchmarkPerm30        32582        29381   -9.82%

[josharian, 2013-12-14 02:21:02]

Hello golang-dev@googlegroups.com,

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

[dave_cheney.net, 2013-12-14 02:24:31]

On 2013/12/14 02:21:02, josharian wrote:
> Hello mailto:golang-dev@googlegroups.com,
> 
> I'd like you to review this change to
> https://code.google.com/p/go

Hi Josh,

Could you please test this on 386 or arm. I have a feeling the additional array
operations (and their bounds checks) makes this change more expensive. ~1-2%
improvement on the nano second range is inside the noise floor for the benchmark
framework IMO

In the future if the compiler gets smarter about eliding bounds checks, this
would be a valuable change.

Cheers

Dave

[josharian, 2013-12-14 22:19:17]

> Could you please test this on 386 or arm.

Absolutely. I've updated the description with numbers for arm. Thanks for
keeping me honest, Dave.


> I have a feeling the additional array operations (and their bounds checks)
makes this change more expensive.

This change is a strict reduction in array operations (and in operations of all
kinds). In case you're curious, you
can see a pretty clear illustration in the arm assembly diff at
https://gist.github.com/josharian/7965541#file-diff_21030043_arm-diff.


> ~1-2% improvement on the nano second range is inside the noise floor for the
benchmark framework IMO

That's fair, although this (admittedly quite small) improvement is very
consistent on 386, when racing old/new side by side.
The arm numbers vary more, but are always favorable.


-josh

[dave_cheney.net, 2013-12-14 23:55:36]

On 2013/12/14 22:19:17, josharian wrote:
> > Could you please test this on 386 or arm.
> 
> Absolutely. I've updated the description with numbers for arm. Thanks for
> keeping me honest, Dave.
> 
> 
> > I have a feeling the additional array operations (and their bounds checks)
> makes this change more expensive.
> 
> This change is a strict reduction in array operations (and in operations of
all
> kinds). In case you're curious, you
> can see a pretty clear illustration in the arm assembly diff at
> https://gist.github.com/josharian/7965541#file-diff_21030043_arm-diff.
> 
> 
> > ~1-2% improvement on the nano second range is inside the noise floor for the
> benchmark framework IMO
> 
> That's fair, although this (admittedly quite small) improvement is very
> consistent on 386, when racing old/new side by side.
> The arm numbers vary more, but are always favorable.
> 
> 
> -josh

Hi Josh,

Thanks for your reply, this looks like a solid improvement on all architectures.
If I had an objection, consider it removed. However, I'm not a mathematician, so
I'll have to wait for someone else to LGTM the change.

[mtj1, 2013-12-15 12:19:31]

Dave,

I understand that this is not intended as a "math/logic" change, just a
cache-friendly read saver, but I don't personally understand part of it.

In the original, m[i] is set to i in the initialization loop so that in the
second (permutation) loop, the swapping of m[i] and m[j] is a typical fair
shuffle. (where j runs from 0 to i inclusively)

In the second, the idea is to delay the setting of m[i] to i until the
swap, since you know that m[i] (the newly "added" array element) has the
value of i. That makes sense. What I don't understand (well, I understand
but don't like) is the case when j == i which happens when  r.Intn(i + 1)
== i. In that case you get:

m[i], m[i] = 0, i

which given the language rules works, since the '0' (from the
zero-initialized m[i]) is assigned to m[i] before the i is assigned to
m[i]. (In fact, perhaps the compiler drops the m[i]=m[i] assignment as an
optimization.) In any case, every reader of this code will puzzle over this
to convince themselves that the uninitialized swap does not put an extra 0
into the permutation. Is it worth 30 seconds of reader's time, every time,
for the small gain?

If nothing else, a comment along the lines of "// don't worry, be happy"
would be good. ;-)

 func (r *Rand) Perm(n int) []int {
        m := make([]int, n)
        for i := 0; i < n; i++ {
-               m[i] = i
-       }
-       for i := 0; i < n; i++ {
                j := r.Intn(i + 1)
-               m[i], m[j] = m[j], m[i]
+               m[i], m[j] = m[j], i
        }
        return m
 }


On Sat, Dec 14, 2013 at 3:55 PM, <dave@cheney.net> wrote:

> On 2013/12/14 22:19:17, josharian wrote:
>
>> > Could you please test this on 386 or arm.
>>
>
>  Absolutely. I've updated the description with numbers for arm. Thanks
>>
> for
>
>> keeping me honest, Dave.
>>
>
>
>  > I have a feeling the additional array operations (and their bounds
>>
> checks)
>
>> makes this change more expensive.
>>
>
>  This change is a strict reduction in array operations (and in
>>
> operations of all
>
>> kinds). In case you're curious, you
>> can see a pretty clear illustration in the arm assembly diff at
>> https://gist.github.com/josharian/7965541#file-diff_21030043_arm-diff.
>>
>
>
>  > ~1-2% improvement on the nano second range is inside the noise floor
>>
> for the
>
>> benchmark framework IMO
>>
>
>  That's fair, although this (admittedly quite small) improvement is
>>
> very
>
>> consistent on 386, when racing old/new side by side.
>> The arm numbers vary more, but are always favorable.
>>
>
>
>  -josh
>>
>
> Hi Josh,
>
> Thanks for your reply, this looks like a solid improvement on all
> architectures. If I had an objection, consider it removed. However, I'm
> not a mathematician, so I'll have to wait for someone else to LGTM the
> change.
>
>
> https://codereview.appspot.com/21030043/
>
> --
>
> ---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.
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765
*(Note: this email has been shared with you under the terms of Regulation
23 <http://go/cory-eula>)*

[mtj1, 2013-12-15 12:21:17]

strike the part about the optimization. that's a dumb mental mistake. all
the rest stands unchanged.


On Sun, Dec 15, 2013 at 4:19 AM, Michael Jones <mtj@google.com> wrote:

> Dave,
>
> I understand that this is not intended as a "math/logic" change, just a
> cache-friendly read saver, but I don't personally understand part of it.
>
> In the original, m[i] is set to i in the initialization loop so that in
> the second (permutation) loop, the swapping of m[i] and m[j] is a typical
> fair shuffle. (where j runs from 0 to i inclusively)
>
> In the second, the idea is to delay the setting of m[i] to i until the
> swap, since you know that m[i] (the newly "added" array element) has the
> value of i. That makes sense. What I don't understand (well, I understand
> but don't like) is the case when j == i which happens when  r.Intn(i + 1)
> == i. In that case you get:
>
> m[i], m[i] = 0, i
>
> which given the language rules works, since the '0' (from the
> zero-initialized m[i]) is assigned to m[i] before the i is assigned to
> m[i]. (In fact, perhaps the compiler drops the m[i]=m[i] assignment as an
> optimization.) In any case, every reader of this code will puzzle over this
> to convince themselves that the uninitialized swap does not put an extra 0
> into the permutation. Is it worth 30 seconds of reader's time, every time,
> for the small gain?
>
> If nothing else, a comment along the lines of "// don't worry, be happy"
> would be good. ;-)
>
>  func (r *Rand) Perm(n int) []int {
>         m := make([]int, n)
>         for i := 0; i < n; i++ {
> -               m[i] = i
> -       }
> -       for i := 0; i < n; i++ {
>                 j := r.Intn(i + 1)
> -               m[i], m[j] = m[j], m[i]
> +               m[i], m[j] = m[j], i
>         }
>         return m
>  }
>
>
> On Sat, Dec 14, 2013 at 3:55 PM, <dave@cheney.net> wrote:
>
>> On 2013/12/14 22:19:17, josharian wrote:
>>
>>> > Could you please test this on 386 or arm.
>>>
>>
>>  Absolutely. I've updated the description with numbers for arm. Thanks
>>>
>> for
>>
>>> keeping me honest, Dave.
>>>
>>
>>
>>  > I have a feeling the additional array operations (and their bounds
>>>
>> checks)
>>
>>> makes this change more expensive.
>>>
>>
>>  This change is a strict reduction in array operations (and in
>>>
>> operations of all
>>
>>> kinds). In case you're curious, you
>>> can see a pretty clear illustration in the arm assembly diff at
>>> https://gist.github.com/josharian/7965541#file-diff_21030043_arm-diff.
>>>
>>
>>
>>  > ~1-2% improvement on the nano second range is inside the noise floor
>>>
>> for the
>>
>>> benchmark framework IMO
>>>
>>
>>  That's fair, although this (admittedly quite small) improvement is
>>>
>> very
>>
>>> consistent on 386, when racing old/new side by side.
>>> The arm numbers vary more, but are always favorable.
>>>
>>
>>
>>  -josh
>>>
>>
>> Hi Josh,
>>
>> Thanks for your reply, this looks like a solid improvement on all
>> architectures. If I had an objection, consider it removed. However, I'm
>> not a mathematician, so I'll have to wait for someone else to LGTM the
>> change.
>>
>>
>> https://codereview.appspot.com/21030043/
>>
>> --
>>
>> ---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.
>>
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765
> *(Note: this email has been shared with you under the terms of Regulation
> 23 <http://go/cory-eula>)*
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765
*(Note: this email has been shared with you under the terms of Regulation
23 <http://go/cory-eula>)*

[josharian, 2013-12-15 16:45:19]

> In any case, every reader of this code will puzzle over this
> to convince themselves that the uninitialized swap does not put an extra 0
> into the permutation. Is it worth 30 seconds of reader's time, every time,
> for the small gain?

No. Readability trumps tiny performance tweaks like this.

Would changing

		m[i], m[j] = m[j], i

to

		m[i] = m[j]
		m[j] = i

help sufficiently, to your mind? If not, I'll cheerily abandon this CL.

-josh

[adg, 2013-12-15 21:35:30]

LGTM

But wait for some consensus I guess

[mtj1, 2013-12-16 15:33:55]

This looks fine to me. It works and it's meaning makes clear that what is
happening is "copy then set" rather than "swap."

I'm not a Go check-in approver though, so you'll need one of them to say
OK. (That said, it *is* OK in all but that gatekeeper regard.)


On Sun, Dec 15, 2013 at 8:45 AM, <josharian@gmail.com> wrote:

>  In any case, every reader of this code will puzzle over this
>> to convince themselves that the uninitialized swap does not put an
>>
> extra 0
>
>> into the permutation. Is it worth 30 seconds of reader's time, every
>>
> time,
>
>> for the small gain?
>>
>
> No. Readability trumps tiny performance tweaks like this.
>
> Would changing
>
>
>                 m[i], m[j] = m[j], i
>
> to
>
>                 m[i] = m[j]
>                 m[j] = i
>
> help sufficiently, to your mind? If not, I'll cheerily abandon this CL.
>
> -josh
>
>
> https://codereview.appspot.com/21030043/
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765
*(Note: this email has been shared with you under the terms of Regulation
23 <http://go/cory-eula>)*

[josharian, 2013-12-17 02:10:56]

Ok, I've incorporated Michael's suggestion, and Dave's worries are allayed.
Andrew, is this sufficient consensus? :)

-josh

[adg, 2013-12-17 02:15:49]

On 17 December 2013 13:10, <josharian@gmail.com> wrote:

> Ok, I've incorporated Michael's suggestion, and Dave's worries are
> allayed. Andrew, is this sufficient consensus? :)
>

Yep :-)

[adg, 2013-12-17 02:49:53]

*** Submitted as https://code.google.com/p/go/source/detail?r=8ef815dd2770 ***

math/rand: minor optimization to Perm

Instead of writing out 0..n and then reading it
back, just use i when it is needed.

Wikipedia calls this the "inside-out" implementation:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

This yields identical values to the previous
implementation, given the same seed. (Note that the
output from Example_rand is unchanged.)

2.8 GHz Intel Core i7, results very stable:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3           138          136   -1.45%
BenchmarkPerm30          825          803   -2.67%

Stock Raspberry Pi, minimum improvement out of three runs:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3          5774         5664   -1.91%
BenchmarkPerm30        32582        29381   -9.82%

R=golang-dev, dave, mtj, adg
CC=golang-dev
https://codereview.appspot.com/21030043

Committer: Andrew Gerrand <adg@golang.org>