[cfe-dev] [Analyzer] Attempting to speed up static analysis

[Ted Kremenek via cfe-dev]

> On Aug 26, 2015, at 8:59 PM, Gábor Horváth <xazax.hun at gmail.com> wrote:
> 
> So ImmutableMap right now uses an AVL tree, which has O(log(n)) complexity for lookup, insertion and deletion. Finger search trees, however, can be implemented as immutable data structures, and they have amortized O(log(n)) lookup and amortized O(1) insertion and deletion (source: https://en.wikipedia.org/wiki/Finger_search_tree <https://urldefense.proofpoint.com/v2/url?u=https-3A__en.wikipedia.org_wiki_Finger-5Fsearch-5Ftree&d=BQMFaQ&c=eEvniauFctOgLOKGJOplqw&r=UVc407_CCx3FapxjS2xZ9jo4Q91upSGpJHRF8fPPYVY&m=ZSn2Xpd2bzTg-eJGSZwPHL5YX99ATIUerX2pwnRrOyU&s=ua5pVdOaNO6HMJElFSPe5UheXE8vDgUI0q6MD5oKVJo&e=>). If inserting a value into the map is the most frequent operation this could be a huge win. 
> Ben, if I am not mistaken, this might be worth to investigate.


That’s a great insight.  That indeed could be a huge win.  We would need to evaluate both the memory and CPU impact of the change, and big-O isn’t everything.  Sometimes the constant factor is important, especially if the majority of maps have a small number of elements.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150826/de4f42ab/attachment.html>