df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Jan Hubicka <jh@suse.cz> writes:

>> Don't bother, i already did it.
>> You'll note that reload makes too many bitmaps, and the 16-24 bytes
>> more overhead + the empty array pointers that the ebitmap takes causes
>> 100-150 meg more memory.
>> Just another point that we shouldn't up and replace them wholesale,
>> rather do it incrementally.
>> 
>> I have resolved this problem by reworking the internals to
>> not need to store empty words at all (ie not even pointers to them).
>
> How did you accomplished that?
You can keep an array only containing the set words (where words in
this whole email means whatever size cluster of real words we actually
use as the array element, it's currently 256 bits)

It requires possible memory moving for setting/clearing bits,
unfortunately.
However, it seems single bits are set/clear generally within given clusters
of 256 bits (at least for regsets), so i make the block size 256 bits
to account for this (so that, in general, we only move memory for the
first set of a bunch of regs, causing the rest to get lost in the
noise).

The worst case memory is N + N/256, where N is the number of *bits*,
for a completely full vector. 
Which isn't too bad, since you shouldn't be using them for completely
full vectors anyway.
Current bitmaps are N + (pointer size * 2 * (N/128)) (I'm in the
middle of Torts, so i'm not positive about this, i'm calculating based
on a first and next pointer and a block of 128 bits)

In order to set or clear a bit in a word that was zero
before, or becomes zero, requires memcpying a contiguous set of
blocks.

This word mask is why i needed to make sbitmaps work properly for
different size 
sbitmaps, because the word masks could be different sizes, but the
destination word mask will always be big enough to hold the result (we
make sure of it).
Before, it would always choose the size of the destination sbitmap,
and assume the input sbitmaps were the exact same size, and end up
performing the logical operation or whatever on random memory, and
storing that into the result, if either of the inputs were smaller
than the destination.

> Is that contained in the updated ebitmap patch?
Not a submitted one.


-- 
"Everywhere is walking distance if you have the time.
"-Steven Wright