From 88eb6482ca5d27ee692623be5148d338ad8ddc8b Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Wed, 19 Oct 2016 14:17:36 +0000 Subject: [PATCH] Add a faster binary search. Even with the hash table cache, binary search was still pretty hot. This can be made even faster with prefetching. Idea from http://cglab.ca/~morin/misc/arraylayout-v2/ I will suggest moving this to llvm. llvm-svn: 284594 --- lld/ELF/InputSection.cpp | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp index 245c5e9..296c3a6 100644 --- a/lld/ELF/InputSection.cpp +++ b/lld/ELF/InputSection.cpp @@ -651,6 +651,19 @@ SectionPiece *MergeInputSection::getSectionPiece(uintX_t Offset) { return const_cast(This->getSectionPiece(Offset)); } +template +static It fastUpperBound(It First, It Last, const T &Value, Compare Comp) { + size_t Size = std::distance(First, Last); + assert(Size != 0); + while (Size != 1) { + size_t H = Size / 2; + const It MI = First + H; + Size -= H; + First = Comp(Value, *MI) ? First : First + H; + } + return Comp(Value, *First) ? First : First + 1; +} + template const SectionPiece * MergeInputSection::getSectionPiece(uintX_t Offset) const { @@ -659,7 +672,7 @@ MergeInputSection::getSectionPiece(uintX_t Offset) const { fatal(getName(this) + ": entry is past the end of the section"); // Find the element this offset points to. - auto I = std::upper_bound( + auto I = fastUpperBound( Pieces.begin(), Pieces.end(), Offset, [](const uintX_t &A, const SectionPiece &B) { return A < B.InputOff; }); --I; -- 2.7.4