tcl-core — Tcl Core Team discussions about Tcl development

[TCLCORE] Non-Panicing Memory Allocator -- Easily Done

[Karl L. <ka...@ne...>]

There is a way to make the Tcl memory allocator not panic and allow Tcl programs to catch allocation failures that is simple, transportable, and doesn't change allocation semantics.  Here's how you do it:

Have Tcl keep track of how much memory it is using.  (It already does this when memory debugging is enabled.)

Have a settable (and queryable) memory limit that is internal to Tcl that is significantly smaller than the allocatable amount of memory on the machine.  (Running a machine out of swap is a bad idea anyway.)

When a memory request causes Tcl's internal limit to be exceeded, fulfill the request as usual (allocation still always succeeds) but use the async mechanism to generate a catchable "memory limit exceeded" error.  You could define two limits, a hard limit and a soft limit.  Or you could let the system impose the hard
limit.

You could also make this limit settable on a per-interpreter basis (although ckalloc would have to know or be able to figure which interpreter is making the request).  An interpreter creating an interpreter could allocate some of its memory allocation to it.  Safe interpreters would be restrictable from memory
exhaustion denial-of-service attacks.

--
Karl Lehenbauer
procplace.com


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

[TCLCORE] Re: PROPOSAL: Tcl_AttemptAlloc

[George H. <ga...@bl...>]

In message <200...@po...>, Brent Welch writes:
 : It sounds like there is consensus for an alternative to Tcl_Alloc,
 : call it Tcl_AttemptAlloc, that will return NULL instead of panicing
 : if it cannot allocate the requested memory block.  The implementation
 : is trivial:
 : 
 : char *
 : Tcl_AttemptAlloc (size)
 :     unsigned int size;
 : {
 :     return TclpAlloc(size);
 : }
 : 

Please also include 

    char *
    Tcl_AttemptRealloc(ptr, size)
	char *ptr;
	int size;
    {
	return TclpRealloc(ptr, size);
    }

in the mix.

--gah

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

[TCLCORE] PROPOSAL: Tcl_AttemptAlloc

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

It sounds like there is consensus for an alternative to Tcl_Alloc,
call it Tcl_AttemptAlloc, that will return NULL instead of panicing
if it cannot allocate the requested memory block.  The implementation
is trivial:

char *
Tcl_AttemptAlloc (size)
    unsigned int size;
{
    return TclpAlloc(size);
}

The main issue is the name.  These have been suggested
Tcl_SafeAlloc
Tcl_TryToAlloc
Tcl_AttemptAlloc

I personally like the third suggestion, but I'm open to more suggestions.

--	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.

[TCLCORE] Re: Hintermayer's string allocation patch

[D. R. H. <dr...@hw...>]

Jeffrey Hobbs wrote:
> 
> For that reason I think the need for a non-panic'ing alloc still exists.
> Tcl_SafeAlloc perhaps?
> 

I want to take issue with the name.  When I hear
"SafeAlloc()" I think of a malloc() that never
returns NULL.  In other words, it is "safe" to use
without checking the return type.  Your usage 
completely inverts that meaning.

Perhaps Tcl_TryToAlloc() or Tcl_AttemptAlloc()
instead.  Here the idea is "try to get me some
memory but its OK if you can't, just let me know."
This will be (I think) a seldom used function, 
so a longer name is not a handicap.
-- 
D. Richard Hipp -- dr...@hw... -- http://www.hwaci.com/drh/

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

[TCLCORE] Re: Hintermayer's string allocation patch

[Mark H. <ma...@us...>]

John Ousterhout <ou...@aj...> wrote:
> So, if you run
> out of memory, you can't necessarily even execute scripts to free
> up memory.  Bottom line: better to panic cleanly with a nice simple
> error message.

At the VHLL conference, Steve Johnson mentioned that this behavior
(dying on memory allocation failure) was a reason that he would never
consider use Tcl in a mission-critical system.

