code review 126720043: test/mapnan.go: add regression test for non-empty inter...

test/mapnan.go: add regression test for non-empty interfaces.

[adonovan, 2014-08-06 19:15:30]

Hello golang-codereviews@googlegroups.com,

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

[adonovan, 2014-08-06 19:19:15]

On 2014/08/06 19:15:30, adonovan wrote:
> Hello mailto:golang-codereviews@googlegroups.com,
> 
> I'd like you to review this change to
> https://code.google.com/p/go/

Having written this regression test, the phrase "lightning never strikes twice"
springs to mind.  Suggestions for worthwhile generalizations much appreciated...

[bradfitz, 2014-08-06 19:19:50]

Seems a little odd the file's called mapnan.go if it does non-nan stuff too.

I see you want to reuse code, though.



On Wed, Aug 6, 2014 at 12:15 PM, adonovan via golang-codereviews <
golang-codereviews@googlegroups.com> wrote:

> Reviewers: golang-codereviews,
>
> Message:
> Hello golang-codereviews@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go/
>
>
> Description:
> test/mapnan.go: add regression test for non-empty interfaces.
>
> Please review this at https://codereview.appspot.com/126720043/
>
> Affected files (+46, -20 lines):
>   M test/mapnan.go
>
>
> Index: test/mapnan.go
> ===================================================================
> --- a/test/mapnan.go
> +++ b/test/mapnan.go
> @@ -5,7 +5,7 @@
>  // Use of this source code is governed by a BSD-style
>  // license that can be found in the LICENSE file.
>
> -// Test that NaNs in maps don't go quadratic.
> +// Test that maps don't go quadratic for NaNs and other values.
>
>  package main
>
> @@ -15,32 +15,26 @@
>         "time"
>  )
>
> -func main() {
> -
> -       // Test that NaNs in maps don't go quadratic.
> -       t := func(n int) time.Duration {
> -               t1 := time.Now()
> -               m := map[float64]int{}
> -               nan := math.NaN()
> -               for i := 0; i < n; i++ {
> -                       m[nan] = 1
> -               }
> -               if len(m) != n {
> -                       panic("wrong size map after nan insertion")
> -               }
> -               return time.Since(t1)
> -       }
> -
> +// checkLinear asserts that the running time of f(n) is in O(n).
> +// tries is the initial number of iterations.
> +func checkLinear(tries int, f func(n int)) {
>         // Depending on the machine and OS, this test might be too fast
>         // to measure with accurate enough granularity. On failure,
>         // make it run longer, hoping that the timing granularity
>         // is eventually sufficient.
>
> -       n := 30000 // ~8ms user time on a Mid 2011 MacBook Air (1.8 GHz
> Core i7)
> +       timeF := func(n int) time.Duration {
> +               t1 := time.Now()
> +               f(n)
> +               return time.Since(t1)
> +       }
> +
> +       n := tries
>         fails := 0
>         for {
> -               t1 := t(n)
> -               t2 := t(2 * n)
> +               t1 := timeF(n)
> +               t2 := timeF(2 * n)
> +
>                 // should be 2x (linear); allow up to 3x
>                 if t2 < 3*t1 {
>                         return
> @@ -54,3 +48,35 @@
>                 }
>         }
>  }
> +
> +type C int
> +
> +func (C) f() {}
> +
> +func main() {
> +       // Test that NaNs in maps don't go quadratic.
> +       tNaN := func(n int) {
> +               m := map[float64]int{}
> +               nan := math.NaN()
> +               for i := 0; i < n; i++ {
> +                       m[nan] = 1
> +               }
> +               if len(m) != n {
> +                       panic("wrong size map after nan insertion")
> +               }
> +       }
> +       checkLinear(30000, tNaN) // ~8ms user time on a Mid 2011 MacBook
> Air (1.8 GHz Core i7))
> +
> +       // Test that non-empty interfaces in maps don't go quadratic.
> +       // (Regression test for CL 119360043.)
> +       tIface := func(n int) {
> +               m := map[interface {
> +                       f()
> +               }]int{}
> +               for i := 0; i < n; i++ {
> +                       m[C(i)] = 1
> +               }
> +       }
> +
> +       checkLinear(3000, tIface) // ~1ms on a 1.6GHz Zeon
> +}
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[rsc, 2014-08-06 19:47:35]

You can hg mv the file to a new name.

[adonovan, 2014-08-06 19:54:08]

Hello rsc@golang.org, khr@golang.org, bradfitz@golang.org (cc:
golang-codereviews@googlegroups.com),

Please take another look.

[adonovan, 2014-08-06 19:55:41]

On 2014/08/06 19:47:35, rsc wrote:
> You can hg mv the file to a new name.

Done.

(FYI, the paltry 3000 iterations was plenty to cause the test to run for ages
with the current toolchain.)

[rsc, 2014-08-06 20:00:59]

the interesting cases are

int (memory)
string
interface{}
interface{f()}
float32
float64
complex64
complex128

can you hit them all?

[adonovan, 2014-08-06 20:32:31]

On 2014/08/06 20:00:59, rsc wrote:
> the interesting cases are
> 
> int (memory)
> string
> interface{}
> interface{f()}
> float32
> float64
> complex64
> complex128
> 
> can you hit them all?

Done (PTAL).  Interestingly all the f.p. ones are non-linear, even prior to the
regression.

[rsc, 2014-08-06 20:36:41]

LGTM

I'll look at the bad float hashes.

[khr, 2014-08-06 20:40:49]

On 2014/08/06 20:36:41, rsc wrote:
> LGTM
> 
> I'll look at the bad float hashes.

LGTM.

Yes, the float hash functions aren't particularly good.  For example, bits only
propagate toward the MSB.  For integers that's bad...

[rsc, 2014-08-06 20:43:24]

Please put the print in an if false before submitting. Otherwise all.bash
does not complete. I have fixed the float hashes and will send that right
now. You might want to wait for that.

[adonovan, 2014-08-06 21:02:58]

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

test/mapnan.go: add regression test for non-empty interfaces.

LGTM=rsc, khr
R=rsc, khr, bradfitz
CC=golang-codereviews
https://codereview.appspot.com/126720043