bera.clement at gmail.com
Mon Jun 18 14:10:12 UTC 2018
> 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>
>> >>> On Mon, 18 Jun 2018, Ben Coman wrote:
>> >>> A random thought, I wonder if size-1 chunks can be managed packed
>> >> size-2 chunks.
>> >> Or, just use the XOR trick to store each node's two links in a single
>> pointer sized 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
>> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Vm-dev