This is an archive of the discontinued LLVM Phabricator instance.

Simplify BitVector code
AcceptedPublic

Authored by serge-sans-paille on Apr 13 2021, 7:34 AM.

Details

Summary

Instead of managing memory by hand, delegate it to std::vector. This makes the
code much simpler, easier to reason on and also avoids repeatedly computing the storage size.

According to valgrind --tool=callgrind, this also slightly decreases the
instruction count, but by a small margin.

Diff Detail

Event Timeline

serge-sans-paille requested review of this revision.Apr 13 2021, 7:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 13 2021, 7:34 AM
nikic added a subscriber: nikic.Apr 13 2021, 10:18 AM
nikic added inline comments.
llvm/include/llvm/ADT/BitVector.h
82–85

Any thoughts on making this SmallVector<BitWord, 0> instead?

163

is preferable imho.

340

Missing NumBitWords?

344

You only call this API with Bits.begin() and it already accessed Bits.end() internally, which makes for a weirdly asymmetric API. Move the Bits.begin() inside the call?

serge-sans-paille marked 4 inline comments as done.

Take review into account.

nikic accepted this revision.Apr 13 2021, 2:53 PM

LGTM

llvm/include/llvm/ADT/BitVector.h
658–659

I'd move these next to the copy/move constructors ... though actually, can we just drop all of these? I don't think the explicit defaulting is necessary in this instance.

This revision is now accepted and ready to land.Apr 13 2021, 2:53 PM
This revision was landed with ongoing or failed builds.Apr 14 2021, 12:29 PM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.Apr 14 2021, 6:04 PM

This broke tests on the expensive checks bot: http://lab.llvm.org:8011/#/builders/16/builds/9331

I have tracked the asan build bot breakage to this change. See below.

I would fix it forward, but the issue isn't obvious to me, and getting things fixed is higher value.

Therefore am reverting.

https://lab.llvm.org/buildbot/#/builders/99/builds/2835

About the actual change: LLVM code tries to be careful with allocations. std::vector is pretty allocation-heavy. Did you check that this doesn't increase malloc traffic?

dexonsmith added inline comments.Apr 14 2021, 8:12 PM
llvm/include/llvm/ADT/BitVector.h
82

BTW, SmallVector<BitWord, 0> should be the same size as MutableArrayRef on 64-bit platforms, whereas std::vector is an extra word. Might be nice to avoid making BitVector bigger.

@saugustine thanks for the revert. I'll investigate that.
@thakis I checked the instruction count and overall execution time and didn't notice much change.
@dexonsmith Yeah that was the plan: switch to SmallVector once that one, hum, validates ;-)

llvm/include/llvm/ADT/BitVector.h
82–85

You read in my mind :-) That's the next step.

Might to good updating the revision before a reland next time :)
It highlights what has changed.

wingrez reopened this revision.Sep 4 2023, 7:57 PM
wingrez added a subscriber: wingrez.

This code snippet was normal before this version, but after this version it produced an assertion failure.

llvm/ADT/SmallVector.h:277: llvm::SmallVectorTemplateCommon::const_reference llvm::SmallVectorTemplateCommon<unsigned long>::operator[](llvm::SmallVectorTemplateCommon::size_type) const [T = unsigned long]: Assertion `idx < size()' failed.
BitVector bv;
auto k = bv.getData();
std::cout << k.size() << std::endl;
This revision is now accepted and ready to land.Sep 4 2023, 7:57 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 4 2023, 7:57 PM