This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] bitmap.c: Speed up bitmap_find_bit.


Hello,

> 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).

Zdenek


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]