On Fri, 2012-07-27 at 15:40 +0200, Richard Guenther wrote: > On Thu, Jul 26, 2012 at 11:57 AM, Steven Bosscher <stevenb....@gmail.com> > wrote: > > On Thu, Jul 26, 2012 at 11:23 AM, Richard Guenther > > <richard.guent...@gmail.com> wrote: > >> Ok! Thanks for adding this exhaustive documentation. > > > > There's more to come! I want to add some explanations to ebitmap, > > pointer-set, fibheap, and splay-tree as sets, and add a chapter in the > > gccint manual too. > > > > Now if only you'd document those loop changes... ;-) > > Eh ... > > > > >> Btw, ebitmap is unused since it was added - maybe we should simply remove > >> it ...? > > > > I wouldn't remove it just yet. I'm going to make sure that bitmap.[ch] > > and ebitmap.[ch] provide the same interface and see if there are > > places where ebitmap is a better choice than bitmap or sbitmap (cprop > > and gcse.c come to mind). > > Btw, just looking over sparseset.h what needs to be documented is that > iterating over the set is faster than for an sbitmap but element ordering > is random! Also it looks less efficient than sbitmap in the case when > your main operation is adding to the set and querying the set randomly. > It's space overhead is really huge - for smaller universes a smaller > SPARSESET_ELT_TYPE would be nice, templates to the rescue! I > wonder in which cases a unsigned HOST_WIDEST_FAST_INT sized > universe is even useful (but a short instead of an int is probably too > small ...)
Another option for sparse sets would be a templatized version of Pugh's skip lists. Iteration is the same as a linked list and random access is logarithmic in the size of the set (not the universe). Space overhead is also logarithmic. The potential downside is that it involves pointers. Bill > > Richard. > > > Ciao! > > Steven
