[PATCH]: Efficient sbitmap based bitset

[Daniel Berlin]

Richard Henderson <rth@redhat.com> writes:

> On Mon, Aug 20, 2001 at 10:56:32AM -0400, Daniel Berlin wrote:
> > Just so people don't think it's only a bitmap replacement.
>
> I understood that.
>
>> Do we know the average lifetime of regsets?
>
> I wonder how much trouble you'd have garbage collecting them.  There
> aren't many that are live across passes, so there shouldn't be many
> that need marking.  In fact, the only long lived regsets I can think
> of are global_live_at_{start,end}.

I've got this going somewhat okay.
The real problem is the use of varrays.
It's either make them able to be garbage collected, or something.
This would mean i'd have to be smarter about growing the ebitmap, so
we don't waste a ton of memory (since we can't realloc garbage
collected memory).
The rest is cake, i've already got gc'able sbitmaps and  ebitmaps,
replacing regsets.
We just leak the varray.

Should I go all the way, and add the ability to make garbage collected
varrays, or is this a bad idea until we have an incremental collector?
>
> It'd still be a good idea to provide a method to free them early, since
> we can save some amount of wastage that way.  A free list that gets
> zapped on collect (a-la unused_insn_list in lists.c) would seem ideal.
>
>> > I also wonder if better memory density could be had by doing
>> > some by-hand memory allocation.  That is, N 64 byte blocks of
>> > memory can be allocated out of raw pages without overhead, 
>> > whereas you'll waste at least 2 pointer's worth with malloc.
>> Hmmmm.
>
> Incidentally, allocating via ggc_alloc largely takes care of this.
> On a 64-bit system, with 64-byte hunks, we have 7 words overhead 
> per 128 hunks.
>
>
> r~

-- 
"When I woke up this morning my girlfriend asked me, "Did you
sleep good?"  I said, "No, I made a few mistakes."
"-Steven Wright