[dev.power64] code review 152570049: all: merge default into dev.power64

test/maplinear.go

 // +build darwin linux
 // run
 
 // Copyright 2013 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Test that maps don't go quadratic for NaNs and other values.
 
 package main
@@ skipping 122 matching lines @@
                 }
         })
 
         // ~32ms on a 1.6GHz Zeon.
         checkLinear("complex128", 10000, func(n int) {
                 m := map[complex128]int{}
                 for i := 0; i < n; i++ {
                         m[complex(float64(i), float64(i))] = 1
                 }
         })
+
+        // ~70ms on a 1.6GHz Zeon.
+        // The iterate/delete idiom currently takes expected
+        // O(n lg n) time.  Fortunately, the checkLinear test
+        // leaves enough wiggle room to include n lg n time
+        // (it actually tests for O(n^log_2(3)).
+        // To prevent false positives, average away variation
+        // by doing multiple rounds within a single run.
+        checkLinear("iterdelete", 2500, func(n int) {
+                for round := 0; round < 4; round++ {
+                        m := map[int]int{}
+                        for i := 0; i < n; i++ {
+                                m[i] = i
+                        }
+                        for i := 0; i < n; i++ {
+                                for k := range m {
+                                        delete(m, k)
+                                        break
+                                }
+                        }
+                }
+        })
 }