<div dir="auto"><div><div class="gmail_quote"><div dir="ltr"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">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.<div dir="auto"><br></div><div dir="auto">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).</div><div dir="auto"><br></div><div dir="auto">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.</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jun 18, 2018, 14:31 Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu" target="_blank" rel="noreferrer">leves@caesar.elte.hu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> Hi Eliot,<br>
<br>
On Sun, 17 Jun 2018, Eliot Miranda wrote:<br>
<br>
> <br>
> Hi Levente,<br>
><br>
><br>
>> On Jun 17, 2018, at 5:36 PM, Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu" rel="noreferrer noreferrer" target="_blank">leves@caesar.elte.hu</a>> wrote:<br>
>> <br>
>>> On Mon, 18 Jun 2018, Ben Coman wrote:<br>
>>> <br>
>>> A random thought, I wonder if size-1 chunks can be managed packed into <br>
>> size-2 chunks.<br>
>> <br>
>> Or, just use the XOR trick to store each node's two links in a single pointer sized field:<br>
>> <a href="https://everything2.com/title/Storing+a+doubly-linked+list+using+just+a+single+pointer+field" rel="noreferrer noreferrer noreferrer" target="_blank">https://everything2.com/title/Storing+a+doubly-linked+list+using+just+a+single+pointer+field</a><br>
><br>
> 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.<br>
<br>
Well, it wasn't clear if that's a requirement, but I could have figured it <br>
out, because if you always iterate over the list, you can just keep a <br>
pointer to the previous node to delete the current node.<br>
<br>
If performance is important here, random deletion can still be done in <br>
O(1) time at the cost of maintaining an external doubly linked list with <br>
each node having a pointer to the chunk and the chunk using its sole slot <br>
to point to its list node.<br>
<br>
><br>
> 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.<br>
<br>
Nice. :)<br>
<br>
Levente<br>
<br>
><br>
>> <br>
>> Levente<br>
>></blockquote></div>
</blockquote></div></div></div>