This is a bit of a long story, but it's a question which I've tried to
research without must progress, and perhaps someone on the list can
help. I've finished up my rework of Marpa's memory allocator. It's
based on GNU's obstacks, but very heavily hacked at this point. It's
extremely efficient, but efficiency is *not* its most important
advantage. Marpa has lots of complex data structures which can be very
hard to destroy, particularly under error conditions -- they may still
be under construction. If you look at Ben Pfaff's AVL code, his most
complex logic is not for the AVL data structures themselves, but the
code that makes sure his AVL's don't leak memory.
Obstacks eliminate my having to worry about this. Each object
(recognizer, grammar, etc.) has an obstack and almost everything is
allocated from that obstack. When the object is destroyed, there's no
need to follow all the links, make sure everything is destroyed in the
right order, etc., etc. -- I just delete the obstack in which everything
was allocated.
Marpa's obstacks have the disadvantage that I cannot resize
allocations. I also cannot free any of the memory without destroying
the entire obstack. In Marpa, I rarely need to do either of these
things. For the few cases where obstacks fall short of what I need, I
just fall back on malloc().
Marpa's obstacks get their memory in big blocks from malloc(). For
obstacks, I have a good deal of freedom in deciding how much memory to
request. My question is, what is the best size?
I am currently followig the strategy used by GNU's obstacks. They
allocated, by default, 4K less a complex calculation based on the size
of various malloc() headers, etc. Their idea was that if they ask for
exactly 4K, GNU's malloc(), because of the extra few bytes needed for
headers, would need to allocate an extra block. That suggests that
doing many allocations, all of exactly 4K, is an almost pessimal way to
use malloc(). But the GNU obstack authors append a comment noting that
they think their analysis, as of the latest GNU malloc, may be obsolete
-- that lots of allocations of exactly 4K are no longer worse than any
other strategy.
Most helpful for me would be pointers to the writeups where this issue
is addressed. I've tried to research this, but the papers that I find
focus on how well they deal with difficult mixes of allocation sizes,
and not on how an application with a lot of flexibility can help
malloc() out.
Thanks, jeffrey
--
You received this message because you are subscribed to the Google Groups "marpa
parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
