This is the mail archive of the 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]

[patch][RFC] bitmaps as lists *or* trees


A recurring problem with GCC's sparse bitmap data structure is that it
performs poorly for random access patterns. Such patterns result in
linked-list walks, and can trigger behavior quadratic in the number of
linked-list member elements in the set.

The attached patch is a first stab at an idea I've had for a while:
Implement a "change of view" for bitmaps, such that a bitmap can be
either a linked list, or a binary tree. I've implemented this idea
with top-down splay trees because splay tree nodes do not need
meta-data on (unlike e.g. color for RB-trees, rank for AVL trees,
etc.) and top-down splay tree operations are very simple to implement
(less than 200 lines of code). As far as I'm aware, this is the first
attempt at allowing different views on bitmaps. The idea came from
Andrew Macleod's tree-ssa-live implementation.

The idea is to convert the bitmap to a tree view if the set
represented by the bitmap is mostly used for membership testing, and
not for iterations over the items (as e.g. for bitmap dataflow). A
typical example of this is e.g. invalid_mode_changes, which just
explodes for the test case of PR55135 at -O0.

I haven't tested this patch at all, except making sure that it
compiles. Just posting this for discussion, and for feedback on the
idea. I know there have been many others before me who've tried
different data structures for bitmaps, perhaps someone has already
tried this before.


Attachment: tbitmap.diff.txt
Description: Text document

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