tcl-core — Tcl Core Team discussions about Tcl development

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

[TCLCORE] Re: Hintermayer's string allocation patch

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

At 01:45 PM 8/31/2000 -0700, Jeffrey Hobbs wrote:
> > From: George Howlett [mailto:ga...@si...]
>         ...
> >  :  However, that requires changing around the ckalloc routines,
> >  :  because they panic by default when malloc returns NULL.
> >
> > In 8.3, "ckalloc" (TclpAlloc) panics at memory exhaustion only when
> > you have compiled with -DTCL_DEBUG and -DUSE_TCLALLOC=1.  If it does
> > otherwise, then TclpAlloc is broken.  The implication from the manual
>
>Well, that's just the way it is.  Tcl_Alloc/ckalloc *will* panic in
>Tcl (since 8.1) if you get a NULL from malloc.  This has been hashed
>out in numerous newsgroup threads.  The basic reasoning that I've heard
>(I wasn't around for this decision), is that if you are running out of
>memory, you're screwed.  It's better to panic with the "Unable to alloc"
>message than it is to follow on and fail because nowhere does the core
>actually handle a NULL return from ckalloc.

This is one of those issues that keeps coming up over and over again
when people learn about the behavior for the first time.  There's a
much better reason than "that's just the way it is".

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.

-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

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

I think this discussion has gone on too long now.  We're at the
point where the same people are repeating the same arguments
over and over again.  This means that there isn't going to be
total agreement.  So, it's time for someone to summarize the
arguments and then for people to reach a decision.

-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: Procedure/Namespace Behaviour

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

>>>Paul Welton said:
 > George Howlett wrote:
 > 
 > > In message <200...@po...>, Brent Welch writes:
 > >
 > >  : The other use of rename - call it "rename without behavior change" -
 > >  : is easy to justify.  That has been used for code profiling, and for
 > >  : enhancing commands by intercepting them, doing something, then
 > >  : calling the original procedure.
 > >
 > > I can do all this now in the same namespace.  Why a different
 > > namespace?
 > >
 > > --gah
 > 
 > Because if I am intercepting a procedure in a namespace that I am not responsible
 > for, I cannot choose a name with total confidence that it will
 > not collide with an existing name or one that may be used in future. Of course if
 > you choose an identifier including your own name and social
 > security number then you are reasonably safe, but I would not like to see the
 > style guide advising this :)

[info command] will help you pick a name that does not collide.

I'd like to bring a new perspective from my friend David Nichols who is
very smart.  When I explained the issue (he used Tcl long before
namespaces, now is a heavy Java user) he instantly understood the two
possible semantics and the various problems.  He said something like this:

"Well, it seems like you'd want closure semantics where you bind the
command to its original namespace.  But, that is very suprising to people.
The only reasonable thing to do is disallow it because both semantics 
have problems.  Futhermore, what happens when you
append a couple lines to the procedure definition and have to recompile,
won't you have to be careful you don't bind to the new namespace."

I think this last point touches on the reasons for the current semantics.
You are unlikely to change the definition of the procedure, but there is
a ordering problem between the rename and when you bytecode compile the command.
If you do the rename before the procedure has been executed, then Tcl
would end up compiling in the context of the new namespace.  However, if
the procedure was executed once first, it would have been compiled in
the context of the original namespace.  So, you have to do something
special or you get different results depending on if the procedure
had been compiled already or not.  I think the easy solution was to
toss the bytecodes at the time of rename, so Tcl would "naturally"
compile the procedure in the context of the new namespace.

So now I'm in a quandry.  I don't understand how the current semantics
can be safely used, and it looks like getting closure semantics
will be harder than might be expected.  I wouldn't be offended if
rename space1::foo spacde2::foo
raised an error.  I'm also still waiting for a compelling example
where renaming between namespaces is used for something other than
hiding the old name.

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

[TCLCORE] Re: Procedure/Namespace Behaviour

[Paul W. <pau...@sy...>]

George Howlett wrote:

> In message <200...@po...>, Brent Welch writes:
>
>  : The other use of rename - call it "rename without behavior change" -
>  : is easy to justify.  That has been used for code profiling, and for
>  : enhancing commands by intercepting them, doing something, then
>  : calling the original procedure.
>
> I can do all this now in the same namespace.  Why a different
> namespace?
>
> --gah

