4 ms·

IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it

by o11c 2y ago

IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. And since hash-first languages provide a broken API, there's no way to provide it for arbitrary types. Compare-first languages (like C++) generally provide it, but paying the price of tree-based structures (assuming a B-tree can't negate it) isn't actually necessary. Rather than either of those choices, I argue that languages really should be "key-first" - rather than having classes implement hashing or comparison themselves, they should return a tuple of the data that will be fed into said hash or comparison. Besides being a nicer API, this also prevents many common bugs.

tialaramex 2y ago
> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.
- alexhornby 2y ago
  Few examples I’ve come across: hashing, float summation, reproducible serialisation
  - tialaramex 2y ago
    Huh. I guess somebody could build a specialised container for this purpose, which deliberately has some arbitrary but unchanging ordering. Certainly that looks practical in Rust (indeed it may already exist, I haven't looked).
  - medstrom 2y ago
    I get two of those, can you tell me more about float summation?
    - tialaramex 2y ago
      Because the exponent varies, it matters what order we add floats together, if we add them in one order we get a very different answer to another. If we expected a consistent result that's very surprising. Suppose you have a billion, and also you have a million ones, all as 32-bit floating point numbers. If we begin with the billion, and add each one, the additions do nothing, because in the representation used for the billion a single one is too small to matter, so our answer is just one billion again each time -- but if we begin with the ones, adding the billion last, we've reached a million when we add the billion, that's not too small to matter and we get 1.001 billion.
      - skratky 2y ago
        Use the Kahan summation algorithm.
        tialaramex 2y ago
        Kahan solves my examples but in general cannot be relied on to deliver any specific benefit - it's never worse but it may not be meaningfully better either. Pairwise algorithms can promise better results but aren't applicable unless we're OK with the idea of separately storing the numbers somewhere while we run the algorithm or we provide this hash table with a random access mechanism it may otherwise have no use for.
- hinkley 2y ago
  LRU caching.
lesam 2y ago
C++ gives both ‘map’ and ‘unordered_map’, and in my experience idiomatic C++ uses unordered_map unless you actually need a tree.
hinkley 2y ago
Java and JavaScript both have a way to get keys back in insertion order. It’s pretty simple to implement an LRU cache when you have time ordered iterators.

by o11c 2y ago

tialaramex 2y ago

> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.

alexhornby 2y ago
Few examples I’ve come across: hashing, float summation, reproducible serialisation
- tialaramex 2y ago
  Huh. I guess somebody could build a specialised container for this purpose, which deliberately has some arbitrary but unchanging ordering. Certainly that looks practical in Rust (indeed it may already exist, I haven't looked).
- medstrom 2y ago
  I get two of those, can you tell me more about float summation?
  - tialaramex 2y ago
    Because the exponent varies, it matters what order we add floats together, if we add them in one order we get a very different answer to another. If we expected a consistent result that's very surprising. Suppose you have a billion, and also you have a million ones, all as 32-bit floating point numbers. If we begin with the billion, and add each one, the additions do nothing, because in the representation used for the billion a single one is too small to matter, so our answer is just one billion again each time -- but if we begin with the ones, adding the billion last, we've reached a million when we add the billion, that's not too small to matter and we get 1.001 billion.
    - skratky 2y ago
      Use the Kahan summation algorithm.
      - tialaramex 2y ago
        Kahan solves my examples but in general cannot be relied on to deliver any specific benefit - it's never worse but it may not be meaningfully better either. Pairwise algorithms can promise better results but aren't applicable unless we're OK with the idea of separately storing the numbers somewhere while we run the algorithm or we provide this hash table with a random access mechanism it may otherwise have no use for.
hinkley 2y ago
LRU caching.

lesam 2y ago

C++ gives both ‘map’ and ‘unordered_map’, and in my experience idiomatic C++ uses unordered_map unless you actually need a tree.

hinkley 2y ago

Java and JavaScript both have a way to get keys back in insertion order. It’s pretty simple to implement an LRU cache when you have time ordered iterators.