On Tue, 2007-04-10 at 16:03 -0400, Diego Novillo wrote: > Dave Korn wrote on 04/10/07 15:39: > > > Reverse-traversing an array really isn't all that painful or slow! > > Instructions are not laid out in an array. Insertion and removal is > done constantly. It would be very expensive to use arrays to represent > basic blocks. Insertions and deletions are all too common. > > > How about delta-linked lists? Makes your iterators bigger, but makes > > every > > single node smaller. > > Worth a shot, I guess. Don't recall what other properties these things had.
Personally, just stick with the double linked lists, be it via pointers or array index. Any of these other suggestions either complicate the algorithms or slow down traversal or both to save that word of memory and slow down the initial implementation. These details are easily changed after the initial TUPLE implementation by replacing the meat of the next/prev iterator. There will be lots of time for everyone to try their favorite double linked list alternative before we write TUPLES out to a file in some production compiler and commit ourselves to specific memory footprint. As long as the entire thing has a clean interface, changing details like this is trivial. Whats important is whether the proposal meets what we expect our future needs to be, such as LTO and such. Have we missed anything critical... Andrew
