std::unordered_map and std::unordered_set

[Avi Drissman]

As per base/containers/README.md:

Note that this advice never suggests the use of std::unordered_map and std::unordered_set. These containers provides similar features to the Abseil flat hash containers but with worse performance. They should only be used if absolutely required for compatibility with third-party code.

Is this something we want to enforce? These "only [to] be used if absolutely required" classes have pretty wide usage.

Avi

[Sylvain Defresne]

I am in favor of enforcing our recommendations automatically. This is better than relying on all reviewers catching those usage, and pointing to the correct documentation.

Though: one thing that I noticed with a recent change is that by default absl::flat_hash_set::find() is not heterogeneous because the default hash is not considered transparent. This can introduce problem if the key is raw_ptr<T> and the code is calling find() with a dangling pointer (this caused failures in https://chromium-review.googlesource.com/c/chromium/src/+/7493299, and I had to specify a different hash).

-- Sylvain

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CACWgwAZnHVZDvQPYrxCaGEOvYvVe3oj5OJ%3DLwxDhoQFK9YHoAA%40mail.gmail.com.

[John Admanski]

I think specifically in the case of the unordered_* containers you could have some kind of lint or presubmit that warns you against using them.

That said, I think in general it's not really feasible to try and enforce the recommendations of that document, as selecting the appropriate container for a task is a non-trivial thing and the document is more aiming to provide good defaults and advice rather than a set of hard rules. Even the paragraph in question here was really just intended to highlight that unless you have a very specific reason why you need those containers in particular, they're probably not a good choice. It wasn't really intended to rise to the level of a ban, if that was the intent then it really would be better placed in the style guide itself.

(I'm not a decider or authoritative on this, I'm just chiming in because I was the author of that particular change)

-- John

[Alex Cooper]

FWIW, the guidance *not* to use std::unordered_map and std::unordered_set was only added (silently, unless I missed an email) about a year ago by this CL. Here's that file from prior to that commit, which while it doesn't ban, does discourage but calls out exceptions where it's fine to use them.

For what it's worth, I feel like I only noticed the change to recommend the absl:: types because I went to double check my memory of something on the table, and I don't remember any broad announcement preferring this type or as like a change to the style/recommendation even on this list.

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAJauWCHBoJ4Ny65-ZYRgkzB7Zp0m6-6z5HyVK48hNHqhbcqVyg%40mail.gmail.com.

[Alexei Svitkine]

If we wanted a presubmit to flag uses of those, here's the place where we have similar checks:

https://source.chromium.org/chromium/chromium/src/+/main:PRESUBMIT.py;drc=7060849d7ef815b99002bc8548ec5027e8d478bd;l=495

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAGOLbz1OyssG75s%2B0hLDaUjoq-PPMP5oFKNP6h39C1qeDpYSeQ%40mail.gmail.com.

[Victor Vianna]

Maybe increasing the scope of the discussion but: the same problem occurs with other containers mentioned in that doc.

"Chromium code should always use base::circular_deque or base::queue in preference to std::deque or std::queue due to memory usage and platform variation." (docs)

There are 213 usages of std::deque outside of third_party (cs) and 400 of std::queue (cs).

"std::stack is like std::queue in that it is a wrapper around an underlying container. The default container is std::deque so everything from the deque section applies. Chromium provides base/containers/stack.h which defines base::stack that should be used in preference to std::stack." (docs)

There are 68 usages of std::stack outside of third_party (cs).

None of the above seems enforced by presubmit, since I could easily upload this CL.

[Victor Vianna]

> That said, I think in general it's not really feasible to try and enforce the recommendations of that document, as selecting the appropriate container for a task is a non-trivial thing and the document is more aiming to provide good defaults and advice rather than a set of hard rules

We can make these presubmit warnings instead of errors. Should we start with that?

https://source.chromium.org/chromium/chromium/src/+/main:PRESUBMIT.py;l=133;drc=fbffe55c2d7d156ce726a5850381664e33c1232e

[Victor Vianna]

Looks like yuje@ started some work on this crbug.com/473916362, I stumbled upon one of their CLs today

[Alex Cooper]

I had a similar change a year ago or so that was large because of the switch to the absl types, and @Daniel Cheng I think had some theories about the increases, but also said we probably shouldn't be too concerned.

On Thu, Feb 5, 2026 at 12:02 PM Jeffrey Yu <yu...@google.com> wrote:

Yes, this is a cleanup effort I started on recently, having noticed the guidance from the Chromium Containers guide.

For instances of std::unordered_set (and instances of std::set that don't require iteration order), I've been replacing with the following priority:

1. If the value is an enum, use base::EnumSet
2. If all values can be determined at compile time, use base::fixed_flat_set
3. If values are written once and the set is used only for lookups, use base::flat_set
4. Use absl::flat_hash_set, unless pointer stability is required. 
5. If pointer stability is required for the value, use absl::flat_hash_set<key, std::unique_ptr<value>>, or absl::node_hash_set<key, value>.

Some discussion:

I noticed that absl::flat_hash_map/set usually increases binary/APK size over the STL container of the equivalent type. I've started mostly with migrating sets first, and one type at a time (std::string, int) so that reduces the growth, but I notice this more on swapping maps, as swapping out a std::unordered_map with absl::flat_hash_map of the same type generally adds 0.5-1.5KiB to the APK size. There only a few hundred instances of std::unordered_map, so a total migration would result in less than 1 MiB APK size increase, but an FYI.

Updating headers to add the Abseil includes on widely-used headers can result in compile size increases that fail the CQ checks, for example in CLs like: https://crrev.com/c/7542821 and https://crrev.com/c/7546326. Using forward declarations to avoid adding includes in headers is tricky because of the optional template params and also needing to forward declare additional classes like the hasher and allocator. In cases like this, should I hold off on sending these CLs or just add a Gerritt footer to ignore the check as an unavoidable cost? 

[Daniel Cheng]

I did a test bulk migration of all unordered maps in //content as an experiment 3+ years ago; I don't recall that test CL failing any binary-size runs back then.

It's possible things have shifted somewhat, but I don't think it'd be that drastic.

This is in contrast to an absl::btree_map experiment, which resulted in something like a 1MB binary size gain for replacing std::map in //content. That CL was https://chromium-review.googlesource.com/c/chromium/src/+/3965496.

Daniel

[Jeffrey Yu]

Yes, this is a cleanup effort I started on recently, having noticed the guidance from the Chromium Containers guide.

For instances of std::unordered_set (and instances of std::set that don't require iteration order), I've been replacing with the following priority:

1. If the value is an enum, use base::EnumSet
2. If all values can be determined at compile time, use base::fixed_flat_set
3. If values are written once and the set is used only for lookups, use base::flat_set
4. Use absl::flat_hash_set, unless pointer stability is required. 
5. If pointer stability is required for the value, use absl::flat_hash_set<key, std::unique_ptr<value>>, or absl::node_hash_set<key, value>.

Some discussion:

I noticed that absl::flat_hash_map/set usually increases binary/APK size over the STL container of the equivalent type. I've started mostly with migrating sets first, and one type at a time (std::string, int) so that reduces the growth, but I notice this more on swapping maps, as swapping out a std::unordered_map with absl::flat_hash_map of the same type generally adds 0.5-1.5KiB to the APK size. There only a few hundred instances of std::unordered_map, so a total migration would result in less than 1 MiB APK size increase, but an FYI.

Updating headers to add the Abseil includes on widely-used headers can result in compile size increases that fail the CQ checks, for example in CLs like: https://crrev.com/c/7542821 and https://crrev.com/c/7546326. Using forward declarations to avoid adding includes in headers is tricky because of the optional template params and also needing to forward declare additional classes like the hasher and allocator. In cases like this, should I hold off on sending these CLs or just add a Gerritt footer to ignore the check as an unavoidable cost? 

On Wed, Feb 4, 2026 at 5:37 AM Victor Vianna <victor...@google.com> wrote:

[Nico Weber]

Do you have numbers that show that this migration has measurable benefits (perf, memory use, what have you)? I'd imagine that "most" maps are small.

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAD4jpnNEv6Pnw%2B3aN1wRTUbr78R2aXEO_hJwfg%3D9L5RXD6ObRw%40mail.gmail.com.

[Jeffrey Yu]

The use of the Swiss tables was tested and benchmarked pretty extensively in Google, through the use of specifically designed microbenchmark tests and fleet-wide profiling:

• https://docs.google.com/presentation/d/1qMK7ALutHJ9MYqswesQMXv0IrgySRTqCqFIBHv9ewQ8/
• go/swisstable-performance
• go/hash-benchmarks-colab 

The conclusion was "flat_hash_map and flat_hash_set outperform all other unordered containers in terms of CPU and memory usage in almost all real-world applications.", in addition to other benefits like using 30% less memory (for KV <int64, int64> and being able to support heterogenous lookup, allowing use of string_view to look up string keys.

For Chrome specifically, I haven't done any benchmarking on the changes, as I see it more as a cleanup and updating the codebase to match general best practices and guidelines, although one reviewer did benchmark to validate a change to v8 and verified the performance improvement: https://crrev.com/c/7405248 

[Daniel Cheng]

In Chrome specifically, tThe Catan team has done some studies using `base::VariantMap` in strategic places. base::VariantMap compares std::map and absl::flat_hash_map, so not quite apples to apples, but it still showed memory improvements without regressing speed.

Overall, the absl unordered containers are strictly better than the STL ones and there are quite a few benchmarks demonstrating this already as noted in Jeffrey's reply.

Daniel

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAD4jpnO1byxdjBW_PtSnbLpyRcrg8xvCopWaaG9eHMqvikigTw%40mail.gmail.com.

[Jeffrey Yu]

Since the number of CLs is getting quite large, I'm following a suggestion to use the LSC process to get explicit review and approval for this change: go/chromium-unordered-lsc

[Nico Weber]

Sure, I've seen those studies. But if most maps are small in practice, it might still not be worth doing all the work of migrating all the maps we have, right?

[Jeffrey Yu]

There's roughly about ~1,300 instances of std::unordered_map/set in the chromium codebase. With an LSC and global approval, I think a full migration could reasonably be done within a few weeks to a quarter, and as a cleanup side project by a volunteer (me). Since the Abseil maps are almost always better, and the worse-case scenario is equivalent performance, an all-at-once migration be better than doing nothing and cost less bandwidth than benchmarking and measuring individual usage points?

[Daniel Cheng]

True, but it's not a lot of work (IMO) to migrate std::unordered_{set,map} to one of the abseil variants. The most trivial migration would simply be to convert everything into `absl::node_hash_*`. A bit more work (but for more benefits) is to migrate everything that doesn't need pointer stability to `absl::flat_hash_*`, which is probably 90%+ of unordered associative containers.

There are other benefits, like network effects to make it easier for new code to follow the best practices.

It's also worth noting that Chrome isn't particularly unique for "most maps are small"; the same is true of Google's code. So this isn't really a reason not to do this work.

Something that /would/ be nice is migrating `std::map` instances as well, but that is more work and would be an entirely separate discussion.

Daniel

[Joe Mason]

Yikes, this thread's moved along since I bookmarked it to reply to...

Based on the results of the VariantMap experiment that Catan did last year, we recommend making absl::flat_hash_map / absl::flat_hash_set the default choice (as containers/README.md recommends now), but NOT spending any effort to migrate existing maps unless they're known to have performance issues.

We've already migrated some of the highest-contention maps (mojo::ReceiverSetState, BinderMapWithContext, SubprocessMetricsProvider) as part of that experiment. We have a short list of other targets that we ran out of time to include, but since the experiment didn't show clear performance gains we're not going to pursue that. Very large maps might be worth converting, for the memory savings, but in most cases there are better improvement targets to spend time on.

(More details in this thread: https://groups.google.com/a/chromium.org/d/msgid/cxx/CAEYHnr2yhaDvtfujFjwSwqKsDu569y3siU%3D2AHoggjrawhDSLQ%40mail.gmail.com?utm_medium=email&utm_source=footer)

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAF3XrKobEbDjR0Ms5Csds6uXF34ZWjrt4sG0X_D81oZxBUbTgg%40mail.gmail.com.