[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>
3 files changed
tree: 8c1c89b77bb0b791ca6bc8d09c8e778ac9965691
  1. .ci/
  2. .github/
  3. bolt/
  4. clang/
  5. clang-tools-extra/
  6. cmake/
  7. compiler-rt/
  8. cross-project-tests/
  9. flang/
  10. flang-rt/
  11. libc/
  12. libclc/
  13. libcxx/
  14. libcxxabi/
  15. libunwind/
  16. lld/
  17. lldb/
  18. llvm/
  19. llvm-libgcc/
  20. mlir/
  21. offload/
  22. openmp/
  23. polly/
  24. runtimes/
  25. third-party/
  26. utils/
  27. .clang-format
  28. .clang-format-ignore
  29. .clang-tidy
  30. .git-blame-ignore-revs
  31. .gitattributes
  32. .gitignore
  33. .mailmap
  34. CODE_OF_CONDUCT.md
  35. CONTRIBUTING.md
  36. LICENSE.TXT
  37. pyproject.toml
  38. README.md
  39. SECURITY.md
README.md

The LLVM Compiler Infrastructure

OpenSSF Scorecard OpenSSF Best Practices libc++

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.

Getting the Source Code and Building LLVM

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.

Getting in touch

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.