Some time ago I developed a fast BitVector class to use in some research here. It uses expression templates to fuse operation loops and runs much faster than the existing BitVector for some important use-cases. It also has the ability to efficiently report if a BitVector's contents changed after some operation. For example: ETBitVector A = ... ETBitVector B = ... ETBitVector C = ... bool Changed = A.assign(A & B | ~C); // Bit operation loops fused Using this resulted in 100x or more speedup over BitVector. Obviously, the speedup is greater the more operations are chained together. For a simple A.assign(A & B) it wouldn't be terribly faster. But the ability to report a change efficiently can be useful even for simple operations. I based this off an old version of BitVector. At the time it was a drop-in replacement but it would need some updating to conform to the current BitVector interface. Before I do that work, is there any interest in this? -David
Krzysztof Parzyszek via llvm-dev
2018-Sep-20 17:26 UTC
[llvm-dev] Interest in fast BitVector?
On 9/20/2018 12:19 PM, David Greene via llvm-dev wrote:> > Before I do that work, is there any interest in this?Do you see a lot of opportunities for fusing bit vector operations in the LLVM code? Bit vectors are very convenient, so having them be fast is certainly worthwhile. -Krzysztof -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
Krzysztof Parzyszek via llvm-dev <llvm-dev at lists.llvm.org> writes:> On 9/20/2018 12:19 PM, David Greene via llvm-dev wrote: >> >> Before I do that work, is there any interest in this? > > Do you see a lot of opportunities for fusing bit vector operations in > the LLVM code? Bit vectors are very convenient, so having them be > fast is certainly worthwhile.I honestly don't know. I developed this for some very specific work, not to fix a problem in existing code. I would say there are two situations where this could be useful: 1. Chained bitvector operations (even two operations would be a win) 2. Desire to know if an operation changes a bitvector's value A quick search through the code turned up this in lib/CodeGen/SafeStackColoring.cpp: bool changed = true; while (changed) { changed = false; for (BasicBlock *BB : depth_first(&F)) { BlockLifetimeInfo &BlockInfo = BlockLiveness[BB]; // Compute LiveIn by unioning together the LiveOut sets of all preds. BitVector LocalLiveIn; for (auto *PredBB : predecessors(BB)) { LivenessMap::const_iterator I = BlockLiveness.find(PredBB); // If a predecessor is unreachable, ignore it. if (I == BlockLiveness.end()) continue; LocalLiveIn |= I->second.LiveOut; } // Compute LiveOut by subtracting out lifetimes that end in this // block, then adding in lifetimes that begin in this block. If // we have both BEGIN and END markers in the same basic block // then we know that the BEGIN marker comes after the END, // because we already handle the case where the BEGIN comes // before the END when collecting the markers (and building the // BEGIN/END vectors). BitVector LocalLiveOut = LocalLiveIn; LocalLiveOut.reset(BlockInfo.End); LocalLiveOut |= BlockInfo.Begin; // Update block LiveIn set, noting whether it has changed. if (LocalLiveIn.test(BlockInfo.LiveIn)) { changed = true; BlockInfo.LiveIn |= LocalLiveIn; } // Update block LiveOut set, noting whether it has changed. if (LocalLiveOut.test(BlockInfo.LiveOut)) { changed = true; BlockInfo.LiveOut |= LocalLiveOut; } } } // while changed. At minimum, this does a loop to test if two BitVectors differ and then another loop to union the two. ETBitVector could do this in one loop. I could also imagine the code being refactored to gather all predecessor bitvectors first and then using operation chaining to fuse the union operation rather than looping over predessors and doing individual union operations. C++17 fold expressions would make this pretty slick. I could add an ETBitVector utility to make such refactoring easier. -David