Paths
| Differential D114394
Compile-time computation of string attribute hashes Needs ReviewPublic Authored by serge-sans-paille on Nov 22 2021, 1:34 PM.
Details Summary This is a simplified —and hopefully easier to review— version of https://reviews.llvm.org/D114082 with a focus on the performance aspect Basically, this change forces usage of an AttributeKey object instead of plain string as Attribute key for free-forms attributes. As these object cache their hash value and this value can be computed at compile time for the common case where we check / retrieve an attribute value, this speeds up attribute lookup.
Diff Detail Event TimelineHerald added subscribers: ormris, dexonsmith, wenlei and 6 others. · View Herald TranscriptNov 22 2021, 1:34 PM JonChesterfield added inline comments.
serge-sans-paille mentioned this in D114082: [WIP] Normalize String Attributes.Nov 23 2021, 12:59 AM Comment Actions Remove static Dict and replace it by a dict attached to LLVMContext. Some early benchmarks, on the SQLite amalgamation, through valgrind --tool=callgrind ./bin/clang -c -o/dev/null sqlite3.c Instruction count Comment Actions I think @aeubanks might be a good reviewer for this. I like the performance wins here.
mehdi_amini added inline comments.
serge-sans-paille marked 6 inline comments as done. Comment ActionsUse CachedHashStringRef as suggested by @MaskRay serge-sans-paille marked an inline comment as done. serge-sans-paille added inline comments.
Comment Actions Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=3608e18a946e77a474a468304b6c3904c55dbce0&to=0ce74a09cc8533a10fb67fdec4fb6ad8de4f1153&stat=instructions Some improvement at O3, not much change for optimized builds. A concern I have is that this may be pessimizing non-clang frontends in favor of clang. Frontends not written in C++ will always be going through the AttributeKey::get() API, which will be slower than the initial state (I think -- we still have to calculate the hash dynamically, but now we also need to intern an AttributeKey by performing an actual hash table lookup.) As a more general thought, I believe a core (performance) problem in the current attribute design is that AttrBuilder represents string attributes as a pair of strings, and most of our attribute manipulation is indirected through AttrBuilders. This means that we end up converting string Attributes into a pair of strings and then construct an Attribute again via FoldingSet lookup. This is of course a lot of unnecessary work. Similarly, there are many hot attributes (like "target-cpu") which are basically always the same, and we could just construct the Attribute upfront and always use that. That would save more than just the attribute name hash calculation. I think we may want to reconsider the AttrBuilder design to store Attributes at least for string attributes, though of course that does make it Context-dependent. Comment Actions *comment removed, I've been doing more detailed benchmark that imply a rework of the patch* Comment Actions Use a DenseSet instead of a DenseMap to store the StringPool. Some benchmark feedback (using a release build compiled with LTO), in number of instructions
I also tried some micro benchmark on the C-API and C++ API, using compile-time known Attribute name #include "llvm-c/Core.h"
#include <cstdio>
#include <cstring>
int main(int argc, char** argv) {
int n = strlen(argv[0]);
LLVMContextRef ctx = LLVMContextCreate();
LLVMModuleRef mod = LLVMModuleCreateWithName("name");
LLVMAttributeRef Key =
LLVMCreateStringAttribute(ctx, argv[0], n, "myvalue", 7);
LLVMValueRef value = LLVMGetIntrinsicDeclaration(mod, 25, {}, 0);
LLVMDumpValue(value);
LLVMAddAttributeAtIndex(value, 0, Key);
unsigned size;
char buffer[100];
for (int i = 0; i < 10000; ++i) {
for (int j = 0; j < 1000; ++j) {
LLVMGetStringAttributeAtIndex(value, 0, argv[0], n);
size += n;
}
}
return size;
}Here are the result (in seconds)
So basically, the drawback of this patch is that there is a double lookup (and thus two calls to strcmp) for each dynamic attribute request. Comment Actions That's interesting, somehow clang spends 1% of its time for sqlite3 in attribute lookup. I wonder how we ended up doing so much string-based attribute lookup. These were not really ever intended to be used for anything semantically interesting for the middle end, they were designed as a way to pass through uninteresting target-specific details like SSE features through to the backend. I guess what happened next is that we added rules to the inliner to block inlining between functions with mismatched CPU features, and that's where these string attribute lookups are coming from. Perhaps there's a design lesson here. Regarding LLVMGetStringAttributeAtIndex and the C API, I don't imagine that most non-C++ frontends do a lot of attribute lookups. They mainly generate IR. I think, on balance, the performance improvements in LLVM itself will outweigh any regressions from doing extra lookups via the C API during IR generation. Comment Actions Update: the strategy used by `AttrBuilder` might not be the best way to build new attributes. I've proposed an alternative implementation in https://reviews.llvm.org/D115798. This is somehow orthogonal to that patch, but it removes the need for temporary copies of string attributes Key/Value in the AttrBuilder which is already a big plus.
Revision Contents
Diff 393058 clang/lib/CodeGen/CGCall.cpp
clang/lib/CodeGen/CGOpenMPRuntime.cpp
clang/lib/CodeGen/CodeGenFunction.cpp
llvm/include/llvm/Analysis/TargetLibraryInfo.h
llvm/include/llvm/Analysis/VectorUtils.h
llvm/include/llvm/CodeGen/CommandFlags.h
llvm/include/llvm/IR/Assumptions.h
llvm/include/llvm/IR/Attributes.h
llvm/include/llvm/IR/Function.h
llvm/include/llvm/IR/GlobalVariable.h
llvm/include/llvm/IR/InstrTypes.h
llvm/include/llvm/ProfileData/SampleProf.h
llvm/lib/Analysis/InlineCost.cpp
llvm/lib/AsmParser/LLParser.cpp
llvm/lib/Bitcode/Reader/BitcodeReader.cpp
llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
llvm/lib/CodeGen/CommandFlags.cpp
llvm/lib/IR/AttributeImpl.h
llvm/lib/IR/Attributes.cpp
llvm/lib/IR/Core.cpp
llvm/lib/IR/DiagnosticInfo.cpp
llvm/lib/IR/Function.cpp
llvm/lib/IR/Instructions.cpp
llvm/lib/IR/LLVMContextImpl.h
llvm/lib/IR/Verifier.cpp
llvm/lib/Transforms/IPO/Attributor.cpp
llvm/lib/Transforms/IPO/OpenMPOpt.cpp
llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp
llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
llvm/lib/Transforms/Utils/CodeExtractor.cpp
llvm/lib/Transforms/Utils/EntryExitInstrumenter.cpp
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||