andy at warmcat.com
Tue Oct 16 03:50:59 CEST 2018
On 16/10/18 09:29, Per Bothner wrote:
> On 10/15/18 5:54 PM, Andy Green wrote:
>> I haven't looked at the obstack implementation... but if you read what
>> they wrote, it does not make any restriction that objects must be
>> deallocated in reverse order,
> "To free an object allocated in an obstack, use the function
> obstack_free. Since the obstack is a stack of objects,
> freeing one object automatically frees all other objects allocated
> more recently in the same obstack."
>> or only the object last allocated in any chunk may be deallocated,
>> which is what you are saying...
> No, that is not a restriction.
IIUI, it actually is.
>> Consider you ended up with two chunks, after 20 sub-allocations... if
>> no tracking, and I "free" say objects 3, 5, 7, a naive high-water mark
>> reduction per-chunk isn't going to do anything useful, is it?
> Freeing object 5 will automatically free objects 6-20 as well, and
> possibly one of the chunks.
> You can later call obstack_free on object 3 - but a reference to object
> 7 would be a dangling pointer,
> and so calling obstack_free on object 7 would be invalid.
I guess this is why it's a "stack"... you can basically pop yourself
back to an earlier state freeing everything inbetween. But as I say
"only the object last allocated in any chunk may be deallocated" (along
with as many others as you like) then...
>> In fact the user code has no idea which chunk an allocation went in,
>> he can't order his frees targeting making a particular chunk having
>> zero high-water mark even if he wanted to. "Object frees" that freed
>> space behind the current high-water mark for the chunk are invisible
>> to such a scheme and it will fail to understand when the last
>> allocation in the chunk does get freed out-of-order, that the
>> allocations behind it were already freed. That requires bloaty per
>> sub-allocation tracking to follow the "holes".
> There are no holes in an obstack (except unused space at the end of a
> chunk or due to alignment).
>> Anyway lwsac was written to support a particular, intense, case that
>> will be coming along presently, where you can imagine for yourself the
>> effect of the bloat it's avoiding.
> Which is cool. You might not want to use obstacks for licensing reasons
> (LGPL), anyway.
I already wrote my own implementation from scratch, including the
conception... I don't need obstack.
> However, I do suggest adding a note like:
> Lwsac is variant of the
> [obstack](https://en.wikipedia.org/wiki/Obstack) data structure.
Eh... while I'm happy to acknowledge it pre-existed what I wrote...
> GNU [obstack](https://en.wikipedia.org/wiki/Obstack) is an older
> implementation of a similar idea.
... I never even heard of it until you mentioned it thismorning. It's
simply a case of a good idea getting evolved again independently.
I certainly owe Stallman, GNU for GCC and their other work, but I don't
owe this any special acknowledgment.
More information about the Libwebsockets