Because if I am intercepting a procedure in a namespace that I am not responsible
for, I cannot choose a name with total confidence that it will
not collide with an existing name or one that may be used in future. Of course if
you choose an identifier including your own name and social
security number then you are reasonably safe, but I would not like to see the
style guide advising this :)




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

[TCLCORE] Re: Procedure/Namespace Behaviour

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

> From: Brent Welch <we...@aj...>
> > OK, I was confused about which side of the argument you were on, ...
> 
> It doesn't help matters that I keep switching sides... :)
> 
> > As for the "history" of this issue, I know that when namespaces were
> > first being implemented in Tcl 8.0 that rename did not change the behavior of
> > a procedure inside a namespace.  
 
> Armed with that clue, I dove into my limited archives of Tcl
> sources, and sure enough in Tcl 8.0b2, [rename] behaves the way
> Donal wishes it did.  This was changed between release 8.0b2 and
> release 8.0p0.  The ChangeLog doesn't go back that far, but the
> changes file contains an entry:
 
> 7/30/97 (bug fix) If a procedure is renamed into a different
> namespace, it now executes in the context of that namespace. (BL)
 
> So...  Who is BL,

IIRC BL = Brian Lewis	(bytecode compiler)

-- 
So long,
	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] Re: Procedure/Namespace Behaviour

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

In message <200...@po...>, Brent Welch writes:

 : The other use of rename - call it "rename without behavior change" -
 : is easy to justify.  That has been used for code profiling, and for
 : enhancing commands by intercepting them, doing something, then
 : calling the original procedure.

I can do all this now in the same namespace.  Why a different
namespace?

--gah

--
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...@si...>]

In message <200...@po...>, Brent Welch writes:
 : So, it is broken.  It is not that we cannot allocate a 1 or 2 Gig string,
 : it is that we may not even be able to grow a Tcl string that will
 : fit into physical memory/swap space.

We can agree that replacing free/malloc with realloc is Ok.  It may
also be worth looking into tuning the grow rate of strings.  If may be
that realloc sufficiently diminishes the cost of allocations such that
a less aggressive growth rate is attractive.

But I don't agree that it's at all necessary that Tcl be able to grow
a string that exceeds physical memory.  Please make the case for any
application that requires such capabilities.

I especially don't like the "large size" memory parameter that doesn't
scale with memory sizes.  It's an simple matter to write a version of
TclpAlloc (and thereby Tcl_Realloc) that doesn't panic when it runs
out of memory.

 : 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?

--gah

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

> -----Original Message-----
> From: ak...@bl... [mailto:ak...@bl...]On
	...
> ... 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.

While this is a good approach, it does require a more extensive patch
to the core - adding new alloc stubs routines (which is probably a
good idea anyway).

Also, it still leaves behind the remnants of poor mem allocation in
Tcl if you use multiple large objects.  For the worst case, each string
in Tcl takes up twice as much space as it needs to.  Thus if we are
working with multiple large objects, we can have 120MB of actual data
taking up 240MB of memory, and we still hit a wall because a new large
object may not get any more memory, although 120MB is wasted.

Of course, the same can happen for lots of smaller objects if you have
the min algorithm switchover high, so there's no 100% win.  Thus the
point is, do we want to accept the fact that Tcl can't effectively use
more than half the available memory?  I find that hard to swallow, which
is why a trade-off should be considered, one that kicks in at a hard-coded
level (where excessive 2* waste is a lot more painful).

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: Procedure/Namespace Behaviour

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

>>>"George Howlett" said:

 > I like the current behavior. If you crowbar it the other way, how do
 > you get the current behavior?  As it stands now, you can explicitly
 > refer to the variable in the old namespace (if you want to hardwire
 > the procedure to a particular namespace variable).  I think by
 > renaming the procedure, you've already indicated something about its
 > portablility.  The other way you anchor the procedure to the
 > namespace.  

You like it, but have you ever taken advantage of it? :-)
I'd like to see a compelling example where you can take a procedure
and jam it into a different namespace and do something useful.