After his talk, we chatted a bit, and I explained that a memory
error was just one of the failure modes we deal with when writing
this kind of system.  The mechanisms that are routinely put into
place for dealing with process death and node failure handle this
situation.

Mark.

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

[TCLCORE] Re: PROPOSAL: use realloc when growing strings

[Donal K. F. <fel...@cs...>]

Brent Welch <we...@aj...>
> My vote is yes.

Yes.

(I'm actually a little surprised it wasn't done like this already... :^)

Donal.
-- 
Donal K. Fellows, Department of Computer Science, University of Manchester, UK.
(work) fel...@cs...     Tel: +44-161-275-6137  (preferred email addr.)
(home) do...@ug...  Tel: +44-1274-401017   Mobile: +44-7957-298955
http://www.cs.man.ac.uk/~fellowsd/  (Don't quote my .sig; I've seen it before!)

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

[TCLCORE] Re: Hintermayer's string allocation patch

[Jim I. <ji...@ap...>]

On Friday, September 1, 2000, at 11:45 AM, Scott Stanton wrote:

>  
> "D. Richard Hipp" said: 
>  > Perhaps Tcl_TryToAlloc() or Tcl_AttemptAlloc() 
>  > instead.  Here the idea is "try to get me some 
>  > memory but its OK if you can't, just let me know." 
>  > This will be (I think) a seldom used function,  
>  > so a longer name is not a handicap. 
>  
> The existing TclpAlloc could be the right way to handle this.  It is  
> usually just a wrapper around malloc() on Unix, so if we fixed the Tcl  
> allocator to avoid panics (as George suggested), then on all platforms it  
> would return NULL on allocation failures.  Then the outer Tcl_Alloc call  
> can implement the guarantee never to return NULL. 
>  

The only problem with this is that we would then be making a "p" routine part of the public Tcl API's.  I am not sure what the  thinking on this is.

Jim

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

--
Jim Ingham                                   ji...@ap...
Developer Tools - gdb
Apple Computer

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

[TCLCORE] Re: Hintermayer's string allocation patch

[Scott S. <st...@aj...>]

"D. Richard Hipp" said:
 > Perhaps Tcl_TryToAlloc() or Tcl_AttemptAlloc()
 > instead.  Here the idea is "try to get me some
 > memory but its OK if you can't, just let me know."
 > This will be (I think) a seldom used function, 
 > so a longer name is not a handicap.

The existing TclpAlloc could be the right way to handle this.  It is 
usually just a wrapper around malloc() on Unix, so if we fixed the Tcl 
allocator to avoid panics (as George suggested), then on all platforms it 
would return NULL on allocation failures.  Then the outer Tcl_Alloc call 
can implement the guarantee never to return NULL.

--Scott


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

[TCLCORE] Re: PROPOSAL: use realloc when growing strings

[Donald G P. <dg...@ca...>]

> From: Brent Welch <we...@aj...>
> If there are major objections, please speak up.  Otherwise someone ought
> to formulate a simple patch that we should adopt.  

Is the following patch (against revision 1.17 of generic/tclStringObj.c)
the subject of this proposal?

*** tclStringObj.c	Fri Sep  1 10:47:04 2000
--- tclStringObj.c.new	Wed Aug 30 11:42:38 2000
***************
*** 667,678 ****
  	 * Not enough space in current string. Reallocate the string
  	 * space and free the old string.
  	 */
! 
! 	new = (char *) ckalloc((unsigned) (length+1));
! 	if (objPtr->bytes != NULL) {
! 	    memcpy((VOID *) new, (VOID *) objPtr->bytes,
! 		    (size_t) objPtr->length);
! 	    Tcl_InvalidateStringRep(objPtr);
  	}
  	objPtr->bytes = new;
  	stringPtr->allocated = length;
--- 712,730 ----
  	 * Not enough space in current string. Reallocate the string
  	 * space and free the old string.
  	 */
