Page MenuHomePhabricator

[analyzer][solver] Redesign constraint ranges data structure
Needs ReviewPublic

Authored by vsavchenko on Aug 24 2020, 8:30 AM.

Details

Summary

ImmutableSet doesn't seem like the perfect fit for the RangeSet
data structure. It is good for saving memory in a persistent
setting, but not for the case when the population of the container
is tiny. This commit replaces RangeSet implementation and
redesigns the most common operations to be more efficient.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
In D86465#2235289, @NoQ wrote:

If the numbers are confirmed to be as good as what i've sneak-peeked so far, that should be pretty amazing. Also whoa, test coverage!~

I'll add the charts with performance in the next couple of days

WDYT about moving introducing a generic "SmallImmutableSet" in llvm/ADT to back your implementation?

Oof, it is not really possible. First of all, existing RangeSet didn't really ensure that ranges do not intersect (add is/was not checking for that), and this is left for the user. Additionally, it is designed and optimized specifically for RangeSet queries and operations. Like intersect and contains in a more generic Set sense mean entirely different things.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
92

Sounds reasonable, I'll give it a shot!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
280

😊

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
206

It is due to shenanigans in test fixtures implementation. I didn't find a better workaround and other tests for other components also use this-> as far as I checked :-(

vsavchenko added inline comments.Aug 25 2020, 1:10 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
119

Surprisingly this is not the case, it is cheaper to do whatever you want on small vectors on the stack and check if we already allocated it.
So, it is a deliberate choice to do it this way (you can see it in the comment inside of the makePersistent function.

vsavchenko added inline comments.Aug 25 2020, 2:18 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
92

On the second thought, it's not going to be pretty. I still will need to allocate SmallVector<..., N>, where N is a compile-time constant, so it would be a big old switch where I "convert" run-time values into compile-time values so-to-speak.

Additionally, the involvement of SmallVector doesn't seem to be necessary at all because in this setting we don't use the main feature of it that it can grow larger than this size onto the heap. So, we can simply do the same trick with ArrayRef and std::array, but with less ambiguity.

However, one of the benefits of the current approach is "let's allocate as little as possible". It does the operation, checks if we allocated space for a container with these contents, and allocates it only if not. It is MUCH cheaper to do the operation and find out that we already have one like this or copy it to the newly allocated place than allocating it every time.

This is a huge change, I've got pretty tired at the end of the review.
I haven't checked the test-cases too deeply.

I've found only minor typos, clarity enhancement opportunities etc. nothing serious.
It was awesome to see how this code can be improved, even becoming comprehensible.

Sorry for my nit spam if it needs further discussion - but it looks good to me.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
34–35

I don't think we should inherit from standard type. It should be a private member instead.
https://quuxplusone.github.io/blog/2018/12/11/dont-inherit-from-std-types/#never-ever-inherit-from-any-std

49

We have dump methods all over the place. Except this.
I propose to rename this to dump.

51–60

It's a good practice to define comparison operators as friend functions inline.
Even if we don't rely on implicit conversions.

114

I think it should be std::size_t.

122–127

What about merge or combine? I know that union is a keyword thus we can not use.

139

Why don't we call this createSetOf?
And createEmptySet.
I know that we don't create the empty set, but then what does a factory if not create stuff?

153–164

I think an example would be awesome here.

174–178

Why does this operation take O(N) time? Shouldn't be O(logN) instead?

194–197
199–200
207

As commented later, this function worth to be documented.

211–212

Why do we need to explicitly spell the RangeSet here?

214–215
217–219
226

class Factory is a nested class of RangeSet, so it can already access all private parts.

229–232

If this is the Rule of 5, where is the defaulted destructor?

257–264

Finally, we got this, awesome!

266–275
294–295

If we implement equality, we should also support inequality.

295–296

Missing explicit.

295–299

TBH, I don't even know what the pin function does.
Should we consider a more descriptive name instead?
Maybe some docs would come handy too.

297

If it's a read-only operation why don't we take by value? Just like contains does.
If it has side-effects which modify the Point, why is that not documented here?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
146–149

Off-topic: Why do the Allocate and the similar allocator functions return T* if there is NO living object there (yet).
There will be, only if the placement constructor called...
I highly agree with you using void * there.

177–178
181–188

Previously we had an early empty check here.
Why don't we have that now?
Same question for the other overload.

280

I agree. These are black magic. xD

321–324

It could definitely bear a longer name.

324–329

What.size() seems not justified here.
As you described previously, there is a case when the resulting range will have one more range then the previous one had.
negate([MIN, X] => [MIN,MIN] U [-X,MAX]

366–369
374

It's unfortunate to refer to the next subrange by the ++Second.
Since operator++ has a side-effect I would recommend the Second+1 instead.

383

It's probably a personal taste though.
I think better to use the more verbose way incrementing an iterator if you are in the body of the loop.
It catches more attention.

431
497–498

Can we use range-based for loops?

vsavchenko added inline comments.Aug 26 2020, 1:47 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
114

Yeah, I didn't see a unified stand of the community on this matter. It looks like both options are pretty widespread. I mimicked SmallVector.h, but I can easily change it.

122–127

Maybe, but the real union function is not present. And I think that in the original code it is add to hint that it's not really a union and nothing complex is done here. Maybe something like mergeUnchecked would work.

153–164

Agree, I simply copy-pasted the comment, but it would be better to expand it a bit because it might be confusing.

174–178

We still create a copy of an old vector to maintain persistence, that's why it's O(N).

194–197

The same thing with this comment, I think I'll rework it even more

199–200

+1

207

I didn't think that it's necessary because of the fact that it's private, but it's pretty important, so I'll do it.

211–212

Good point!

214–215

+1

217–219

+1

229–232

It is, and it is forgotten, good catch!

294–295

Sure!

295–296

More like missing /* implicit */ because it is intentional

297

Good point. Essentially it modifies the argument the same way pin functions do - by changing its type. I'll add the comments

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
146–149

100% agree. It might be a source of mistakes where the type system doesn't help.

177–178

I don't really see the benefits of one way over another and as I said in another comment, I don't really like to pay for an extra copy with iterators as just a rule of thumb.

181–188

I'll add assertions checking for non-emptiness.
Essentially, it is a private function and the callers ensure this precondition.

321–324

I think that there is nothing wrong in spelling out std::swap twice.
And do we have a naming convention for lambdas, is it a variable or a function from a naming perspective?

366–369

OK

374

NP

383

It basically makes it Second++, and even though for these iterators it doesn't really matter I prefer not to pay extra copy when I don't need it.

497–498

We sure can, I wanted to change it but forgot

Here are some benchmarking results.
In docker:



Natively on my Mac (no memory measurements due to this issue during psutil installation):

Here are some benchmarking results.
In docker:



Natively on my Mac (no memory measurements due to this issue during psutil installation):

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)
Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

steakhal added inline comments.Aug 26 2020, 5:49 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
122–127

Now I get it. Let's keep it as-is.
Might worth highlighting the **with all ranges from both** part though.

174–178

Thanks. BTW I just forgot about this comment :D

295–296

It doesn't have a too long identifier.
The users can always refer to it auto R = RangeSet(...), so we still don't repeat ourselves.
Do you have any particular counterexample?
Probably the tests will become slightly more bloated but eh. whatever.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
177–178

Iterators supposed to be cheap to copy. That is why we take them by value all over the place.
IMO it should boil down to the very same codegen in both cases. https://godbolt.org/z/8x1zMh

To prove it, I disassembled the following functions in release clang build:

// _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &raw_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  --It;
  return It->To();
}
// _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &std_prev_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  return std::prev(It)->To();
}
(gdb) disassemble _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function raw_rangeset_iterator(clang::ento::RangeSet):
   0x0000000006102b10 <+0>:	mov    (%rdi),%rax
   0x0000000006102b13 <+3>:	mov    -0x8(%rax),%rax
   0x0000000006102b17 <+7>:	retq   
