Comment by deathanatos
1 day ago
Well … it seems like you're right. (A playground — https://go.dev/play/p/OHQTIuDWicd — if anyone is curious.)
That's … pretty surprising, since that would seem to imply that iteration would require a O(n) sized chunk of memory somewhere to reify the order into. (And probably O(n) time to do the shuffle, or at least, a copy of the ordering; we should shuffle as we go, I suppose, but we'd need to track what we've emitted & what we've not, hence O(n) time & space to populate that scratch…) That seems undesirable.
They actually do it without needing a O(n) memory chunk, aiui.
1. choose starting bucket randomly
2. From there iterate through buckets in usual order (wrapping around)
3. Within each bucket, generate permutation of 0..7, and stream it in that order.
See func mapiterinit() in runtime/map.go
This is just me musing, but you can probably precompute all permutations of 0..7 and store it for ~20KB once for the whole runtime, and just index that each time. Can avoid the fischer yates each time.