Hacker News Reader

Comment by cempaka | Hacker News Reader

> While I understand the reason for this (i.e.: to avoid developers relying in a specific iteration order), I still find it weird, and I think this is something unique for Go.

Haha well, fun fact, Java did this as well after a bunch of code was broken by a JDK upgrade which changed HashMap iteration order that programmers had been relying upon. Java does at least have ordered maps in the standard lib though. IMO it is a questionable decision to spend CPU resources on randomization in order to mollycoddle programmers with a flawed understanding of an API like this, but then again I'm not the one who gets the backlash when their stuff breaks.

Also, on the subject of nullability, while JSR305 may be considered dead, there's still pretty active work on the Java nullability question both from the angle of tooling (https://www.infoq.com/news/2024/08/jspecify-java-nullability...) and language design (https://openjdk.org/jeps/8316779).

View on HN

I was about to comment the same. Also happened in absl (Google's alternative to the STL template library for C++ which started its life as GTL) -- when changing the default hash function for unordered maps it led to breaking changes in both test and production code that had depended on it.

OrderedDict types are nice sometimes but shouldn't be the default behavior, IMO.

There are good reasons for the second point (about default/named parameters) -- any calling code is making some assumptions based on that default value so there's a risk it can't be changed or added to. If you really want a default value, make a wrapper function for it. In the example it would be a simple matter of defining ReplaceAll with three arguments that always passes -1 to Replace(...)

Perl has done per-run randomization of the iteration order as well for a while (more than a decade).

    % repeat 5 perl -e '%h=(a => 1, b  => 2, c=> 3); print for keys %h; print "\n"'
    bca
    cba
    bac
    bac
    bac

Cute story on why that came to be. At Booking.com, a degenerate case that lead to a DoS that you could cause with specially crafted URLs (I think, memory is a bit foggy) spurned Yves Orton to do that hacking. And it broke a lot of code where the ordering had been consistent enough that people relied on it.

Way longer than a decade. You can see it in the perlfunc man page way back in 1996[0].

Of the same vintage is `Tie::IxHash`, which retains insertion order

    % repeat 5 perl -MTie::IxHash -E 'tie my %foo, "Tie::IxHash"; @foo{qw{ c a b }} = (1)x3; printf("%s%s%s\n",keys %foo)'
    cab
    cab
    cab
    cab
    cab

[0] https://metacpan.org/release/NI-S/perl5.003_02a/view/pod/per...

No, Yves added randomization per iteration as described in the parent.

Before it was only dependent on the per-process seed. So the seed could be computed given enough attempts to iter a hash (eg a public JSON API)

But the parent is invoking `perl` itself 5 times, rather than iterating 5 times within one process.

I wouldn't call it mollycoddling. I can understand why people make that mistake. Interfaces should be designed to reduce the chance of mistakes as much as possible, under the knowledge that people (including you!) make mistakes. They shouldn't be designed under the assumption that people always read and understand the manual and never make mistakes.

That's why we don't do `load` and `load_safe`; we do `load` and `load_unsafe`.

> Java did this as well after a bunch of code was broken by a JDK upgrade which changed HashMap iteration order that programmers had been relying upon.

This is incorrect (or I’m misunderstanding you). OpenJDK’s HashMap doesn’t use randomization, and the iteration order is thus deterministic under that implementation, although the API specification does not guarantee it. To mitigate DoS attacks, keys in the same hash bucket are stored as a balanced tree. For keys that implement Comparable (strings in particular), this guarantees O(n log n).

Ah you're right, what I had in mind was the iteration order of the immutable/unmodifiable maps created by Collections.unmodifiableMap() or Map.of(): https://docs.oracle.com/en/java/javase/20/core/creating-immu...

> IMO it is a questionable decision to spend CPU resources on randomization …

It takes about 3 ns to choose a random starting bucket, which is basically free relative to the iteration itself.

Isn't the trick that the runtime picks another hash-constant every time?

Aside from keying the hash function, Go specifically randomises the start offset of each map iteration.

They just added custom iterators ("range over func") to the language in 1.23 but somehow missed the obvious opportunity to add e.g. maps.SortedByKeys. It's clunky to write:

    for _, k := range slices.Sorted(maps.Keys(m)) {
        v := m[k]
        _ = v // do something with k and v
    }

though, it's not as bad as before:

    keys := make([]string, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    slices.Sort(keys)
    for _, k := range keys {
        v := m[k]
        _ = v
    }

> maps.SortedByKeys

thats what you call overfitting kids

Whatever you think the best name for it is, it's still missing from the library.

the point is you dont need it. by your own admission, it would save literally 0 lines of code from your current example. you need discipline when adding sugar otherwise you can ruin a language.

I said no such thing.

First, it would save one line of code (v := m[k]). Second, it would also allow an optimization. When iterating a map directly, you have both the key and the value at the same time. However, since we iterate only the keys here, we then have to look up the value anew for each key. That takes extra time and, for large maps, will thrash the CPU cache.

So the following would be both fewer lines of code and faster:

    for k, v := range maps.Sorted(m) {
        // do something with k and v
    }

Making common operations clear and concise is not mere sugar in my opinion. It not only improves the developer experience, it also clarifies the developer's intent, which enables better optimizations, and allows bugs and traps to be addressed in one place, instead of languishing in far-flung places.

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

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

And yet slices.Sorted was added which does exactly this already, but only for single-valued iterators.

> 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.

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.

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.

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.)

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.

> both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all.

That is literally the edge case example I gave. Perhaps there is a better way to describe it than "edge case", but semantics is a silly game.

> then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request.

And, indeed, the standard library provides slices.Sorted(maps.Keys(m)) for exactly that. Ergonomic enough, while making the compromise being made reasonably explicit to help with readability – which is far more important than saving a few keystrokes. If typing is your bottleneck, practice will quickly solve that problem.

It's never really been about saving keystrokes, but about re-writing the same (fairly common) operation over and over again (and not necessarily the same way each time), and not being able to benefit from future optimizations.

However, as examined in a sibling thread, there doesn't seem to actually be any missed optimization which could potentially be applied here.

In what way is the operation common? We obviously would never say that there is never a use for such thing as there are clear edge cases where it is necessary, but as jerf points out, it is probably not what you actually need in most cases.

Even ignoring that in the most common case the map isn't the right structure to begin with, what even is the general case for the situations that remain? You mentioned the marshalling of arbitrary data case, but in that case you also have reflection details to worry about, and which you can optimize for with a custom implementation, and thus wouldn't likely use the built-in anyway. A sibling thread discussed the cache benefits of colocating the values with the keys if a map is exceedingly small, but as soon as the map is of any reasonable size the added overhead of the values is almost certainly going to blow the cache even where the keys alone might still fit.

All of which is to say that the best approach is highly context dependent. How do you even begin to choose which is the general case if you were to include such a function?

> 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 a function returns an iterator, it should be iterating the input. thats impossible in this situation. you'd need to loop the entire map, then return an iterator that tricks the user into thinking they are getting better performance when they are getting the worst possible performance.

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.

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

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.

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).

