Re: Allocation speed

Re: Allocation speed

[Alex Blakemore]

In article <21870@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'K
eefe) writes:
> Over the year, I have noticed that
>     malloc() and free() in C
>     new() and dispose() in Pascal
> are often ____very____ slow on the UNIX systems I use.

> I've been told that this is just a "quality-of-implementation issue",
> I know that the Ada LRM says nothing about the _performance_ of allocation
> or unchecked deallocation, but what does the _culture_ say?  Do real Ada
> programmers put up with inferior performance for these operations?

one simple thing worth considering

have your ADTs export create/free operations
and then have all clients call them.

then in the package body that defines the ADT,
you can start with a simple implementation that uses 
"new" for allocation and doesnt even bother to implement free.

then over time, use unchecked deallocation for free.

if its too slow, start using a free list - should avoid many
of the OS calls (easy for fixed length records)

other advantages of this approach are that you can
do other things in these subprogram bodies such as:
  emit tracers to a terminal or log file upon each allocation/deallocation
    useful for debugging
  record statistics 
    useful for understanding/tuning memory use
  special initialization
  maintaining reference counts
    to support structural sharing
  switch to a free list implementation
    to improve time/space performance
  switch to some other implementation
    such as alloc a big array and hand out chunks via unchecked_conversion

you can even turn this stuff on and off conditionally
to experiment with different approaches, either dynamically
or with a compile time constant relying upon dead code elimination.

some of my code reads a secret environment variable
and prints out some of this stuff if its set, its real useful
during development and can be easily turned off for speed
if necessary in the final version.

drawbacks of this approach
  procedure call overhead
    easily overcome with pragma inline
  relies upon user discipline 
    (not calling new if type is not private, remembering to call free)
    this isnt too onerous, but Ada9X makes it possible to be more reliable  

another pleasing aspect is that this limits 
the places unchecked_deallocation is withed somewhat.

-- begin anecdote
one of my previous coworkers who occasionally reads this group, once
implemented a package which managed both packed and unpacked versions
of a data structure.  there would be hundreds of thousands
of these things around at once, so the packing had to be extremely tight,
but packing and unpacking happened alot - so the conversion had to be simple&fa
st.
we encapsulated the pack/unpack calls similar to the new/free calls above.

we started with a simple moderately efficient version to get the system to work
,
and then in the end experimented with 5 different variations of the package bod
y.
my coworker plotted time costs for each variation - allowing us to quantitative
ly
choose the best packing scheme (which was almost but not quite the tightest pac
ker).
the one that packed the tightest was so complex that it actually cost time even
though it saved space and paging.

the cool thing was that encapsulation allowed us to safely defer the
experimentation till we were ready, and then to make implementation changes
reliably and with confidence that it would not affect other aspects of the syst
em.

you can do this in any language, but in Ada the compiler can help ensure
the separation is strictly maintained.  
-- 
Alex Blakemore       alex@cs.umd.edu        NeXT mail accepted
--------------------------------------------------------------
"Without an engaged and motivated human being at the keyboard,
the computer is just another dumb box."      William Raspberry

Re: Allocation speed

[agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!cis.ohio-state.edu!bo]

In article <70400@mimsy.umd.edu> alex@cs.umd.edu (Alex Blakemore)
writes about the many advantages of a disciplined approach to storage
management, in response to a question about performance of dynamic
memory allocation and deallocation.  His arguments are very
persuasive.  For some specific suggestions about how to encapsulate
Alex's suggestions (and others) in a nice way, see:

  Hollingsworth, J.E., and Weide, B.W., "Engineering 'Unbounded'
  Reusable Ada Generics," Proc. 10th Ann. Natl. Conf. on Ada Technology,
  ANCOST, Inc, Feb. 1992, pp. 82-97.

Related packages designed to facilitate multiple implementations of
low-level storage management details can be found in the first
author's Ph.D. dissertation.  It is available by anonymous FTP from
host ftp.cis.ohio-state.edu in the directory pub/tech-report/TR1-1993.

Cheers,
    -Bruce