[llvm][mustache] Avoid excessive hash lookups in EscapeStringStream (#160166)
The naive char-by-char lookup performed OK, but we can skip ahead to the
next match, avoiding all the extra hash lookups in the key map. Likely
there is a faster method than this, but its already a 42% win in the
BM_Mustache_StringRendering/Escaped benchmark, and an order of magnitude
improvement for BM_Mustache_LargeOutputString.
| Benchmark | Before (ns) | After (ns) | Speedup |
| :--- | ---: | ---: | ---: |
| `StringRendering/Escaped` | 29,440,922 | 16,583,603 | ~44% |
| `LargeOutputString` | 15,139,251 | 929,891 | ~94% |
| `HugeArrayIteration` | 102,148,245 | 95,943,960 | ~6% |
| `PartialsRendering` | 308,330,014 | 303,556,563 | ~1.6% |
Unreported benchmarks, like those for parsing, had no significant
change.
diff --git a/llvm/lib/Support/Mustache.cpp b/llvm/lib/Support/Mustache.cpp
index be9cbfd..686688a 100644
--- a/llvm/lib/Support/Mustache.cpp
+++ b/llvm/lib/Support/Mustache.cpp
@@ -397,19 +397,32 @@
public:
explicit EscapeStringStream(llvm::raw_ostream &WrappedStream,
EscapeMap &Escape)
- : Escape(Escape), WrappedStream(WrappedStream) {
+ : Escape(Escape), EscapeChars(Escape.keys().begin(), Escape.keys().end()),
+ WrappedStream(WrappedStream) {
SetUnbuffered();
}
protected:
void write_impl(const char *Ptr, size_t Size) override {
- llvm::StringRef Data(Ptr, Size);
- for (char C : Data) {
- auto It = Escape.find(C);
- if (It != Escape.end())
- WrappedStream << It->getSecond();
- else
- WrappedStream << C;
+ StringRef Data(Ptr, Size);
+ size_t Start = 0;
+ while (Start < Size) {
+ // Find the next character that needs to be escaped.
+ size_t Next = Data.find_first_of(EscapeChars.str(), Start);
+
+ // If no escapable characters are found, write the rest of the string.
+ if (Next == StringRef::npos) {
+ WrappedStream << Data.substr(Start);
+ return;
+ }
+
+ // Write the chunk of text before the escapable character.
+ if (Next > Start)
+ WrappedStream << Data.substr(Start, Next - Start);
+
+ // Look up and write the escaped version of the character.
+ WrappedStream << Escape[Data[Next]];
+ Start = Next + 1;
}
}
@@ -417,6 +430,7 @@
private:
EscapeMap &Escape;
+ SmallString<8> EscapeChars;
llvm::raw_ostream &WrappedStream;
};
