Il 06/08/2012 13:15, Steven Bosscher ha scritto:
> On Mon, Aug 6, 2012 at 1:07 PM, Paolo Bonzini <bonz...@gnu.org> wrote:
>> Il 06/08/2012 08:54, Steven Bosscher ha scritto:
>>> Hello,
>>>
>>> In PR54146, ifcvt spends a lot of time just clearing memory. This
>>> patch changes the value maps to pointer-maps to fix this issue.
>>>
>>> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?
>>
>> Nice, but perhaps we need a sparsemap to do even better?
>
> If you mean sparseset: no, it won't do any better.
No, I mean "inventing" a sparseset that cannot do boolean operations,
but can store an associative value in a second dense array. That is
sparsemap_insert(m, k, v)
{
if (!sparsemap_contains(m, k)) {
s->sparse[k] = s->members++;
s->dense_keys[i] = k;
}
i = s->sparse[k];
s->dense_values[i] = v;
}
sparsemap_contains(m, k)
{
if (!sparsemap_contains(m, k)) {
return -1;
} else {
return s->dense_values[i];
}
> My first idea was to use a sparseset, but:
>
> 1. The amount of memory allocated is simply too big. In fact, it'd be
> even worse than before: 4*max_regno*sizeof(rtx) instead of "only"
> 2*max_regno*sizeof(rtx).
Yeah, sparseset wastes some memory. I wonder if the dense array should
be allocated separately and even made dynamically resizable, also because...
> 2. sparseset has the same problem of memory clearing (for valgrind,
> see sparseset_alloc).
... only the sparse array needs this clearing, but currently we do it
for both.
> What could work, is to allocate a sparseset once at the beginning of
> if_convert, but I don't see any good reason to add a pair of global
> variables for this.
Yes, this is what I meant. Fast clearing is where sparsesets behave
well, so it makes sense to make them global in that case. What I missed
was that the maps remain small. Otherwise they would also need clearing.
Paolo
