vsavchenko added a comment.
In D99797#2666565 <https://reviews.llvm.org/D99797#2666565>, @ASDenysPetrov
wrote:
> @vsavchenko
> OK, what do you think of ***adjacency*** feature? I mean it simplifies such
> ranges `[1,2][3,4][5,6]` to `[1,6]`. Is it worth for implementation?
I want to clarify my position here. It's not that I am opposed to this change
in principle, but I want to understand the motivation (a small example will be
sufficient) and I don't want to sacrifice a single bit of performance
efficiency of this part of code.
Even for the `O(N + M)` solution, I'd still be standing strong on keeping the
old functions as is (except for maybe renaming them). Range sets are small and
asymptotics don't work that well when reasoning about the expected performance
benefits and gains.
For this reason, whenever we can, we should have the simplest operation
possible in terms of the number of instructions, ie the constant factor is very
strong here.
================
Comment at:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:128
///
- /// Complexity: O(N + M)
+ /// Complexity: O(N + Mlog(N))
/// where N = size(LHS), M = size(RHS)
----------------
ASDenysPetrov wrote:
> vsavchenko wrote:
> > This most certainly can be done in `O(N + M)` the same way the intersection
> > is done.
> Actually yes, it can. And it was, when I played with different solutions. But
> the code was poor readable. So I decided make it easier to understand to
> bring to review. Of couse I can move further to improve it and retain
> readability. I'll do.
Bring it here and we'll see what can be done on that front. *makeover time!*
================
Comment at:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:146
+ ///
+ /// Complexity: O(N + log(N))
+ /// where N = size(Original)
----------------
nit: `O(N + log(N)) == O(N)`
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D99797/new/
https://reviews.llvm.org/D99797
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
