[Vm-dev] free-chunk-management-in-the-cog-vm

[Eliot Miranda]

Hi Levente,


> On Jun 17, 2018, at 5:36 PM, Levente Uzonyi <leves at caesar.elte.hu> wrote:
> 
>> On Mon, 18 Jun 2018, Ben Coman wrote:
>> 
>> A random thought, I wonder if size-1 chunks can be managed packed into 
> size-2 chunks.
> 
> Or, just use the XOR trick to store each node's two links in a single pointer sized field:
> https://everything2.com/title/Storing+a+doubly-linked+list+using+just+a+single+pointer+field

Alas, while this lovely trick does indeed encode a doubly-linked list in a single field it only works for full traversals.  The xor is of the two neighbours, so to get to the next one needs the prev, and to get to the prev one needs the next.  So one can start from either end but not in the middle.  Clément’s modification is to allow rapid removal without needing to traverse the entire list, so the xor trick is not fit for purpose here.

BTW the compactor I wrote before the current one (SpurPigCompactor preceded SpurPlanningCompactor) used exactly this trick.  It didn’t work for reasons unrelated to the xor trick.  Just mentioning it as proof that I love the technique.

> 
> Levente
>