martong added a comment. > So I think the most valuable optimizations are low-level optimizations to > `ImmutableMap`. There were a few suggestions on the mailing list to use > something more modern than the AVL trees under the hood but I don't think > authors found much success with those.
Back then I was experimenting <https://github.com/martong/llvm-project/compare/febe75032f6f8322cce1dcbba11a44559aaa14e3..0fda74ee6a5123fbf1f6f6e7945f7c2c160c2ff7> by replacing some of our `ImmutableMap` instances with an alternative implementation. I've started with `Environment::ExprBindings` because profiling showed that as the most frequently used. I've chosen `immer::map` as an alternative immutable map implementation. It seemed to be very promising because of - the applied Relaxed Radix Balanced Tree implementation <https://public.sinusoid.es/misc/immer/immer-icfp17.pdf> - efficient batch manipulations <https://sinusoid.es/immer/design.html#efficient-batch-manipulations> . Results: I could make the LIT tests pass, except two checks. The performance was not promising though. The run-time was similar that we had with the AVL trees, however, the memory consumption was 5-10x higher! Consequently, I've abandoned the prototype. But, I think an **//efficient batch manipulation implementation with the existing AVL based//** `ImmutableMap` might be worth to experiment with further. > - From high-level perspective almost half the time is spent in mark-and-sweep > garbage collection in `ExprEngine::removeDead()`. Which can't really be cut > as running `removeDead()` less often only increases the analysis time as it > makes the maps larger and therefore slower to access. And it's also hard to > optimize because the procedure is very complicated and fragile and very few > people actually understand how it works. Yes, this is also aligned with my measurements. There are analyzer options to manipulate when the `removeDead` is called, before every Stmt, or before every basic block, or never. Actually, the last option is meaningless, because renders both the engine and many checkers faulty. The `before every basic block` option might still be worth to experiment with, but I could not find reasonable arguments to change to that yet (I cannot recall, but some lit tests were failing miserably with that option too). CHANGES SINCE LAST ACTION https://reviews.llvm.org/D131707/new/ https://reviews.llvm.org/D131707 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
