[libcxx] Avoid hash key in __hash_table::find() if it is empty. (#126837) If the hash table is empty, with or without buckets, the find() can do fast return. Then computing hash key is useless and avoidable, since it could be expensive for some key types, such as long strings. This is a small optimization but useful in cases like a checklist (unordered_set/map) which is mostly empty. ``` For std::unordered_set<*>, `--benchmark_filter=find` 1. With the opt: --------------------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------------------------- std::unordered_set<int>::find(key) (existent)/0 0.118 ns 0.118 ns 5939922720 std::unordered_set<int>::find(key) (existent)/32 52.1 ns 52.1 ns 13287232 std::unordered_set<int>::find(key) (existent)/1024 51.1 ns 51.1 ns 13449472 std::unordered_set<int>::find(key) (existent)/8192 53.1 ns 53.1 ns 13420864 std::unordered_set<int>::find(key) (non-existent)/0 14.7 ns 14.7 ns 47725472 std::unordered_set<int>::find(key) (non-existent)/32 44.1 ns 44.1 ns 15478144 std::unordered_set<int>::find(key) (non-existent)/1024 41.2 ns 41.2 ns 15082464 std::unordered_set<int>::find(key) (non-existent)/8192 49.5 ns 49.5 ns 15233600 std::unordered_set<std::string>::find(key) (existent)/0 0.136 ns 0.136 ns 5157977920 std::unordered_set<std::string>::find(key) (existent)/32 739 ns 739 ns 1023744 std::unordered_set<std::string>::find(key) (existent)/1024 836 ns 836 ns 840448 std::unordered_set<std::string>::find(key) (existent)/8192 768 ns 768 ns 1085664 std::unordered_set<std::string>::find(key) (non-existent)/0 14.6 ns 14.6 ns 47844160 std::unordered_set<std::string>::find(key) (non-existent)/32 608 ns 608 ns 1106496 std::unordered_set<std::string>::find(key) (non-existent)/1024 646 ns 646 ns 986272 std::unordered_set<std::string>::find(key) (non-existent)/8192 669 ns 669 ns 1047584 2. Without the opt: --------------------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------------------------- std::unordered_set<int>::find(key) (existent)/0 0.135 ns 0.135 ns 5188502304 std::unordered_set<int>::find(key) (existent)/32 54.4 ns 54.4 ns 12954144 std::unordered_set<int>::find(key) (existent)/1024 57.7 ns 57.7 ns 13107008 std::unordered_set<int>::find(key) (existent)/8192 50.7 ns 50.7 ns 12953312 std::unordered_set<int>::find(key) (non-existent)/0 16.1 ns 16.1 ns 43460192 std::unordered_set<int>::find(key) (non-existent)/32 45.8 ns 45.8 ns 17139584 std::unordered_set<int>::find(key) (non-existent)/1024 44.6 ns 44.6 ns 16538048 std::unordered_set<int>::find(key) (non-existent)/8192 41.5 ns 41.5 ns 12850816 std::unordered_set<std::string>::find(key) (existent)/0 0.133 ns 0.133 ns 5214104992 std::unordered_set<std::string>::find(key) (existent)/32 731 ns 731 ns 1000576 std::unordered_set<std::string>::find(key) (existent)/1024 716 ns 716 ns 1131584 std::unordered_set<std::string>::find(key) (existent)/8192 745 ns 745 ns 909632 std::unordered_set<std::string>::find(key) (non-existent)/0 600 ns 600 ns 1089792 std::unordered_set<std::string>::find(key) (non-existent)/32 645 ns 645 ns 979232 std::unordered_set<std::string>::find(key) (non-existent)/1024 675 ns 675 ns 962240 std::unordered_set<std::string>::find(key) (non-existent)/8192 711 ns 711 ns 1054880 ``` We can see the improvements when find() for non-existent `std::string`(random size 1~1024) keys: ``` std::unordered_set<std::string>::find(key) (non-existent)/0 14.6 ns 14.6 ns 47844160 std::unordered_set<std::string>::find(key) (non-existent)/0 600 ns 600 ns 1089792 ``` --------- Co-authored-by: yangxiaobing <yangxiaobing@jwzg.com>
Welcome to the LLVM project!
This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.
C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
Consult the Getting Started with LLVM page for information on building and running LLVM.
For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.
The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.