On 11 April 2007 17:05, Andi Kleen wrote:
>>> 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.
No, you've misunderstood. You can't "xor deltas" because there is only one
of them. Go read the link that explains what a delta-linked list is. It's
the *exact* same as what you're describing, only instead of storing the XOR of
the next and prev pointers, you store the difference between them. You're
changing the xor operation for a subtract, nothing else. This has the
advantage that the delta doesn't need recalculation if you move the whole
memory block en-masse to a new address, unlike an xor.
>> 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.
Yes, I'm aware of the elementary principles of software engineering, as is
everyone else in the discussion. If you wouldn't mind *reading* the earlier
discussion, rather than insisting on repeating it word for word...
> 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.
I think the real point is that the tuples implementation is a big enough and
risky enough and resource-consuming-enough change already to not want to get
fancy about it. Iterative, incremental: we can change to delta pointers at a
future time if we decide the memory savings outweigh any potential code
obfuscation.
> 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.
I don't see you offering to actually do any of the *work*, just repeating an
idea that's already been suggested and that the people who actually /are/
going to do the work have politely declined as being nonessential extra effort
for little reward.
cheers,
DaveK
--
Can't think of a witty .sigline today....
