Pool allocators for purely functional data structures
Jon Harrop
I’ve tinkered with pool allocation of purely functional data structures using different techniques. One is to preallocate a block of elements and claim them in turn using CAS. References to old versions refer to the end of this data structure, oblivious to new writes outside the range they can see. This greatly reduces the stress on the GC by allocating fewer larger heap blocks but I have not seen performance gains on .NET, probably because its GC is efficient and because initializing a value allocated from the pool can incur the write barrier (whereas initialization from the GC’s nursery does not).
Has anyone else been doing similar things? Any successes or failures to report?
I should also note that there is potential for integration with the GC in this context. The VM knows that each pool-allocated value is only assigned once so it could skip the write barrier.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.