Performance optimization on ImmutableMap/ImmutableSet:

- Use a DenseSet instead of a FoldingSet to cache
canonicalized nodes.  This reduces the overhead
of double-hashing.

- Use reference counts in ImutAVLTree to much
more aggressively recover tree nodes that are
no longer usable.  We can generate many
transient nodes while using add() and remove()
on ImmutableSet/ImmutableMaps to generate a final
set/map.

For the clang static analyzer (the main client
of these data structures), this results in
a slight speedup (0.5%) when analyzing sqlite3,
but much more importantly results in a 30-60%
reduction in peak memory usage when the analyzer
is analyzing a given function in a file.  On
average that's about a ** 44% reduction ** in the
memory footprint of the static analyzer.

llvm-svn: 120459

0 files changed, 0 insertions, 0 deletions