<div dir="ltr">Hi Levente,<div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jun 19, 2018 at 4:50 PM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br>On Mon, 18 Jun 2018, Clément Bera wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
There are still some unlinking, but it's less common so the single <br>
</blockquote>
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).<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
In selective compactor, segments are compacted using unlinking but only <br>
</blockquote>
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.<br>
<br>
Great.<br>
Btw, why did you decide to use a tree instead of a hash table?<br></blockquote><div><br></div><div>To keep it simple.  The scheme really comes from the free lists.  There is either a 32 or a 64 element array with all the free chunks from size 1 to 32 or 1 to 64.  So this gives fast allocation for the common case of a smallish object.  Then what to do with element 0?  A binary tree works well since it is populated only with larger chunks and, given that all chunks of the same size are, effectively, a single node in the tree, the tree typically isn't that large.  That and some very simple balancing hacks keep it from degenerating into a list whenever I've looked at its state (although we might investigate organizing it as an AVL tree; I like AVL trees but they're a lot of work for little gain if in practice a tree doesn't degenerate).</div><div><br></div><div>The use of 32 or 64 elements allows the use of a bitmask word to serve as a non-empty list cache, so that when the system looks for chunks bigger than needed (if a smaller list is empty) it is fast to check the list(s) at 2x, 3x, etc...</div><div><br></div><div>A hash table needs heap space to organize and unlike the binary tree this space may need to grow if the number of free chunks is very large.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I had a look at the tree implementation, and it seems to be a simple binary tree. Is that correct?<br></blockquote><div><br></div><div>Yes.  A binary tree of lists.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Levente<br></blockquote></div><br>and you are very welcome to experiment with alternative representations.<br clear="all"><div><br></div><div class="m_-1459104079426999643gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div>
</div></div>