vsavchenko added inline comments.
================ Comment at: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:245-246 + /// + /// Complexity: O(N^2) + /// where N = size(What) + RangeSet castTo(RangeSet What, APSIntType Ty); ---------------- ASDenysPetrov wrote: > ASDenysPetrov wrote: > > vsavchenko wrote: > > > That is a bit of a red flag because instantly my intuition tells me that > > > there should be a linear option. > > Unfortunately, `castTo` is N^2 because technically we can call > > `unite`(which is N) inside it N times. > Corrected. > Unfortunately, castTo is N^2 because technically we can call unite(which is > **N+M**) inside it N times. > Unfortunately, castTo is N^2 because technically we can call unite(which is > N) inside it N times. I know why you put N^2, and what I meant was that there is probably a better algorithm than that. And as I said there is a linear algorithm: If you have a smaller type that is, let's say, 8 times smaller than the larger type. We can split the original range set into 8 range sets and unite them. This difference between type sizes is limited (because we don't support integer types of arbitrary bit width) aka is a constant. However, IRL the size of range sets is very small, and this constant factor can make it much slower than your N^2 algorithm. But it doesn't mean that there is no better algorithm and that you HAVE TO call `unite` in a loop N times. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D103094/new/ https://reviews.llvm.org/D103094 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
