This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [new-regalloc] What is the status on current sources
On Sat, Feb 10, 2001 at 01:26:03PM -0500, Daniel Berlin wrote:
> On Fri, 9 Feb 2001, Zack Weinberg wrote:
> >
> > This will make three different bitmap systems in gcc (sbitmap, bitmap,
> > and yours). They all have the same basic interface, but different
> > back-end representations. Do you think it would be feasible to merge
> > them all into some sort of parametrized thingy?
>
> Sure.
>
> It might actually pay, however, to make the parameterization be based on
> "speed" or "space", or something, so that we could build a bitmap that
> automatically switched representations when it got too large, or
> something.
That would be useful, but I'm not sure if we can make the
parametrization as simple as "speed" / "space". sbitmaps end up being
slow when they get large and sparse, just because of cache pollution.
"dense" / "sparse" might be a better fit. I'm not sure if we always
know whether or not a given bitmap will be dense.
Also, the tradeoffs between bitmap.c's list of (offset, length) blocks
and your run compression are not obvious. We need to investigate
that.
There's also the extremely sparse set algorithm from the Morgan book
(pp. 90-92; cites _ACM Letters on Programming Languages and Systems_
2(1-4): 59-69). This is O(1) for insert, delete, and lookup,
O(members) for scanning, but needs two ints per set member so it can
take a lot more memory in the worst case.
> Maybe I should just move this stuff into libiberty anyway?
I'm in favor of moving general data structures to libiberty just on
principle.
zw