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

[Levente Uzonyi]

Hi Eliot,

On Sun, 17 Jun 2018, Eliot Miranda wrote:

> 
> 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.

Well, it wasn't clear if that's a requirement, but I could have figured it 
out, because if you always iterate over the list, you can just keep a 
pointer to the previous node to delete the current node.

If performance is important here, random deletion can still be done in 
O(1) time at the cost of maintaining an external doubly linked list with 
each node having a pointer to the chunk and the chunk using its sole slot 
to point to its list node.

>
> 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.

Nice. :)

Levente

>
>> 
>> Levente
>>