The other use of rename - call it "rename without behavior change" -
is easy to justify.  That has been used for code profiling, and for
enhancing commands by intercepting them, doing something, then
calling the original procedure.

 > I think Brent's right about working on the real problem which is an
 > onexit handler.

Right - probably should be a new thread.

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

[TCLCORE] Re: Procedure/Namespace Behaviour

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

In message <200...@po...>, Brent Welch writes:

 : I urge everyone to consider the following test program that sets a namespace
 : variable.  If the procedure is renamed to a different namespace, should it
 : modify the namespace variable in the new namespace, or continue to modify
 : the variable it was originally written to modify?

I like the current behavior. If you crowbar it the other way, how do
you get the current behavior?  As it stands now, you can explicitly
refer to the variable in the old namespace (if you want to hardwire
the procedure to a particular namespace variable).  I think by
renaming the procedure, you've already indicated something about its
portablility.  The other way you anchor the procedure to the
namespace.  

I think Brent's right about working on the real problem which is an
onexit handler.

--gah

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

[TCLCORE] Re: Procedure/Namespace Behaviour

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

> It's been a while so I don't recall all the context, but I believe I made
> the bug fix after someone complained that they were surprised by the
> initial "execute in the original namespace" semantics. Thinking
> about it now, I'm not sure what semantics are correct. The current scheme 
> really moves the proc including where it's globals point. The original
> scheme would let you repackage procs under a new namespace (good),
> but then those procs can have side effects outside their repackaged
> namespace (probably bad). 

Thanks for weighing in.  It's too bad the particular problem which
prompted the change can't be recalled.  Any chance there's an internal
log somewhere which might contain notes on this?

This is a complex enough design issue, that has been thought through
before, I'd sure like to be sure we're considering everything as we
re-think this.

The 8.0b2 behavior sure looks right to me, but I'd be more confident 
stating that if I knew in more detail why it was changed the first time.

DGP


--
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...@si...>]

In message <200...@po...>, Dan Kuchler writes:
 : > But if one still wants to handle this within Tcl, I have a slightly
 : > different tact.  When realloc fails, pull back the size.  It can fail
 : > when you can't allocate even the extra space needed.
 : 
 : Right.  If you look at Jeff's posts from yesterday
 : he mentions this option.  I initially proposed this
 : several weeks ago.  The current tcl C memory allocation
 : APIs will panic when the allocation fails.  I proposed
 : that a new API be added for growth algorithms where
 : you could specify two quantities.  One would be the
 : bare minimum amount of space needed to continue (the
 : size of the initial string + the size of the appended
 : string).  The second size would be the desired amount
 : of space to allocate (this would use a growth algorithm
 : similar to the one in the core today).  Then the
 : allocation function would (if the allocation failed)
 : gradually reduce the quantity of space asked for by
 : some algorithm/factor until it was at the minimum.
 : When the minimum was reached, if the allocation failed
 : it would panic.
 : 
 : The only issue with this was that it was probably a
 : little more work to implement.  I think that there
 : is room for both solutions.  One makes the core a
 : little more memory efficient and the other makes
 : the core a little more flexible in its memory
 : allocation.
 : 
 : Alternatively, if the TCT really thinks this is
 : too specialized the 'large string' size could
 : be included at a *really* high setting, and
 : only those who need it could tune the core
 : to use it.

This is a solution in need of a problem. 

While I think Gerhard's realloc mods sound very good, I reiterate my
question.  Where do you need a a 1 Gigabyte string?  (BTW, that's 1/2
of a 32-bit address space).

Please don't fix Tcl's growth scheme until it's broken.  First, make
the case for all the applications that this change fixes.  Otherwise
this is another Tcl pseudo-improvement.

--gah



--
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...@si...>]

In message <NDB...@aj...>, "Je
ffrey Hobbs" writes:

 :  However, that requires changing around the ckalloc routines,
 :  because they panic by default when malloc returns NULL.  

In 8.3, "ckalloc" (TclpAlloc) panics at memory exhaustion only when
you have compiled with -DTCL_DEBUG and -DUSE_TCLALLOC=1.  If it does
otherwise, then TclpAlloc is broken.  The implication from the manual
page is that Tcl_Alloc and Tcl_Free are replacements for malloc and
free.  Therefore Tcl_Alloc should ape malloc's behavior.

     These procedures provide a platform and compiler independent
     interface  for  memory  allocation.   Programs  that need to
     transfer ownership of memory blocks between  Tcl  and  other
     modules  should  use  these  routines rather than the native
     malloc() and free() routines  provided  by  the  C  run-time
     library.