It's one of the things I like in Kotlin: it defaults to using ordered maps. It also has default arguments in functions, lambda functions, and of course nullable types.

> Java does at least have ordered maps

Weird

An "ordered map" is not a hash table. I think they want a tree.

But you can get the keys and sort them.

I really do not see the problem

Use a tree if order matters, Hash if not.

(Since I am not a Go programmer, maybe I missed something)

Java’s LinkedHashMap is a hash table with an additional linked-list structure on the entries that records the insertion order. The map is thus ordered by insertion order, an order that is independent from the keys.

A map ordered by keys is a SortedMap in Java. While ordered, LinkedHashMap is not a SortedMap. In other words, unordered < ordered < sorted.

> An "ordered map" is not a hash table. I think they want a tree.

An ordered map is absolutely a hashmap.

> But you can get the keys and sort them.

That gives you a sorted thing, which is completely different.

> Use a tree if order matters, Hash if not.

That is incorrect. “Ordered” in the context of maps generally denotes the preservation of insertion order, and more rarely the ability to change that order. Trees don’t help with that, quite the opposite.

> An ordered map is absolutely a hashmap

I have never heard of O(1) insert and retrieval from anything ordered.

So, no. An ordered map is not a hashmap

> I have never heard of O(1) insert and retrieval from anything ordered.

