On Wed, Mar 6, 2013 at 5:06 PM, Jan Hubicka wrote: > And for the RFC, i also find it interesting experiment. I implemented some > time ago splay tree based bitmap with API same as bitmap's but never attempted > to put it to mainline since Danny introduced his ebitmap and there was a lot > of > discussion about whether one needs more than one bitmap in the compiler. I
Right, I think the ebitmap.c experiment shows that there is *not* room for another bitmap implementation. This is why I developed these splay-tree bitmaps using the same data structures as the existing linked-list sparse bitmaps: Not another bitmap, just another way of looking at the existing bitmap. I required that changing the view of the bitmap from linked-list to splay tree and vv. to be almost free. > never experimented with bitmap.c change itself, just tested that replacing all > bitmaps by tree based ones causes quite some memory consumption on RA side > (with old RA) because bitmaps are pretty good for regsets they were introduced > for. Memory consumption as in higher peak memory? That cannot happen with my splay-tree bitmaps. They take exactly the same amount of memory, independent of whether the current view on the bitmap is linked-list or splay tree. As for cache behavior or number of memory operations (loads, stores) I think this is directly correlated to the lookup success ratio, hence the access pattern, and so if the right view on the bitmap is selected for the right circumstances then the number of memory ops should also be no worse in splay tree view than in linked-list view. Another idea I'm currently (right now on gcc17 ;-) working on, is a trivial speed-up for bitmaps used as regsets. The idea is that bitmap_find_bit should look at head->first if head->current is not the element containing the sought bit, and *not* update head->current if head->first is the right element. This speeds up regsets because a common access pattern is to look at sets containing both pseudos and hardregs, and on most targets all hardregs are in head->first. Not updating head->current preserves a pointer to the latest accessed pseudos. I'll implement this idea and come back with some timings. Ciao! Steven