And from Sun's manual on malloc(3X)...

     If  there  is  no  available  memory,  malloc(),  realloc(),
     memalign(),  valloc(),  and  calloc() return a null pointer.
     When realloc() returns NULL, the block pointed to by ptr  is
     left  intact.   If  size,  nelem,  or  elsize is 0, a unique
     pointer to the arena is returned.

 : bytes = (char *) ckallocEx(howMuchIWant, howMuchINeed);

I disagree with this.  We don't need another API function/macro to do
the right thing.  Is there some unexplained reason why ckalloc should
panic when out of memory?  Other than the fact the calling routine
sometimes doesn't test the result...

--gah

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

[Joe E. <jen...@fl...>]

Eric Melski <er...@aj...> wrote:
>
> Yes, the performance will be bad, but is it better to have a badly
> performing system that can allocate all of memory, or a really fast system
> that cannot?  This seems like a no-brainer to me:

It seems like a no-brainer to me too, but I come
to the exact opposite conclusion :-)

The quantity "all available memory" is really a
fuzzy concept on modern OSes.  The current patch
may allow a very few programs to run to completion that
would have failed under the old policy, but as
soon as somebody tries to run Netscape at the
same time those programs are going to fail again.

(Not to mention the fact that the programs which this
patch helps the most are, by definition, memory pigs.)


> 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.  This modification is simple, it works,
> and it is already implemented.  I have not yet seen any other proposal
> that can say the same.

I am highly suspicious of any modification that
changes the time complexity of [append].  [append x $y]
has *always* been O([string length $y]) asymptotically.
I have no idea how much code has been written that
relies on that fact, but my guess is "a lot".

The patch will improve Tcl's memory usage by at most
a constant factor.  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.


--Joe English

  jen...@fl...

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

[Joe E. <jen...@fl...>]

Donald G Porter <dg...@ca...> wrote:
>
> Yes, because (3KB * 1000) compares 2 big reallocs (original algorithm)
> with ~400 small reallocs (new algorithm).  (1KB * 1000) compares only
> 1 big realloc (original algorithm) to ~300 small reallocs.
>
> Results from Tcl 8.4a1:
> 047 {{STR append (1MB + 1KB * 1000)} 61321}
> Results from Tcl in CVS, 2000 August 31:
> 047 {{STR append (1MB + 1KB * 1000)} 68370}
>
> Now, neither test is "the right test".  They're both particular tests,
> but this should dispute the claim that the new patch is faster
> "in all cases".

In addition, since there is only about a ~10% difference
between the two numbers, I strongly suspect that the
"lots of little reallocs" case only does as well as
it does because of the way realloc() happens to be
implemented on the system on which it was run.
IOW: Don's system's realloc() is most likely growing
the allocated memory by powers-of-two internally *anyway*.


> It's worth considering the asymptotics, too.  As others have
> observed, the O(N**2) behavior of the new algorithm will bite when
> the "1000" in these benchmarks grows to 10000, 100000, 1000000, ...

Or on a system with a naive realloc() implementation,
if my guess is correct.


--Joe English

  jen...@fl...

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

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

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

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

[TCLCORE] Re: Hintermayer's string allocation patch

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

>>>"George Howlett" said:

 > While I think Gerhard's realloc mods sound very good, I reiterate my
 > question.  Where do you need a a 1 Gigabyte string?  (BTW, that's 1/2
 > of a 32-bit address space).
 > 
 > Please don't fix Tcl's growth scheme until it's broken.  First, make
 > the case for all the applications that this change fixes.  Otherwise
 > this is another Tcl pseudo-improvement.

>>> Brent Welch said:
> Apparently MacOS is more advanced than UNIX in this area.  In UNIX you
> have to be able to allocate the swap space to cover the virtual
> memory.  So, in practice, if you have 300 Meg of swap space, 192 Meg
> of real memory, and a 160 Meg string, you cannot append one byte to it
> in Tcl. 