End of assembler dump.
(gdb) disassemble _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE:
   0x00000000061040d0 <+0>:	mov    (%rdi),%rax
   0x00000000061040d3 <+3>:	mov    -0x8(%rax),%rax
   0x00000000061040d7 <+7>:	retq   
End of assembler dump.
321–324

That's a good question :)
I would say that its a variable, since you can mark it const, otherwise you could overwrite it. xD But that's a different story I think.
About the swap thingie, its a good practice to respect ADL for functions which know to be used via ADL.
Even if we don't depend on ADL in this particular case.

vsavchenko marked 21 inline comments as done.

Fix review remarks

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)

Thanks 😊

Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

The measurements fluctuate quite significantly and as you can see the means for both old and new experiments for oatpp are pretty close. So, I would say that the memory differences are not conclusive.
This being said, the performance measurements should also be taken with a grain of salt. We can't really say that we get 5-10% performance improvement for sure, but that analysis tends to be faster instead.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
51–60

It doesn't seem like there is a single opinion on this in the codebase.

139

The naming is this way to be consistent with ImmutableSet::Factory

295–296

These constructors are private and used in Factory methods. IMO they make those methods less cluttered.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
321–324

I'm sorry but I still don't get the importance of dropping std:: here.

Previously, I liked this. Now I love it!
The benchmarks look promising as well.

I think I can not convince you about not modifying iterators using ++,--, etc. outside of loop-expressions. So be it :D

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
49

How about marking this LLVM_DUMP_METHOD?
Also, defining the operator<< would come handly later.

51–60

Okay.

110

Shouldn't we call this const_iterator?

139

Makes sense.

209
211
278

Btw in C++20 we will have a way expressing this: explicit(false)

281–290

Aww, excellent. Thanks.

295–296

Okay.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
321–324

Since we don't rely on Argument Dependent Lookup in this particular case, both versions do the same.
So it's perfectly fine as-is.
You should interpret my previous comment in a broader sense, like a guideline.
Which is meaningful mostly in generic programming.

326
462–470

It might be overkill, but we can do this using transform.

495–507

Hmm, we could simplify this further, assuming Range::operator<< is defined.

Here is my five cents. I haven't done with the review yet. I'm gonna return to it a bit later.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
56

I'm not sure about optimizations but it seems like it could have less commands by omiting this.

139

IMO function's name should match to what it does. If it creates smth, so its name should starts with create. Even if all other functions have misleading names it doesn't mean we are delegated to ignore this fact.
My another suggestion is that Set is a common term to RangeSet. So I'd prefer to use getRangeSet instead.