[LLVMbugs] [Bug 5174] ImmutableMap is slow

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=5174


Ted Kremenek <kremenek at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID




--- Comment #1 from Ted Kremenek <kremenek at apple.com>  2009-10-13 12:47:05 ---
I suspect that this is probably a case of using the wrong data structure for a
given problem.

If all you are doing is using ImmutableMap just like you would use DenseMap, it
is never going to come as close to the performance as DenseMap.  It uses a
balanced-AVL tree, and allocates new tree nodes whenever you do an insert and
removal in order to really leave the original map untouched.  Algorithmically,
DenseMap is just going to leave it in the dust if all you care about are doing
lookups and insert/deletions to a single map.  Where ImmutableMap is useful for
cases where you need (many) multiple copies (or versions) of the same map
around at the same time.  DenseMap would not be a good data structure for such
scenarios.

ImmutableMap also has the invariant that no matter what *order* you
insert/remove values from the map,  you will still get the same physical map. 
The ImmutableMap object is just a smart pointer to an AVL tree node (the root),
and operator== is implemented using a simple pointer comparison of the two root
nodes.  This is really value for the static analyzer, as it frequently does
comparisons between maps.  This comes at a cost, however, as such
canonicalization of the maps takes work (via a FoldingSet).

Is there a reason you need to use ImmutableMap for GVN?


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.