Comprehending subpools

Comprehending subpools

[sbelmont700]

Hi,

I've been trying for what I guess is six years now to figure out subpools, and I just can't seem to make heads or tails of it.  Yes, I understand it inasmuch as it means you can deallocate multiple objects at once with proper finalization, but it seems like a hell of a lot of work went into it, with multiple AI's, hundreds of comments, and what has to be thousands of man-hours for a feature that seems niche, at best.  The AI's are filled with big talk and grand plans (the phrase "portable garbage collecting pool" was uttered), and even the "Controlled" pragma was marked as being supplanted by subpools, but what made it into the language seems, well, not much better than what was there already.  But it wouldn't be the first Ada feature that was too complex for programmers to understand, so please point out where I have gone off the rails.

The rationale says "this is far safer and often cheaper than trying to associate lifetimes with individual objects".  But is it really? 

Deallocating subpools is still just as unchecked as deallocating an individual objects, and it's not like you get partial credit for dangling references.  Deallocating a subpool with a reference into it still hanging around is just as unsafe as regular Unchecked_Deallocation, so you still have the same old problem of either limiting the scope, or reference counting everything.  And practically, if you are going to reference count it, it's going to be some generic, reusable package that either works right for everything or nothing at all, which is exactly as safe/unsafe as it was before.

Moreover, reference counting in a world of subpools is even harder, because not only do you have to worry about the objects in the subpool, but the subpool handle itself.  So it becomes a *more* complex task of ensuring that a) all the references into the subpool are gone and B) all references to the subpool itself are gone.  The reference counted values would need some mechanism to know which subpool they came from, which probably means the subpool handle, which now also has to be reference counted, so you have shared pointers inside of shared pointers, which i would classify as "at best equally complex and error prone" instead of "far safer".  You could argue you might save some bytes by only having a single total reference count instead of many, but that is probably offset by needing to save the subpool reference anyway.  And of course this means reference counted subpool values would be different than normal reference counted values, which means a THIRD type of incompatible pointer running around; i.e. you still can't have a set of references that can hold 'regular' (accessibility-checked) access values, 'standard' reference counted values, and subpool counted values.

Alright, so maybe this is intended for the case where you can control the entire scope, and not have to worry about passing them around.  But in those cases, can't you just declare a new access type and use 'Storage_Size (or a normal storage pool) to give you exactly that?  The only reason to use a subpool is when the type has to be declared at a higher scope, which is presumably so you can pass that type around (and save it off somewhere), which demands some sort of reference counting.

So then perhaps it's "often cheaper"?  It will certainly be faster to deallocate a big chunk than a bunch of little chunks, but all premature optimization platitudes aside, I can honestly not think of a time when the speed of deallocations concerned me in the least, as either programmer or user.  Normally this happens when the program (or significant portion of it) is over, at which point who cares how long some thread runs in the background cleaning up storage?  Even the given example of a retail shopping web site seems forced; who worries about how long a web server takes to deallocate old shopping cart data after the user has closed his browser?  If anything that example demonstrates the need for some form of automated garbage collection, not optimizing the manual method.

Moreover, even in a supposed use-case where speed DOES matter, the whole point of this change was to do it in a way that allows for finalization of the objects; otherwise the pre-existing Mark/Release pool was sufficient.  But if you need a subpool because all these objects are going to have complex finalization, isn't that almost certainly going to be the bottleneck?  The runtime still has to walk through the list of objects, one-by-one, and run their big, slow, complex Finalize procedures.  So the idea that you can just 'adjust a pointer' and be done with it really doesn't hold water either.

So at the end of the day, i can't see how much of any of this is better than what was already there, and certainly not to the extent it was worth the apparently enormous amount of time spent, especially when there are other things begging for improvement.  It seems like it would have been much more efficient to just make the mark/release pool a standard library package instead of an example, and add a rule that saying that the implementation needs to finalize the objects within.

