runtime: make map iteration less defined

Fixes #3726

1 files changed, 22 insertions, 3 deletions

diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go
index a148415f7..93bbb2f41 100644
--- a/src/runtime/hashmap.go
+++ b/src/runtime/hashmap.go
@@ -45,8 +45,11 @@ type hashmapIterator struct {
 	buckets      unsafe.Pointer // pointer to array of hashapBuckets
 	numBuckets   uintptr        // length of buckets array
 	bucketNumber uintptr        // current index into buckets array
+	startBucket  uintptr        // starting location for iterator
 	bucket       *hashmapBucket // current bucket in chain
 	bucketIndex  uint8          // current index into bucket
+	startIndex   uint8          // starting bucket index for iterator
+	wrapped      bool           // true if the iterator has wrapped
 }
 
 func hashmapNewIterator() unsafe.Pointer {
@@ -390,28 +393,44 @@ func hashmapNext(m *hashmap, it *hashmapIterator, key, value unsafe.Pointer) boo
 		// initialize iterator
 		it.buckets = m.buckets
 		it.numBuckets = uintptr(1) << m.bucketBits
+		it.startBucket = uintptr(fastrand()) & (it.numBuckets - 1)
+		it.startIndex = uint8(fastrand() & 7)
+
+		it.bucketNumber = it.startBucket
+		it.bucket = hashmapBucketAddr(m, it.buckets, it.bucketNumber)
+		it.bucketIndex = it.startIndex
 	}
 
 	for {
+		// If we've wrapped and we're back at our starting location, terminate the iteration.
+		if it.wrapped && it.bucketNumber == it.startBucket && it.bucketIndex == it.startIndex {
+			return false
+		}
+
 		if it.bucketIndex >= 8 {
 			// end of bucket, move to the next in the chain
 			it.bucketIndex = 0
 			it.bucket = it.bucket.next
 		}
+
 		if it.bucket == nil {
+			it.bucketNumber++ // next bucket
 			if it.bucketNumber >= it.numBuckets {
-				// went through all buckets
-				return false
+				// went through all buckets -- wrap around
+				it.bucketNumber = 0
+				it.wrapped = true
 			}
 			it.bucket = hashmapBucketAddr(m, it.buckets, it.bucketNumber)
-			it.bucketNumber++ // next bucket
+			continue
 		}
+
 		if it.bucket.tophash[it.bucketIndex] == 0 {
 			// slot is empty - move on
 			it.bucketIndex++
 			continue
 		}
 
+		// Found a key.
 		slotKey := hashmapSlotKey(m, it.bucket, it.bucketIndex)
 		memcpy(key, slotKey, m.keySize)