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

[Brent W. <we...@aj...>]

[Note - I botched the description of Hintermayer's algorithm, and
there is also the issue of internal memeory allocation that I'd like
to add, so this is another version of my summary.]

Background:
Tcl currently doubles the storage for a string when appending to it.
This has the excellent property that the cost of appending to a 
string is almost O(n).  In contrast, a naive algorithm that only
allocates exactly enough space for the appended bytes has O(n-squared)
cost.  This simple agorithm is captured in a few lines of code,
where numBytes is the append size.

    newLength = numBytes + oldLength;
    if (newLength > (int) stringPtr->allocated) {
        Tcl_SetObjLength(objPtr, 2*newLength);
     }

The problem:
On most operating systems the amount of memory a process can allocate is
limited to physical memory+swap space (i.e., backing store on disk),
which could be far less than the size of the virtual address space
depending on how the machine is configured and the OS. Therefore,
when Tcl tries to append data to a string that is slightly over
half the size of the *available memory* then the memory doubling
algorithm will fail.  It fails because the Tcl_Alloc procedure
panics when it cannot allocate memory.  This leads to a cases where
a machine has, for example, 512 Meg of available memory but cannot
grow a string past 256 Meg.
Problem 2:
There is also an internal memory fragmentation issue where the worst
case behavior of the current algorithm wastes space that is approximately
1/2 of the available memory.

Solution 1 - "get more memory"
Without changing Tcl we can just document this behavior and suggest
that users make sure they have twice the available swap space
to cover their physical memory.  That way you can grow a string
that fits into physical memory before you start paging.
Benefits:
No change to Tcl
Drawbacks:
Users have to know how to configure their machine to be able
to fully utilize memory.

Solution 2 - "Hintermayer's string allocation patch"
Change the memory growing algorithm for a string to:

    newLength = numBytes + oldLength;
    if (newLength > (int) stringPtr->allocated) 
        extra = newLength>=TCL_LARGE_STRING ? TCL_STRING_PAD+2*numBytes : newLength;
        Tcl_SetObjLength(objPtr, newLength+extra);
     }

The original patch used 1 Meg for TCL_LARGE_STRING and 1 K for TCL_STRING_PAD.
Jeff has suggested 4 Meg and 4 K, and I personally think 4Meg and 4Meg
(i.e., make the two constants equal) may be best.
Benefits:
This algorithm allows strings to grow within TCL_STRING_PAD of
the available memory size.  The amount of memory wasted by internal
fragmentation is TCL_STRING_PAD times the number of large strings.
Drawbacks:
This algorithm can slow down the append operation of strings
larger than TCL_LARGE_STRING.  Also, the best choice of
for these constants is dependent on the configuration of
the current machine.
Aside: We could export an interface to set this parameters dynamically
as opposed to compiling them into Tcl.

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:

    growth = oldSize + appendSize;
    do {
	newSize = oldSize + appendSize + growth;
	newMem = realloc(oldMem, newSize);
	growth /= 2;
	if (growth < appendSize) {
	     break;
        }
    } while (newMem == NULL);

Benefits:
This retains the memory doubling algorithm until the current machine
cannot tolerate it, so it has good performance.
It also lets you allocate essentially every byte of available memory.
It doesn't require that we choose arbitrary constants that may
not be suitable for all machines and configurations.
Drawbacks:
Memory allocation slows down as you approach the limits of available memory.
This does not address the internal fragmentation problem, so I think it
may have the same worst case memory behavior as the original solution.
Also, implementing this will require a bit of rework on the internal
interfaces because currently the new size choice is made by a different
procedure, AppendUtfToUtfRep, than the procedure that does the allocation,
Tcl_SetObjLength.  We'll need a variation on Tcl_SetObjLength that
accepts a range of allowed values.

Next steps:
If I've gotten something wrong, please speak up.  I don't have to ask for that!
Our goal is to reach a decision without much further rehash of the algorithms
and issues.  Things that would be helpful are a patch that implements
Solution 3, as well as more benchmarking to compare the approaches.

--	Brent Welch	<we...@aj...>
	http://www.ajubasolutions.com
	Scriptics has become Ajuba Solutions

--
The TclCore mailing list is sponsored by Ajuba Solutions
To unsubscribe:  email tcl...@aj... with the 
                 word UNSUBSCRIBE as the subject.





--
The TclCore mailing list is sponsored by Ajuba Solutions
To unsubscribe:  email tcl...@aj... with the 
                 word UNSUBSCRIBE as the subject.