4 ms·

I think the problem with putting this into the standard library is that while Go may not be super focused on absolutely top-tier performance, it does generally

by jerf 2y ago

I think the problem with putting this into the standard library is that while Go may not be super focused on absolutely top-tier performance, it does generally try to avoid offering things that are unexpectedly slow or unexpectedly allocate large things. A sort-by-keys on the standard map would require allocating a full slice for the keys in the sort routine to do the sort, which would surprise people who expect build-in iterators to not immediately do that. Plus it's in the class of things that's pretty easy to implement yourself now. There's always a huge supply of "but the library could just compose these two things for me". If you stick them all in things get bloated. You could literally have written it in the time it took to write the complaint. You got 80% of the way there as it is, I just tweaked your code a bit to turn it into an iterator: https://go.dev/play/p/agBGl_rT7XS https://go.dev/play/p/agBGl_rT7XS

38 2y ago
its completely pointless to make this an iterator, because you have to loop the entire map to do so, which kills any benefit of using iterators
- kbolino 2y ago
  And yet slices.Sorted was added which does exactly this already, but only for single-valued iterators.
  - deleted 2y ago
    [deleted]
  - randomdata 2y ago
    > And yet slices.Sorted was added which does exactly this already It does not. slices.Sorted accepts an iterator, but returns a slice. Like the earlier comments point out, Go tries its best to give a reasonable idea of what kind of complexity is involved at the API level. slices.Sorted returning an iterator would mask that. By returning a slice, it makes clear that the entire collection of data needs to be first iterated over as the parent described.
    - kbolino 2y ago
      This is a good point which likely explains why maps.Sorted doesn't exist (yet): what would it even return? I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. If it ought to return a slice of entries, that opens up new problems. What is an entry? A two-member generic struct? Ok, fine, but then how do I ergonomically iterate over them, pulling out both members? There's no clear solution to that problem yet.
      - randomdata 2y ago
        There is another, perhaps more important, reason: If you need sorted keys, the map is almost certainly the wrong data structure. Sure, there may be some edge case situations, like where you are dealing with someone else's code where you don't have control over the structures you've been given, but: 1. The standard library doesn't appeal to edge cases. 2. The "noiser" solutions to deal with the edge case serve as a reminder that you aren't working in the optimal space.
        jerf 2y ago
        I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that if you think you need sorted keys, double-check. I program an awful lot of things without sorted keys, and I am quite aware of the issues around sorting, and I suspect without proof that a lot of people swearing by sorted maps are imposing false ordering requirements on their code more often than they realize. The ideal solution is not need order at all. (I am especially suspicious of extensive use of maps where the keys are sorted by insertion order. That smells... antipatternish to me.)
        kbolino 2y ago
        This is a bridge that the standard library has already crossed, though. Off the top of my head, both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. Whether in particular cases, a properly ordered data structure (like a tree) should be used instead, is a valid question to ask, and thanks to the custom iterators, it'll now be more ergonomic to use. But if I usually use a particular map for its O(1) operations and only occasionally iterate over the whole thing, yet need consistent iteration order, then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request.
- randomdata 2y ago
  Not completely pointless. It avoids the need to retain a full copy of all the values. But a good demonstration of why this kind of thing isn't a good fit for the standard library.
kbolino 2y ago
As I mentioned in another reply, this simple solution is not cache-friendly.
- deleted 2y ago
  [deleted]
- jerf 2y ago
  The cache friendly alternative is to use a different data structure. There is no cache-friendly iterate-in-order on the standard map. But I've got plenty of cases where this in fact is cache friendly, because the entire map fits into L2 or even L1 anyhow because it's going to have maybe 4 keys in its lifetime. Not every map has fifty million values in it. I'm always keeping at least a little bit of track about such details when I'm using maps.
  - deleted 2y ago
    [deleted]
  - kbolino 2y ago
    I did some benchmarks, and it seems you are right that there's no (more) cache-friendly solution in general (at least, not that I could come up with). Memoizing the full entries (key and value) into a slice and then sorting that slice by key has basically the same cache-thrashing characteristics as randomly accessing the values, and is no faster (sometimes slower).

by jerf 2y ago

38 2y ago

its completely pointless to make this an iterator, because you have to loop the entire map to do so, which kills any benefit of using iterators

kbolino 2y ago
And yet slices.Sorted was added which does exactly this already, but only for single-valued iterators.
- deleted 2y ago
  [deleted]
- randomdata 2y ago
  > And yet slices.Sorted was added which does exactly this already It does not. slices.Sorted accepts an iterator, but returns a slice. Like the earlier comments point out, Go tries its best to give a reasonable idea of what kind of complexity is involved at the API level. slices.Sorted returning an iterator would mask that. By returning a slice, it makes clear that the entire collection of data needs to be first iterated over as the parent described.
  - kbolino 2y ago
    This is a good point which likely explains why maps.Sorted doesn't exist (yet): what would it even return? I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. If it ought to return a slice of entries, that opens up new problems. What is an entry? A two-member generic struct? Ok, fine, but then how do I ergonomically iterate over them, pulling out both members? There's no clear solution to that problem yet.
    - randomdata 2y ago
      There is another, perhaps more important, reason: If you need sorted keys, the map is almost certainly the wrong data structure. Sure, there may be some edge case situations, like where you are dealing with someone else's code where you don't have control over the structures you've been given, but: 1. The standard library doesn't appeal to edge cases. 2. The "noiser" solutions to deal with the edge case serve as a reminder that you aren't working in the optimal space.
      - jerf 2y ago
        I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that if you think you need sorted keys, double-check. I program an awful lot of things without sorted keys, and I am quite aware of the issues around sorting, and I suspect without proof that a lot of people swearing by sorted maps are imposing false ordering requirements on their code more often than they realize. The ideal solution is not need order at all. (I am especially suspicious of extensive use of maps where the keys are sorted by insertion order. That smells... antipatternish to me.)
      - kbolino 2y ago
        This is a bridge that the standard library has already crossed, though. Off the top of my head, both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. Whether in particular cases, a properly ordered data structure (like a tree) should be used instead, is a valid question to ask, and thanks to the custom iterators, it'll now be more ergonomic to use. But if I usually use a particular map for its O(1) operations and only occasionally iterate over the whole thing, yet need consistent iteration order, then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request.
randomdata 2y ago
Not completely pointless. It avoids the need to retain a full copy of all the values. But a good demonstration of why this kind of thing isn't a good fit for the standard library.

kbolino 2y ago

As I mentioned in another reply, this simple solution is not cache-friendly.

deleted 2y ago
[deleted]
jerf 2y ago
The cache friendly alternative is to use a different data structure. There is no cache-friendly iterate-in-order on the standard map. But I've got plenty of cases where this in fact is cache friendly, because the entire map fits into L2 or even L1 anyhow because it's going to have maybe 4 keys in its lifetime. Not every map has fifty million values in it. I'm always keeping at least a little bit of track about such details when I'm using maps.
- deleted 2y ago
  [deleted]
- kbolino 2y ago
  I did some benchmarks, and it seems you are right that there's no (more) cache-friendly solution in general (at least, not that I could come up with). Memoizing the full entries (key and value) into a slice and then sorting that slice by key has basically the same cache-thrashing characteristics as randomly accessing the values, and is no faster (sometimes slower).