3 ms·

> simply adding an element and then immediately removing it with no lines of code in between those two calls was enough, in some cases, to completely mess up wh

by kokada 2y ago

> simply adding an element and then immediately removing it with no lines of code in between those two calls was enough, in some cases, to completely mess up whatever order I thought there was. Yes, this is what I expect too. But this is NOT what Go is doing here. Go is actually randomising the order EVERY time you try to iterate, even if you do NO manipulation of the items inside the map. See this comment thread for more details: https://news.ycombinator.com/item?id=41274850#41276274 https://news.ycombinator.com/item?id=41274850#41276274. This is the surprising part, not that the iteration order may change if you add/remove items. > My own OSS hashmap library, on github Does your hashmap library, say, have a `iterate()` method that randomises the order of items every time it is called? If yes, ok, we are talking about the same thing here. But I am almost sure that it does not, and this is what Go is doing here.

lelanthran 2y ago
> Go is actually randomising the order EVERY time you try to iterate Which is 100% perfectly within specification of the hashmap concept. It may not match your expectation of what a hashmap is, but it is what it is, and that's what a hashmap is. IOW, there is no guarantee, and a library that randomises the order that it returns hashmap elements when iterating is perfectly correct!
- kokada 2y ago
  I never said once that the implementation is incorrect, just that it is weird and uncommon.
  - coldtea 2y ago
    Yes, but the expectation for non-weirdness is not based on the actual specs a hashmap must have, just on contingencies ("but no other language I know does it like this") that apply to quite narrow criteria (iterating over statically added hashmap entries, if you added entries from a dynamic source, or added them in parallel, etc, they could very well change for every run without the language randomizing anything explicitly).
    - kokada 2y ago
      That is still a valid expectation, just look at other commenters on the thread that they also find the behavior surprising.
    - pests 2y ago
      I agree with you but I do see his perspective. "Hashmaps make no guarantee about iteration order" does not imply the implementation is going to do _EXTRA WORK_ to make that true. It being ordered, or providing a guarantee of some order, is still within spec of the hashmap concept. To expend extra cycles to force no order, when any order is fine (esp if it falls out of the data structure), is extra work. Its an extra constraint, one a hashmap does not require. I wonder how much energy we have collectively spent sorting lists for no reason.
coldtea 2y ago
>Yes, this is what I expect too. But this is NOT what Go is doing here. Go is actually randomising the order EVERY time you try to iterate, even if you do NO manipulation of the items inside the map. The parent's point is that this is still within the guarantees hashmap (the abstract data structure) gives about order: none. All the rest are details that are based on your particular conditions, which are very very very specific: - you only had a set fixed list of items, added always with a particular order (whereas for a program the items or order can also be totally dynamic, e.g. coming from a REST call, or a DB query of data that changes, or from parallel parsing something which doesn't guarantee any order etc). - you only cared about specific runs within the same build or within the same Go compiler version to be stable. People who care for reproducibility normally care for reproducibility across builds and Go versions too. This "I care for reproducibility and order, but only very partially" is quite rare. E.g. if your tests depended on the order being stable, one would want the tests to keep working if Go changes their salt or hashmap algorithm or whatever in a subsequent version, no? >Does your hashmap library, say, have a `iterate()` method that randomises the order of items every time it is called? If yes, ok, we are talking about the same thing here. But I am almost sure that it does not, and this is what Go is doing here. That's an implementation detail that shouldn't concern the user though. Go just goes out of the way to instill this, whereas other languages/libs do not.
- kokada 2y ago
  > The parent's point is that this is still within the guarantees hashmap (the abstract data structure) gives about order: none. This is not the point from the parent point, at least nothing else in the text suggests so. > All the rest are details that are based on your particular conditions, which are very very very specific: They're not "very very specific", they're based on my experience in other programming languages. And when I say this, I am not talking about Python (that has ordered maps by default), but languages like Ruby or Java. > That's an implementation detail that shouldn't concern the user though. Go just goes out of the way to instill this, whereas other languages/libs do not. I think this thread is going anywhere, again, I am not saying Go or any other hash map implementation that does the same is wrong here. It is just that it is uncommon, that I had "one case in the past that if Go didn't randomise I wouldn't need to write extra code" (and I didn't say this case was common either), and that I would like ordered maps in the stdlib not just because of this particular case but because they are a really versatile (and would help in this case, but I never said it was the only case either where ordered maps matter). Keep in mind that I wrote this post on a sleepless night and didn't give much thought. My argument was never "this is the reason why we should have ordered maps in Go", it was mostly "I had this issue once, I think ordered maps are cool and if Go had them I wouldn't had this issue". I am still surprised how much (good) discussion this post ended up generating considering how little thought I gave at this post.

