Malloc broke Serenity's JPGLoader, or: how to win the lottery (2021)
sin-ack.github.io
sin-ack.github.io
It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.
I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map. Often if I think I need an unordered map it turns out to be wrong for some subtle reason.
For general purpose hash maps in standard libraries, I think you ought to either randomize the iteration order so that it's different every time, or guarantee an iteration order. Leaving it unspecified but predictable in practice is a recipe to fall victim to Hyrum's Law (https://www.hyrumslaw.com/).
For immutable data that can fit to the CPU cache, utilizing a sorted vector can be many times faster and uses less memory compared to the maps.
Deserialized non-trivial objects are generally larger than the original serialised value.
IndexMap should not generally be significantly larger than a HashMap though, unless the key and value are very small (sub-word).
Deserializing into a defined struct does not waste as much memory as Value does. Especially due to the recursive nature of the Map variant, which can hold another Map.
That is strange and I’d assume the maintainers would be interested in the information.
By my reckoning HashMap would be consuming about capacity * 10/9 * (8 + sizeof key + sizeof value) while indexmap should be consuming capacity * 10/9 * 8 + capacity * (8 + sizeof key + sizeof value).
Unless indexmap reuses hashbrown directly in which case you’d get something like capacity * 10/9 (16 + sizeof key) + capacity * sizeof value.
Now, if you have an enum such as `serde_json::Value` which is kind of recursive with its `Map` variant, and you have a ton of dynamic JSON parsing in your code, these numbers really add up. And serde_json uses `BTreeMap` (I was wrong in my previous message) by default which is even smaller than `HashMap`.
The learning here is to avoid dynamic JSON parsing if you can. And if needing it, but not caring the insertion order, avoid the `preserve_order` feature flag.
The other learning here is that there is no map structure that fits to all purposes. They all have their pros and cons and you should choose the right one for the problem.
Python is probably the better known one, as it went through "arbitrary but deterministic" (before 3.3) to "wilfully non-deterministic" (from 3.3 to 3.6) to "insertion ordered" from 3.6, the latter of which was initially an implementation detail of improving the hashmap but was then made into the language spec starting 3.7.
One minor nit (which the Perl press releases also mess up): the randomisation is per-interpreter, not per-process.
That's not a pedantic distinction. I've seen a couple of bugs/bad behaviors caused by forking servers forgetting to call srand(3)/re-randomize the hash seed after fork(2) and then relying on more randomness than they actually have. Suddenly (for example) hashing rate limiters or bloom filters all operate in near-lockstep, which can cause significant issues at high volumes.
Forking has also caused randomness-related issues (though not necessarily specifically re: hashing) for Rust[1] and Ruby[2], and probably many other platforms. OpenSSL seems to sidestep[3] the issue by using the PID as part of its salt internally.
1: https://github.com/rust-lang/rust/issues/16799
Its arrays, which also behave like hash maps, respect insertion order.
For example, if you append the keys/values to an arena instead of inline in the hash you get a different set of performance tradeoffs. However insertion order is then available by walking the arena.
Appending to an arena in the background is a decent choice for variably sized data, as opposed to heap allocating everything one at a time. That probably has to store the size of each item, hence a forward iterator over the arena at zero cost. Minor quibbles around deleting and tombstones notwithstanding.
You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely critical in practice. It can be made more efficient if the hash map doesn’t need to support deletion.
Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.
If your hash map uses chaining, then you weave an extra doubly linked list through your entries (see OpenJDK's OrderedHashMap, for a pretty readable open source example).
Huh. This hasn’t been my experience. I very rarely need maps to be ordered. In recent years, the only case I can remember is when serializing to TOML and wanting the keys to be written in a specific order. There have been the occasional other case where insertion order is what I wanted, but I almost never need ordering in map keys.
> I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map.
I’m the opposite, I prefer to be given a choice so I can make the tradeoffs when I want to or need to. If you don’t want to choose, you are free to always choose ordered map, but even if ordered map is the default, there should always be a choice to use unordered map. It’s been very rare that I started with the wrong one and had to change.
When I write python or JavaScript I typically don’t care and will just use whatever is the default, but when I write C++, I very much do care and the vast majority of cases use phmap’s flat_hash_map, which has superior space and speed over std::map and std::unordered_map. For ordered maps I use tsl::ordered_map but that still comes at a cost over flat_hash_map and its unordered variants.
As much as possible I want my code to give the same results from one run to the next.
Some sources of non-determinism are unavoidable, but e.g. unordered maps and unstable sorts both have deterministic alternatives that are almost as performant.
Maps are such a common data structure that eliminating unordered maps has a big impact on whole program reproducibility.
Regarding wanting your code to produce the same results from one run to the next, so do I, and I get this by using appropriate data structures. If iterating a map is producing non-deterministic results then I’m doing something wrong, because that means that the order of iteration matters. It’s just that it’s not that common in my code that this is the case. Where I need specific order, more often than not, a list (array/vector) has been a more appropriate structure. Sometimes an ordered map is indeed the correct structure, but ordered map doesn’t by itself give you the determinism you desire, you also need to ensure that the insertion order is itself deterministic and consistent between runs, and that the order is maintained during processing/data manipulation between insertion time and iteration time.
Typically a better approach, in my opinion, is to process the data in whatever form makes sense (eg unordered) and then when you reach a point where order matters, that’s where you sort by the order you require, rather than trying to make sure that you insert in the correct order and don’t lose that order somewhere in the process. Of course it’s valid to think about the steps and say “if I use an ordered map, this set of operations maintains the order, so I can omit the sorting” and that’s a good optimisation, but that should, in my opinion, be a conscious decision based on analysis if the problem, your solution, and your requirements.
I agree that I handled the situation unprofessionally, but I feel excused, considering the circumstances. Whether I'd do it again depends on who'd need to clear up this mess. If it's people I care about because I got to know them - I'd keep my cool. But if it's some abstract "organization" where I was just a random cogwheel with zero connection to other cogwheels, then you can't expect me to care about anything that doesn't include "me".
Maybe you'll find the same.
Well only if you happen to insert your elements in order. If you want a proper ordered map like `std::map` in C++ or `BTreeMap` in Rust then you are out of luck (at least in Python and Javascript).
If the random component is a seed that can be forced/stored/logged/reproduced then it's okay. Otherwise it's actually an horrible idea because it complicates debugging other issues.
Randomness is the enemy, not the friend.
> It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.
Yeah, 20 years ago this was a thing to attack Java webservers: crafting URL with parameters so that they'd all end up in the same bucket. Big denial-of-service one. IIRC PHP webservers suffered from the exact same security issue.
It was fixed by implementing a hash table with a seed and that seed was, of course, under the control of the dev because...
Randomness is the enemy, not the friend.
I have been in this business for decades and I have run into the situation where changing the shape of memory uncovers bugs. Every time it causes many hours and days of debugging.
If programming weren’t hard, they wouldn’t need us to do it. (I’m not sure how much longer that phrase will hold up under large language models.)
Yes. Even if it were, I don't think it needs to be mentioned in the commit message. Gunnar improved something, which triggered problems with old broken code. For his efforts he gets:
> Gunnar, I like you, but please don't make me go through this again. :^)
> Gunnar in particular was the one who uncovered this bug, and despite my satirical jab in the commit message helped uncover this very interesting bug, so he’s the one who made this post possible.
Gunnar is also credited right in the same commit message for help:
> Credits to Andrew Kaster, bgianf, CxByte and Gunnar for the debugging help.
And judging from how the author of the actually broken code in question is (reasonably) not investigated or publicized, it seems quite obvious to me that the article's author is not trying to play the blame game.
I think SerenityOS has some folks that help each other out with resources and PCs for testing purposes.
I mean, this is like trying to do Windows Vista development with a computer released in the timeframe between Windows 3.1 and Windows 95
Perhaps not relatively speaking, but my 2021 CPU is 10x faster than my 2015 CPU on workload which parallelise (which compiling generally does).
Windows 3.1 came out in 1992. One of the highlights in the CPU world in 1992 was the launch of the Intel DX2 (https://en.wikipedia.org/wiki/Intel_DX2). It used an 800nm process node, ran at up to 66MHz, had 8k of cache, and was usually coupled with either 4 or 8 MB of RAM.
Windows Vista came out in 2007. That's the year Intel released their Core 2 Quad (https://en.wikipedia.org/wiki/Intel_Core_2). It was a quad core, manufactured on a 45nm process node, running at up to 3.5GHz, with 256k of L1 cache and 8M of L2 cache. In this era, computers often had around 2 GB of RAM.
So we're talking 4x the number of cores, 50x the clock speed, 256x the RAM, 1024x the cache. Benchmarks comparing the two are extremely difficult to find, because they're from completely different eras of computing; but I think it's pretty safe to say that your 10x is completely insignificant in comparison.
I'm not saying that the Core 2 Quad is 50x more powerful because it has 50x the Hz, or that the Core 2 Quad is 200x more powerful because it has 4x the cores @ 50x the Hz, or that it's 1024x more powerful because it has 1024x the cache, or anything like that. I'm trying to illustrate the extreme evolution of the microprocessor from the early 90s to the late '00s.
Were it not for the fact that increasing the clock frequency increases the power consumption more than the throughput, clock frequency would have been the most important factor, because increasing any of the other factors increases the throughput by less than their increment, due to various inefficiencies or because not all applications can benefit from those improvements.
For the computer user only the total throughput matters, not how it is achieved.
A motherboard with a 486 CPU of 1992 would have had an L2 cache memory with a size between 64 kB and 256 kB, made with discrete SRAM chips.
During the year 2000, the second generations of Intel Pentium III and of AMD Athlon were the first to have an L2 cache memory integrated in the CPU. When first launched in 1999, both Pentium III and Athlon still had external L2 cache memories.
External L2 cache memories had been the norm in all motherboards except in the cheapest models, starting already with 80386DX, before 1990.
So the L2 cache memory of 2007 was only around 64 times the size of that of 1992.
The increase in IPC (instructions per clock cycle) was huge between 1985 and 1995, i.e. 80386 => 80486 => Pentium => Pentium Pro. After that, the increase in IPC has been continuous until the AMD Zen 5 and Intel Lunar Lake of 2024, but at a much slower pace.
From 1995 to 2003, there was a huge increase in clock frequency, from 0.2 GHz to 3.2 GHz, i.e. 16 times, while in the next 20 years the clock speed has increased less than 2 times.
From 2005 (AMD dual core) until today the greatest speed increases have been provided by either increasing the number of cores per socket or the width of the SIMD execution units. For consumer CPUs (i.e. non-server) Intel has provided a sequence of throughput doublings in the sequence Core 2 (double SIMD throughput vs. previous Athlon X2) => Nehalem (4 cores/socket) => Sandy Bridge (double SIMD throughput) => Haswell (double SIMD throughput), but after that the following throughput doublings in consumer CPUs have all been provided by AMD, with the increase of the number of cores per socket to 8 then 16, and now with the double width of the SIMD units in the desktop variant of Zen 5, i.e. Granite Ridge.
So the increase in throughput per socket (in personal computers) between 2004 and 2024 has been of 256 times, due to increases of core count or SIMD width. For comparison with this 20-year improvement, the increase in clock frequency from 1985 to 2003, during 18 years, had been from 16 MHz to 3.2 GHz, i.e. of 200 times. I do not know the exact increase in IPC between 1985 and 2003, as that would require the choice of a benchmark program, to be run both on an 80386 and on a Pentium 4 or on an Opteron, but it might have been around 20 times. The increase in IPC from 2003 to 2024 might be of at most 6 to 8 times, when accepting an increase of 10% to 20% every 2 to 3 years. So overall, with a doubling of the clock frequency from 2004 to 2024, there would be an increase in the throughput per socket for personal (non-server) computers of around 4000 times both during the 19 years from 1985 to 2004 and during the last 20 years.
This corresponds on average to a little more than a doubling of the throughput per socket (in personal computers) every 2 years, during the last 40 years (i.e. from an Intel 80386 @ 16 MHz to an AMD 9950X).
And yeah, my comparison is completely missing IPC, but that's difficult to quantify... ideally we'd have something like Geekbench results from both, but I struggled to find comparable benchmarks.
Equivalent chip today: https://ark.intel.com/content/www/us/en/ark/products/236784/...
4 cores/4 threads up to 14 cores/20 threads. Max memory supported 32GB up to 192GB. 3.7Ghz turbo up to 5Ghz. 6MB cache up to 24MB+11.5MB L2. Memory bandwidth 21GB/sec up to 76GB/sec. AVX2. Faster GPU.
It’s not so dramatic but it’s not nothing; 5x the threads, nearly 4x memory bandwidth, 1/3rd higher clock speed, 4x the cache, much higher bus bandwidth I think ~5x?
It doesn't refute your claim that modern CPUs are drastically faster than 12 years ago, but there has definitely been quite a regression in how much we've been gaining the past years
Quite impressive that a CPU from 13 years ago can still work on modern projects today when the same wasn't quite as true back then. And a CPU released today will (hopefully) be able to work satisfactorily beyond 2037. 8)
I do need to upgrade, but damn, for a system I basically saved from a Dumpster, it is decent.
I'd really like to see a video of VS running great on such a machine. My experience with it is that it doesn't run great at all on a top-of-the-line 2022 laptop with laggy interactions left and right. For the kind of software VS is, literally any UI lag is completely unacceptable.
> Someone used a HashTable to store objects that should be ordered, then iterated over it using the basic HashTable iterator