So, it is broken.  It is not that we cannot allocate a 1 or 2 Gig string,
it is that we may not even be able to grow a Tcl string that will
fit into physical memory/swap space.

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?

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

[TCLCORE] Re: Hintermayer's string allocation patch

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

> From: George Howlett [mailto:ga...@si...]
	...
>  :  However, that requires changing around the ckalloc routines,
>  :  because they panic by default when malloc returns NULL.
>
> In 8.3, "ckalloc" (TclpAlloc) panics at memory exhaustion only when
> you have compiled with -DTCL_DEBUG and -DUSE_TCLALLOC=1.  If it does
> otherwise, then TclpAlloc is broken.  The implication from the manual

Well, that's just the way it is.  Tcl_Alloc/ckalloc *will* panic in
Tcl (since 8.1) if you get a NULL from malloc.  This has been hashed
out in numerous newsgroup threads.  The basic reasoning that I've heard
(I wasn't around for this decision), is that if you are running out of
memory, you're screwed.  It's better to panic with the "Unable to alloc"
message than it is to follow on and fail because nowhere does the core
actually handle a NULL return from ckalloc.

BTW, the docs for Tcl_Alloc, et al don't say anywhere that they are
drop-in replacements for malloc, et al, just that they should instead
be used when fiddling with memory shared by the core routines.

>  : bytes = (char *) ckallocEx(howMuchIWant, howMuchINeed);
>
> I disagree with this.  We don't need another API function/macro to do
> the right thing.  Is there some unexplained reason why ckalloc should
> panic when out of memory?  Other than the fact the calling routine
> sometimes doesn't test the result...

"sometimes" is actually never for the core, and I suppose it was easier
to make the check in the alloc function.  Anyway, creating an alternative
ckalloc would solve these problems.

In any case for core "improvements", lets not argue about what is the
"right thing" (this goes with other running threads).  Accept what the
core does now, for whatever reason, and then lets question whether there
is a more intuitive/appropriate way to do things.

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: Hintermayer's string allocation patch

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

> > > 2.  Tcl is faster in all append cases.  

> > Add this to string.bench and check the results:
> > 
> > bench -desc "STR append (1MB + 1KB * 1000)" \
> > 	-body {str-append $base $kilobyte 1000}

> Does this case produce significantly different results from:
> 
> bench -desc "STR append (1MB + 3KB * 1000)" \
>         -body {str-append $base $kilo3 1000}

Yes, because (3KB * 1000) compares 2 big reallocs (original algorithm)
with ~400 small reallocs (new algorithm).  (1KB * 1000) compares only
1 big realloc (original algorithm) to ~300 small reallocs.  

Results from Tcl 8.4a1:

$ tclsh src/tclbench/libbench.tcl src/tclbench/tcl/string.bench
047 {{STR append (1MB + 1KB * 1000)} 61321}

Results from Tcl in CVS, 2000 August 31:
$ src/tcl8.4/unix/tclsh src/tclbench/libbench.tcl src/tclbench/tcl/string.bench ...
047 {{STR append (1MB + 1KB * 1000)} 68370}

Now, neither test is "the right test".  They're both particular tests,
but this should dispute the claim that the new patch is faster
"in all cases".

It's worth considering the asymptotics, too.  As others have
observed, the O(N**2) behavior of the new algorithm will bite when
the "1000" in these benchmarks grows to 10000, 100000, 1000000, ...

Another concern is the platform-specific tuning necessary to choose
good values for TCL_GROWTH_LARGE_STRING and TCL_GROWTH_MIN_ALLOC.
How will good values for these be determined over all the platforms
Tcl runs on and will run on over the next, say, 5 years?

DGP

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

[TCLCORE] Re: Procedure/Namespace Behaviour

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

>>>"Jeffrey Hobbs" said:
 > > From: Donald G Porter [mailto:dg...@ca...]

 > The quandry being whether ::B::foo should still have executed in the
 > creating namespace (::A).  Personally I think the above seems logical,
 > but some argue that the original proc author should be the only one
 > to say what namespace the proc evals in.

There is "logic" to both semantics, but I can only see the value in
the semantics where rename does not change the behavior of the command.
In the absence of namespaces, rename just changed the name of the
command and had no effect on how it operated (unless you deleted it, of 
course).
The 8.0b2 release had these semantics also, basically because the
bytecodes had all been compiled and resolved to the original namespace.
I cannot see the value in "repackaging" a procedure to suddenly operate
on a different namespace.  Well, I suppose I can see power, but is there
some other programming language construct this would emulate? By analogy,
in an O-O system, it is as if a method of class A were suddenly a
method of class B.  Unless you are lucky, it just won't operate right
in the new class.  Are there class systems that allow this sort of renaming?
If not, and I suspect there are not any, I think a rename operation
that *does not* change the behavior of the command is best.

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

[TCLCORE] Re: Procedure/Namespace Behaviour

[Brian L. <Bri...@En...>]

dg...@ca... said:
> It's too bad the particular problem which prompted the change can't be
> recalled.  Any chance there's an internal log somewhere which might
> contain notes on this?

I just tried looking through my Tcl mail for 1997 and didn't find 
anything about this. 

> This is a complex enough design issue, that has been thought through
> before, I'd sure like to be sure we're considering everything as we
> re-think this.

Mike McLennan may have some things to say. He's the original implementor
of namespaces. 

  Brian



--
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...@si...>]

