summaryrefslogtreecommitdiff
path: root/absl/hash/internal/low_level_hash.cc
Commit message (Collapse)AuthorAge
* Optimize LowLevelHash by breaking dependency between final loads and ↵Gravatar Connal de Souza2024-03-28
| | | | | | | | | previous len/ptr updates. No functional change. PiperOrigin-RevId: 619979819 Change-Id: I71a4ae14272bcdf1da2e201ed286f95213ecb5e2
* Optimize `absl::Hash` by making `LowLevelHash` faster.Gravatar Shahriar Rouf2024-02-07
| | | | | | | | | | | | | | | | Throughput of the 64 byte chunk loop inside `LowLevelHash` (or now in `LowLevelHashLenGt16`) gets limited by the loop carried dependency on `current_state`. By using 4 states instead of 2, we can reduce this duration by 1 cycle. On Skylake, it is reduced from 9 cycles to 8 cycles (12.5% faster asymptotically). To see the reduction in a simplified version of `LowLevelHash` implementation on Skylake: * Before: https://godbolt.org/z/Tcj9vsGax, llvm-mca (https://godbolt.org/z/3o78Msr63) shows 9 cycles / iteration. * After: https://godbolt.org/z/q4GM4EjPr, llvm-mca (https://godbolt.org/z/W5d1KEMzq) shows 8 cycles / iteration. * This CL is removing 1 xor (1 cycle) per iteration from the critical path. A block for 32 byte chunk is also added. Finally, just before returning, `Mix` is called 1 time instead of twice. PiperOrigin-RevId: 605090653 Change-Id: Ib7517ebb8bef7484066cd14cf41a943953e93377
* Adding sw prefetchers to absl::hash.Gravatar Abseil Team2023-07-13
| | | | | PiperOrigin-RevId: 547850162 Change-Id: I43208c7fa1eaa2a7acfad5891b80c150ee58c65f
* Eliminate AArch64-specific code paths from LowLevelHashGravatar Benjamin Barenblat2022-12-08
| | | | | | | | | | | | | | After internal investigation, it’s no longer clear that the alternative LowLevelHash mixer committed in a05366d851c5cb88065272f951e03955197e7c11 unequivocally improves performance on AArch64. It unnecessarily reduces performance on Apple Silicon and the AWS Graviton. It also lowers hash quality, which offsets much of the performance gain it provides on the Arm Neoverse N1 (see https://github.com/abseil/abseil-cpp/issues/1093). Switch back to the original mixer. Closes: https://github.com/abseil/abseil-cpp/issues/1093 PiperOrigin-RevId: 493941913 Change-Id: I84c789b2f88c91dec22f6f0f6e8c5129d2939a6f
* Fix "unsafe narrowing" warnings in absl, 2/n.Gravatar Abseil Team2022-08-01
| | | | | | | | | | | | | | | Addresses failures with the following, in some files: -Wshorten-64-to-32 -Wimplicit-int-conversion -Wsign-compare -Wsign-conversion -Wtautological-unsigned-zero-compare (This specific CL focuses on .cc files in dirs a-h.) Bug: chromium:1292951 PiperOrigin-RevId: 464541951 Change-Id: If23b63ccea8e9b730159ff1c7288e9300a40b6bd
* Fix -Warray-parameter warningGravatar Abseil Team2022-07-13
| | | | | | | | | | Clang recently added this warning which flags inconsistencies between array parameters in function declarations. See https://crbug.com/1343303 PiperOrigin-RevId: 460725261 Change-Id: I57b1e99f13698c947e948c6024e3f6f4642ea189
* Export of internal Abseil changesGravatar Abseil Team2021-08-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 04cb3b22497190170aa5b774e98080c5de2ba60b by Abseil Team <absl-team@google.com>: Alternative bit mixer for LowLevelHash on ARM LowLevelHash's bit-mixer is inefficient on ARM because it calculates a 128-bit product of two 64-bit numbers. On ARM, this requires a sequence of two instructions with a high combined latency and poor throughput. This change provides alternative bit-mixing code for ARM that uses only 64-bit arithmetic (multiplication, xor, and left-shifts) and speeds things up considerably. The bit-mixing code for ARM was inspired by by Woothash[1] and xxh3[1]. Once I landed on a sequence of operations that provided good mixing, I used a test harness to search for the combination of shift / rotate factors that provided the best mixing, as indicated by SMHasher hash quality tests. The new mixing code passes 13 out of 15 of the hash quality test suites in SMHasher, with the two failures being in the noise range: e.g. 1 collision vs. zero expected in a keyset of ~8m keys. [1]: https://github.com/tommyettinger/waterhash/blob/49f5cf0b63b9/woothash.h#L16-L20 [2]: https://github.com/Cyan4973/xxHash/blob/6853ddc36e46/xxhash.h#L3240-L3265 PiperOrigin-RevId: 391833008 -- 17a4de1f9d623155c75b19285d414cd55a487cd6 by Saleem Abdulrasool <abdulras@google.com>: debugging: add support for unwinding on RISCV Linux This adds partial support for unwinding the RISCV call stack. It is largely duplicated from the AArch64 support with alterations for the ELF RISCV psABI. This covers RISCV64 and RISCV32, though not the ILP32E calling convention. PiperOrigin-RevId: 391818522 -- 32c93e449327b2cea32b32f6365e84b420fe1ed3 by Gennadiy Rozental <rogeeff@google.com>: New storage for types smaller than 8 bytes. Also adding new read interface for types smaller than or rqual to 8 bytes to avoid passing the pointer. PiperOrigin-RevId: 391726822 -- e987ac08a7787801cbfc7d7c96649e97fa8cff1a by Abseil Team <absl-team@google.com>: Extern template `find_first_non_full` to reduce linkage size for TU with single not inlined function. PiperOrigin-RevId: 391718862 -- 73af9bfcb5bf045089133e18bbd20eb5bb699172 by Gennadiy Rozental <rogeeff@google.com>: Make most non-mutable most int128 methods and friend free functions constexpr. Some functions are implemented offline (at least in some configurations) and can't be made constexpr. Mutable methods can't be made constexpr until we drop c++11 support. Fixes #978 PiperOrigin-RevId: 391706535 GitOrigin-RevId: 04cb3b22497190170aa5b774e98080c5de2ba60b Change-Id: If051fad5ff004e2e82fa53618fc04a6fe3d2d4be
* Export of internal Abseil changesGravatar Abseil Team2021-08-13
-- 3a9b4e8e5ecba532db5cc4ac12d12660307ce9fb by Derek Mauro <dmauro@google.com>: Use the Bazel @platforms repository for platform constraints Fixes #1000 PiperOrigin-RevId: 390644226 -- b34e4d2f8a86b54bd483ec4c9c3dd781ad2d8b68 by Abseil Team <absl-team@google.com>: debugging: add some handling for RISC-V The RISC-V architecture uses a downward growing stack and can host Linux using ELF files. Adjust a few sites accordingly to indicate how to handle the RISC-V architecture. PiperOrigin-RevId: 390631894 -- 5fa3a0961bf3dd0799c048956a0128f7b8113f1e by Samuel Benzaquen <sbenza@google.com>: Rename the buffer hash function to LowLevelHash. Although it started as wyhash, it will depart from it so it does not make sense to keep the name. PiperOrigin-RevId: 390483506 -- 2e7867a2301d58ad4cd5abcaa5fd6f0db973ae7b by Abseil Team <absl-team@google.com>: This is an internal change. PiperOrigin-RevId: 390349746 GitOrigin-RevId: 3a9b4e8e5ecba532db5cc4ac12d12660307ce9fb Change-Id: I322c3762552a2107e6c6b108c25c01e5efa8aecd
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-04 21:28:52 +0000