diff options
| author |  Vitaly Goldshteyn <goldvitaly@google.com> | 2024-06-10 14:05:35 -0700 |
|---|---|---|
| committer |  Copybara-Service <copybara-worker@google.com> | 2024-06-10 14:06:41 -0700 |
| commit | 1d401d9c5a2d0896ec7abb69efbd199b05f9e55e (patch) | |
| tree | 858db91a89653dec9ac26007a739f3e94f12ef82 /absl/container/CMakeLists.txt | |
| parent | d30298a1b6f3dd8939910561e211fe990e4e2e8e (diff) | |
Use `IterateOverFullSlots` in `absl::erase_if` for hash table.
`EraseIf` itself is not very hot function, but I want to use that as demonstration of the speed of iteration via `IterateOverFullSlots`.
Motivation:
1. We are still going to save some resources.
2. It is the first step to implement faster `absl::c_for_each` that may give larger benefits. Will require readability considerations.
`BM_EraseIf/num_elements:1000/num_erased:0` is just iteration and it gives 60% speed up.
On smaller tables removing all elements shows 25% speed up. Note that on small tables erasing is much faster due to cl/592272653.
```
name old cpu/op new cpu/op delta
BM_EraseIf/num_elements:10/num_erased:0 3.41ns ± 5% 3.03ns ± 3% -11.14% (p=0.000 n=37+35)
BM_EraseIf/num_elements:1000/num_erased:0 6.06ns ± 3% 2.42ns ± 3% -60.05% (p=0.000 n=34+37)
BM_EraseIf/num_elements:10/num_erased:5 5.90ns ± 3% 4.44ns ± 4% -24.88% (p=0.000 n=36+37)
BM_EraseIf/num_elements:1000/num_erased:500 11.0ns ± 2% 9.2ns ± 2% -16.60% (p=0.000 n=35+37)
BM_EraseIf/num_elements:10/num_erased:10 8.03ns ± 3% 5.77ns ± 2% -28.19% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 9.00ns ± 3% 7.83ns ± 2% -12.98% (p=0.000 n=37+37)
name old time/op new time/op delta
BM_EraseIf/num_elements:10/num_erased:0 3.42ns ± 5% 3.04ns ± 3% -11.13% (p=0.000 n=37+36)
BM_EraseIf/num_elements:1000/num_erased:0 6.07ns ± 3% 2.42ns ± 3% -60.10% (p=0.000 n=34+37)
BM_EraseIf/num_elements:10/num_erased:5 5.93ns ± 3% 4.45ns ± 4% -24.89% (p=0.000 n=36+37)
BM_EraseIf/num_elements:1000/num_erased:500 11.1ns ± 2% 9.2ns ± 2% -16.61% (p=0.000 n=35+37)
BM_EraseIf/num_elements:10/num_erased:10 8.06ns ± 3% 5.79ns ± 2% -28.19% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 9.03ns ± 3% 7.85ns ± 2% -12.98% (p=0.000 n=37+37)
name old INSTRUCTIONS/op new INSTRUCTIONS/op delta
BM_EraseIf/num_elements:10/num_erased:0 19.5 ± 1% 14.9 ± 0% -23.79% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:0 19.9 ± 0% 12.7 ± 0% -36.20% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 36.9 ± 1% 30.9 ± 0% -16.47% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500 44.8 ± 0% 37.6 ± 0% -16.06% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10 53.0 ± 1% 46.9 ± 0% -11.61% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 69.8 ± 0% 62.6 ± 0% -10.32% (p=0.000 n=36+37)
name old CYCLES/op new CYCLES/op delta
BM_EraseIf/num_elements:10/num_erased:0 6.10 ± 7% 4.91 ± 1% -19.49% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:0 19.4 ± 1% 7.7 ± 2% -60.04% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 13.9 ± 4% 9.2 ± 3% -33.80% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500 35.5 ± 0% 29.5 ± 1% -16.74% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10 20.8 ± 5% 13.5 ± 0% -35.07% (p=0.000 n=37+30)
BM_EraseIf/num_elements:1000/num_erased:1000 28.9 ± 0% 25.1 ± 0% -13.06% (p=0.000 n=37+37)
```
PiperOrigin-RevId: 642016364
Change-Id: I8be6af5916bd45fd110bb0398c3ffe932a6a083f
Diffstat (limited to 'absl/container/CMakeLists.txt')
| -rw-r--r-- | absl/container/CMakeLists.txt | 2 |
1 files changed, 2 insertions, 0 deletions
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index a1023def..dd994f0b 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -783,10 +783,12 @@ absl_cc_test( absl::hashtablez_sampler absl::log absl::memory + absl::node_hash_set absl::prefetch absl::raw_hash_set absl::strings absl::test_allocator + absl::test_instance_tracker absl::type_traits GTest::gmock_main ) |