Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hash Ordering and Hyrum's Law

eaftan.github.io

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Hash Ordering and Hyrum's Law

#31

Post by tialaramex »

medstrom wrote: post #28
alexhornby wrote: post #23

Earlier quoted context omitted.

Few examples I’ve come across: hashing, float summation, reproducible serialisation

I get two of those, can you tell me more about float summation?

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.

Re: Hash Ordering and Hyrum's Law

#32

Post by skratky »

tialaramex wrote: post #31
medstrom wrote: post #28

Earlier quoted context omitted.

I get two of those, can you tell me more about float summation?

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 th…

Use the Kahan summation algorithm.

Re: Hash Ordering and Hyrum's Law

#33

Post by the8472 »

> Can’t you just break them? They’re violating the spec!

> No, you can’t break them.

You can. A vendor playing nice may provide advance warnings, fallbacks, assess blast radius etc, but that's no way a given, some vendors will not act nicely and leave you out cold if you ignore the spec.

Java 7 switched array.sort() to TimSort. It broke some users, they switched nevertheless and offered an override option for some time so people could migrate. Java 9 introduced the modules, which broke some things that tried to access internals, there were overrides for some time so people could migrate.

By default Rust does not specify the field order of its structs, people relied on it anyway. Several releases changed the ordering algorithm, no opt-out was offered since there already was an annotation to specify a fixed layout, people just had to use it.

It's called "API contract" for a reason, it puts obligations on both sides.

Re: Hash Ordering and Hyrum's Law

#34

Post by impoppy »

Didn’t Python tackle a similar problem? I remember that dictionaries were known to be unsorted, however, when writing tests, I’ve noticed that the items were always in the same order. I don’t remember what was I looking up, but my manager and I came to a conclusion that depending on order items of a dictionary was acceptable and having to fix the tests if they somehow broke later was an okay tradeoff. Now, reading Python docs on that topic, they briefly[1] mention that dictionaries’ list views yield items in the order they were inserted without any mentions if items are sorted or not.

[1] briefly in this regard means I’ve seen it in the docs exactly once without much attention paid to that sentence

https://docs.python.org/3/tutorial/datastructures.html#dicti...

Re: Hash Ordering and Hyrum's Law

#35

Post by Tarean »

impoppy wrote: post #34

Didn’t Python tackle a similar problem? I remember that dictionaries were known to be unsorted, however, when writing tests, I’ve noticed that the items were always in the same order. I don’t remember what was I looking up, but my manager and I came to a conclusion that depending on order items of a dictionary was acceptable and having to fix the tests if they somehow broke later was an okay tradeoff. Now, reading Py…

This behaviour was introduced in 3.6 (and made part of the spec in 3.7 iirc)

From the python 3.6 change log:

New dict implementation¶ The dict type now uses a “compact” representation based on a proposal by Raymond Hettinger which was first implemented by PyPy. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5.

The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon (this may change in the future, but it is desired to have this new dict implementation in the language for a few releases before changing the language spec to mandate order-preserving semantics for all current and future Python implementations; this also helps preserve backwards-compatibility with older versions of the language where random iteration order is still in effect, e.g. Python 3.5). (Contributed by INADA Naoki in bpo-27350. Idea originally suggested by Raymond Hettinger.)

https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple...

Re: Hash Ordering and Hyrum's Law

#36

Post by jerf »

the8472 wrote: post #33

> Can’t you just break them? They’re violating the spec! > No, you can’t break them. You can. A vendor playing nice may provide advance warnings, fallbacks, assess blast radius etc, but that's no way a given, some vendors will not act nicely and leave you out cold if you ignore the spec. Java 7 switched array.sort() to TimSort. It broke some users, they switched nevertheless and offered an override option for some ti…

I am reminded of how Postel's Law has fallen from Iron Law of the Internet to somewhat distasteful in the past 5-10 years. Yes, it's no fun to break your clients and customers today. But if you don't do it today, and you don't do it next month, next year, or the next four years, you'll find yourself in a position where you can't do anything anymore because you've basically let Hyrum's Law "build up" in your system until there's no room to move.

Obviously, one should not willy-nilly break customers for no reason. The point is not to create a management metric around Number Of Times We've Broken The Customer and reward the team for getting their numbers up, up, up. The point is to retain flexibility and the ability to move forward, and that is done through intelligent design up front to the extent possible, and carefully selecting when to break customers over the course of years. It's always expensive and should definitely be treated as an expense, not a benefit on its own terms. But as the Hyrum's Law "builds up" its expense to the company over all will in not really all that long overwhelm the costs of the occasional breakage to stay up-to-date with the world.

Re: Hash Ordering and Hyrum's Law

#37

Post by tialaramex »

skratky wrote: post #32
tialaramex wrote: post #31

Earlier quoted context omitted.

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 th…

Use the Kahan summation algorithm.

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.

Re: Hash Ordering and Hyrum's Law

#38

Post by smarks »

prattmic wrote: post #14
lsy wrote: post #6

What's the advantage of specifying it as random over specifying it as sequential in some way? Aren't both just specifying a behavior, where one behavior is potentially more useful than the other? I guess I understand the principled point that a set of hash keys is not an array. But it seems like more complexity than is necessary, and even possible to fall victim to Hyrum's law besides… you can imagine someone using r…

In addition to the DoS aspect mentioned in a sibling comment, the primary reason you would do this is to avoid constraining the implementation. If you want to change the design to improve performance, for example, being forced to match the implicit ordering of the old implementation may be very difficult. It certainly may be useful to define an specific ordering. Maps ordered by insertion time and maps ordered by key…

Cool! Yes, that’s been our experience in Java as well. The randomized order of unmodifiable Set and Map (from `Set.of` and `Map.of`) have enabled us to make optimizations to the internals mostly with impunity. We’ve done so twice since their introduction and we might do so again.

Re: Hash Ordering and Hyrum's Law

#39

Post by hinkley »

Oh I remember this happening. Fuckin’ JUnit.

Your tests shouldn’t depend on what order they get run, and upgrade hell has been much worse many times since, but for developers of a certain age this might have been one of the first and most frivolous feeling ones. Can’t upgrade not because the app acts differently but the tests are failing??

Only this didn’t just happen between Java 6 and 7 (I must have dodged that one or learned my lesson), it first happened in Java 5.

Re: Hash Ordering and Hyrum's Law

#40

Post by hinkley »

o11c wrote: post #15
smarks wrote: post #12

(from Feb 2021) Some of the JDK's unmodifiable collections, such as those from `Set.of()` and `Map.of()`, also randomize iteration order. At the time they were added, Go and Python also randomized iteration order. However, more recently, Python moved away from randomization. Early in the Python 3.x releases, dict iteration order was randomized. In 3.6, iteration order was insertion order, but only as an implementatio…

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 n…

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.

Post reply on HN