Migrate `ProcessorEntityTracker` maps to `absl::flat_hash_map` [chromium/src : main]
Ankush Singh (Gerrit)
Ankush Singh added 1 comment![]( "Open in Gerrit")
#include "absl/container/flat_hash_map.h"Just a fly-by: `third_party/abseil-cpp/absl/container/flat_hash_map.h` plus removes the change in DEPS.
Related details
- Marc Treib
- Michael Tatarski
Code-Coverage
Code-Owners
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Tatarski (Gerrit)
Michael Tatarski voted and added 2 comments![]( "Open in Gerrit")
Votes added by Michael Tatarski
| Auto-Submit | +1 |
| Commit-Queue | +1 |
2 comments
Just a fly-by: `third_party/abseil-cpp/absl/container/flat_hash_map.h` plus removes the change in DEPS.
- Ankush Singh
- Marc Treib
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Marc Treib (Gerrit)
Marc Treib added 5 comments![]( "Open in Gerrit")
Marc TreibThese changes touch critical pieces of sync infra. I want to get the approval of the TL for this CL!
This should unlock a significant performance gain as we move from O(log(N)) to (1) TC behaviour in our internal sync data structures.
significant performance gain
I'll believe that when you show me the timing measurements! :P
But the absl containers are generally recommended as the default these days, and AFAIK they have essentially no downsides compared to the std ones, so this is still a good change to make overall.
for (const auto& pair : map) {
memory_usage += EstimateItemMemoryUsage(pair.first);
memory_usage += EstimateItemMemoryUsage(pair.second);
}Won't this double-count the memory?
If we do need to iterate over the elements, could this use `EstimateIterableMemoryUsage`?
// plus control bytes (capacity * sizeof(char)).Add `https://abseil.io/docs/cpp/guides/container#memory-usage` as a reference?
// For use in absl::flat_hash_set.`or absl::flat_hash_set`, right?
entities_;Just a note: This will change the ordering of the elements. I'm pretty sure that's fine, since (a) the ordering was arbitrary anyway, and (b) none of the usages seem to care about the order.
But out of curiosity: Did you check all the usages?
Related details
- Ankush Singh
- Michael Tatarski
Code-Coverage
Code-Owners
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Tatarski (Gerrit)
Michael Tatarski voted and added 5 comments![]( "Open in Gerrit")
Votes added by Michael Tatarski
| Auto-Submit | +1 |
| Commit-Queue | +1 |
5 comments
WDYT if I measure the performance difference and present it in our "Technical discussion / knowledge sharing" meeting?
for (const auto& pair : map) {
memory_usage += EstimateItemMemoryUsage(pair.first);
memory_usage += EstimateItemMemoryUsage(pair.second);
}Won't this double-count the memory?
If we do need to iterate over the elements, could this use `EstimateIterableMemoryUsage`?
The calculation is done in two parts:
**map.capacity() * (sizeof(value_type) + sizeof(char)):** This accounts for the memory allocated by the flat_hash_map itself to hold the std::pair elements.
**The iteration over elements:** This sums up any memory that is dynamically allocated by the elements themselves (e.g., the character buffer for a std::string key or value).
This is consistent with how memory is estimated for other containers in this file.
However, you are right that the loop can be simplified by using EstimateIterableMemoryUsage
// plus control bytes (capacity * sizeof(char)).Add `https://abseil.io/docs/cpp/guides/container#memory-usage` as a reference?
Done
// For use in absl::flat_hash_set.`or absl::flat_hash_set`, right?
Right! But you mean `absl::flat_hash_map`, correct?
Just a note: This will change the ordering of the elements. I'm pretty sure that's fine, since (a) the ordering was arbitrary anyway, and (b) none of the usages seem to care about the order.
But out of curiosity: Did you check all the usages?
Yes, none of the usages rely on the map being sorted! Most of the time we just want to find a random element or we are simply iterating over a map.
Related details
- Ankush Singh
- Marc Treib
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Marc Treib (Gerrit)
Marc Treib voted and added 3 comments![]( "Open in Gerrit")
Votes added by Marc Treib
| Code-Review | +1 |
3 comments
WDYT if I measure the performance difference and present it in our "Technical discussion / knowledge sharing" meeting?
Per my other comment, I think for this one it's not necessary - it's just following general best practices.
(If you *want* to measure it I'm not going to stop you, but the results from that other CL would be more interesting!)
for (const auto& pair : map) {
memory_usage += EstimateItemMemoryUsage(pair.first);
memory_usage += EstimateItemMemoryUsage(pair.second);
}Michael TatarskiWon't this double-count the memory?
If we do need to iterate over the elements, could this use `EstimateIterableMemoryUsage`?
The calculation is done in two parts:
**map.capacity() * (sizeof(value_type) + sizeof(char)):** This accounts for the memory allocated by the flat_hash_map itself to hold the std::pair elements.
**The iteration over elements:** This sums up any memory that is dynamically allocated by the elements themselves (e.g., the character buffer for a std::string key or value).
This is consistent with how memory is estimated for other containers in this file.However, you are right that the loop can be simplified by using EstimateIterableMemoryUsage
Ah, I had missed that `EstimateItemMemoryUsage` only counts *dynamically allocated* memory, not the memory usage of the object itself, e.g. for an `int` it'll return 0. That's quite subtle, and the naming could IMO be better, but that's definitely not for this CL.
// For use in absl::flat_hash_set.Michael Tatarski`or absl::flat_hash_set`, right?
Right! But you mean `absl::flat_hash_map`, correct?
- Ankush Singh
- Michael Tatarski
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Tatarski (Gerrit)
Message from Michael Tatarski![]( "Open in Gerrit")
- Marc Treib
- Michael Tatarski
- Nico Weber
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Nico Weber (Gerrit)
Nico Weber voted Code-Review+1![]( "Open in Gerrit")
- Michael Tatarski
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Tatarski (Gerrit)
Michael Tatarski voted Commit-Queue+2![]( "Open in Gerrit")
Code-Coverage
Code-Owners
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Chromium LUCI CQ (Gerrit)
Chromium LUCI CQ submitted the change![]( "Open in Gerrit")
Change information
Migrate `ProcessorEntityTracker` maps to `absl::flat_hash_map`
This change replaces `std::map` with `absl::flat_hash_map` for
`entities_` and `storage_key_to_tag_hash_` in `ProcessorEntityTracker`.
To support this, `ClientTagHash` is made compatible with Abseil hashing
by adding an `AbslHashValue` function. Additionally, a memory usage
estimator for `absl::flat_hash_map` is added to
`base/trace_event/memory_usage_estimator.h`. The usage of
`std::erase_if` is updated to `absl::erase_if` for the new container
type.
- M base/trace_event/memory_usage_estimator.h
- M components/sync/base/client_tag_hash.h
- M components/sync/model/processor_entity_tracker.cc
- M components/sync/model/processor_entity_tracker.h
Code-Review: +1 by Marc Treib, +1 by Nico Weber
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |