> 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.
Rust's `HashMap` and `HashSet` also do the same with the default hasher (you can plug your own deterministic hasher though). The reason for this choice, which I think also applies to Go, is to be resistant against HashDOS attacks, which can lead to hashmap lookups becoming O(n) on average. This is especially important for maps that will contain data coming from untrusted sources, like data submitted in a GET/POST request.
I do agree though that an ordered map would nicely solve the issue.
> Rust's `HashMap` and `HashSet` also do the same with the default hasher
Technically no.
Rust does use per-hashmap seeds for its keyed hashes (where many languages use per-process seeds).
Go does that, will also randomise iteration for each iteration (it randomises the start offset of the iteration). This latter operation has nothing to do with hashdos mitigation, and exists exclusively to frustrate accidental reliance on iteration order.
> I do agree though that an ordered map would nicely solve the issue.
To be precise, Rust does provide an ordered map in the standard library, it's std::collections::BTreeMap. However, iteration order is key comparison order, not insertion order.
I personally prefer something like Rust's `indexmap` instead, which is basically a hash table mapping from key to an index into a `Vec` containing the values. AFAIK this is also the approach taken by C#'s Dictionary.
I believe one rewrite of Python's dict was the first mainstream use of this sort of hash map as a default implementation.
I wish they provided a sort method to re-sort and re-index the vector to change the iteration order without the space overhead of creating a and sorting a separate vector/list of keys (or key-value pairs, depending on use case. You might want to change iteration order based on the currently held value).
> I believe one rewrite of Python's dict was the first mainstream use of this sort of hash map as a default implementation.
Technically pypy and I believe php implemented this model first, though it's probably most well known from cpython (for which it had been proposed first, by raymond hettinger).
Ordering generally denotes the preservation of insertion ordering, and possibly the alteration of that order. Sorted iteration is a completely different beast (and generally you’d use a tree-based collection if you need that).
If you're using a central dictionary then it should be worst case O(log n), but the price you pay for that is attacker controlled allocated memory growth.
there are various ways to structure dictionaries. one was to essentially create an array with each entry pointing into a list of values. you hash the key, then add the key/value to the list in that slot. the hash attacks would ensure everything hashed to the same slot, forcing the dict to become effectively become an alist.
it would do similar to implementations that keep jumping X slots mod size looking for an open slot, using the hash as the start slot. since everything hashed to the same value, everything you stuck in the dict would have to walk over every slot that had been stuck in the dict, again effectively making the dict into an overly complex association list for all practical reasons.
>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. This decision means that even if you don't care about a specific order, you will still need to sort the map before doing something else if you want reproducibility
Even if they didn't randomize, unless they also explicitly guaranteed stable map order across versions, you DO need to sort the map if you want reproducibility.
Because if you relied on it being conveniently stable within the same Go version, with no guarantees, your program would still be broken (reproducibility wise), if they changed the hashmap implementation.
There was a very insightful comment here on HN a while back; someone noted how terrible some SAP UI for travel was, because it provided a huge list of destinations in random order.
The insightful comment said they were sure that whoever was implementing the UI noted the list of destinations was always ordered, so never bothered to sort out themselves. And I guess the data source never guaranteed it was ordered, it was just a coincidence, and one day they stopped providing the list in-order.
Yeah, that's frequent card creation cause in our systems.
Relatively junior (e.g. graduated less than a year ago) engineer is tasked to make a List of Rooms. They write some EF, despite an actual formal course on SQL none of them seems to know the first thing about databases, but they can figure out EF apparently, the EF gives them a list of Rooms and it appears (at a glance) to be right so they commit their work and this ships to our users.
The people using the software ask why "8340B" is between "8340D" and "8340E" and the technical answer is "During database changes a year ago, the underlying data was reordered and that's where this record is" but that's not what they mean, they mean "Why didn't you idiots sort the data?" and the answer is well, junior engineer.
Of course with a layer of people to decide requirements by the time the card is in my next item pile it doesn't say "Just sort the EF query" - now it's about how we need to adjust the column widths, change to a new colour scheme, and add a checkbox nobody will use... oh, but also can this list be sorted ? So there's an excellent chance if another junior engineer takes that card the sorting gets overlooked and the users assume we can't (rather than don't) fix it.
> Even if they didn't randomize, unless they also explicitly guaranteed stable map order across versions, you DO need to sort the map if you want reproducibility.
Author here.
The particular case where this behaviour took me by surprise was when I wanted to print all available options from a toy CLI program that I wrote. I defined the options in a map (that had a function handler as a value) and didn't care about the order at all, but at least I expected the print order to be stable.
So it took me by surprise when I ran the program 3 times and the order changed. First I thought I did something wrong, then I found the issue after some search.
Now, it can be argued that this behaviour was good because I ended up sorting the values before printing, and now they have a predictable order. But I still think this was that kind of code that I didn't have to write (thanks to how Go works, I need to create a separate list and sort it instead; I think it is better with iterators in Go 1.23 though).
> Because if you relied on it being conveniently stable within the same Go version, with no guarantees, your program would still be broken (reproducibility wise), if they changed the hashmap implementation.
Well, not in this particular case. I just wanted it to print it in a stable way between multiple runs of the program. Again, maybe this whole thing helped me write a better program. But I still feel that it is unnecessary, and would prefer to just use a orderedmap instead.
> I defined the options in a map (that had a function handler as a value) and didn't care about the order at all, but at least I expected the print order to be stable.
But that means that you did care about the order. You may not have cared what it was, but you cared that it existed.
IOW, you relied on the order.
In any hashmap, it's a given that you cannot rely on the order. Some languages may explicitly give you those guarantees but that is separate from the prescription for 'hashmap'.
I think you're nitpicking about semantics, but ok.
> In any hashmap, it's a given that you cannot rely on the order.
Again, any order was fine, as long it was stable (it could be even stable between compiled versions, if Go say, add a salt during compilation). The weird part here is that it changed between runs.
> Again, any order was fine, as long it was stable
Understood, but that is not a guarantee of hashmaps. Hashmaps, by themselves, are a concept independent of any programming language.
So, sure, I get that your expectations of a hashmap's behaviour was set by some programming language $FOO, and that it is reasonable to expect that someone who learned on $FOO has the expectation that a hashmap has a specific behaviour.
But, that being said, after you learn that a hashmap is a concept independent of any programming language, and after you learned that that concept does not guarantee the behaviour you expect, it's signficantly easier to change your expectations for hashmap behaviour than to change the definition of the concept's guarantees.
Is this just not human desires projecting extra requirements?
You say you don't care about order, but then you clarify that you do want them to be stable between runs.
Those are not the same thing. To a computer without judgement, any order is fine. The first run is somehow blessed by you, so any runs after seem off or weird. If it didn't actually matter to a computer, it wouldn't care if it was different each run.
Not even that, because if you iterate multiple times you get random order in each different iteration:
package main
func main() {
m := map[string]bool{"foo": true, "bar": false, "baz": true, "qux": false, "quux": true}
for range 5 {
for k := range m {
println(k)
}
println()
}
}
$ go run ./main.go
bar
baz
qux
quux
foo
foo
bar
baz
qux
quux
qux
quux
foo
bar
baz
baz
qux
quux
foo
bar
quux
foo
bar
baz
qux
> You say you don't care about order, but then you clarify that you do want them to be stable between runs.
Being stable between runs doesn't mean I want a specific order. Slightly different things.
> Those are not the same thing. To a computer without judgement, any order is fine. The first run is somehow blessed by you, so any runs after seem off or weird. If it didn't actually matter to a computer, it wouldn't care if it was different each run.
If you want to argue about how computers work, remember that computers are bad at doing random things, this is why they need special hardware to do so.
The fact that Go goes as far to actually randomise each iteration is the surprising thing here, making iteration unstable, and not the fact that iterating between hash maps values are random.
> The fact that Go goes as far to actually randomise each iteration is the surprising thing here,
I gotta be honest, having come to Go after having first programmed professionally for around 25 years, I have never run into this problem. My expectation for hashmaps was set decades ago, and it was set as "Thou Shalt Not Depend On The Order Of Hashmaps!" :-)
Having used hashmaps via some obscure C library in the 90s, I quickly came to realise that I couldn't rely on the order - 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.
My own OSS hashmap library, on github, specifically doesn't mention order, because I (maybe naively) assumed that everyone reaching for a hashmap already knows that the order isn't guaranteed to be stable at all, even if the hashmap is never modified by the caller in between reads.
> 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.
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.
> 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!
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).
"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.
>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.
> 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.
>My expectation for hashmaps was set decades ago, and it was set as "Thou Shalt Not Depend On The Order Of Hashmaps!"
"when chasing a bug during development, it is nice to have a program demonstrate the bug every time you run it with the same inputs and not randomise things to make the bug intermittent" is what people mean when they say they want something to "be stable" or "the same". It's not a crazy thing to want control over, and for some reason this whole thread yammers on and on and doesn't address this point.
So did Go in the early days, which quickly proved to be problematic. Randomization was eventually added to try and call attention to buggy (in the typical case; yours may be an exception) code.
SQL does not guarantee the order, as well as go but we don’t complain about this in SQL :)
Some things needs to be accepted and I am actually glad go does randomization of the order — it makes programs more robust if the backing storage of the map will change in the future.
Having better data structures in stdlib will be beneficial, but we just got iterators so this will follow in 1-3 years time I believe.
I would prefer to not have generics in the language personally, but luckily they’re not that common in the codebases anyways.
This looks incredible. I used to write Go, but it always felt like wearing a straight jacket. Too many missing features relative to alternatives, but this fixes a big list of my complaints.
I am leery to tap into a new ecosystem, but the risk in this case might not be terrible. Theoretically, you could always take the transpiled code and port to idiomatic Go if the project died.
Yeah. That's similar to my thoughts. But only 2 contributors and no update in 3 months. And there are a number of open issues with zero responses. I'm not in a position to contribute myself. I don't know enough about compiling/transpiling and I have too much on my plate already. So I can't complain, but I'd by happy if more people joined the project and it had more activity. It's exactly what I'm looking for.
It looks like Borgo is to Golang what Typescript is to Javascript. It's kind of ridiculous that Golang would need this, but it actually makes sense to me as something you'd want to use.
> It's kind of ridiculous that Golang would need this
It's because Go is a ridiculous language. People don't want to admit this, but it was designed by people stuck in the last millennium when it comes to language design.
This exactly. I’m doing go now for a few years after coming from Java, Lisp, Ruby etc. I’ve often wondered while coding in it, if it was the result of a time traveller explaining garbage collection and lambdas to a 70’s C programmer living under a rock.
Come here to us in .NET land, we have even smaller AOT binaries, nullability and better systems programming story. And type unions, whenever they come around in one of the next releases.
How small can a .NET binary for a CLI application be using .NET? Any special instructions for compiling one? (Sorry that this is offtopic but I had the impression that .NET binaries were big so I thought I'd take this opportunity to ask... I like F#)
Short answer: 1-1.3MiB AOT, down to ~800KiB if you add flags to really push it (impractical). Will grow as you add dependencies. ~130KiB for runtime-less JIT, ~13MiB for JIT+runtime. All these imply a single runnable executable you can ship to user as is.
To get this just type `dotnet new console --aot && dotnet publish -o .` in a folder of choice. The binary and .csproj will have the name as the folder they are placed in. You can rename Program.cs too if it bothers you.
Long answer:
There are 3 main ways to publish a binary for a CLI (as well as back-end and often GUI too). .NET is quite flexible about this, which comes down to what you need:
- AOT which starts at 1-1.3MiB, this is what you get out of `dotnet new console --aot` template compiled with `dotnet publish -o .`
- JIT+runtime which starts at 12-13MiB, this is a combination of flags (which frankly would make a good default) trimmed, self-contained and single-file. Normally you get those by specifying them in .csproj or just doing `dotnet publish -o . -p:PublishTrimmed=true -p:PublishSingleFile=true`.
- JIT without runtime (expects the host to have .NET runtime installed) which starts at 120-140KiB. Notably, it's just a thin runtime launcher with pure CIL assemblies embedded in it. This can be achieved with `dotnet publish -o . -p:PublishSingleFile=true --sc false`.
All these have their own use cases that determine which one is the best. Usually, for CLI you either want to use the first or the third one. My personal preference for all kinds of on-off utilities is AOT as it has the best startup time. There are other ways to publish a binary, including the historical default which dumps all assemblies separately, but I think they are not useful given the nature of your question, nor something you need to deal with in practice.
For more comprehensive comparison of what to expect from .NET AOT, you can look at https://github.com/MichalStrehovsky/rt-sz/issues/63 which is a job that tracks binary size improvements/regressions from runtime contributions with the exact data for different templates and sample use cases (full vs stripped down console hello world, asp.net core webapiaot template, avalonia template, etc.)
Overall, what I meant by "smaller binary sizes" is that .NET's AOT tooling has become quite advanced over the last two releases, and provides better scalability as you add dependencies than Go due to metadata compression, dehydrated binary sections, flow analysis, etc.
To give you an example, there's https://github.com/codr7/sharpl that was on HN not so long ago, when compiled with .NET 9 RC.1 it takes about 2.6MiB on my machine.
On F# - 'FSharp.Core' has quite a few dated bits inside, and custom metadata, both of which are not very friendly to linking and AOT compilation size - it will produce trim warnings which means that there is code that might have been "trimmed away" but might be dynamically accessed at runtime, causing an exception. This is normally addressed by using one of the JIT options. Mind you, they still have good startup latency, just not the <100ms one.
I disagree with having the ordering embedded into the map implementation. That imposes an unnecessary performance overhead to support a small subset of use cases.
I think what the author requires is iterating over a sorted list of keys. That is pretty easy to implement using the standard library, and imposes the performance penalty only when it is needed.
There are three distinct types being discussed here, let me try to briefly explain them.
1. Just a hash table, Rust's std::collections::HashMap, C++ std::unordered_map, Go's map
This type is not about the "order" of its contents. If you want the "order" in any sense, that's not what this is for and you have the wrong type just as surely as if you were surprised that your integer type can't store a half. Types of this kind can be optimised to provide extremely fast indexing by key which is why they exist as this is useful in many problems.
2. A container arranged by the value of the keys, Rust's BTreeMap, C++ std::map
This type is about the order of its contents by value. It doesn't matter when you put a 4 into this container, it goes between 3 and 5 anyway. This type is good when you need to work in that "by value" order later, for example to take the "Most important" item or the "Soonest". It doesn't remember the order in which things were added, and it is relatively slow to find items by their key.
This type remembers the order in which you inserted items into the container and can give them all back in that order efficiently. In other ways it's like the first container, but it compromises performance significantly to deliver this "order" promise.
It is problematic that people talk past each other on this, both in terms of a useful discussion on HN, but much worse in a Software Engineerign team if you thought you were being given an OrderedDict, but it was actually a BTreeMap for example.
Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.
> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container
I believe this misses quite an important bit of history. Python's dict retains key creation order since 3.6, and the behaviour was made official from 3.7 onwards. But before that, the keys were in unspecified order. Not random, because the order was stable: if you iterated through the same dict twice within the same process, you got the keys in the same order.
The property of retaining key creation order was a side effect from the underlying implementation. In the 3.6 release, Python switched over to their new dictionary implementation, lifted from the PyPy project. From what I recall, the reason for the change was that the new implementation had a notably lower per-key overhead. That decrease in memory use resulted, I believe, in the slightly faster performance as well. Order retention came "for free".
Personally I believe that order retention as a default property is a mistake. Now, I admit that OrderedDict semantics are often more convenient, but they break from the expected dict/map semantics with other languages. And since we are stating our opinions, in my mind Go choosing to forcibly randomise maps' key traversal order is a good safeguard. It guarantees that no-one can even accidentally depend on key iteration order. (Yes, I have seen production outages thanks to someone's code implicitly relying on key creation/traversal order when processing RESTful payloads.)
As should be apparent, I disagree with the current behaviour being "least surprising".
Sure. This is from the previous job. And for background: the service in question would routinely have several thousand concurrent, live user sessions. All stateful.
Two teams, let's call them Team A and team B, would have their respective services handling user traffic. Service maintained by Team A would handle the traffic, while service maintained by Team B would handle the more complex background state transitions that Team A would not have to care about during the day.
Service A would hold a complete client session state. Service B was stateless. Messages sent from service A to service B would contain all the necessary data to build up the correct state for every message received. Team A wrote their service in "not Python" language. Team B wrote theirs in Python. Communication between the services was RESTful, so essentially "JSON payload in a HTTP POST message".
Service B had a construction in their code that in simplified terms looked a bit like this:
data = json.loads(msg.data)
for key_, val_ in data.items():
do_stuff(key_, val_)
And then inside the do_stuff() routine, there was a piece of logic that used an implicit state machine. It wasn't written like one, but it happened to rely on the processing order... Like this:
def do_stuff(field, vals):
if field in (<possible action triggers>):
# do something based on field
else:
# other things
Because service B was written in Python, and this was post python 3.6 days, the 'data' read from the message created a dictionary with keys in the same order they happened to come off the wire. Everything worked fine, because the way the on-the-wire JSON payload at service A was constructed also happened to put field keys in a specific order. Service B could process the fields in the order they came through and could build a larger state internally based on each of the fields.
Then, as happens to every well used service, requirements change. In order to support new use cases, service A would need to include a new field - and for the maintainers of that service, the most logical place in their internal structure was between existing fields. This change was known, and service B had added support for this additional field. In 'do_stuff' internals, they had added the new field to the end of the possible action triggers. They also had unit tests - written by themselves - to ensure their service would work correctly whether it received old or new payloads.
The unit tests had added the new field after the existing fields in their test inputs. Their internal state machine was coherent and correct.
And then, Team A ships their new service. Service B promptly starts to crash. Every crash triggers Sentry client to serialise the full stack trace and send it over. In order to prevent a cascade failure, Sentry itself has been configured with a throttle, so once enough in-flight request are lined up, it starts to apply backpressure and response delays. Sentry clients within service B end up blocking their respective workers. Service A can not reliably send its message over, because service B is bogged down waiting for N+1 Sentry client submissions to complete. In order to capture the error situations properly, service A also has Sentry client within it...
It takes about 10 minutes for the teams to figure out what's going on before team A rolls back their deployment. But that was nonetheless visible downtime during live trading hours.
The root cause was obviously a logic bug, but it was only possible to build up to having such a logic bug due to the key iteration order semantics.
Not to take away from your broader point (that different data types are appropriate in different scenarios), but:
> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.
The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself.
Up until python 3.6, cpython dictionaries were not ordered. At version 3.6, cpython dicts were made ordered, but only as an implementation detail. And at version 3.7, the preserves-insertion-order property of dicts was officially made part of the language spec, so that all python implementations need to support it.
The 3.6 change was made purely for performance reasons (and the stdlib already included an OrderedDict anyways). It was then made part of the language spec in 3.7 for several reasons: reduced maintenance burden for OrderedDict, convenience to developers using python, reducing the chance of accidental footguns of people relying on the implementation detail as if it were actually part of the language (and it then being removed later and breaking things), etc.
The decision was made as part of this thread[1], if you're curious.
> The python dict implementation is actually extremely optimized
It was upgraded from "optimized" terrible garbage to a sane attempt to do the same thing but smaller and faster. In the Python world I'm sure that's "extremely optimized". In the rest of the world we know it's not optimisation unless you measure and when you measure the Python dict is mediocre (but used to be much worse)
> used in very critical hot paths throughout the interpreter and object model
The old even worse one was used in the very same Python "critical hot paths" for many years.
Actually the earlier Python dict reminds me of "I can't believe it can sort" which is a weird sort algorithm which looks like it's a defective Insertion Sort that won't work, but is actually a working (but O(n*2) best case) sort algorithm. The old dict does in fact provide a hash table type for Python. It's much bigger than it needs to be, in order to enable an "optimization" which also makes it much slower than it needs to be.
>The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself.
Yes. Raymond Hettinger has one or more videos on YouTube titled something like "Python dictionaries" or "Modern Python dictionaries" that talk about the optimisations done on them.
The maintenance burden for ordered dict was not changed: ODict supports constant time moving to or removing from the start or end, so it has to be a linked hashmap, regardless of the ordering of the underlying map.
> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.
That is completely incorrect. The builtin dict is similar to https://docs.rs/indexmap/latest/indexmap/ not a linked hashmap, it was used because it significantly improves iteration speed and uses less memory.
The crucial thing about IndexedMap is that it is not actually order preserving.
If it gets inconvenient to preserve order, it's just not preserved. For example if I put sixty items in, then remove thirty and add forty more, IndexedMap doesn't put all those forty items "after" the remaining thirty from the removal because that's more work.
Python does preserve order, the fact that internally it looks somewhat like IndexedMap is an implementation detail.
> the fact that internally it looks somewhat like IndexedMap is an implementation detail.
It really is not. IndexMap was directly inspired by Python’s naturally ordered dicts. It’s spelled out right in the readme.
And while indexmap has weaker ordering guarantees for performance reasons (though also additional features aplenty), “ordermap” was revived as a wrapper which does conserve ordering on removal.
If you do the remove naively yes, but you can use tombstoning which amortises the cost (at that of an increased iteration overhead), or using a non-order-preserving remove (like indexmap itself, though `remove` has been deprecated and you now get to pick your poison).
I deserved that, maybe I should write up a whole blog post about this topic where I can include a diagram so that we're clear it's the value (as opposed to its age or any other characteristic) of the key
if you want your comments to make any sense, you need to use "key value" with every usage of "value", otherwise people are going to think "container value"
The author is not saying that ordering needs to be added to the _current_ map implementation. He suggests adding an additional map implementation that has ordering built in. That way, you can choose between functionality and (hypothetical) better performance
The author does not seem to require iterating over a sorted list. Sorting is not the same as ordering. An ordered map is a map in which the insertion order is preserved when iterating over the elements. A sorted map outputs the elements in an order defined by a comparison function when iterating, regardless of their insertion order. You can for example sort alphabetical in case of string keys.
In most cases the performance penalty of having an extra internal array to keep track of insertion order is minimal, and the whole point of built-in collections is so people can quickly write correct programs. When optimizing for performance default collections are likely to get replaced with hand-rolled versions anyway. But in all other cases a dictionary that “just works” is preferable to one that has such an annoying footgun that the go team had to randomize the iteration order in an attempt to treat the symptom instead of choosing correctness. Go isn’t even a high-performance language and many language design choices (channels!) explicit prioritize correctness over performance.
It’s like having an unstable sort as the default standard library sort function. People reasonably expect that when calling sort twice the second sort to do nothing, but you can always find people who will passionately argue that people deserve to get burned if they assume a sort function is stable.
In case you haven't realized yet, a hash table that maintains the insertion order can be still do O(1) deletes as long as the key order doesn't change arbitrarily after the initial insertion.
An array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)
That depends on what someone is willing to compromise. Extra space to point back at exactly that key (but that also needs to be updated each compaction?); personally I'd normally rather pay the lookup or key sort on iterator snapshot fee. An 'insert, or re-sorted order' side index which allows for nodes to be marked as 'deleted' (maybe nil / null, maybe a sentinel value meaning skip?); I might propose that to see if it fit the requirements well enough.
> I disagree with having the ordering embedded into the map implementation.
Good thing that's not what they are asking at all. They just want an ordered map to be in the standard library.
> That imposes an unnecessary performance overhead to support a small subset of use cases.
Naturally ordered hash maps generally have a small performance hit on lookup and a performance gain on iteration, as iteration goes through a dense array.
Linked hash maps do tend to have worse performances for all cases.
> I think what the author requires is iterating over a sorted list of keys.
Had they needed that, they'd have said that. But they did not. And they specifically refer to an ordered map, and to Python's built-in and Ordered dicts, which are not sorted.
This is actually terrible. I tried that a while ago, but after a short while removed all of the Optional[] code and went back to pointers. Why? The default ser/des in go just cannot play. It instead works great with pointers.
Using pointers that are nillable whenever I want to have an optional value. How did I solve the usability problem? I just introduced 2 simple methods: Or and Of. First one will resolve ptr to a value or default if nil (provided in param) and the second one will make a ptr from a value type. That is actually all you need! Don't have the code here or I'd post it but it's easy enough to make your own (with generics).
We have started doing this at work as well. It makes the code a lot easier to understand, and I think it's worth the small hassle that this entails (because without a `match` statement, dealing with an Option type is verbose).
> 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.
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(...)
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.
Notice how almost all of those are just a variable name or a number on a line by itself. Those being valid programs says very little about Perl as a language.
A few semicolons being okay in a mix with the above doesn't say much either, and the couple gnarliest examples happened to hit #, the comment character, so the rest isn't even being treated as code.
Counterpoint - Perl 5 should be (and frankly probably is) required reading for all language designers. You may not like its opinionated point of view, but it glued together the early internet, and occupied a niche so large for so long that calling it a niche is underselling it. Misunderstanding why Perl worked, and what worked about it is a miss in an any serious software engineer’s education.
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).
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
}
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
> 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.
> 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.
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.
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 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.)
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).
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.
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.
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’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.
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.
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.
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.
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.
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.
The lack of default argument values initially annoyed me, but I kind of came to like it. It makes me put more thought into my function interfaces.
In the rare cases I do want a default it's usually reasonable to just add a second function that calls the first with the default value.
I don't end up doing this a lot, but I certainly have in a couple handful of cases. A lot of Go libraries for HTTP related activities do this with the default context. They'll have a function that accepts a context and a function that has the default context.
FWIW a lot of those packages with default context wrapper functions have that as a backwards compatibility measure for code written before the context package existed. It's almost always preferable to call the newer function with your own context instead
Sure, one can make a new function. That's what I do, too, but then I end up greatly missing function overloading. In the example's case I might end up making a ReplaceAll function. It creates namespace clutter.
Function overloading could easily handle context with and without arguments.
I think if there are a lot of functions (or a function with a lot of arguments, common to python) you have clutter regardless. I would rather have a bunch of different names than a bunch of different functions with the same name. Having to choose names for each of the functions is a gentle push back asking “do you really need all these flavours of function or are you abstracting this in the wrong way?”
I've seen the python ordered dict thing bite ex-python programmers over and over, in two different ways.
First, assuming that the keys iterate in the order they're inserted, the cliche problem.
Second, marshalling JSON and unconsciously relying on the order in the JSON as hidden semantics. This makes it hard to understand the JSON as a human, as well as making what ought to be a portable format with other languages hard to reuse.
I've decided that Python is in the wrong here, not technically, but rather for encouraging humans to assume too much.
> First, assuming that the keys iterate in the order they're inserted, the cliche problem.
Author here.
I never assume that hash maps can be iterated in the same order as the insertion in any language, however the fact that in Go each iteration results in a different ordering is surprising.
As the article says, reproducibility is important. If I have a bug on one run, I want to get that bug again on the second run. I want to be able to run the program again and again and have the same breakpoints hit in the same order with the same variables. If I run tests, I want them to give the same results each time.
Randomness is bugs. Adding randomness to a language is adding bugs.
You can't avoid randomness and entropy, it's just something that's needed in too many places. For test repeatability though, whatever seeds a test run uses should be saved in order to repeat that test exactly.
Best of both worlds: you get to cover weird bugs that only show up when stuff is in a certain order, and you can repeat the tests exactly.
I wish that an unhandled error would crash its way up the stack automatically returning error if the next function up can do so, until it is either caught into a variable or can't be returned (panic if error can't be returned).
This would get close to python try/catch with even lighter syntax.
This would cut so much boilerplate hand carrying error up the stack.
I didn't say this is error handling, this is a stack trace for debugging on error.
Similar to an uncaught exception in other languages. And yes, I will not use this on production applications or libraries, I mostly use this in scripts where this kind of thing makes sense.
The thing that bothers me is... golang actually has exceptions. It is just that nobody will dare mention it. Panic and recover eh? It is just that by default error is the thing you should use and everything and everyone does. Then the exception mechanism comes along and you now have 2 ways of handling errors. Making things quite confusing.
“I don't think the language needs to support the generic solution for nullability, that would be either having proper Union or Sum types.”
- then goes on to describe some of the problems sum types would solve. Why. Why doesn’t go need this? It was just presented as a blanket statement without a reason.
Personally, I see missing sum types as a major gap, and I reach for them all the time in other languages.
I didn't develop too much because as I said in another thread, I wrote this post without giving much thought. Sorry for not being at the HN standards, but this post wasn't even supposed to be here, and here we are ;).
That said, I think given the current state of the language, adding nullability would be much easier to do than adding Union or Sum types. And from my experience with Kotlin, nullability already gives much of the benefits.
I am not saying I will not change my opinion in the future. I got my first job working with a language that has algebraic types (Scala), so my opinion may change in future. However, even if it changes I think getting Union or Sum types in a language like Go is impossible, while nullables are unlikely to happen but at least not impossible.
The generic type params already supports a sum type like interface, it’s almost there.
So, if you could, please expound with on “why”
Is there something in the type system, something in the compiler that prevents it?
Anyway, re: not up to HN standards… I’m not sure what you’re talking about. You made it to the front page, you called out some legitimate issues, I liked reading what you had to say, I was just asking for more
I think I recommend you reading the proposal them. I don't claim of being a specialist in Go to say if it is possible or not, but I find it highly unlikely given how the language is.
The reason I think nullability is more likely than sum types is because Go tries to be a simple language (whatever the developers of the language think simple is), and nullability is simpler than sum types (both to implement and use). But again, I don't have any special insight
I've heard this several times - "Go would be great if only they added <my-favourite-feature>"...
Go's philosophy is that a coherent, curated feature set is as valid an approach to language design as the C++/Python/... approach of adding every possible language feature.
In particular I doubt Go will ever add null-safety - given the above philosophy, the language's pervasive use of "zero values", and its strong commitment to backwards compatibility.
I can’t see how Go feature list is any more curated or more coherent than in other languages. Seriously to me it feels like many Go features were rushed and some added despite the evidence they are a bad idea. Like, why an unused import / unused variable is a hard error but an unused function is not? Or why for a very long time maps and channels were special by being generic but you could not use generics in your own types (that has fortunately changed). Why add nil / default values at the time where virtually everybody knows this is a bad feature and there are better solutions established?
In the cases where this is important, you can use pointers. Go allows you to make pointers to primitives as well (making the zero value nil) so you can explicitly define those edge cases.
You’d be surprised how infrequently that’s actually a concern though.
Using pointers feels horrible as a workaround though because it completely muddies the intent. Is it a pointer because it could be zero or <not set>, is it a pointer for performance reasons, is it a pointer because the function mutates it? To me it flies directly in the face of Go's desire to keep things simple and easy to reason about.
> You’d be surprised how infrequently that’s actually a concern though
I admittedly don't write a huge amount of Go, but I run into this fairly often any time I'm dealing with user input. Something like an optional numeric input is not at all uncommon.
What? That is actually an everyday concern and devs assuming that information is not needed will bring pain down the road.
Just two cases of the top of my head: working with databases and json interop with other systems that actually do differentiate. And the second one should not happen, but people do make assumptions and sometimes those are inherently incompatible with how golang works.
I was wondering if there's a pattern of using Option types or something to signal the difference.
I ask because I hit this issue a fair few years ago with protobuf v3, we ended up using a wrapper type pattern. Can't recall why it was important to know at the time, but it was.
Being unable to access struct fields a.b.c without risking a panic sucks (and which caused the panic: a.b or b.c?). There's no remotely ergonomic solution to the problem, because there's no nil-safe struct member operator, there's no ternary operator, and if-statements can't be used as expressions.
This wouldn't be such a problem, since of course you can just "choose" to not use pointer- or interface-typed fields in "your" structs, but as soon as serialization, databases, or other people's APIs are involved, you don't have that "choice" anymore.
In the same vein, being unable to write e.g. &true or &"foo" is annoying too. If I can write &struct{...} why can't I write &true?
Not being able to take a pointer to a literal is one of my pet peeves with Go - especially when using the AWS SDK, which requires pointers to literals everywhere. At least with generics, a wrapper function doesn't require a separate function per type though, and can be simply:
Yeah, that particular case got better with generics. It's still more verbose to write ptr.To(true) than &true though.
Unfortunately, there's no generic type constraint for "is an interface" or even "is nilable" so you can't use generics to solve nil-safety issues in general.
I always thought there should be a two-arg overload of new, so you could write new(bool, true) or new(int, 20). Would solve the problem without any trickery.
(e.g. if some data is not initialized along the way, or you put in some new object which just isn't meant to have that field but some related logic needs to check for it)
Yup, it is Kotlin-style nullability analysis that is a default everywhere now. The last place that does not have ideal behavior is System.Text.Json, but that is fixable with a flag, maybe two, and there are edge cases where static analysis can't see through some expressions and assumes null so you have to specify it isn't with '!'. Nonetheless, works great with '??', '??=' expressions, required fields/props and pattern matching.
From practical standpoint, a project with Nullable: enable, WarningsAsErrors: nullable has almost never have to think about unexpected nulls again - a solved problem.
Having nullability has its own set of issues. I prefer explicit error handling to null checks. That being said, I don’t think there is really that much of a difference in that you might use Interface as a JS Any sort of thing in Go (it’s obviously difference), and where you would deal with nil pointers is often where you would perform a null check anyway.
I prefer the go style of doing a check every time rather than some of the time with the risk of missing a time. Or on the flip-side simply defining your own default.
I know that a lot of people like how C# is becoming more and more reliant on the compiler to handle type checks, but it also opens up the risk of more developer mistakes. It’s mostly down to opinion and preference. So I don’t think you can really call it a “problem” as such. Having nullability will be a feature to some, and not having it will be a feature to others. I think both decisions were right for their respective languages. C# needs it for its close integration with mssql and its exception handling. Go doesn’t want it because it favours simplicity in types and direct error handling.
> Having nullability has its own set of issues. I prefer explicit error handling to null checks.
Nullability does not preclude explicit checks. In fact it requires them. Which Go currently does not: you can dereference any pointer or use any interface and it will blow in your face if either is nil.
> C# is becoming more and more reliant on the compiler to handle type checks, but it also opens up the risk of more developer mistakes.
That literally makes no sense. The entire point of moving checks to the compiler is that it catches developer errors upstream and prevents them.
> C# needs it for its close integration with mssql and its exception handling.
That's a nonsensical just-so story. Go on, explain how Haskell or Swift or Zig have explicit nullability for their close integration with mssql and exception handling (and while at it, do explain the relationship between exception handling and nullability)
I am constantly criticising the C# community for not looking at other languages enough, but in this case it cuts both ways: C# has every feature mentioned here. Including a pretty good model for nullable.
I don't think having nullables can be called a feature as such. It adds complexity to your code and it directly goes against Go's philosophy of explicit error handling and simple types. Of course it's completely opinion based but I think having people handle errors directly instead of dealing with them through exceptions and checks makes for much more predictable code. I'm also not sure I really see the difference that GP does. I think that in a lot of code you're going to do a lot of null checks anyway, maybe even more than how often you'll check if your pointers are nil, but at least with Go you're not risking missing one.
Maybe the Go engineers didn't think about nullables, but I think there is a good chance they simply decided against them for various reasons.
We could argue about the Go philosophy till the cows come home, but maybe it would be better to just consider that not having a nullable int makes modelling database tables painful.
Yes it does. I just don’t understand why does everyone want every language to be the same language? If you want all the sugar then C#, Java, latest C++ all are perfectly mature and usable and fit that niche
Because languages are more then just syntax, so ofcourse You'd rather have your favorite language copy some syntax you like, then be forced to switch entire stack to another language just to be able to use that syntax
In Java, objects are responsible for their equals/hashCode implementations. The contract they must abide by is:
1. If two objects are equal, they must produce the same hash code; and
2. If they are not equal, they may produce the same hash code.
So if you had a list of 10 Strings and put them in a map in Java, it's likely you'll get a deterministic order for iterating over them unless you added a random factor. That factor could be a random seed tied to the map that you XOR the hash code with.
You can't really change the hash code itself to avoid a Hash DoS attack because you might break that contract. So how does Go (and Rust?) deal with that? Is Go adding a random seed to each hash map? If not, what is it doing?
As for nullability, there's no going back once you use a type system that expresses nullability.
Lastly, PHP arrays are incredibly convenient, ignoring the weirdness with them being array and hash map hybrids. But th ekey aspect is that they maintain insertion order when you use them like a map. This is so often what you want. Yes, other langauges do this too (eg Java's LinkedHashMap) but it's (IMHO) such a useful default.
What you do is have a "family" of hash functions. The random seed value chooses a new hash function. The same properties apply to each individual map's hash function, but each map has a different hash function
Secondary, go map iteration starts from a random position in the hashmap. The order on subsequent iterations is the same, but rotated as a result of the random start index
You don't use the object hash as the key directly. You combine it with a value chosen randomly per-map using a function that works hard to erase correlations between the input object hash and the output table location.
I never expected this post to get here in HN the way it was. It is definitely a work in progress, most some personal notes that I will probably add more when I use other parts in Go that bothers me.
BTW, I will confess: the orderedmap one is something that I put mostly because I know it is something that would be feasible to implement in a future version of the language and it would probably be relatively uncontroversial.
So I was expecting maybe someone will end up doing the work to propose and/or implement this to Go. Who knows, maybe this will work.
Yes, I did cover this point in the post, but basically the main issue of not having this in stdlib is because now the choice is not obvious: if you search "ordered map for golang" you will find a dozen of different implementations.
Streamlining the awful error handling would seriously make the developer experience SO much better... but this is Go, where developer experience comes dead last in priority.
But having done some Rust development lately, I really miss the ? thing every time I go back to golang. It's such a small change and purely syntactic but ould make ones code much shorter and maybe even more readable.
I suspect the reason why so many people are passionate about Go language features is that, if it only had their one pet feature, it would be the perfect language. But I agree that the error handling could be better!
I agree with most of this list, and I'd add some kind of null coalescing or ternary operator, even if it was limited to one operater per expression, and a date time handling library that doesn't make me want to pull.my hair out.
There's several things that keep me on Go, single binary, decent built in tooling, and decent speed.
I've started playing around with tinygo on Pi Pico's, and after the dealing with getting C and C++ onto other MCUs it's a breath of fresh air.
But the rough edges are very rough. At some point another language is going to come along with better syntax with the same single binary and good tooling and I'll probably switch over as fast as possible.
Interesting, I agree with the the main idea: in general I find Go a productive language, but there’s a few rough edges.
The specific examples don’t ring true to me though.
Instead of named arguments, use the functional optional pattern.
An ordered map can be implemented as a slice with a get function. If you want to stamp out some code duplication, Go has generics and iterators these days.
What I really miss are enums. Specifically, the ability to map two value sets to each other and get a compile time error if the mapping becomes stale due to a new value.
And other assorted stuff. Like better nil handling, the weird time and http client libraries, nil interfaces and slices, and so on.
The functional optional pattern thing seems fine for constructors, but I wouldn't want to have to implement it for every single function. A lot of the times it is just about readability at the call site, e.g. (using the author's example)
But it can also be awkward to have to declare a variable for every arg, which is probably why python allows you to call it both ways. Plus the variable names and positional arg could not match up, which can be a source of hard to find bugs
The fact that `strings.ReplaceAll` exists I think is a good argument for having default arguments, because I can't think of a good reason why we need a separate function for this case.
But maybe it was a bad example. I remember that there is one function in `strings` that I almost always use the same value in every call I do because it is the correct value in 80% of the cases. I thought it was `strings.Replace`, but probably it is something else. If I ever remember which function it is, I will update the post.
> Instead of named arguments, use the functional optional pattern.
Options pattern is an alternative, I use it frequently, but still miss named arguments and default arguments if I'm going back and forth with Python.
- The options pattern is much more verbose to implement.
- The defaults aren't as easily clear, they need to be documented and kept consistent.
- You can't, or it's not as easy to, make some arguments required.
- And, as a caller, if the API I'm using doesn't support them, I sometimes have to rely on comments to clarify what each arg is. For example, if a function takes a bools like `func MyFunc(dryrun, inverse bool, items ...string) error { ... }`
Also the functional options pattern usually implies that there is an object on which the functions operate. Default values for parameters is something that can apply to any function, not just initializers.
I wonder if parent could give us an alternative for strings.Replace using functional options.
> The specific examples don’t ring true to me though.
And I don't think it should. To start, the list is small because it is a work in progress, I plan to write more once I have more to talk. I didn't expect this post to hit HN that soon, but thanks to whoever posted this here. Got some really interesting points of view. But also they are particular pet peeves of mine, and don't necessarily reflect other people's experiences.
If you use functional options, please don't implement them with closures. Closures aren't comparable, so there's essentially no way to build middleware that varies behavior based on those arguments.
Just make a `type thearg string` or whatever instead. Very similar amounts of code, similarly hidden implementation, but MUCH more usable.
The whole point of the "functional" options pattern is that the option's own identity or type doesn't matter, only its side-effects. If you do need to examine the option itself, you're either using the wrong pattern, or you should be using an interface with additional, self-descriptive methods instead.
For example, I have used an interface similar to the following for a custom HTTP client wrapper (as discussed in another thread):
The Priority method might seem like overkill, but it was useful here because there are default options for the whole client and local options on each call, which have to be merged and applied in the proper order.
If you're using the functional options pattern, and you're trying to == or type-assert one of the options, you're the one doing something abnormal.
Maybe it makes sense in the broader context of what you're trying to do, but then I'd say that the functional options pattern isn't the right fit in the first place.
Also, "side effect" in computer science has a pretty straightforward definition, and equality comparisons are not side effects.
Side effect: agreed, but the way you used it makes no sense in that definition (arguments cannot have side effects on a function call, they're resolved before the function is called), and the main other option in Go is to pass a struct or separate typed arguments which also has no side effects, and the only other interpretation is "the side effects you can trigger in the function based on the argument" which is identical in all scenarios...
so I figured you were using it in the more colloquial way where it's closer "observable behavior [of the argument's type]". Or "the unintended consequences of a design decision".
The entire purpose of this function is to be called, and when called, to change something about the value pointed to by ptr. That seems like a classic case of side effect to me, since the function returns no value (hence it's not a "pure function") but instead mutates some state (which lives beyond the function call).
For example, we can make such an option like this:
The options would then be accepted by another function, such as:
func Example(requiredArg string, options ...Option) T {
val := T{someField: requiredArg}
for _, option := range options {
option(&val)
}
return val
}
In the body of Example, there's no need to use == on an Option. Each Option does its thing when called, and then we move on to the next one. We would use all of these things like this:
Obviously, this is a trivial example, but I think it illustrates the point that functional options are used for their side-effects. If you need to do fancier things than just unconditionally set a field, you do all of that in the option itself (either before creating the closure, or inside the body of the closure).
You're describing the absolute basics of functional options to someone who, by cautioning about a niche usability issue with this exact implementation, has demonstrated a solid understanding of them.
I've re-read everything you've written so far, and I think we're just in violent agreement. It would have helped if you provided some explanatory code, but the word "middleware" in your original post (which may have been edited in? if not, sorry, that's on me) clarifies a lot for me.
If you do need to == or type-assert the options, then don't make them functional. That seems to be what you were saying with `type thearg string` earlier. However, I think my original example with an interface illustrated another/better way to solve the same problem: make the options self-describing.
My issue with using closures as your functional option implementation type (i.e. "functional options" is "call this function to get an opaque arg" which does not imply that you need to use a closure, it's just a common implementation strategy) is that when a library does it, it prevents anyone from writing middleware that is interested in argument equality. Among other useful desires.
That's quite common in my experience, and working around it on the library-user side is rather painful, as it often requires reimplementing roughly the entire API so it can be controlled.
The alternative is to have your return type be an opaque interface, which can have any implementation (including closures):
type Option {
apply(...) // privately implementable only
// or just have an empty `private()` or something
}
type someoption string
func (s someoption) apply(...) {
// whatever is needed, it can be changed any time
}
func SomeOption(val string) Option {
return someoption(val)
}
wrap(thing, SomeOption("arg"))
^ in this, the wrapper can check if options include `SomeOption("arg")` if that becomes useful for some reason. Quite often that reason is "tests", but I do keep running into other scenarios where it'd be useful too. I've helped multiple people work around it by reflecting on the function's signature, constructing the private arg type, calling the func, and comparing the mutated private apply-arg-type to a known value, but this isn't always possible and those cases are stuck either not doing the thing they wanted, or writing tons of code to wrap the types completely.
Using a more concrete type also logs/prints/debugs usefully by default in most cases, giving you `someoption{"arg"}` instead of `(fntype)(&0x3768dh893)`.
As a library author you generally cannot predict this kind of need, and using function closures is by far the least flexible and least-user-friendly option for your users. So I recommend not doing that.
Oh interested in the issues with http clients you have? I think they are great to use for being right in the standard library. Only complaint I have is defaults for timeouts and such, but you make that mistake once and don't forget.
The reason for randomized hash is most probably to mitigate DOS attacks based on users knowing which hash function is used (Go is open source, after all) and finding a way to fill a map - any map - with untouched tokens.
There’s a lot of situations in reasonable unordered map implementations where the elements, by chance, do happen to be ordered. Just due to arbitrary implementation decisions.
But the Go spec says that maps are unordered, and library writers want to reserve the right to change the implementation in the future.
So always ransoming the dict prevents code from accidentally depending on some specific map implementation detail.
> The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another.
> In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order.
> This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a mapl.
After getting used to Python's dicts being ordered since 3.6, I really wish every language would do this. I think it is natural to think about the keys being kept in inserted order, and it is very handy a lot of the time. Rust's `indexmap` for example is nearly as performant if I recall as the stdlib `HashMap`, so it probably wouldn't be much in the way of overhead to do so. Regardless, every major lang should have an ordered map in the stdlib in my opinion.
I think this perfectly illustrates the problem the thing I would most want to see is sum types e.g. we all have some particular thing we would want to add and we can't add em all.
I guess i don’t care very much about the “ergonomics”, like sorted hashes or whatever. I’d be really happy with faster execution, smaller memory footprint, smaller binaries. Conditional compilation would be great, but maybe smart utilization of code generation is sufficient here. For me the glaring gap i suffer with is data processing and ML, which is a community/library thing.
Nullability is poor man's `Maybe`/`Optional`, and I'd love to see that at the type system level (cf. `data Maybe a = Just a | Nothing`) rather than current {sql,null}.Null* mess or whatever was proposed in https://github.com/golang/go/issues/48702. But I doubt if that'll ever happen.
Default arguments being hidden/unclear/wrong/hard to find/undocumented is by far the #1 source of bugs I encounter in Python programs. It's not even close. Probably around 70%.
Even worse when you see function X takes some parameters and then passes *args and **kwargs to a client function. Makes the available (or required) parameters very difficult to track down.
I’m not convinced that limiting expressiveness (for example by not supporting generics) will make software easier to read and maintain. For smaller programs that might very well be true, but for me personally, having more expressiveness makes it easier to navigate bigger code bases because you don’t have to trudge through code duplication, unnecessary boilerplate etc.
Generics in Go have been appeared in 2022 (in Go1.18). There were many popular open source projects with big code bases written in Go before 2022 - Docker, Kubernetes, Prometheus, Caddy, InfluxDB, etcd, minio, Terraform, CockroachDB, Consul, Helm, VictoriaMetrics, etc. The absence of generics didn't prevent from writing and maintaining these projects.
I'm unaware of popular projects in Go, which have been appeared after 2022 thanks to generics.
I agree. The limited expressiveness in Go also worked as an advantage because of its simplicity. Additionally, as the article mentions, the lack of lambdas made the syntax less convenient. For me, it struck a good balance before generics and other features were added.
> Any programming language that allows it is flawed.
I think any language that allows that has different priorities than complete code correctness. There might even be programmers out there that would also prefer those priorities (simplicity, speed, etc) over having the compiler spend time every compilation to make sure a pointer is null or not.
The amount of time spent every compilation on this is negligible: a nullable type is just another type like any other. I don’t buy your argument at all.
It’s a clear no-brainer at this point: null references were a mistake, and any language with compile-time type checking is flawed if they’re allowed.
> It’s a clear no-brainer at this point: null references were a mistake, and any language with compile-time type checking is flawed if they’re allowed.
Maybe you mean 'dereferences', not 'references', because without NULL/null/nil, we can't interface to the real world which is filled with "there is no value here!" values.
No. The null reference shouldn't exist. That's Tony Hoare's "Billion Dollar Mistake".
Rust does not have null references. If I have a reference it is not null.
The "there is no value here" semantic is provided by Option<T> - if I mean that there may or may not be a reference I want Option<&T> an optional reference.
> No. The null reference shouldn't exist. That's Tony Hoare's "Billion Dollar Mistake".
This gets repeated so much, so often, that at this point it's safer to assume that the person who is citing it is just so new to programming that they don't realise we've all already seen multiple times, almost always posted by an enthusiastic but ultimately green newbie.
> Rust does not have null references.
So? The word "reference" in Rust is defined by that languages specification, which is not the same definition as the word "reference" used in English, nor in other programming languages.
If you were having a Rust-specific discussion, you should have said so.
> - if I mean that there may or may not be a reference I want Option<&T>
And one of those options is `this reference does not exist`, which is what Tony Hoare referred to as a null reference in his writing(s).
Hence it's the dereference that's a problem in programming languages other than Rust, not the existence of the null reference in languages other than Rust.
Note, I am using the word 'reference' as defined everywhere outside of Rust. I am also using the word 'dereference' as defined everywhere outside of Rust.
Yes, other people are going to keep pointing you at Tony's lecture because people like you are going to keep insisting that somehow this was a good idea, which it was not.
I wouldn't have mentioned Tony's lecture in this sort of rant decades ago when I graduated because he hadn't given it. I would probably have cited his lament about Z (a formal notation, which I had by then learned) because some of the same lessons apply. New Jersey languages won for a long time, simplicity of implementation trumped correctness. Languages like C and eventually C++ dominated because while the programs were invariably wrong, the enormous cost of that could be somewhat justified by an insistence that better alternatives don't exist, even though of course better alternatives did exist.
But notice that even in C++ there are no null references. It's just that unlike Rust the C++ language inherits C's "strong typed, weakly checked" approach to types, it's trivial to make such an "impossible" thing, so although there are no null references, your references might be null anyway...
The whole point is the ergonomics, which you are ignoring whether out of ignorance or because you think you'll get away with it rhetorically. Option<&T> isn't a &T it only might be one. That's why C++ is probably getting std::optional<T&> at last in C++ 26, and why languages like C# add "non-nullable" types. Tony's mistake has terrible ergonomics.
> because people like you are going to keep insisting that somehow this was a good idea,
Woah, there cowboy, you're mischaracterising my position.
When, and where, did I "insist that this was a good idea"?
Me pointing out that the real world is filled with null references is irrelevant to whether or not I think they're a bad or good idea.
> The whole point is the ergonomics, which you are ignoring whether out of ignorance or because you think you'll get away with it rhetorically.
Which bit made you think I'm ignoring it?
The sad fact of life is that programs are written to interface to the real world, which is filled with missing values. Regardless of the programming language you use, you'll still deal with them.
Some programming languages make it easier to deal with, and some harder. Regardless, you'll still have to deal with them, and IME the best way for a program to deal with the outside world is by doing Parse, Don't Validate at the system boundaries.
Since that is, and was, my position before this conversation took place, it seems to me that you've set up a strawman (i.e. my position is something other than what I now stated) so that you could destroy it to make your argument for Rust stronger.
In reality, if you're doing Parse, Don't Validate, then its really irrelevant if your language has compile-time-checked nullability types or not.
> In reality, if you're doing Parse, Don't Validate, then its really irrelevant if your language has compile-time-checked nullability types or not.
If you never make any mistakes then there's no value in systems which prevent mistakes. But you're human, so you do make mistakes, Most of us work in larger organisations in which there are many humans and they all make mistakes.
Parse, Don't Validate is very much a pattern in which it's crucial to avoid mistakes where maybe you don't have a reference and you need to care about that. In languages where the type system won't help catch that mistake it is likely to leak into production.
The other end of this is that people moan about the expense, and that's why I brought up Rust. With the Guaranteed Niche Optimisation Rust says that Option<T> is the same size as T where there's a niche, that means not only references, including the popular string slice reference &str, but many other types.
Rust's Option<OwnedFd> is exactly the same size in RAM as the C int would be for the same purpose (typically 4 bytes on a modern system). But your code won't accidentally try to read from a non-existent file descriptor in Rust, because instead of the int being this magic value -1, there is no corresponding OwnedFd, your Option<<OwnedFd> was None.
> Parse, Don't Validate is very much a pattern in which it's crucial to avoid mistakes where maybe you don't have a reference and you need to care about that.
Wait, what?
Parse, Don't Validate is a way to make sure that invalid representations of data don't make its way into your system. Null is just one of many invalid data. Parse, Don't Validate does MORE than just prevent nulls, while the approach you are repeating only protects against nulls.
> In languages where the type system won't help catch that mistake it is likely to leak into production.
You are correct here: Languages with no enforced compilation step (Python, PHP, Ruby, Javascript) can't help even if you do do Parse, Don't Validate.
Languages with a compilation step and mandatory types (C, Go, Java, C++, etc) get the benefit of doing Parse, Don't Validate. While the benefit includes protecting against null dereferencing, it also includes protecting against other incorrect representations of the data.
In other words, if you're doing Parse, Don't Validate in Go, or C, or Java, etc, there's not much benefit, if any, to be gained from an option type. Once that $THING enters your system, it's already been transformed into the correct datatype and the compiler will ensure correctness, as far as type mismatches against null go.
As predicted you decided that since it matters, not having a reference is "invalid". But it wasn't invalid, like I said, maybe you don't have a reference. Only maybe. Either way is valid in this system. The user needs to care which is which.
In the languages you prefer (such as C), we can't distinguish this case from the case where we should always have a reference and not having one is a bug, they look the same, the machine can't help us get this right and hopefully the user carefully consults our documentation "NB this value may be NULL". Ugh.
Go is a wonderful example of a language that's grossly unsuited to this problem. Instead of "Make invalid states unrepresentable" Go chooses "Make representable states valid". Don't want a default for this type? Too bad, Go insists zero is valid and that's always your default, feel free to name this "DoNotUse_GoIsAWful" if you like, in a large system it'll get used anyway.
> At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement
So, it doesn't seem unlikely at all that other languages with type systems[0] probably just carried this behavior forward because it's how other languages worked at the time. The idea that you could have references which weren't allowed to be null probably seemed limiting, because other languages allowed it.
That this was a mistake is pretty broadly accepted at this point. It's not even a controversial statement any more.
[0] I'm excluding languages that don't have type checking at compile time (or without any compile time at all), that's a different discussion. I'm limiting the scope of my criticism to languages that (1) have a compile-time type checker but (2) opt to have that type checker allow null references to be used as if they're non-null.
Compiler designers don't have a choice. Their skill and intelligence is not evidence in either direction, because they're not the ones adding null to the language.
No, "simplicity" and "speed" are in fact both conditional on correctness. Simple wrong answers aren't useful, fast wrong answers aren't useful. There can be accuracy and you might trade lower accuracy for speed, but that's not correctness.
If the answer is "Chicago" then "A City in North America" is low accuracy but "New York" is wrong.
I’ve ran into a few edge cases where nil was a desirable feature. But on the whole I do agree with you. Those situations I mentioned could have been solved another way if nils weren’t available. It would have been more code but it might have had the side effect of that codes behaviour being more explicit. So potential win-win.
This argument feels somewhat moot though. I cannot see how Go could ever reverse their nil decision because it’s so core to how interfaces work that I suspect it would end up being a massive breaking change.
> I’ve ran into a few edge cases where nil was a desirable feature. But on the whole I do agree with you. Those situations I mentioned could have been solved another way if nils weren’t available.
In every language where pointers / references / values are not universally nullable, it's just an opt-in away, either as a wrapper type (Option/Maybe), a union type (T* | Nil), or a built-in language feature.
Either way you can pretty much always say "this may be nil", the difference is that you can't use a nullable value where a non-nullable value is expected, the language will require explicit checking (or in the worst case coercion).
It depends. In this trivial case, what do you do if you find s == nil is true? You probably panic anyway. Unless you have some specific reason to panic with a different message to the default “nil pointer dereference” then there’s no point checking it.
The point is that you should check for null, then be able to represent the variable as something that can't be null.
That way once you've checked it's not null (somewhere you're not forced to panic ideally), you can pass around the pointer & be confident you don't need to ever check it again.
> Go isn't different, it has map, that is Go implementation of a hash table.
It's a bit nitpicky, but this always annoys me. Maps/dictionaries are not hashtables. A hashtable is one of the structures you can use to implement a map. A hashtable stores arbitrary items, not key-value associations, and can be used to quickly retrieve an item knowing its hash. If you want to implement a map using a hashtable, you need to also define a type that wraps a key-value pair and handles hashing and equality by only comparing the key.
Also, maps can be implemented with other underlying data structures as well. Java's standard library even offers a built-in TreeMap, which uses a red-black tree to store the pairs instead of HashMap's hashtable.
Rust's `HashMap` and `HashSet` also do the same with the default hasher (you can plug your own deterministic hasher though). The reason for this choice, which I think also applies to Go, is to be resistant against HashDOS attacks, which can lead to hashmap lookups becoming O(n) on average. This is especially important for maps that will contain data coming from untrusted sources, like data submitted in a GET/POST request.
I do agree though that an ordered map would nicely solve the issue.