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][LTO] cgraph node set.


Inserting anywhere but the end takes an O(n) memmove (once per
element, where element size is 128 right now).
Most insertions are in monotonic increasing order in GCC, so it
doesn't really matter.
Memory size of the word mask (which is currently an sbitmap) can be
greater than storage of the bits if your bitmap is really really
sparse but bit numbers are exceptionally high.

This is pretty rare, but possible.

For random access, it's about 30-40% faster than bitmap.

2008/7/14 Diego Novillo <dnovillo@google.com>:
> 2008/7/14 Doug Kwan (Ãö®¶¼w) <dougkwan@google.com>:
>> That's another alternative.  How efficient is iterating a sparse bitmap?
>
> Iteration is not too bad.  What kills you is random accesses.  Danny
> had another sparse bitmap implementation that was friendlier to random
> accesses, though it had some other drawback I can't remember ATM.
>
>
> Diego.
>

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