| Name |
Last commit
|
Last Update |
|---|---|---|
| .. | ||
| algorithm | ||
| base | ||
| cleanup | ||
| container | ||
| copts | ||
| debugging | ||
| flags | ||
| functional | ||
| hash | ||
| memory | ||
| meta | ||
| numeric | ||
| profiling | ||
| random | ||
| status | ||
| strings | ||
| synchronization | ||
| time | ||
| types | ||
| utility | ||
| BUILD.bazel | ||
| CMakeLists.txt | ||
| abseil.podspec.gen.py |
Benchmarks: https://pastebin.com/tZ7dr67W. Works well especially on smaller ranges. After a week on spending optimizing NEON SIMD where I almost managed to make hash tables work with NEON SIMD without performance hits (still 1 cycle to optimize and I gave up a little), I found an interesting optimization for aarch64 to use cls instruction (count leading sign bits). The loop has a property that ctrl_ group is not matched against count when the first slot is empty or deleted. ``` void skip_empty_or_deleted() { while (IsEmptyOrDeleted(*ctrl_)) { uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted(); ctrl_ += shift; slot_ += shift; } ... } ``` However, `kEmpty` and `kDeleted` have format of `1xxxxxx0` and `~ctrl & (ctrl >> 7)` always sets the lowest bit to 1. In naive implementation, it does +1 to start counting zero bits, however, in aarch64 we may start counting one bits immediately. This saves 1 cycle and 5% of iteration performance. Then it becomes hard to find a supported and sustainable C++ version of it. `__clsll` is not supported by GCC and was supported only since clang 8, `__builtin_clrsb` is not producing optimal codegen for clang. `__rbit` is not supported by GCC and there is no intrinsic to do that, however, in clang we have `__builtin_bitreverse{32,64}`. For now I decided to enable this only for clang, only if they have appropriate builtins. PiperOrigin-RevId: 451168570 Change-Id: I7e9256a60aecdc88ced4e6eb15ebc257281b6664
| Name |
Last commit
|
Last Update |
|---|---|---|
| .. | ||
| algorithm | Loading commit data... | |
| base | Loading commit data... | |
| cleanup | Loading commit data... | |
| container | Loading commit data... | |
| copts | Loading commit data... | |
| debugging | Loading commit data... | |
| flags | Loading commit data... | |
| functional | Loading commit data... | |
| hash | Loading commit data... | |
| memory | Loading commit data... | |
| meta | Loading commit data... | |
| numeric | Loading commit data... | |
| profiling | Loading commit data... | |
| random | Loading commit data... | |
| status | Loading commit data... | |
| strings | Loading commit data... | |
| synchronization | Loading commit data... | |
| time | Loading commit data... | |
| types | Loading commit data... | |
| utility | Loading commit data... | |
| BUILD.bazel | Loading commit data... | |
| CMakeLists.txt | Loading commit data... | |
| abseil.podspec.gen.py | Loading commit data... |