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

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

2: https://bugs.ruby-lang.org/issues/4579

3: https://wiki.openssl.org/index.php/Random_fork-safety

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.

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.

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

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.

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

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

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.

Does anyone have to, well, not really, but it'd be the nice thing to do.

I doubt whether the lady in question is as bothered by it as much as you are.

I am more upset by the brutality being inflicted on the innocents in Gaza and the fact in my country the UK, families with both parents in work still struggle to pay their bills.

Describing me as someone who is angry and needs therapy is simply attacking the messenger instead of engaging with the argument. We both have a chance to learn from this exchange.

Whether or not Lenna is bothered by this is not, to me, the issue. What is the issue? We are a field where women are underrepresented and often feel unwelcome. This kind of content and the history behind it only reinforce that. They also sends a terrible message to men that this is appropriate in technical discussions. We can make different choices that are more inclusive at zero cost. Why would we continue to tolerate this? Let’s call it out and do better.

But that aside, the rest of your argument is just the fallacy of relative privation.

That image is over 50 years old and is her immortality.

You guys need to find another outlet for your communist ideology of seeking some real or imagined social flaws as a means of venting your shrewish tendencies.

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.

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

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.

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.

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.

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.

Why not be mad at IEEE for a change? They apparently only managed to ban use of the image in April of 2024.

Note that video compression has "foreman", of the opposite gender, and the angry mob hasn't gone after that one.

Even if you think it's woke, there's good reason to respect the model's wish

> Forsén herself has also suggested that the photo should be retired. In 2019, she said she was “really proud” of the picture and she re-created the shot for Wired magazine, which called her “the patron saint of JPEGs”. But later that year, the documentary Losing Lena spearheaded the latest effort to encourage computer science to move on. “I retired from modelling a long time ago,” Forsén said on its release. “It’s time I retired from tech, too. We can make a simple change today that creates a lasting change for tomorrow. Let’s commit to losing me.”

I'm sure Naomi Wu would be up for it.

She absolutely can. And we, collectively, can choose to respect that wish by using a different test image in future. And why not? It's no real burden to make the change.

Are we back in the 60s where a father has to sign off on the daughters job application? We are talking about a woman who willingly signed up for a playboy photoshoot, had been aware of the image being used and circulated for decades with no issues.

Strawnan bs. No one advocated anything like that.

> We are talking about a woman who willingly signed up for a playboy photoshoo

Yep. And decades later asked it to not be used anymore.

You can waste as much time with long winded arguments as you want. Or you could just be decent and not use the image. Your call.

Then how are her parents even remotely relevant?

> You can waste as much time with long winded arguments as you want

Brought to you by the people who bring this argument up every time the image is used.

At the end of the day its a stolen photo, and immoral to continue to use against the express wishes of the subject, no matter how you want to justify it -- she asked, so just respect it instead of finding ways to justify being a jerk.

EDIT: Why the downvotes? I'm genuinely curious. I see the word thrown around a lot but I can't get a grasp on what it means

This is your definition. I doubt you will find any agreement on what "woke" means, because right-wingers use it to refer to anything and everything that they dislike.

If this is how you behave I think most of us would far prefer to have Petee as a coworker than you. If you’re having a lot of conflicts with your colleagues about this, the problem might not lie with your colleagues…

That's not an accurate reading of the Petee's post.

> I think most of us would far prefer to have Petee as a coworker than you.

Speak for yourself.

You can happily go back in your bubble and pretend everyone in the world is ok with your level of mediocrity.

At some point, I’ll probably watch the “Losing Lena” documentary. But I wasted a few minutes to determine the comment was not related to the story

Stop putting politics in everything you touch. Once upon a time, before being an activist poseur was in vogue, open source was all about code, not idiotic posturing for terminally online people.

Oh, the beautiful, inclusive movement of brigading and "with us or against us" black-and-white thinking. Very tolerant indeed.

So much for a project that claims to be apolitical

It seems to be a space designed to avoid anything which the typical 90s white male geek type wouldn't perceive as political. Which in itself is a highly political goal.

"Using Lenna is on-brand for SerenityOS" is not meant as a compliment.

That's an interesting interpretation. Considering that the project has several trans developers and even a handful of (biological) women I'm going to suggest another interpretation: They're not trying to be a safe haven for bigots, they just don't want the endless CoC/pronouns bikeshedding that plagues too many projects these days.

If a project welcomes diverse contributors and doesn't foster an environment that alienates them (which, in part, you can evidence by their continued presence and contributions), that seems way more worth its weight than academic quibbles about the language used in documentation.

Are cis and trans women contributors speaking up about any problems? If not, then is the issue really important? I'd rather see a project not actively alienate cis and trans women developers - a higher bar to actively meet than you'd think - than to be religiously attentive to "microaggressions" and the like while doing very little to actually accommodate them as contributors.

This by the way is exactly why I approve of any policies that keep people like you out of projects. If you can't learn to get along with people with different beliefs then don't expect them to welcome you.

This conversation is boring, you're not getting anything out of it, and I'm not getting anything out of it. How about we leave it here?

Regardless, I forgive you.

I hate that term "virtue signaling". I most often see it when people simply don't understand the opinions of the other person. "It's impossible that you disagree with me, so I will accuse you of holding inauthentic positions".

EDIT: Someone else in the thread said this is from 2021 but I can’t tell since neither the URL nor the page itself give a date. I’ll never understand people hiding/not showing the publish date on blog posts.

[0] https://news.ycombinator.com/item?id=39885977

The Git commits in the article indicate the date.