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

[Eliot Miranda]

Hi Levente,

On Tue, Jun 19, 2018 at 4:50 PM, Levente Uzonyi <leves at caesar.elte.hu>
wrote:

>
> On Mon, 18 Jun 2018, Clément Bera wrote:
>
> 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.
>
> Great.
> Btw, why did you decide to use a tree instead of a hash table?
>

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

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

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.


> I had a look at the tree implementation, and it seems to be a simple
> binary tree. Is that correct?
>

Yes.  A binary tree of lists.


> Levente
>

and you are very welcome to experiment with alternative representations.

_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20180619/2d50b1f2/attachment.html>