This is the mail archive of the
mailing list for the GCC project.
Re: [patch] bitmap.c: Speed up bitmap_find_bit.
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: Jeffrey A Law <law at redhat dot com>
- Cc: Diego Novillo <dnovillo at redhat dot com>,Kazu Hirata <kazu at cs dot umass dot edu>,"gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 25 Nov 2004 20:17:30 +0100
- Subject: Re: [patch] bitmap.c: Speed up bitmap_find_bit.
- References: <firstname.lastname@example.org>
> On Thu, 2004-11-25 at 11:46 -0500, Diego Novillo wrote:
> > True, but we should also try and optimize the data structure itself. We
> > can't always avoid random accesses to bitmaps.
> > Perhaps we should have another instance of bitmaps more streamlined for
> > non-linear references?
> They're call sbitmaps.
you have problems with them if you do not know number of bits in
advance. It also is not efficient to use them if the considered
set is sparse. Also iterating over elements in sbitmap is inefficient.
I know about several places where we use bitmaps simply because they are
the better choice from two bad ones.
It might be worthwhile to try other possibilities for representing sets
(several possibilities derived from various kinds of trees or
something similar to Van Emde-Boas queues or their variants
seem like good candidates OTOH).