[TCLCORE] Re: PROPOSAL (2nd) Limit memory doubling when appending to strings

[Eric M. <er...@aj...>]

> Solultion 3 - "Adaptive allocation" suggested by George
> 
> Retain the doubling algorithm until an attempt to allocate
> memory fails.  When that occurs, reduce the growth by
> halves until the allocation succeeds:

I have an implementation of (basically) this adaptive allocation
algorithm.  My implementation uses the following algorithm:

attempt to allocate 2*(oldsize + appendsize)
on failure, attempt to allocate oldsize + (2 * appendsize) + TCL_MIN_GROWTH
on failure, panic

This is based on some new allocation routines:

Tcl_AttemptRealloc
Tcl_AttemptAlloc
Tcl_AttemptDbCkalloc
Tcl_AttemptDbCkrealloc

Each of these is identical in function to the Tcl function of the same
name less the Attempt bit, except that the Tcl_Attempt* functions do _not_
panic on failure to allocate memory.  In addition, I added the function

Tcl_AttemptSetObjLength

Which is functionally identical to Tcl_SetObjLength except that it uses
the Tcl_Attempt* allocators, so it will not panic on failure.  It returns
0 for failure, 1 for success.

These functions are used together to implement the adaptive growth
algorithm.  Note that the smaller growth allocation is not used until the
doubling allocation has failed, so this modification will not affect any
existing programs.  It strictly enhances the capabilities of Tcl to
allow the use of more memory.  In addition, it does not cause any
noticeable performance penalty; for the normal case (the double allocation
is successful), it cause one additional integer comparison.  For the other
case (the double allocation is not successful), the original Tcl interp
would just panic, so we can't really compare performance there.

On my system (448 MB of total memory, with X and a couple of applications 
running, for a total of about 400 MB free according to 'top'), running the
attached script "testGrowth.tcl", produces the following results with an
unmodified Tcl:

----
total 10000000
total 20000000
.
.
.
total 290000000
total 300000000
unable to realloc 620000001 bytes
Abort
----

And with the new algorithm:

----
total 10000000
total 20000000
.
.
.
total 390000000
total 400000000
unable to realloc 420001025 bytes
Abort
----

With this new algorithm, I am able to use an additional 100 MB of the
memory on my machine.

Running the tclbench string append benchmarks produces the following
results:

8.4a1: 8.4a1 patched to use realloc as appropriate for appends
8.4a2: Same as above, with fallback algorithm for failure on doubling alloc's

000 VERSIONS:                     1:8.4a2 2:8.4a1
001 STR append                         50      51
002 STR append (1KB + 1KB)             41      43
003 STR append (10KB + 1KB)           131     129
004 STR append (1MB + 2b * 1000)    12563   12507
005 STR append (1MB + 1KB)           7775    7752
006 STR append (1MB + 1KB * 1000)   32360   32724
007 STR append (1MB + 1KB * 20)      7981    8115
008 STR append (1MB + 1MB * 3)      31842   32067
END VERSIONS:                     1:8.4a2 2:8.4a1

As you can see, the numbers are effectively equal; differences can be
chalked up to system "noise".

The patch is attached for your review, if you like.  It includes
documentation for the new functions.

Are there any objections to incorporating this modification into the core?

   Eric Melski                            The Other Tcl Guy
   ericm at ajubasolutions.com            Ajuba Solutions