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

[Clément Bera]

> In the end I decided to rebuild the linked lists while sweeping
> afterdiscussing with Eliot. It avoids most of the unlinking operations on
> the linked lists of free chunks.
>
> There are still some unlinking, but it's less common so the single linked
> list for chunk of size 1 is now affordable (I don't see 75% of time spent
> in free chunk unlinking like before on pathological cases).
>
> In selective compactor, segments are compacted using unlinking but only
> segments mostly empty are compacted, so low amount of free chunks of size
> 1. The problem was in the sweep phase and we fixed it.
>
> On Mon, Jun 18, 2018, 14:31 Levente Uzonyi <leves at caesar.elte.hu> wrote:
>
>>  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
>> >>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20180618/c3ab70cf/attachment.html>