I have to assume I just haven't had that "a-ha!" moment that readjusts my old way of thinking, so does someone actually have a real, serious, concrete example of something using subpools that warrants the time and expense that this took?  I'm all for revising the memory management facilities in Ada (I long for the day when you can use raw access values from a reference-counting pool, a mark/sweep pool, and those generated from 'Access interchangeably), but this just doesn't seem to be it.

-sb


 

Re: Comprehending subpools

[Randy Brukardt]

>Alright, so maybe this is intended for the case where you can control the
>entire scope, and not have to worry about passing them around.  But in
>those cases, can't you just declare a new access type and use 'Storage_Size
>(or a normal storage pool) to give you exactly that?

The use case is situations when you have separable data structures that it 
only makes sense to treat as a whole. Think of an expression tree in a 
compiler. There are a lot of inter-structure links, so a reference counting 
scheme for every pointer doesn't work. Rather, you can use a subpool and 
only reference count the references to the entire tree. When that goes to 
zero, you use the subpool to clobber the entire structure. Alternatively, 
you might have weak references to the tree, that automatically get nulled 
when the tree is clobbered.

You can't use separate access types in cases like this, since there's lots 
of shared code that needs to take pointers to these trees. And you want to 
clobber the whole structure at once, as that reduces the possibility of 
dangling pointers.

Tucker originally had various weak and strong references with the subpool 
proposal, but those were massively complex and can easily be constructed out 
of existing Ada concepts. So the subpool is a tool, but it's expected to be 
used with programmer constructed strong and weak references - by itself, it 
only really provides one thing: the ability to finalize a group of objects 
together. (The one thing that you can't do without it.)

It *is* a niche need; personally, I think using tree containers to represent 
an expression tree would be a better solution to the problem given above. 
Those too can have dangling pointers, but only if you insist on an 
implementation that puts performance above safety. (Unfortunately, many 
users do exactly that.) It's relatively easy to detect all dangling cursors 
for the unbounded containers (the requirement for the packages to be Pure 
prevents such detection for the bounded containers, although the usual 
implementation of a bounded container  means that such cursors still point 
at *something*, it's just not what you expect).

In any case, subpools precedes the tree containers, so that wasn't an option 
then. For me, I'd try to avoid ever writing an access type and use the 
containers instead (you can get dangling detection for free, and many 
operations -- like iteration and lookup -- never need a cursor in the first 
place).

                                          Randy.

Re: Comprehending subpools

[Dmitry A. Kazakov]

On 2018-06-14 23:21, Randy Brukardt wrote:

> The use case is situations when you have separable data structures that it
> only makes sense to treat as a whole. Think of an expression tree in a
> compiler. There are a lot of inter-structure links, so a reference counting
> scheme for every pointer doesn't work. Rather, you can use a subpool and
> only reference count the references to the entire tree. When that goes to
> zero, you use the subpool to clobber the entire structure. Alternatively,
> you might have weak references to the tree, that automatically get nulled
> when the tree is clobbered.

I think the questions rather were:

1. What is so special about arena or a mark-and-release pool that it 
cannot be handled by a user-defined pool in Ada 95?

2. Arena is inherently unsafe whatever implementation used. So all talk 
about "safety" does not make much sense.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Comprehending subpools

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:pfvp1k$ph4$1@gioia.aioe.org...
> On 2018-06-14 23:21, Randy Brukardt wrote:
>
>> The use case is situations when you have separable data structures that 
>> it
>> only makes sense to treat as a whole. Think of an expression tree in a
>> compiler. There are a lot of inter-structure links, so a reference 
>> counting
>> scheme for every pointer doesn't work. Rather, you can use a subpool and
>> only reference count the references to the entire tree. When that goes to
>> zero, you use the subpool to clobber the entire structure. Alternatively,
>> you might have weak references to the tree, that automatically get nulled
>> when the tree is clobbered.
>
> I think the questions rather were:
>
> 1. What is so special about arena or a mark-and-release pool that it 
> cannot be handled by a user-defined pool in Ada 95?

No pool that does block deallocation (not using Unchecked_Deallocation) can 
work properly with controlled objects. For almost all implementations, 
attempting to do that with controlled objects would cause the program to 
instantly crash because of an attempt to follow pointers that no longer 
exist.

Since virtually all memory management schemes in Ada use controlled types or 
some language-defined equivalent, that essentially means that you would be 
so limited in what you can put into such a pool that it is close to useless.

> 2. Arena is inherently unsafe whatever implementation used. So all talk 
> about "safety" does not make much sense.

"Safety" in this case is related to properly handling controlled types. With 
that, one can construct properly working strong and weak references and 
other safe memory management structures that will work on essentially any 
Ada objects. Without it, you have no chance of any safe memory management.

The basic idea is that one manages the "strong" references to an arena (such 
as the reference to the root of a tree), and when they are all gone, one can 
safety destroy the arena. The weak references aren't managed for that 
purpose, but don't become erroneous when the arena is destroyed, but rather 
just get (effectively) nulled out.

One could implement the containers this way, such that when a container is 
destroyed, that the entire arena of nodes is immediately reclaimed. (There's 
no legal references into the container at that point.)

In any case, a subpool by itself doesn't provide any safety; it's just a 
building block to be used to provide such safety. All of the other things 
needed to build such abstractions already existed in Ada, the only thing 
missing was an ability to finalize all of the objects in an arena (subpool) 
at once.

Draw your own conclusions as to how valuable (or not) that is.

                                       Randy.

Re: Comprehending subpools

[Dmitry A. Kazakov]

On 2018-06-16 00:15, Randy Brukardt wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:pfvp1k$ph4$1@gioia.aioe.org...
>> On 2018-06-14 23:21, Randy Brukardt wrote:
>>
>>> The use case is situations when you have separable data structures that
>>> it
>>> only makes sense to treat as a whole. Think of an expression tree in a
>>> compiler. There are a lot of inter-structure links, so a reference
>>> counting
>>> scheme for every pointer doesn't work. Rather, you can use a subpool and
>>> only reference count the references to the entire tree. When that goes to
>>> zero, you use the subpool to clobber the entire structure. Alternatively,
>>> you might have weak references to the tree, that automatically get nulled
>>> when the tree is clobbered.
>>
>> I think the questions rather were:
>>
>> 1. What is so special about arena or a mark-and-release pool that it
>> cannot be handled by a user-defined pool in Ada 95?
> 
> No pool that does block deallocation (not using Unchecked_Deallocation) can
> work properly with controlled objects.

Yes, but that was the second question. The first was if arena can be 
implemented in Ada 95. It can.

>> 2. Arena is inherently unsafe whatever implementation used. So all talk
>> about "safety" does not make much sense.
> 
> "Safety" in this case is related to properly handling controlled types. With
> that, one can construct properly working strong and weak references and
> other safe memory management structures that will work on essentially any
> Ada objects. Without it, you have no chance of any safe memory management.
> 
> The basic idea is that one manages the "strong" references to an arena (such
> as the reference to the root of a tree), and when they are all gone, one can
> safety destroy the arena. The weak references aren't managed for that
> purpose, but don't become erroneous when the arena is destroyed, but rather
> just get (effectively) nulled out.

In effect it means that all references to the objects also hold a 
reference to the pool. It is no problem to implement with an Ada 95 pool.

> One could implement the containers this way, such that when a container is
> destroyed, that the entire arena of nodes is immediately reclaimed. (There's
> no legal references into the container at that point.)
> 
> In any case, a subpool by itself doesn't provide any safety; it's just a
> building block to be used to provide such safety. All of the other things
> needed to build such abstractions already existed in Ada, the only thing
> missing was an ability to finalize all of the objects in an arena (subpool)
> at once.

Right, it is so special case that I join OP wondering why this was paid 
any attention at all. Normally the schema is reverse, the objects must 
go when the arena goes, if any safety could be added, then a linked list 
of objects to finalize [prematurely, BTW] as it is done in other cases.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Comprehending subpools

[sbelmont700]

I guess it's just a case of me reading too much into things.  The rationale declares subpools "a major new facility", but I just couldn't (and perhaps still can't) see a niche feature as being worth all the time and trouble.  When people say "far safer" i think of code that doesn't have to be prefixed with Unchecked_* at all, not just "you have to call it less".

And sure, finalization is of course important, but subpools seem almost specifically engineered to solve one problem that one person had writing one type of program, and not a general-purpose building block (which happily most features in Ada are).  Which is fine for small features that are relatively easy, but just judging from the AI text, subpools seems to be the biggest change to 2012 second only to contracts, and it mostly seems, well, wasted.  It doesn't appear the default pool has to support them (?), so step one to using a subpool is to go and implement a pool-with-subpools and hardcode your program to use it, and that's a high barrier to entry even when it's warrented.  And when there are so many other things developers on CLA are always clamoring for (<cough>constructors<cough>), it all seems like an odd way to focus energies.  Not to be flippant, but my kingdom for a do loop...and 'do' is already a reserved word!

I'd rather pull all the nonsense of wrapping access values in controlled types out of the client in the first place and put it into the pool itself (a callback passed to allocate or something?), instead of just solving the problems piecemeal.  Having to use controlled types for memory management is the problem IMHO.  Let code work with access values directly and leave it to the pool they came from to decide how and when to clean it up.

I suppose i was just hoping for more.  I would, however, be interested to hear examples of how other people have found them useful in their own code (outside of compiler ASTs) to help foster my imagination of what else can be done with them.

Thank you again for the responses and continued support.

-sb

Re: Comprehending subpools

[Randy Brukardt]

<sbelmont700@gmail.com> wrote in message 
news:351c6acd-8a8c-41a3-bb52-dd3f82322829@googlegroups.com...
...
>I'd rather pull all the nonsense of wrapping access values in controlled 
>types
>out of the client in the first place and put it into the pool itself (a 
>callback
>passed to allocate or something?), instead of just solving the problems
>piecemeal.  Having to use controlled types for memory management is the
>problem IMHO.  Let code work with access values directly and leave it to
> the pool they came from to decide how and when to clean it up.

That was my original idea for what eventually became generalized references. 
The problem being that the you have to lie about the specification of pools 
for that to work (the "System.Address" parameters become handles that you 
pass into a a dereferencor). And magic was required for the call-back needed 
to tell the pool when the dereference wasn't needed anymore. Most readers 
couldn't wrap their heads around either part of that.

Using a totally different specification for a new kind of pool wasn't 
appealing, as it would mean having to support multiple ways of doing the 
same thing.

                                                 Randy.

P.S. The original driving force for subpools came from Tucker Taft and Bob 
Duff, who had used a system like this when implementing the tool now known 
as CodePeer. The original proposal was ten times more complicated, 
containing strong and weak references, and automated deallocation 
mechanisms. All of these can easily be constructed with the building blocks 
available, and trying to support all of that would have taken a lot more 
effort.

I've never seen much value for arena memory management myself, but I prefer 
to hide access types as much as possible with almost no visible surface. In 
that case, all of the memory management belongs to the objects, and that 
tends to require separate management for each object.

Re: Comprehending subpools

[Shark8]

On Friday, June 29, 2018 at 1:57:10 PM UTC-6, Randy Brukardt wrote:
> 
> I've never seen much value for arena memory management myself, but I prefer 
> to hide access types as much as possible with almost no visible surface. In 
> that case, all of the memory management belongs to the objects, and that 
> tends to require separate management for each object.

Hm, maybe they could be useful for some sort of distributed system? I mean if you're considering a shared memory-space (like, say, IEEE 1394) then disconnection of a device and reclaiming the address-values ala arena management seem to be fairly analogous.