diff options
| author | Connal de Souza <connaldesouza@google.com> | 2023-08-04 09:37:41 -0700 |
|---|---|---|
| committer | Copybara-Service <copybara-worker@google.com> | 2023-08-04 09:39:01 -0700 |
| commit | 039d70f69b34b59d9696c655689316a94026fd0e (patch) | |
| tree | bd6846859b243eaf41ac6cb2af7b60e15f759dfa /absl/container/internal/raw_hash_set_test.cc | |
| parent | 14a91eefa7a3f3bf0a949e82ce5854659588a5c0 (diff) | |
| download | abseil-039d70f69b34b59d9696c655689316a94026fd0e.tar.gz abseil-039d70f69b34b59d9696c655689316a94026fd0e.tar.bz2 abseil-039d70f69b34b59d9696c655689316a94026fd0e.zip | |
Optimize Swissmap Match on Arm.
Currently we require only a single bit to be set in each abstract bit for iterable bitmasks. However, in most cases, where we have a single match, or no matches in a group, iteration is not needed. We move the masking to the iteration function instead of having it as a requirement for iterable Bitmask construction.
This is 4-8% faster for Find and Insert operations.
This can hurt performance if we need to iterate many times (there are many matches in the same Group), however this is unlikely, even if we assume the table is completely full.
If there are 0 or 1 matches in a group, or the first match is the correct item we are looking for, we save 1 instruction/cycle (most cases)
If there are 2 matches in a group, and the first is a false positive, this is neutral (< 3%)
If there are more than 2 matches in a group and the first two are false positives, this can be slower by 1 cycle/instruction per additional iteration (< 0.1%)
No change to x86.
PiperOrigin-RevId: 553831814
Change-Id: I08620899847eaf0086da989d829a1029ea24173a
Diffstat (limited to 'absl/container/internal/raw_hash_set_test.cc')
0 files changed, 0 insertions, 0 deletions