[libc++] Optimize search_n (#171389) This changes the algorithm to more efficiently skip ranges which cannot match the needle for random access iterators. Specifically, we now search for a mismatching element from the back of the subrange we want to check. When a mismatch occurs we can directly start one after the mismatched element, since there cannot possibly be a matching subrange starting between the start of the subrange we checked and the mismatched element (since all elements have to be equal). The algorithm also remembers the subrange which was already match as being equal and doesn't try to compare it a second time, reducing the time spent in case of a match. ``` Benchmark old new Difference % Difference --------------------------------------------------- -------------- -------------- ------------ -------------- rng::search_n(deque<int>)_(no_match)/1000 458.33 14.22 -444.11 -96.90% rng::search_n(deque<int>)_(no_match)/1024 456.17 13.89 -442.28 -96.95% rng::search_n(deque<int>)_(no_match)/1048576 453420.38 17.69 -453402.69 -100.00% rng::search_n(deque<int>)_(no_match)/8192 3566.08 17.60 -3548.49 -99.51% rng::search_n(deque<int>,_pred)_(no_match)/1000 597.88 15.25 -582.63 -97.45% rng::search_n(deque<int>,_pred)_(no_match)/1024 608.42 15.39 -593.03 -97.47% rng::search_n(deque<int>,_pred)_(no_match)/1048576 594533.99 18.91 -594515.08 -100.00% rng::search_n(deque<int>,_pred)_(no_match)/8192 4670.23 18.88 -4651.35 -99.60% rng::search_n(list<int>)_(no_match)/1000 733.72 730.22 -3.50 -0.48% rng::search_n(list<int>)_(no_match)/1024 759.93 753.10 -6.84 -0.90% rng::search_n(list<int>)_(no_match)/1048576 833841.54 813483.75 -20357.79 -2.44% rng::search_n(list<int>)_(no_match)/8192 8352.18 8417.31 65.14 0.78% rng::search_n(list<int>,_pred)_(no_match)/1000 776.79 789.72 12.93 1.66% rng::search_n(list<int>,_pred)_(no_match)/1024 788.42 806.70 18.28 2.32% rng::search_n(list<int>,_pred)_(no_match)/1048576 955536.40 982976.81 27440.41 2.87% rng::search_n(list<int>,_pred)_(no_match)/8192 8874.02 8915.18 41.16 0.46% rng::search_n(vector<int>)_(no_match)/1000 212.69 3.79 -208.90 -98.22% rng::search_n(vector<int>)_(no_match)/1024 219.67 3.70 -215.96 -98.31% rng::search_n(vector<int>)_(no_match)/1048576 209622.54 3.67 -209618.87 -100.00% rng::search_n(vector<int>)_(no_match)/8192 1643.80 3.83 -1639.98 -99.77% rng::search_n(vector<int>,_pred)_(no_match)/1000 461.93 7.55 -454.38 -98.36% rng::search_n(vector<int>,_pred)_(no_match)/1024 472.43 7.74 -464.69 -98.36% rng::search_n(vector<int>,_pred)_(no_match)/1048576 546180.29 8.71 -546171.58 -100.00% rng::search_n(vector<int>,_pred)_(no_match)/8192 3786.26 7.88 -3778.38 -99.79% std::search_n(deque<int>)_(no_match)/1000 455.53 14.19 -441.34 -96.88% std::search_n(deque<int>)_(no_match)/1024 459.79 13.98 -445.81 -96.96% std::search_n(deque<int>)_(no_match)/1048576 449780.32 17.99 -449762.33 -100.00% std::search_n(deque<int>)_(no_match)/8192 3508.55 17.97 -3490.58 -99.49% std::search_n(deque<int>,_pred)_(no_match)/1000 571.53 17.16 -554.37 -97.00% std::search_n(deque<int>,_pred)_(no_match)/1024 584.43 17.09 -567.34 -97.08% std::search_n(deque<int>,_pred)_(no_match)/1048576 581418.31 19.16 -581399.15 -100.00% std::search_n(deque<int>,_pred)_(no_match)/8192 4661.97 19.36 -4642.61 -99.58% std::search_n(list<int>)_(no_match)/1000 722.45 710.39 -12.06 -1.67% std::search_n(list<int>)_(no_match)/1024 748.50 727.08 -21.42 -2.86% std::search_n(list<int>)_(no_match)/1048576 821655.28 784520.12 -37135.16 -4.52% std::search_n(list<int>)_(no_match)/8192 7941.73 8002.05 60.32 0.76% std::search_n(list<int>,_pred)_(no_match)/1000 766.59 786.31 19.72 2.57% std::search_n(list<int>,_pred)_(no_match)/1024 785.92 804.43 18.51 2.35% std::search_n(list<int>,_pred)_(no_match)/1048576 948252.76 969125.41 20872.65 2.20% std::search_n(list<int>,_pred)_(no_match)/8192 8658.99 8825.71 166.72 1.93% std::search_n(vector<int>)_(no_match)/1000 210.36 3.47 -206.89 -98.35% std::search_n(vector<int>)_(no_match)/1024 217.60 4.13 -213.47 -98.10% std::search_n(vector<int>)_(no_match)/1048576 209386.43 3.51 -209382.92 -100.00% std::search_n(vector<int>)_(no_match)/8192 1643.79 3.50 -1640.29 -99.79% std::search_n(vector<int>,_pred)_(no_match)/1000 460.88 5.44 -455.45 -98.82% std::search_n(vector<int>,_pred)_(no_match)/1024 475.36 5.43 -469.93 -98.86% std::search_n(vector<int>,_pred)_(no_match)/1048576 682722.75 7.15 -682715.60 -100.00% std::search_n(vector<int>,_pred)_(no_match)/8192 3779.95 5.43 -3774.52 -99.86% Geomean 4956.15 87.96 -4868.19 -98.23% ``` Fixes #129327
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.