[PATCH] irange_pool class

[Martin Sebor]

On 9/18/20 8:10 AM, Aldy Hernandez via Gcc-patches wrote:
> 
> 
> On 9/18/20 2:28 PM, David Malcolm wrote:
>> On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote:
>>>
>>> On 9/18/20 3:43 AM, David Malcolm wrote:
>>>> On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches
>>>> wrote:
>>>>> This is the irange storage class.  It is used to allocate the
>>>>> minimum
>>>>> amount of storage needed for a given irange.  Storage is
>>>>> automatically
>>>>> freed at destruction.
>>>>>
>>>>> It is meant for long term storage, as opposed to int_range_max
>>>>> which
>>>>> is
>>>>> meant for intermediate temporary results on the stack.
>>>>>
>>>>> The general gist is:
>>>>>
>>>>>     irange_pool pool;
>>>>>
>>>>>     // Allocate an irange of 5 sub-ranges.
>>>>>     irange *p = pool.allocate (5);
>>>>>
>>>>>     // Allocate an irange of 3 sub-ranges.
>>>>>     irange *q = pool.allocate (3);
>>>>>
>>>>>     // Allocate an irange with as many sub-ranges as are currently
>>>>>     // used in "some_other_range".
>>>>>     irange *r = pool.allocate (some_other_range);
>>>>
>>>> FWIW my first thoughts reading this example were - "how do I
>>>> deallocate
>>>> these iranges?" and "do I need to call pool.deallocate on them, or
>>>> is
>>>> that done for me by the irange dtor?"
>>>
>>> Thus the description front and center of the header file:
>>>
>>> "Storage is automatically freed at destruction..."
>>>
>>>> I think of a "pool allocator" as something that makes a small
>>>> number of
>>>> large allocation under the covers, and then uses that to serve
>>>> large
>>>> numbers of fixed sized small allocations and deallocations with
>>>> O(1)
>>>> using a free list.
>>>
>>> Ah, I didn't know pool had a different meaning.
>>
>> See e.g. gcc/alloc-pool.h
>>
>>
>>>> [...]
>>>>
>>>>> +// This is the irange storage class.  It is used to allocate the
>>>>> +// minimum amount of storage needed for a given irange.  Storage
>>>>> is
>>>>> +// automatically freed at destruction.
>>>>
>>>> "at destruction" of what object - the irange or the irange_pool?
>>>> Reading the code, it turns out to be "at destruction of the
>>>> irange_pool", and it turns out that irange_pool is an obstack under
>>>> the
>>>> covers (also called a "bump allocator") and thus, I believe, the
>>>> lifetime of the irange instances is that of the storage instance.
>>>
>>> The sentence is talking about the storage class, so I thought it was
>>> obvious that the destruction we talk about is the storage class
>>> itself.
>>> I suppose if it isn't clear we could say:
>>>
>>> "Storage is automatically freed at destruction of the storage class."
>>
>>
>>>> I think it would be clearer to name this "irange_obstack", or
>>>> somesuch.
>>>
>>> I'd prefer something more generic.  We don't want to tie the name of
>>> the
>>> allocator to the underlying implementation.  What if we later change
>>> to
>>> malloc?  We'd have to change the name to irange_malloc.
>>
>>> irange_allocator?  Or is there something more generically appropriate
>>> here?
>>
>> How about "irange_bump_allocator?"   Rather long, but it expresses the
>> key point that the irange instances coming out of it don't have
>> independent lifetimes - their lifetimes are those of the allocator; the
>> client code doesn't need to find and clean up all of those individual
>> iranges, right?  (assuming I'm reading the code correctly)   (That name
>> also avoids mentioning the implementation detail that it uses obstack).
> 
> I'm sorry, but that's _really_ ugly.
> 
> Surely irange_allocator can't be that confusing.  A casual look at the 
> header file would dispel all doubts.

David's point abut different strategies was also in the back my
mind but it took me a bit to formulate a question about the design.
Is a pool of ranges with a fixed allocation policy the right design
for long-term storage of irange objects?  What are some example use
cases?

Here's one that comes to mind based on what I want to do in
gimple-ssa-isolate-paths.c.  I need to store irange instances as
members of my own class, but I don't know how many subranges each
instance might need to store (it depends on the IL).  I store
objects of this class a container (e.g., hash_map or set).
I don't want to use int_range_max because that would be wasteful
but I can't use the pool as a proxy because it's not copyable.
So I either have to dynamically allocate the pool and store
a pointer to it instead, in addition to the instances, or derive
my own class from irange and manage the tree arrays myself.  In
both cases I'm adding a layer of memory management on top of what
that the pool is there to provide.  So the design doesn't seem
very well suited for my use case.

I don't mean this as an objection to the patch (I'm sure there's
a use case I'm not thinking of), but more as a question.

Martin

> 
> Aldy
> 
>>
>> Sorry if I'm nitpicking; I think my high level thought here is that we
>> have various memory management strategies inside GCC (in no particular
>> order):
>>    - garbage collection
>>    - explicit malloc/free
>>    - explicit new/delete
>>    - explicit new/delete backed by allocation pools
>>    - RAII
>>    - bump allocators aka obstacks
>> and I like to be clear about what "owns" each object (responsibility
>> for cleanup, lifetimes, etc)
>>
>> Hope this is constructive
>> Dave
>>
>