map: use batch lookups in Map.Iterate()

[ti-mo]

I would like to discuss the future of the Map Iterator API. Currently, it doesn't transparently use batch lookups under the hood
However, the current batch API, as it is in the library, is relatively barebones, and it hasn't been iterated on since its inception or integrated with other parts of the Map API.

Maybe it could be an option to either break the API of the current Map.Iterate() (and make it take a config struct),
or introduce a new Map.Range() or Map.For() method that takes a configuration struct. Or maybe simply Map.IterateBatch(), but that sounds rather unimaginative.

Ideally, we'd have a unified API where the caller can disable batch lookups if needed for certain use cases. Thinking
of hash map clearing where each call to .Next() is expected to point at the first element, which gets subsequently deleted.

Wondering if anyone's thought about this before, or if there's any opinions around this. Thanks!

[lmb]

I would love it if Map.Iterate transparently used batch lookups if possible. (Less of a fan of a new API, we might have to break compat when / if Go gets iterators.) The devil is in the details though:

• How many keys and values do we fetch in one go? There is not really a number that is correct for all cases. I'd probably start with a heuristic of using a page of memory for keys and values each, something like os.Getpagesize() / Sizeof(T). Allow the user to override that somehow. MapIterator.Items or something like that?
• How do we deal with differences in semantics? For example, right now concurrent iteration and delete is undefined behaviour. I don't expect that to change with batch lookup (can't get more undefined) but is there a difference in practice to the reset behaviour we get for single key lookups?

[tommyp1ckles]

Stumbled upon this, I did some work recently in Cilium that dealt with the issue of default batch sizes that is likely related.

There's been work done to significantly improve the batch lookup API, but it would be nice to start looking at maybe providing a iterator pattern that would satisfy the Go rangefunc experimental feature.

[lmb]

I would love that. However, your work plus my recent experience with #1485 makes me think that the current API is basically unusable in a generic fashion. We don't know anything about the map in question except the max entries really. In the worst case, we could have a single bucket with max_entries in it. How would we deal with that? Fall back to regular iteration at some point?

[ti-mo]

Given the (IMO huge) difference in semantics between regular and batch lookups, I'm inclined to close this for now. If we want to add support for Go iterators, that can be done for both iteration strategies individually. Unifying them feels unrealistic. Happy to change my mind about it, though.