Malloc broke Serenity's JPGLoader, or: how to win the lottery (2021)(sin-ack.github.io)
sin-ack.github.io
Malloc broke Serenity's JPGLoader, or: how to win the lottery (2021)
https://sin-ack.github.io/posts/jpg-loader-bork/
201 comments
Many implementations these days also go the opposite way, guaranteeing that hash tables always iterate in insertion order.
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.
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.
JavaScript is probably the most notable example of that. It used to not have a guaranteed iteration order, but browsers implemented it in such a way that the iteration order was the insertion order, and then that eventually got standardized because websites started depending on it.
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 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/).
Javascript is kinda weird as the numerical keys have their own special ordering.
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.
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.
Perl also changed its behavior, but in the other direction: a random seed was used per interpreter start after 5.18.
https://www.perlmonks.org/?node_id=1005122
https://www.perlmonks.org/?node_id=1005122
That's actually the first python transition I mentioned, per-process hash randomisation had the effect of making map iteration non-deterministic. I believe in both cases this was in response to the hashdos concern / attacks.
Ah, sorry I didn't read that closely.
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
2: https://bugs.ruby-lang.org/issues/4579
3: https://wiki.openssl.org/index.php/Random_fork-safety
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
2: https://bugs.ruby-lang.org/issues/4579
3: https://wiki.openssl.org/index.php/Random_fork-safety
I remember that it actually broke a critical algorithm I was testing at the time. Fun times.
Rust has HashMap with random order and BTreeMap which is ordered by the key. Additionally one can use IndexMap crate if wanting to keep the order of insertion in the map. The issue with the latter is how much memory it can waste in the worst cases. A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string.
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.
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.
> A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string.
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).
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).
We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually.
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.
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.
> We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually.
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.
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.
It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&editio...
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.
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.
Indexmap does reuse hashbrown. It consists of a hashtable containing `usize` indexes into a `Vec` which in turn contains the actual entries (keys and values), along with a cached hash for the key. In the end the overhead should only be that index and the hash.
PHP too.
Its arrays, which also behave like hash maps, respect insertion order.
https://www.php.net/manual/en/language.types.array.php
Its arrays, which also behave like hash maps, respect insertion order.
https://www.php.net/manual/en/language.types.array.php
Python also, similar story.
tucnak(2)
> Often if I think I need an unordered map it turns out to be wrong for some subtle reason.
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.
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 a rule I’m happy to sacrifice cycles for determinism, because non-deterministic bugs are disproportionately wasteful of developer time.
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.
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.
I agree with sibling commenter. If I need determinism, I choose the deterministic container. If I don’t know whether I need determinism or not, I don’t understand the problem well enough yet.
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.
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.
Picking a tool without thinking about it is a surefire way to get runtime bugs.
> I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map.
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).
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).
You can always use a library or roll your own.
I don't understand this reasoning. If there is a subtle reason wouldn't you take the time to think through it carefully? Are you in such a rush that you don't have time to decide the required data structure (ordered vs unordered)? Or do you have insufficient control of downstream software that you fear for unknown bugs caused by this? And since insertion order is often related to some other ordering in the input, you are comfortable that downstream software completely rely on this ordering even when it's undocumented? Genuinely curious because this kind of reasoning is alien to me.
Isn't that just a different data structure? How do you preserve insertion order in a hash map?
> How do you preserve insertion order in a hash map?
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.
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.
Ah yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)
Kind of? It usually means you've compromised the data structure somehow but occasionally it shows up incidentally.
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.
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.
If your hash map uses open addressing, instead of a sparse array of pair<key, value>, you can have a vector<pair<key,value>> and a sparse array holding offsets into the vector. Depending on the sizes of keys, values, and offsets, as well as the average loading factor, this might or might not save space.
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).
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).
[deleted]
At my previous company my boss made me angry after I already handed in my two weeks notice so I stopped caring, and I wrote code that depended on the insertion order into a map. Of course I didn't document it. Have fun guys.
Your ex-boss made you angry and you left code that will make the life more difficult for whom? Only your ex-boss or more people? Who gets punished for what you perceive as one person's mistake?
It was a company where 80% of employees were interns, I was one of them, the other 20% were people who couldn't get hired elsewhere, with just a handful of those who actually knew what they were doing. There was no leadership.
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".
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".
We can expect a lot from you, but I guess you’re always free to let people down.
If I counted each time people let down me I'd definitely broaden my vocabulary of huge numbers.
Vengeful behavior can be gratifying in the short term, but in the long term I've never felt good about it.
Maybe you'll find the same.
Maybe you'll find the same.
> This is one of the reasons why many hashtable implementations introduce a random component into the algorithm.
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.
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.
This seems like a case where a little more debugging would have saved time over brute force bisection. The logging to print component orders had to be done eventually anyway.
Kudos on the debugging but also on that commit message. It managed to condense the cause and the fix into a couple of paragraphs.
For whatever its worth, if we wait long enough C++ will include the equivalent of `malloc_good_size`. https://github.com/cplusplus/papers/issues/18
Needs [2021] in title
This isn’t Gunnar’s fault. The problem was whomever stored ordered data in a hash file.
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.)
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.)
> This isn’t Gunnar’s fault. The problem was whomever stored ordered data in a hash file.
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. :^)
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. :^)
If the smiley face and the commit message's tone didn't make it clear that it's
a joke, TFA explicitly ends with this:
> 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.
> 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.
As long as LLMs are trained on code that has bugs, they'll suggest code that has bugs.
Indeed. And contrary to the title, the fault isn't malloc()'s either.
> As a result, during the 1000 commits I ended up bisecting for, I had to build SerenityOS from scratch about 4-5 times on a 2011 laptop with Sandy Bridge Mobile. While this isn’t the fault of the project, I’m still mad.
I think SerenityOS has some folks that help each other out with resources and PCs for testing purposes.
I think SerenityOS has some folks that help each other out with resources and PCs for testing purposes.
[deleted]
> I had to build SerenityOS from scratch about 4-5 times on a 2011 laptop with Sandy Bridge Mobile.
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
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
Maybe in terms of time, but not in terms of actual performance. CPUs haven’t changed that much since 2011 (relatively speaking), but between Windows 3.1 and Vista we got x64 and multicore CPUs everywhere became the norm.
> CPUs haven’t changed that much since 2011 (relatively speaking)
Perhaps not relatively speaking, but my 2021 CPU is 10x faster than my 2015 CPU on workload which parallelise (which compiling generally does).
Perhaps not relatively speaking, but my 2021 CPU is 10x faster than my 2015 CPU on workload which parallelise (which compiling generally does).
Good, let's look at hard numbers!
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.
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.
An intel chip from 2011: https://ark.intel.com/content/www/us/en/ark/products/52210/i...
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?
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?
Using max memory supported in this case seems disingenuous, the truth is that the average computer in 2011 had 8GBs of ram, and the average computer in 2024 has 16GBs of ram, 32 if we're being generous.
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
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
Plus probably like 2x IPC
While I agree that the increase in speed per socket was greater in the 15 years between 1992 and 2007 than in the following 15 years from 2007 to 2022, your comparison for the cache size is not correct.
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).
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).
Thanks, this is good context; I had no idea that the L2 cache used to be on the motherboard.
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.
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.
Clock speed is irrelevant as a comparison point between highly out of order micro-architectures with execution ports approaching dozen by now.
For the throughput of a computer the clock frequency is at least as important as the number of cores, the IPC (instructions per clock cycle) and the amount of work done by one instruction.
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.
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.
Come on. We're not comparing 2.1GHz and 2.4GHz here. We're comparing 66MHz and 3500MHz. That difference is significant regardless of execution ports and other micro-architectural details.
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.
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.
[deleted]
Nice comparison. Indeed, the developer's CPU is about 13 years old. Vista was released internationally in early 2007, so a 13 year old CPU at release would've been released in 1994, about a year after the original Pentium was released. But many were still using their trusty 486 DX2-66 CPUs.
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)
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)
My main desktop for the last year has been a 2011 Lenovo i5 running Windows 11 on dual monitors. Visual Studio runs great on it. Photoshop (the on-system AI tools can be a tiny bit sluggish). I probably have 200 tabs open in Chrome. Slack, WhatsApp. Three different browsers for testing. CapCut could be a little quicker when editing 4K, but it gets by just fine with complex 2K projects. The only thing I've hit the buffers with a little is complicated After Effects projects. It no likey those.
I do need to upgrade, but damn, for a system I basically saved from a Dumpster, it is decent.
I do need to upgrade, but damn, for a system I basically saved from a Dumpster, it is decent.
> Visual Studio runs great on it.
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.
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.
I got Deja Vu upon seeing "Alien Lenna" and sure enough... I've seen and commented on this before: https://news.ycombinator.com/item?id=27374942 (2021)
[deleted]
riedel(4)
TL;DR:
> Someone used a HashTable to store objects that should be ordered, then iterated over it using the basic HashTable iterator
> Someone used a HashTable to store objects that should be ordered, then iterated over it using the basic HashTable iterator
[deleted]
Zardoz84(5)
avidphantasm(2)
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.