Page MenuHomePhabricator

Simplify BitVector code
ClosedPublic

Authored by serge-sans-paille on Tue, Apr 13, 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.Tue, Apr 13, 7:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Apr 13, 7:34 AM
nikic added a subscriber: nikic.Tue, Apr 13, 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.Tue, Apr 13, 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.Tue, Apr 13, 2:53 PM
This revision was landed with ongoing or failed builds.Wed, Apr 14, 12:29 PM
This revision was automatically updated to reflect the committed changes.

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.Wed, Apr 14, 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.