eliot.miranda at gmail.com
Wed Jun 20 00:45:07 UTC 2018
On Tue, Jun 19, 2018 at 4:50 PM, Levente Uzonyi <leves at caesar.elte.hu>
> 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.
> 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
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,
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.
and you are very welcome to experiment with alternative representations.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Vm-dev