On Wed, Apr 11, 2007 at 04:55:02PM +0100, Dave Korn wrote: > On 11 April 2007 12:53, Andi Kleen wrote: > > > Richard Henderson <[EMAIL PROTECTED]> writes: > > > >> On Tue, Apr 10, 2007 at 11:13:44AM -0700, Ian Lance Taylor wrote: > >>> The obvious way to make the proposed tuples position independent would > >>> be to use array offsets rather than pointers. > >> > >> I suggest instead, if we want something like this, that we make > >> the references be pc-relative. So something like > > > > If you go this way (and require special GC/debugger support) you > > could as well xor next/prev too and save another field. > > > > Adding a xor is basically free and much cheaper than any cache miss > > from larger data structures. > > Using a delta is even better than an XOR, because it remains constant when > you relocate the data.
You can xor deltas as well as pointers. The concepts are independent. Delta alone doesn't save anything on 32bit -- and on 64bit only when you accept < 2GB data (which might be reasonable for a basic block, but probably not for a full function). xor always halves the space needed for links. > > > The only thing that wouldn't work is that when you have a pointer > > to an arbitary element (without starting from beginning/end first) > > you couldn't get previous or next. > > You need a pointer to two consecutive nodes to act as an iterator. > > However we already discussed the whole idea upthread and the general feeling > was that it's a whole bunch of tricky code for a small saving, so not worth Is it tricky? You just need some abstraced iterators and a special case in the GC. And some gdb macros. I wrote a couple of xor list implementations in the past and didn't fid it particularly tricky, but given that was without any GC. > doing in the first iteration. Maybe as a future refinement. See the earlier > posts in this thread for the discussion. When you need to go over all the code anyways it would make sense to do such changes in one go. Or at least move to abstracted iterators early :- if you do that then changing the actual data structure later is relatively easy. Both xor list and deltas can be hidden with some care. -Andi
