[LLVMdev] Efficient Constant Uniquing

[Meador Inge]

On Wed, Feb 1, 2012 at 9:56 PM, Talin <viridia at gmail.com> wrote:

> Chris asked me to look into improving the current sad state of
> ConstantUniqueMap, and by coincidence Meador Inge started working on the
> same thing on his own initiative, so I'm writing down a concrete proposal to
> make sure we're not working at cross purposes.

I was going to try an implement this using a folding set, but the
implementation that
you have posted on PR1210 is simpler than what I was working on.

> The ConstantUniqueMap template class is used to store unique instances of
> ConstantStruct, ConstantVector, ConstantArray, ConstantExpr and InlineAsm
> objects. As implemented, this class has a number of problems: For one thing,
> the map keys contain a std::vector, meaning that just to do a find()
> operation you need to allocate memory. Also, it keeps two copies of the
> operands: One copy lives inside the Constant as part of the regular operand
> list, and a second copy is stored as a std::vector as part of the map key.
> So if you have a 1000-element constant array, that's actually 2000 *
> sizeof(Constant*) worth of memory consumed.

I verified this with some quick benchmarks using your latest patch.  In one case
containing 2000 array constants each with 2000 elements where no two array
constants are identical I saw a 52.73% decrease in the amount of
memory allocated.  The differences I saw with execution time are negligible.

Overall your patch seems reasonable.

-- 
# Meador