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.
