2007/4/10, Dave Korn <[EMAIL PROTECTED]> wrote:
On 10 April 2007 20:02, Diego Novillo wrote:
>> The obvious way to make the proposed tuples position independent would
>> be to use array offsets rather than pointers. This has the obvious
>> disadvantage that every access through a pointer requires an
>> additional memory reference. On the other hand, it has some other
>> advantages: it may no longer be necessary to keep a previous pointer
>
> I doubt this. We had started with single-linked chains but reverse
> traversals do occur, and they were very painful and slow.
Reverse-traversing an array really isn't all that painful or slow!
>> in each tuple; we can delete tuples by marking them with a deleted
>> code, and we can periodically garbage collect deleted tuples and fix
>> up the next pointers. On a 64-bit system, we do not need to burn 64
>> bits for each pointer; 32 bits will be sufficient for an array offset.
>>
>> I would like us to seriously think about this approach. Most of the
>> details would be hidden by accessor macros when it comes to actual
>> coding. The question is whether we can tolerate some slow down for
>> normal processing in return for a benefit to LTO.
>>
>> If anybody can see how to get the best of both worlds, that would of
>> course be even better.
>
> I've thought about this a little bit and it may not be all that onerous.
> So, if you take the components of a tuple:
>
> next Could be a UID to the next tuple
> prev Likewise
How about delta-linked lists? Makes your iterators bigger, but makes every
single node smaller.
cheers,
DaveK
--
Can't think of a witty .sigline today....
delta-linked lists?
Better one iterator than complicating this with several iterators.
Function prev_of_this_instruction(word) -> word
The singleton (global structure) of prev_of_this_instruction
contains a small cache to accelerate the reverse-traversing.
This cache is like a hashmap of { word this instruction => word prev
instruction }.
If this instruction isn't in the cache then go to the beginning of a BB of this
instruction and start to traverse adding pointers to the cache.
Use LRU/old-age-used/less-frequently-used to replace their entries.
To have many smaller nodes in the heap is better.
J.C. Pizarro :)