Then you’ve not gotten out much. Here’s one: https://docs.python.org/3/library/stdtypes.html#dict

Here’s an other one: https://docs.python.org/3/library/collections.html#collectio...

Here’s a third one: https://docs.rs/indexmap/latest/indexmap/map/struct.IndexMap...

And a fourth: https://docs.oracle.com/en/java/javase/22/docs/api/java.base...

> So, no. An ordered map is not a hashmap

Still wrong.

That is not O(1) for insert and read

Sort is O(log N)

Insert into sorted list is O(log N)

I am correct

If you need sorted keys that is easy but you cannot get O(1) which HASH gets on a good day

Not in this universe

The person who wants a HASH table with sorted keys actually wants a tree. Maths

> That is not O(1) for insert and read

Of course it is.

> Sort is O(log N)

Sort is irrelevant, as I already told you ordered != sorted.

> I am correct

No my dude, you’ve got no idea what you’re talking about and you apparently can’t read.

> If you need sorted keys

Then you’re in the wrong place because that’s not what ordered maps do.

> The person who wants a HASH table with sorted keys

Is not germane to the discussion.

> Maths

Maths have nothing to do with your apparent inability to understand basic English or intake new information.

How are you maintaining a sorted list (required) O(1)?

Again, for the fourth time, you are not. An ordered collection is not a sorted collection.

SO you want a HASH table and a stack?

Wih the Hash table keep a stack of keys.

How do you delete them? Oh. Same problem.

You have O(1) insert and O(log N) deletion

Or the stack grows for ever.

When you ask for ordered keys, at zero cost, in a Hash it is like asking the Tooth Fairy. You can ask for anything you want, but you cannot have anything you want!

Man you’re a lost cause. It takes you two days to understand a simple idea and when you finally do you’re incapable of even acknowledging it, and instead have to move the goalposts to an irrelevant aside only to be wrong again.

Is this a kink? Do you get off on appearing incompetent? If so good job.

It is a kink of mine to argue with people who wish for the impossible

The goal post was a HASH table with ordered keys. ' Such a thing cannot exist and retain the desirable properties of a HASH tab=le

Do you think that statement is untrue?

Do you understand order analysis?

Because it came up recently for me (triggered a starvation bug), a caution for people expecting Go to randomize everything like this:

Blocked channel reads and writes are unblocked in FIFO order, not random. Mutexes are similar (afaict not quite identical, but the intent is the same).

Go randomizes a lot and I am thrilled they do that, and I knew about mutexes already, but the chan part was a surprise to me. It's reasonable and matches mutexes, so that's probably for the better, but still a bit oof.

Meh, what if people rely on randomness. They should flip between random and ordered at random too.

Yeah, gotta keep the programmer on his toes. He needs to embrace non-determinism, and second guess everything.

In case Go developer switches to a different language, we don't want to build bad habits. Map key iteration should be non-deterministically deterministic.

Well, every once in a while the random order will look like it's ordered

> Meh, what if people rely on randomness.

Then they are creating fragile software. They're always one language version upgrade away from disaster.

Yes, but that criticism already applies to the original iteration order before Go introduces a performance penalty by intentionally randomizing order on every iteration just so people can't rely on it.

> Blocked channel reads and writes are unblocked in FIFO order, not random

This should be obvious since the buffer is optional.

> but the chan part was a surprise to me

With multiple receivers it is effectively random _which_ receiver gets the wakeup.

Yeah, I don't mean buffered data. I mean blocked queueing operations.

>With multiple receivers it is effectively random _which_ receiver gets the wakeup.

That's why I brought it up: no it isn't. It's ordered. Intentionally.

https://github.com/golang/go/issues/11506

It's pretty easy to prove to yourself too, it only takes a couple dozen lines to write a test. I'm not confident it's guaranteed in all scenarios (mutexes are not, for example), but I've yet to see it do anything but perfect FIFO when not racing on starting both read and write simultaneously.

---

A single select statement with multiple eligible channel operations is random, which is part of why I expected blocked channel operations themselves to be random. But nope.

Reply on news.ycombinator.com