!  	if (objPtr->bytes != tclEmptyStringRep) {
! 	    new = (char *) ckrealloc((char *)objPtr->bytes,
! 		    (unsigned)(length+1));
!  	} else {
! 	    new = NULL;
!  	}
!  	if (new == NULL) {
! 	    new = (char *) ckalloc((unsigned) (length+1));
! 	    if (objPtr->bytes != NULL && objPtr->length != 0) {
!  	    	memcpy((VOID *) new, (VOID *) objPtr->bytes,
!  		    	(size_t) objPtr->length);
!  	    	Tcl_InvalidateStringRep(objPtr);
! 	    }
  	}
  	objPtr->bytes = new;
  	stringPtr->allocated = length;

If so, then my vote is yes.

> I'd rather not have to vote on every core change so long as there is
> general concensus.  

Yes, it would be better to set up something more like the staged
commits that were discussed here a few days ago.  Whatever maintainers
were assigned to the file generic/tclStringObj.c would just make the call.

Their decisions are, of course, subject to the peer review inherent
in open source development, so if they do something really dumb, it
can be taken out later, but that system avoids lots of bureaucratic
systems on the front end.

DGP

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

[TCLCORE] Re: Non-Panicing Memory Allocator (was Hintermayer's string allocation patch)

[Jim I. <ji...@ap...>]

I think the idea of introducing a non-panicing memory allocator is a separate proposal as well, since I agree with George that it is a good thing even if we don't use it for the Big string allocator.  Especially since there are other areas in Tcl where it should be used - for instance in the "image create" command.

Jim

On Friday, September 1, 2000, at 10:21 AM, Jeffrey Hobbs wrote:

> The default builds on both Unix and Windows (I don't know about the 
> Mac) will hit the panic code.  The twisty trail of following #defines 
> in tcl.h/tclCkalloc.c can be confusing, but it happens.  I assume the 
> same for the Mac. 
>  

Yup...

Jim
--
Jim Ingham                                   ji...@ap...
Developer Tools - gdb
Apple Computer

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

[TCLCORE] Re: Hintermayer's string allocation patch

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

>>>"Jeffrey Hobbs" said:
 
 > The default builds on both Unix and Windows (I don't know about the
 > Mac) will hit the panic code.  The twisty trail of following #defines
 > in tcl.h/tclCkalloc.c can be confusing, but it happens.  I assume the
 > same for the Mac.

The panics are in the generic code

char *
Tcl_Alloc (size)
    unsigned int size;
{
    char *result;

    result = TclpAlloc(size);
    /*
     * Most systems will not alloc(0), instead bumping it to one so
     * that NULL isn't returned.  Some systems (AIX, Tru64) will alloc(0)
     * by returning NULL, so we have to check that the NULL we get is
     * not in response to alloc(0).
     *
     * The ANSI spec actually says that systems either return NULL *or*
     * a special pointer on failure, but we only check for NULL
     */
    if ((result == NULL) && size) {
        panic("unable to alloc %d bytes", size);
    }
    return result;
}

char *
Tcl_DbCkalloc(size, file, line)
    unsigned int size;
    char        *file;
    int          line;
{
    struct mem_header *result;

    if (validate_memory)
        Tcl_ValidateAllMemory (file, line);

    result = (struct mem_header *) TclpAlloc((unsigned)size +
                              sizeof(struct mem_header) + HIGH_GUARD_SIZE);
    if (result == NULL) {
        fflush(stdout);
        TclDumpMemoryInfo(stderr);
        panic("unable to alloc %d bytes, %s line %d", size, file, line);
    }


--	Brent Welch	<we...@aj...>
	http://www.ajubasolutions.com
	Scriptics changes to Ajuba Solutions
	scriptics.com => ajubasolutions.com


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

Re: [TCLCORE] Re: Hintermayer's string allocation patch

[Mark H. <ma...@us...>]

Andreas Kupries <a.k...@we...> wrote:
> I go with George and John here, i.e. allocate until you the wall and
> then retract from the boundary to fill the rest in smaller
> increments.

I also concur with this...

Joe English <jen...@fl...> wrote:
> If it has the potential to
> adversely affect the performance of Tcl programs
> by a quadratic factor (which I believe it does),
> it shouldn't be applied.

...and this.

Eric Melski <er...@aj...> wrote:
> Again, I urge everybody not to get hung up on the performance issue and
> consider the memory issue:  without _some_ kind of change, Tcl simply
> cannot use all available memory.

I disagree with this.  It is not a good tradeoff.  In addition, if an
application has a requirement to deal with data this size, there are
probably better solutions than shuffling strings around in swap space.

Amusing anecdote:  DSC Communications had exactly one customer problem
report related to Tcl in five years.  A programmer had attempted to
use a text widget to watch log data, but didn't get the code write
to delete the oldest test lines, so the text data kept growing.  After
about 3 days, the machine ran out of swap, and the other processes in
the system started to die -- but the text widget process kept going with
no problem.  It's the only trouble I've ever seen complaining that a
program was too robust.

Mark.

--
Mark Harrison                          AsiaInfo Holdings, Inc.
ma...@us...                Beijing/Santa Clara

[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.

[TCLCORE] Re: Hintermayer's string allocation patch

[Jeffrey H. <jef...@aj...>]

> From: George Howlett [mailto:gah@blueberry]
	...
> I agree with you on this last point.  In my own code do the same
> thing.  When allocating memory for structures, strings, etc., there's
> no practical way of recovering from memory exhaustion.  Panic-ing is a
> reasonable solution.
>
> But there's another class of allocations where I do want to know if I
> can't allocate the requested amount of memory.  When I allocate a
> large block of storage for for a vector, the contents of a file, etc.
> I want to tell the user that his/her request failed.

For that reason I think the need for a non-panic'ing alloc still exists.
Tcl_SafeAlloc perhaps?

	...
> I have no argument with panic-ing.  But after looking at TclpAlloc, I
> don't see where it will panic unless TCL_DEBUG is defined.  And this
> is only if you also turn on USE_TCL_ALLOC (-DUSE_TCLALLOC=1).  So for
> non-Windows users, they will get a segfault instead of an error
> message.

The default builds on both Unix and Windows (I don't know about the
Mac) will hit the panic code.  The twisty trail of following #defines
in tcl.h/tclCkalloc.c can be confusing, but it happens.  I assume the
same for the Mac.

BTW, just to make it clear for others, Tcl still does use the Tcl mem
allocator by default on Windows (-DUSE_TCLALLOC=1), but not on Unix.
We were considering changing this when moving to default compiling with
VC++6, as we've been told the default mem allocator finally has some
brains on Windows.

Jeffrey Hobbs                     Tcl Ambassador
ho...@Aj...          Ajuba Solutions (née Scriptics)

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

[TCLCORE] Using our time well

[John O. <ou...@aj...>]

The discussion about string allocation highlights one of the key
problems the Tcl Core Team needs to face, which is how to operate
efficiently.  It was lots of fun arguing the pros and cons of various
schemes, but I don't think that such a detailed discussion was worth
the time.  I doubt that this issue would make it onto anyone's
top-100 list of most important things to worry about in Tcl, yet it
seems to have occupied much of the Team's energy for couple of days.
Was that really the best way to spend our time?

I don't have a simple solution to propose, but we will need to operate
more efficiently than this.

The main thing I would suggest is for everyone to keep the big picture
in mind: what are the *most important* things we can do to enhance Tcl?
Small issues will need to be settled very very quickly  or else we'll
never get to the big issues.  One thought is that for a small issue like
this, if there isn't pretty immediate agreement on what to do then we
should just drop it and leave things as they are.  In this particular
case the problems were mostly theoretical anyhow: how many people have
actually run into issues that would be addressed by any of the proposed
fixes, versus, say, how many people would like a tab notebook widget?

-John-
________________________________________________________________________
John Ousterhout                            650-210-0102 tel
Chairman and Chief Technology Officer      650-230-4070 fax
Ajuba Solutions                            ou...@aj...
http://www.ajubasolutions.com

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

[TCLCORE] Re: Hintermayer's string allocation patch

[Jeffrey H. <jef...@aj...>]

> From: Mark Harrison [mailto:ma...@us...]
	...
> John Ousterhout <ou...@aj...> wrote:
> > So, if you run
> > out of memory, you can't necessarily even execute scripts to free
> > up memory.  Bottom line: better to panic cleanly with a nice simple
> > error message.
>
> At the VHLL conference, Steve Johnson mentioned that this behavior
> (dying on memory allocation failure) was a reason that he would never
> consider use Tcl in a mission-critical system.
>
> After his talk, we chatted a bit, and I explained that a memory
> error was just one of the failure modes we deal with when writing
> this kind of system.  The mechanisms that are routinely put into
> place for dealing with process death and node failure handle this
> situation.

At the same time it should also be said that people can override the
panic proc (with Tcl_SetPanicProc) and create a system that will
capture out-of-mem situations and allow some element of recovery.
I've outlined in detail how this can be done on the newsgroup, if
someone needs to pass it on.

Jeffrey Hobbs                     Tcl Ambassador
ho...@Aj...          Ajuba Solutions (née Scriptics)

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

[TCLCORE] Re: PROPOSAL: use realloc when growing strings

[John O. <ou...@aj...>]

I vote yes.

At 10:30 PM 8/31/2000 -0700, Brent Welch wrote:
>I think most would agree that using the system realloc() procedure instead
>of manually doing an alloc and copy.  The performance numbers shown by
>Eric showed that using realloc accounted for significant performance
>improvements, enough to justify a change.
>
>If there are major objections, please speak up.  Otherwise someone ought
>to formulate a simple patch that we should adopt.  If there are objections
>then we can call a vote on this issue. Otherwise, my take from the
>discussions is that folks are behind using realloc().
>
>I'd rather not have to vote on every core change so long as there is
>general concensus.  If I am off base here, again, please speak up.
>Perhaps its just as easy to hear a "yes" vote from everyone.
>
>My vote is yes.
>
>--      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.

________________________________________________________________________
John Ousterhout                            650-210-0102 tel
Chairman and Chief Technology Officer      650-230-4070 fax
Ajuba Solutions                            ou...@aj...
http://www.ajubasolutions.com

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

[TCLCORE] Re: Hintermayer's string allocation patch

[George H. <ga...@bl...>]

In message <4.2...@ma...>, John Ouste
rhout writes:

Thank you for taking the time to explain this.

 : The reason for the behavior is that recovering from memory outages
 : just isn't possible (IMHO).  There are way too many places where
 : memory is allocated, so it would add a lot of complexity to Tcl to
 : try and behave reasonably in every instance.  Furthermore, it is
 : difficult to figure out how to test memory exhaustion in all of these
 : places reliably, so in practice recovery wouldn't work ("if it hasn't
 : been used, it doesn't work").  Lastly, the whole idea of recovery
 : assumes that Tcl could do something useful even if it ran out of
 : memory, and that isn't true.  Dynamic memory allocation is used
 : *everywhere*, even in the guts of the interpreter.  So, if you run
 : out of memory, you can't necessarily even execute scripts to free
 : up memory.  Bottom line: better to panic cleanly with a nice simple
 : error message.

I agree with you on this last point.  In my own code do the same
thing.  When allocating memory for structures, strings, etc., there's
no practical way of recovering from memory exhaustion.  Panic-ing is a
reasonable solution.

But there's another class of allocations where I do want to know if I
can't allocate the requested amount of memory.  When I allocate a
large block of storage for for a vector, the contents of a file, etc.
I want to tell the user that his/her request failed.

    Tcl_GetIntFromObj(interp, objv[2], &requestedSize);
    arrayPtr = (double *)Tcl_Alloc(sizeof(double) * requestedSize);
    if (arrayPtr == NULL) {
        Tcl_AppendResult(interp, "can't allocate vector of ",
  	    Tcl_GetString(objv[2]), " bytes", (char *)NULL);
	return TCL_ERROR;
    }

I have no argument with panic-ing.  But after looking at TclpAlloc, I
don't see where it will panic unless TCL_DEBUG is defined.  And this
is only if you also turn on USE_TCL_ALLOC (-DUSE_TCLALLOC=1).  So for
non-Windows users, they will get a segfault instead of an error
message.  

We can make this consistent for all platforms by removing the
panic-ing from the TclpAlloc and putting it into (let's say) the
ckalloc macro.  As a consequence, I can check against memory
exhaustion for the rare cases where I can recover gracefully from it.

--gah

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

Re: [TCLCORE] PROPOSAL: use realloc when growing strings

[Andreas K. <a.k...@we...>]

--------; charset=us-ascii

> I think most would agree that using the system realloc() procedure instead
> of manually doing an alloc and copy.  The performance numbers shown by
> Eric showed that using realloc accounted for significant performance
> improvements, enough to justify a change.
 
> If there are major objections, please speak up.

I have no objection.

>  Otherwise someone ought
> to formulate a simple patch that we should adopt.  If there are objections
> then we can call a vote on this issue. Otherwise, my take from the
> discussions is that folks are behind using realloc().

I am.

> I'd rather not have to vote on every core change so long as there is
> general concensus.

Sure, but in this case it touches critical subsystem, so I believe a vote is 
appropriate.

>  If I am off base here, again, please speak up.
> Perhaps its just as easy to hear a "yes" vote from everyone.
> 
> My vote is yes.

I vote yes too.

-- 
Sincerely,
	Andreas Kupries <a.k...@we...>
		<http://www.purl.org/NET/akupries/>
-------------------------------------------------------------------------------

Re: [TCLCORE] Re: Hintermayer's string allocation patch

[Gerhard H. <g.h...@in...>]

Andreas Kupries wrote:
> 
> Hi, my two cents or so in this.
> 
> I go with George and John here, i.e. allocate until you the wall and
> then retract from the boundary to fill the rest in smaller
> increments.
> 
> What I like about this algorithm is that it not only preserves maximum
> performance for as long as possible while still being able to fill the
> memory to the max. but also that it is "self-tuning".
> 
> With this I mean that there is no need to adjust (tinker / fiddle
> with) some parameters like with the current patch proposed as by
> Gerhard to adapt the core to the host it is running on to get good
> performance on average. We get this automatically.
> 
> This makes it also easier for distributors of binaries. No need to
> guess some values for the parameters which will give good performance
> over a __range_of_machines__.
> 
> Gerhard, are you willing to try and write a second patch which uses
> this algorithm to solve the problem so that we may compare hard
> numbers instead of running in argumentative circles without hard data ?
> 

Well, I'm sorry, no. I do not have that much spare time and besides the
discussion I started by submitting this patch was a bit frustrating.
Ok, the patch is not the best solution, but I think it was worth
spending the time, I looked for a quick solution and didn't want to
rewrite the whole memory handling. Of course there are better
implementations, but that would require more time and maybe expertise,
which I don't have.
Maybe someone from the core team can do this.
It is a pity, that this discussion consumed more of my time than
actually writing the patch.

Gerhard
-- 
Gerhard Hintermayer
http://www.inode.at/g.hintermayer

[TCLCORE] Re: PROPOSAL: Limit memory doubling when appending to strings

[Dan K. <ku...@aj...>]

Brent the memory allocation algorithms you included in the
summary don't match those posted in Erics original post in
this thread (those in the patch).

>From Erics original post:

> Formerly, the growth algorithm was:
> 
>         newsize = 2 * (oldsize + appendsize)
> 
> Now, the growth algorithm is:
> 
>         if (oldsize + appendsize >= TCL_GROWTH_LARGE_STRING)
>             newsize = oldsize + (2 * appendsize) +  TCL_GROWTH_MIN_ALLOC
>         else 
>             newsize = 2 * (oldsize + appendsize)
>         endif
> 
> TCL_GROWTH_LARGE_STRING defaults to 1 megabyte; TCL_GROWTH_MIN_ALLOC
> defaults to 1 kilobyte, and is included to efficiently handle repeated
> small appends to a large string.

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

[TCLCORE] PROPOSAL: Limit memory doubling when appending to strings

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

This issue is more contentious, so instead of calling for a vote
I'll summarize the approaches proposed so far and try to summarize
the issues of each.

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.

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 TclpAlloc 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.

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:
if {size < LARGE_STRING_SIZE} {
    newsize = 2 * size;
} else {
    newsize = size + STRING_GROW_SIZE;
}
The values for LARGE_STRING_SIZE and STRING_GROW_SIZE are not yet
specified.  The original patch used 1 Meg and 1 K, 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 STRING_GROW_SIZE of
the available memory size.
Drawbacks:
This algorithm can slow down the append operation of strings
larger than LARGE_STRING_SIZE.  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"
(My descrption of this may not be accurate)
Retain the doubling algorithm until an attempt to allocate
memory fails.  When that occurs, reduce the growth by
halves until the allocation succeeds:
extra = size;
do {
    newsize = size + extra;
    newbuf = realloc(buf, newsize);
    extra = extra / 2;
} until (newbuf != NULL || extra < size_needed);
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.

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.

[TCLCORE] Re: Hintermayer's string allocation patch

[Andreas K. <a.k...@we...>]

Hi, my two cents or so in this.

I go with George and John here, i.e. allocate until you the wall and
then retract from the boundary to fill the rest in smaller
increments.

What I like about this algorithm is that it not only preserves maximum
performance for as long as possible while still being able to fill the
memory to the max. but also that it is "self-tuning".

With this I mean that there is no need to adjust (tinker / fiddle
with) some parameters like with the current patch proposed as by
Gerhard to adapt the core to the host it is running on to get good
performance on average. We get this automatically.

This makes it also easier for distributors of binaries. No need to
guess some values for the parameters which will give good performance
over a __range_of_machines__.



Gerhard, are you willing to try and write a second patch which uses
this algorithm to solve the problem so that we may compare hard
numbers instead of running in argumentative circles without hard data ?


-- 
Sincerely,
	Andreas Kupries <a.k...@we...>
		<http://www.purl.org/NET/akupries/>
-------------------------------------------------------------------------------

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

[TCLCORE] PROPOSAL: use realloc when growing strings

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

I think most would agree that using the system realloc() procedure instead
of manually doing an alloc and copy.  The performance numbers shown by
Eric showed that using realloc accounted for significant performance
improvements, enough to justify a change.

If there are major objections, please speak up.  Otherwise someone ought
to formulate a simple patch that we should adopt.  If there are objections
then we can call a vote on this issue. Otherwise, my take from the
discussions is that folks are behind using realloc().

I'd rather not have to vote on every core change so long as there is
general concensus.  If I am off base here, again, please speak up.
Perhaps its just as easy to hear a "yes" vote from everyone.

My vote is yes.

--	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.

[TCLCORE] Re: Hintermayer's string allocation patch

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

>>>"George Howlett" said:
 >  : Brent said:
 >  : Also, if you look at the patch, it replaces like 8 lines with 16 lines,
 >  : and by tuning the "large size" limit and the growth chunk size, we
 >  : can make the performance hit for things over the "large size" acceptable.
 >  : 
 >  : Can we be done with this now?
 > 
 > Please forgive me if I'm a little slow in seeing how the TCT operates.
 > BTW. Was this how the panic-ing version of TclpAlloc was included?

My "can we be done now" comment was premature and not appropriate.
I think we are all novices in the way TCT operates, or should operate.

I would like to bring this issue to closure, if possible.  So, let me
start by stating two different proposals, one for realloc, which I
hope is easy to resolve, and the other is for the large string append
problem where there are two different camps.
I'll start new threads for it.

--	Brent Welch	<we...@aj...>
	http://www.ajubasolutions.com
	Scriptics changes to Ajuba Solutions
	scriptics.com => ajubasolutions.com

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