On Thu, 2008-04-24 at 20:23 -0400, Vladimir Makarov wrote:
Hi, Peter. The last time I looked at the conflict builder
(ra-conflict.c), I did not see the compressed matrix. Is it in the
trunk? What should I look at?
Yes, the compressed bit matrix was committed as revision 129037 on
October 5th, so it's been there a while. Note that the old square
bit matrix was used not only for testing for conflicts, but also for
visiting an allocno's neighbors. The new code (and all compilers I've
worked on/with), use a {,compressed} upper triangular bit matrix for
testing for conflicts and an adjacency list for visiting neighbors.
I have also another question. I saw that sparset was used for the
conflict builder. I tried that too when I worked on YARA project. I
even wanted to contribute a generic sparset implementation. But I found
that in general case bitmaps are not worse the sparse sets and much
better if we take a needed space into account. May be you have another
impression? It would be very interesting for me to hear it. I found
that bitmaps have more advanced design than sparsets. I always wanted
to find inventors the bitmaps but never tracked them down.
The sparseset representation is only used for the allocnos_live set.
The old version was a bit vector to match up with the square bit matrix.
Since I changed that to save space, I had to reimplement allocnos_live.
Danny suggested I use a bitmap for that set and I tried it, but I found
for the particular usage of allocnos_live, a sparseset was noticeably
faster than bitmaps. I'll note that the main operations on allocnos_live
are to add allocnos to the set, remove allonos to the set and iterate over
the members of the set and occasionally clear the entire set. These are
all O(1) operations for the sparseset with fairly low constant factors
too. I didn't look too closely, but I'm guessing that the main problem
with bitmaps for this type of usage was the slower iterating over all
of the members of the set versus the sparseset.
Obviously, bitmaps are much better than sparsesets wrt space usage, so
you have to use them sparingly. You wouldn't want an array of these
things! :) But there are use cases where they work very very well.
The currently "live" set is one such use. Another use I have found
where they work well is in the needLoad set used by Briggs' allocator.
Whether you want/should use a sparseset really depends on the number
and type of set operations your particular usage will see. I'm sure
there are many usage cases where bitmaps are superior to sparsesets,
just like there are usage cases where sparsesets are superior. I know
that sounds like a cop-out, but it really does depend on how you're
going to use it.