🚀 go-pugleaf

In article <1992Mar25.202719.7162@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at writes:
>The efficiency of Prolog as it stands now (IMHO) can be understood with a
>rather simple model, your estimations will diverge only by small factors
>which is similar to other programming languages. (also C-programs can diverge in
>a surprising manner from the estimations. To give a small example: use malloc()
>on different systems, or even on the same machine but different operating system
>releases!)

I call C a write only language - you don't want to have to read it
or debug it, and you only use it to gain that extra ounce of speed.

But to illustrate the problem with malloc (in the GNU GPP - and
current BSD versions), here is a comment from a program just before I
implemented something directly with sbrk.  Note that no Prolog I
know of garbage collects its symbol tables, and several seem to
reallocate them following one of the schemes I discuss below: I've
seen the resulting thrashing.  (This interning of symbols forever
is a real problem for long running programs that process lots of
unique atoms but don't store them permanently.)

I've also run tests which demonstrate 75% wasting of memory (which
being virtual means both core and swap space) by malloc.

/*
 * In fact, malloc allocates shells which are always a power of two less overhead
 * and realloc will return the same block while it retains the same size shell.
 * However the different size shells are kept on separate free lists and malloc
 * will never return the same block if it binary order changes.
 * Worse still this allocation strategy can waste up to 85% of memory!
 * The allocation strategy assumes that virtual memory really is unlimited
 * (it says it shouldn't fail up to 2^30 would you believe).
 * The worst thing you can do is use realloc - and it is worst of all if
 * you free it first and try to reallocate later because it then wastes a lot 
 * of time looking for it on the free list to determine its size.
 *
 * So let's see how it end up allowing you to use less than 15% of memory/disk
 * Suppose you have just one data structure (what any others do is relevant too)
 * which needs to grow (that's why we HAVE realloc afterall).  You use malloc
 * to allocate it initially (it will be clear providing you haven't freed it),
 * or you use calloc which clears it again just to make sure (it doesn't know).
 * When it is full, you realloc it to extend it by an increment equal to its
 * initial size, and this you do repeatedly as it keeps on growing and growing.
 * In fact, malloc will allocate new pages each time it reaches a new order.
 * So the shells malloc actually allocates actually double in size upon
 * certain calls.  The smaller shells of all smaller powers of two are vacant
 * and by the time you add the extra memory if the data structure started
 * smaller than a page, you already have more memory NOT used than used.
 * If we actually use a doubling strategy rather than an incrementing strategy
 * as malloc will end up doing this anyway, we can make things worse.  Because
 * if we are allocating, as we might naively do, exact powers of two, malloc
 * will actually have to place it in a higher power of two shell because of
 * a few overhead bytes (size and/or freelist pointer information).
 *
 * So we now have a sitation in which half of the shell we are actually using
 * is not being used. and we are wasting 75% of our memory/disk.  Now consider
 * what happens the time it grows and finds you don't have enough disk space.
 * Because it insists on powers of two, a shortfall of just one page will
 * suffice to prevent expansion.  Remember it is asking for as much memory
 * again as it already has.  Thus up to 50% of memory/disk is wasted at this
 * last step, and 75% of the 50% we are already using is wasted, so we are
 * using only 12.5% of available virtual memory when we run out!
 *
 * The moral of the story: Don't use realloc!  But if you must, then you
 * may as well double rather than increment.  And if you double, start with 
 * something a little less than a power of two (around 10 bytes less is best).
 * Better still, always ask 10 bytes less than a power of two - don't do exact
 * doubling!  Following this latter advice you'll only waste half your memory!!
 */

dP
-- 
Dr David M. W. Powers	   Email: powers@kub.nl	 SHOE   E xtraction
ITK, Tilburg University,     Tel: +31-13 663116	       O f
P.O. Box  90153		     Fax: +31-13 663019	      H ierarchical
5000 LE TILBURG		     Sec: +31-13 663060      S tructure