--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CABiGVV9hnyt6fmf1sDtW325d_toeRXpCajzPs9yjYPa_H9kB9Q%40mail.gmail.com.
Have you also looked at Blink's types? I think there's an open question of whether it makes sense to move some of them in base/. (apologies if I missed threads discussing this)
This came to my mind because (assuming I read the code correctly) WTF::HashMap uses open addressing, so it doesn't have to do allocations for most insertions. I'd expect WTF::HashMap to do better than std::map for elements that are efficiently copyable / moveable. WTF::HashMap is still not very cache-friendly*, but then again, neither is the red-black tree behind std::map.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAP_mGKrF5qJ1L2pCpWc5msN432NOZk9LX5Ek-qVPOV5O7u%3D%2B%3DA%40mail.gmail.com.
Histogram: Map.Size recorded 169828 samples, mean = 1.2 (flags = 0x1)
0 ------------------------------------------------------------------------O (110025 = 64.8%)
1 ----------O (15713 = 9.3%) {64.8%}
2 -----------------O (25289 = 14.9%) {74.0%}
3 -------O (10520 = 6.2%) {88.9%}
4 -O (1866 = 1.1%) {95.1%}
5 O (1462 = 0.9%) {96.2%}
7 -O (2424 = 1.4%) {97.1%}
9 O (597 = 0.4%) {98.5%}
12 O (508 = 0.3%) {98.9%}
16 O (869 = 0.5%) {99.2%}
21 O (118 = 0.1%) {99.7%}
28 O (132 = 0.1%) {99.7%}
<long tail omitted>
I just would like to chime in very briefly on this discussion to talk about base::flat_map. Recently a CL landed on base::values.h, changing the storage type for base::DictionaryValue from std::map (I think) to base::flat_map. I can understand the reasoning for that, but this change has a potential to make base::Values unusable in some cases, especially if you are loading base::Values from some JSON content, which doesn't understand the consideration involved in this choice.
I'm only giving a heads up because I've seen cases in which any performance gain with this change is lost due to the fact that base::flat_map uses brute force look up for uniqueness.
I don't want to be too critical of WTF::HashMap or imply it sucks. The open addressing is clearly faster and the memory access patterns are also better.But the real problem we have in most Chrome code is that we have a zillion almost empty maps. Hash tables of any type make this worse. I hacked std::map and put a histogram in the destructor of the map size. Here's the pattern for the browser process:
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CABiGVV-Q0tuO5Mn_MyDJ1Y6Aj7MYtcrDkkZCN7%2BkFrgjdH4tPQ%40mail.gmail.com.
On Wed, Apr 26, 2017 at 8:35 AM, Brett Wilson <bre...@chromium.org> wrote:I don't want to be too critical of WTF::HashMap or imply it sucks. The open addressing is clearly faster and the memory access patterns are also better.But the real problem we have in most Chrome code is that we have a zillion almost empty maps. Hash tables of any type make this worse. I hacked std::map and put a histogram in the destructor of the map size. Here's the pattern for the browser process:The contents of some maps may be cleaned up before the maps are destructed.It might be useful to keep track of max_size and log it in the destructor.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CABiGVV8Tx%3Dq9Kxk9ihODw-ofYwwRX%3DqtgJ%2BdNKjLcm3uUGN_vA%40mail.gmail.com.
Shameless plug for base::SmallMap! It turns all of those small maps into vectors, which (at that size) are superior in every way [citation needed] ESPECIALLY if the keys are in-lined memory in the array.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/3228ccc1-2897-43b5-8dec-3e6bf693b98c%40chromium.org.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CABiGVV9hnyt6fmf1sDtW325d_toeRXpCajzPs9yjYPa_H9kB9Q%40mail.gmail.com.
I’ve always told people to use trees instead of hash tables unless there was profiling evidence that hash tables would be faster for their application. The extra lg n factor only matters when n is large, and for a lot of use cases (such as a std::string for the key) a less than comparison can be a lot cheaper than a hash + equality comparison.
I don’t believe there is much that can be done on code size here (at least under our current ABI) – pretty much everything in a container has to depend on T, or at least on the allocator (which depends on T). (We do want to switch list to forward_list here, like libc++ does, but that’s an ABI break)
A robin-hood open-addressed hashed container might have better performance for small containers (since it would avoid per-element allocation), but the standard doesn’t have one (and my understanding is that unordered_map can’t be backed with one due to some of the iterator guarantees it provides).
Billy3
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/b2a73810-b0e3-49ee-a1e4-e25aedd3cd61n%40chromium.org.
In libc++ unordered_map seems to have better memory usage in general than maps have. I think we need to revisit the default map type guidelines.
* Generally avoid `std::unordered_set` and `std::unordered_map`. In the common
case, query performance is unlikely to be sufficiently higher than
`std::map` to make a difference, insert performance is slightly worse, and
the memory overhead is high. This makes sense mostly for large tables where
you expect a lot of lookups.
* Use `std::map` and `std::set` if you can't decide. Even if they're not
great, they're unlikely to be bad or surprising.
<snip about guidance about some specific cases, like "small" maps with wording such as
"better or comparable to other containers even for several dozen items">
* Use `std::map` and `std::set` if you can't decide. Even if they're not
great, they're unlikely to be bad or surprising.
So per the above, there's still the recommendation to use std::map unless it fits some definition of small, where the example is "several dozen items". Due to vagueness of what "small" and the guidance for defaulting to std::map if it's not clear. I'd wager I'm not the only one to arrive at that case via the "flow chart" of "small" not explicitly defined. (In my case, I was thinking of scenarios like number of field trials, which is in the hundreds range, or histograms, which are in the thousands range. Neither case was obviously a "small" map given the definition in the README.md).
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAKFU2SCH7287k42GjmHqXY4aib1NAYsES6XEjuA1%2B6phXkgYVg%40mail.gmail.com.
The default load factor for the standard containers is 1, not 0.5. Note that the standard containers are a separate chaining hash table, not an open addressed hash table, so relatively high load factors are much less ruinous for it (but of course it has worse constant factors). See http://eel.is/c++draft/unord#map.cnstr-1
From: K. Moon <km...@chromium.org>
Sent: Friday, February 5, 2021 12:30 PM
To: Chris Hamilton <chr...@chromium.org>
Cc: Alexei Svitkine <asvi...@chromium.org>; Peter Kasting <pkas...@chromium.org>; sabba...@gmail.com <sabba...@gmail.com>; Chromium-dev <chromi...@chromium.org>; Brett Wilson <bre...@chromium.org>; Jeffrey Yasskin <jyas...@chromium.org>; Stephan T. Lavavej <s...@exchange.microsoft.com>; Billy O'Neal (VC LIBS) <bi...@microsoft.com>
Subject: Re: [chromium-dev] Re: Please avoid std::unordered_map
Ah, makes sense. (I just wanted to underscore that a load factor of 1 makes sense here since lots of folks will be comparing with Google DenseHash or SwissTables or similar and wondering why things are different)
Thanks!
From: K. Moon <km...@chromium.org>
Sent: Friday, February 5, 2021 01:05 PM
To: Billy O'Neal (VC LIBS) <bi...@microsoft.com>
Cc: Chris Hamilton <chr...@chromium.org>; Alexei Svitkine <asvi...@chromium.org>; Peter Kasting <pkas...@chromium.org>; sabba...@gmail.com <sabba...@gmail.com>; Chromium-dev <chromi...@chromium.org>; Brett Wilson <bre...@chromium.org>; Jeffrey Yasskin <jyas...@chromium.org>; Stephan T. Lavavej <s...@exchange.microsoft.com>
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/74c8ba56-752d-44f5-a3cf-86ba28ebff02n%40chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAF3XrKq3Z0HL-%2BR3Q2wH4VM_w_QusDemLby8gV5OSBL2Ui%2BU-A%40mail.gmail.com.