Bulk allocation and partial deallocation for tree data structures.

[Filip Bystricky via Digitalmars-d-learn]

On Tuesday, 4 July 2017 at 03:52:39 UTC, Moritz Maxeiner wrote:

First of all thank you for your responses!

> On Tuesday, 4 July 2017 at 02:53:00 UTC, Filip Bystricky wrote:
>> On Tuesday, 4 July 2017 at 01:56:11 UTC, Moritz Maxeiner wrote:
>>> [...]
>>
>> However, in many cases it is unacceptable to have to prevent 
>> the whole block from being freed (especially if the memory is 
>> managed by a compacting gc).
>
> Then you must adjust your acceptance parameters, because:
> Eventually (down the parent Allocator call chain) you will have 
> to get the memory from the operating system, and AFAIK they 
> only support deallocating via pointers to the beginning of a 
> previously allocated block;

You're right, this would only work for a layer on top of the 
system allocator, such as regions.

> let PartiallyDeallocatableAllocator (PDA) be our Allocator 
> implementation supporting partial deallocations via such a 
> parent Allocator (Parent) that can only (de)allocate in whole 
> blocks.
> That means even if Parent collects garbage it will not be able 
> to allocate memory from within a block previously allocated (by 
> PDA calling Parent's allocate) until that (whole) block has 
> been been deallocated in Parent, either explicitly (by PDA), or 
> implicitly by being collected.
> And since PDA will want to track deallocated subblocks and hand 
> them out in its own `allocate`, bypassing Parent when feasible 
> (otherwise what's the point of supporting partial deallocations 
> if you can't reuse the freed memory), it will have to have 
> pointers to these subblocks, i.e. even if Parent collects 
> garbage, PDA will block the collection, anyway (live pointers 
> into the block).
You're right, but I think it's sufficient to allow the PDA to 
hold on to the whole block, provided it can re-allocate chunks of 
partially deallocated blocks.
>
>> I think the feature would work better as an additional 
>> allocator primitive, which should be easy to implement for 
>> most allocators that support reallocate (e.g. bitmapped-block 
>> and free-list allocators).
>
> I don't see how reallocate helps here, as you can only 
> grow/shrink towards the end of a block, not the beginning (so 
> you can only do mimick partial deallocations at the end of a 
> block).

I meant rather that I think that what makes it possible for 
allocators to implement reallocate should usually make it 
possible to implement partialDeallocate. For example, a free-list 
allocator that tracks blocks by pointer and length will probably 
realloc by splitting a block into two. Well, you could split a 
block in similar ways to partially deallocate it. Another example 
would be a bitmapped block allocator: just clear all the bits of 
the blocks you want to deallocate (in this case a block is a 
fixed-length chunk, and the allocation comprises several blocks).

You're right, realloc doesn't help, and nor do any of the other 
primitives. This is why it would make more sense as its own 
primitive.

>
>> In the meantime I realized that since a child node can only 
>> [...]
>
> Good to see that you found an easier solution :)


On Tuesday, 4 July 2017 at 04:11:11 UTC, Moritz Maxeiner wrote:
> On Tuesday, 4 July 2017 at 03:13:14 UTC, Filip Bystricky wrote:
>> Oh and I forgot to mention: another use-case for this would be 
>> for arrays. For manually managed arrays like 
>> std.container.array, it would make it possible to transfer 
>> ownership of individual objects from the array back to the 
>> program after the array goes out of scope.
>
> Not sure I understand you here: If an instance of such a manual 
> array implementation goes out of scope it must destruct (if 
> they are objects and not primitives) and deallocate its 
> elements. There is no ownership transfer going on here (and who 
> would be the target, anyway?).

I was thinking of a Range of some large value type T, that stores 
values in a T[], but that can give ownership of an elements by 
splitting the backing array into two parts, before the element 
and after it, then returning a Unique!T pointer to the element. 
Then whether the range or the Unique!T goes out of scope first, 
their corresponding "owned" memory will be deallocated.
But I realized that in this case it would probably be less 
overhead to just store the values as a (Unique!T)[].

>
>> For gc slices, it could enable some gc implementations to 
>> deallocate parts of an array even if there are still 
>> references pointing inside that array.
>
> I'm fairly certain the necessary bookkeeping logic for partial 
> deallocations will outweigh any gain from it. In the case of 
> such gc slices, I would rather just memcpy to a new, smaller 
> block and update pointers to it (-> a moving GC).

But sometimes you have a huge chunk of memory and want to free 
half of it, but don't want to copy the other half (or maybe you 
don't have enough RAM to do so). One operation is O(n) (n = size 
of the new, smaller block), the other is O(m) (m = the number of 
chunks you're splitting the block into). That's why realloc 
exists, and we don't just always memcpy to a new, smaller array.