by kokada 2y ago

lelanthran 2y ago

> Go is actually randomising the order EVERY time you try to iterate Which is 100% perfectly within specification of the hashmap concept. It may not match your expectation of what a hashmap is, but it is what it is, and that's what a hashmap is. IOW, there is no guarantee, and a library that randomises the order that it returns hashmap elements when iterating is perfectly correct!

kokada 2y ago
I never said once that the implementation is incorrect, just that it is weird and uncommon.
- coldtea 2y ago
  Yes, but the expectation for non-weirdness is not based on the actual specs a hashmap must have, just on contingencies ("but no other language I know does it like this") that apply to quite narrow criteria (iterating over statically added hashmap entries, if you added entries from a dynamic source, or added them in parallel, etc, they could very well change for every run without the language randomizing anything explicitly).
  - kokada 2y ago
    That is still a valid expectation, just look at other commenters on the thread that they also find the behavior surprising.
  - pests 2y ago
    I agree with you but I do see his perspective. "Hashmaps make no guarantee about iteration order" does not imply the implementation is going to do _EXTRA WORK_ to make that true. It being ordered, or providing a guarantee of some order, is still within spec of the hashmap concept. To expend extra cycles to force no order, when any order is fine (esp if it falls out of the data structure), is extra work. Its an extra constraint, one a hashmap does not require. I wonder how much energy we have collectively spent sorting lists for no reason.

coldtea 2y ago

>Yes, this is what I expect too. But this is NOT what Go is doing here. Go is actually randomising the order EVERY time you try to iterate, even if you do NO manipulation of the items inside the map. The parent's point is that this is still within the guarantees hashmap (the abstract data structure) gives about order: none. All the rest are details that are based on your particular conditions, which are very very very specific: - you only had a set fixed list of items, added always with a particular order (whereas for a program the items or order can also be totally dynamic, e.g. coming from a REST call, or a DB query of data that changes, or from parallel parsing something which doesn't guarantee any order etc). - you only cared about specific runs within the same build or within the same Go compiler version to be stable. People who care for reproducibility normally care for reproducibility across builds and Go versions too. This "I care for reproducibility and order, but only very partially" is quite rare. E.g. if your tests depended on the order being stable, one would want the tests to keep working if Go changes their salt or hashmap algorithm or whatever in a subsequent version, no? >Does your hashmap library, say, have a `iterate()` method that randomises the order of items every time it is called? If yes, ok, we are talking about the same thing here. But I am almost sure that it does not, and this is what Go is doing here. That's an implementation detail that shouldn't concern the user though. Go just goes out of the way to instill this, whereas other languages/libs do not.

kokada 2y ago
> The parent's point is that this is still within the guarantees hashmap (the abstract data structure) gives about order: none. This is not the point from the parent point, at least nothing else in the text suggests so. > All the rest are details that are based on your particular conditions, which are very very very specific: They're not "very very specific", they're based on my experience in other programming languages. And when I say this, I am not talking about Python (that has ordered maps by default), but languages like Ruby or Java. > That's an implementation detail that shouldn't concern the user though. Go just goes out of the way to instill this, whereas other languages/libs do not. I think this thread is going anywhere, again, I am not saying Go or any other hash map implementation that does the same is wrong here. It is just that it is uncommon, that I had "one case in the past that if Go didn't randomise I wouldn't need to write extra code" (and I didn't say this case was common either), and that I would like ordered maps in the stdlib not just because of this particular case but because they are a really versatile (and would help in this case, but I never said it was the only case either where ordered maps matter). Keep in mind that I wrote this post on a sleepless night and didn't give much thought. My argument was never "this is the reason why we should have ordered maps in Go", it was mostly "I had this issue once, I think ordered maps are cool and if Go had them I wouldn't had this issue". I am still surprised how much (good) discussion this post ended up generating considering how little thought I gave at this post.