In message <39A...@in...>, Gerhard Hintermayer writes:

 : The original problem was the "Maximum string length" thread discussed so
 : time ago in c.l.t. Actually I never had a problem running out of memory
 : when using strings, but somebody else had, and this was an interesting
 : challence. I thought there had to be changed something. The doubling
 : algorithm might be good under normal circumstances, but not when
 : reaching really large strings.

 : Suppose you give somebody 100 $, but at the same moment you tell him,
 : "be carefull, you cannot spend more than 50 $". Thats not logical. If
 : some Tcl-programmers need a string longer than half of his system
 : memory, for whatever reason, why not giving him the chance to do so ?
 : You could tell him, you _can_ handle that large strings, but at a cost
 : of performance.


 : As I've already stated in c.l.t., the speed improvement is only because
 : I replaced the call of malloc with a call to realloc and by not having
 : to copy the string data if the allocated memory block is simply
 : extended.
 : If you don't like changing the doubling algorithm, well you don't have
 : to. It is independent of the replacement of the malloc call. If you
 : don't use it, you will still have the speed improvements.

Thank you for the more complete description.  It helps a lot.

It does seem worthwhile to change malloc/free to realloc and test the
performance differences.  The test should include reallocations at
different rates: 200 bytes, 2K, 2M, 200M, variable sizes, etc.

The current algorithm is a bit greedy.  Usually one keeps doubling the
old size until it's at least the new required size.
    
    newSize = oldSize + appendSize;
    while (oldSize < newSize) {
	oldSize += oldSize;
    }

You use less memory, but make more reallocations.  We can argue about
tradeoffs.  But I still agree with John.  When one is asking for more
than 1/2 virtual memory, you probably have exhausted physical memory
and are now benchmarking the swapper.

I've never run into this problem and at some point it becomes special
purpose enough to require a custom solution (e.g. allocate your own
buffer).  I don't know if this a practical or theoretical problem?
Why does anyone need a 1 Gig string?

But if one still wants to handle this within Tcl, I have a slightly
different tact.  When realloc fails, pull back the size.  It can fail
when you can't allocate even the extra space needed.

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

At least this way the penalty is all on the special case, not general
usage.   

--gah

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

[TCLCORE] Re: Procedure/Namespace Behaviour

[Brian L. <Bri...@En...>]

jef...@aj... said:
> The quandry being whether ::B::foo should still have executed in the
> creating namespace (::A).  Personally I think the above seems logical,
> but some argue that the original proc author should be the only one to
> say what namespace the proc evals in.

It's been a while so I don't recall all the context, but I believe I made
the bug fix after someone complained that they were surprised by the
initial "execute in the original namespace" semantics. Thinking
about it now, I'm not sure what semantics are correct. The current scheme 
really moves the proc including where it's globals point. The original
scheme would let you repackage procs under a new namespace (good),
but then those procs can have side effects outside their repackaged
namespace (probably bad). 

  Brian



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