Maximum variable length in TCL
mrei...@my-deja.com
we need to know the maximum allowed length of TCL
variables (resp. strings), as we write some expect
scripts expecting *very* long messages.
Thanks,
Markus
Sent via Deja.com http://www.deja.com/
Before you buy.
Jeffrey Hobbs
> we need to know the maximum allowed length of TCL
> variables (resp. strings), as we write some expect
> scripts expecting *very* long messages.
How much memory do you have? Subtract some overhead and that's
about how much.
--
Jeffrey Hobbs The Tcl Guy
hobbs at ajubasolutions.com Ajuba Solutions (née Scriptics)
Paul Duffin
>
> Hello all,
>
> we need to know the maximum allowed length of TCL
> variables (resp. strings), as we write some expect
> scripts expecting *very* long messages.
>
Tcl has no fixed limits like that. There are limits but they come from things
outside Tcl's control like available memory, type sizes, ...
How *long* are your messages ? 1K 10K 100K 1M 10M 100M ...
Expect may have some limits in it to with line length, buffer size but I
don't know for certain.
Phil Ehrens
>mrei...@my-deja.com wrote:
>> we need to know the maximum allowed length of TCL
>> variables (resp. strings), as we write some expect
>> scripts expecting *very* long messages.
>
>about how much.
>
Hmmm... shouldn't there be a "divide by something" in there
somewhere? This looks like on of those Fannie Farmer recipes
where if you follow it too closely you get "New England
Spoiled Beef".
Jan Hildebrandt
> Tcl has no fixed limits like that. There are limits but they come
> from things outside Tcl's control like available memory, type
> sizes, ...
> How *long* are your messages ? 1K 10K 100K 1M 10M 100M ...
> Expect may have some limits in it to with line length, buffer size
> but I don't know for certain.
Recently I tried to find an answer to the initial question myself.
On a big machine (virtual mem > 1 GB) I started a test script
that (in an endless loop) appends some characters to a variable
and prints the actual length of the string. The script aborted with
a segfault when the string had a length of about 100.000.000 chars.
I also tried to load a very big file (approx. 1 GB) using read - same
result, segfault.
I have to admit I was somewhat disappointed. Everything has an end,
especially RAM ;-) - but a segfault isn't what I'm expecting here.
By the way, this was Tcl/Tk 8.1.0, on that particular machine we
had no newer version. Does something like that still happen with
Tcl 8.3.1?
Regards,
Jan Hildebrandt
MATHEMA Software GmbH (http://www.mathema.de)
Nägelsbachstraße 25a D-91052 Erlangen, Germany
Tel: (+49)9131/8903-0 Fax: (+49)9131/8903-55
Paul Duffin
>
> Paul Duffin <pdu...@hursley.ibm.com> wrote:
>
> > Tcl has no fixed limits like that. There are limits but they come
> > from things outside Tcl's control like available memory, type
> > sizes, ...
>
> > How *long* are your messages ? 1K 10K 100K 1M 10M 100M ...
>
> > Expect may have some limits in it to with line length, buffer size
> > but I don't know for certain.
>
> Recently I tried to find an answer to the initial question myself.
> On a big machine (virtual mem > 1 GB) I started a test script
> that (in an endless loop) appends some characters to a variable
> and prints the actual length of the string. The script aborted with
> a segfault when the string had a length of about 100.000.000 chars.
> I also tried to load a very big file (approx. 1 GB) using read - same
> result, segfault.
> I have to admit I was somewhat disappointed. Everything has an end,
> especially RAM ;-) - but a segfault isn't what I'm expecting here.
>
> By the way, this was Tcl/Tk 8.1.0, on that particular machine we
> had no newer version. Does something like that still happen with
> Tcl 8.3.1?
>
Seg faults shouldn't happen, as far as I know Tcl should just panic. Not
the cleanest of things but there is not a lot else that you can do.
Do you have call stacks of the segfaults ?
Gerhard Hintermayer
>
> Paul Duffin <pdu...@hursley.ibm.com> wrote:
>
> > Tcl has no fixed limits like that. There are limits but they come
> > from things outside Tcl's control like available memory, type
> > sizes, ...
>
> > How *long* are your messages ? 1K 10K 100K 1M 10M 100M ...
>
> > Expect may have some limits in it to with line length, buffer size
> > but I don't know for certain.
>
> Recently I tried to find an answer to the initial question myself.
> On a big machine (virtual mem > 1 GB) I started a test script
> that (in an endless loop) appends some characters to a variable
> and prints the actual length of the string. The script aborted with
> a segfault when the string had a length of about 100.000.000 chars.
> I also tried to load a very big file (approx. 1 GB) using read - same
> result, segfault.
> I have to admit I was somewhat disappointed. Everything has an end,
> especially RAM ;-) - but a segfault isn't what I'm expecting here.
>
> By the way, this was Tcl/Tk 8.1.0, on that particular machine we
> had no newer version. Does something like that still happen with
> Tcl 8.3.1?
>
when the length of the string gets ~ 126.000.000 I get a "unable to
alloc 254000001 bytes","Aborted" message.
Seems to me, that the string has to fit into real memory, since my swap
space is not used.
--
Gerhard Hintermayer
http://members.aon.at/gerhard.hintermayer
Jan Hildebrandt
[...]
> Seg faults shouldn't happen, as far as I know Tcl should just
> panic. Not the cleanest of things but there is not a lot else
> that you can do.
But in fact there *was* enough memory. That's why I was so
disappointed; it's (sort of) OK if it segfaults when there
is no memory left, but this was a machine with *lots* of RAM
(not only 100 MB...) and a lot more swap.
> Do you have call stacks of the segfaults ?
No, I don't. I didn't investigate that further, just was interested
if there's a hard coded limit for variable length in the interpreter.
I was sure there isn't, and it seems to be so.
Maybe you just want to try it yourself with Tcl 8.3.1, could be
of interest to all... if you add not only 3 chars (like I did) per
iteration (I had plenty of time for the test...) but maybe 10 or
20 and you've got a fast machine you should see some results soon.
Paul Duffin
>
> Tested this under 8.3.1 with 256M Ram
> when the length of the string gets ~ 126.000.000 I get a "unable to
> alloc 254000001 bytes","Aborted" message.
>
> Seems to me, that the string has to fit into real memory, since my swap
> space is not used.
>
That is an operating system issue, not a Tcl one. What operating system
did you test it on ?
Gerhard Hintermayer
Linux
Should'nt it be possible to allocate memory segments up to real mem+swap
space (minus memory for active processes and some overhead) on unixes ?
Jan Hildebrandt
> Gerhard Hintermayer wrote:
>>
>> Tested this under 8.3.1 with 256M Ram
>> when the length of the string gets ~ 126.000.000 I get a "unable to
>> alloc 254000001 bytes","Aborted" message.
Mmmh, interesting. I didn't get such a message, just a seg
fault :-(
>> Seems to me, that the string has to fit into real memory, since my swap
>> space is not used.
>>
> That is an operating system issue, not a Tcl one. What operating system
> did you test it on ?
I tested that on a Sparc machine running Solaris 2.6.
On what platform did you try it, Gerhard?
Have a nice weekend,
Dan Kuchler
> Mmmh, interesting. I didn't get such a message, just a seg
> fault :-(
You should rerun your tests with tcl/tk 8.3.1 instead of using
8.1
There are a lot of bug fixes that have been made between 8.1 and
8.3.1
I don't know if that will change the results of your particular
test, but it can't hurt.
--Dan
Paul Duffin
>
> Paul Duffin wrote:
> >
> > Gerhard Hintermayer wrote:
> > >
> > > Tested this under 8.3.1 with 256M Ram
> > > when the length of the string gets ~ 126.000.000 I get a "unable to
> > > alloc 254000001 bytes","Aborted" message.
> > >
> > > space is not used.
> > >
> >
> > That is an operating system issue, not a Tcl one. What operating system
> > did you test it on ?
>
>
> Should'nt it be possible to allocate memory segments up to real mem+swap
> space (minus memory for active processes and some overhead) on unixes ?
See my other post about the process limit on memory and the ulimit command.
I am not sure whether Linux supports that but it is worth looking at.
Gerhard Hintermayer
>
> [...]
> >
> > Should'nt it be possible to allocate memory segments up to real mem+swap
> > space (minus memory for active processes and some overhead) on unixes ?
>
> See my other post about the process limit on memory and the ulimit command.
> I am not sure whether Linux supports that but it is worth looking at.
ulimit says unlimited. Strange thing is, that none of the swap space is
consumed, when the size of the string grows larger than available phys
mem. When I do a calloc in C of approx 250M, free tells me, that almost
no memory is available anymore, and all swap space is consumed too.
Strange is also, that append needs 2 times x (plus something) memory to
append to a string of length x ? Does append use "copy on write" instead
of modifying the append var directly ?
Mark Stucky
Jan Hildebrandt wrote:
>
> Paul Duffin <pdu...@hursley.ibm.com> wrote:
> [...]
> > Seg faults shouldn't happen, as far as I know Tcl should just
> > panic. Not the cleanest of things but there is not a lot else
> > that you can do.
>
> But in fact there *was* enough memory. That's why I was so
> disappointed; it's (sort of) OK if it segfaults when there
> is no memory left, but this was a machine with *lots* of RAM
> (not only 100 MB...) and a lot more swap.
Are you sure there *was* enough memory???
On some systems, the OS limits how much memory a given process
can use.
--Mark
> Regards,
Paul Duffin
>
> Paul Duffin <pdu...@hursley.ibm.com> wrote:
> [...]
> > Seg faults shouldn't happen, as far as I know Tcl should just
> > panic. Not the cleanest of things but there is not a lot else
> > that you can do.
>
> But in fact there *was* enough memory. That's why I was so
> disappointed; it's (sort of) OK if it segfaults when there
> is no memory left, but this was a machine with *lots* of RAM
> (not only 100 MB...) and a lot more swap.
>
There are a couple of things which could affect this, firstly when
appending Tcl may need to grow the allocated memory and when it does
this it asks for twice as much as it thinks it needs. This means that
at the time you had a 100MB string Tcl could have been trying to
allocate another 200MB string which means that your total requirement
was 300MB or so.
Also, if it is Unix then there can be per process limits on the size of
the heap which means that a process can run out of heap while there is
still a lot of physical and virtual memory available.
Running ulimit -a on my AIX machine results in
time(seconds) unlimited
file(blocks) 2097151
data(kbytes) 131072
stack(kbytes) 32768
memory(kbytes) 32768
coredump(kbytes) 2097151
nofiles(descriptors) 2000
> > Do you have call stacks of the segfaults ?
>
> No, I don't. I didn't investigate that further, just was interested
> if there's a hard coded limit for variable length in the interpreter.
> I was sure there isn't, and it seems to be so.
>
> Maybe you just want to try it yourself with Tcl 8.3.1, could be
> of interest to all... if you add not only 3 chars (like I did) per
> iteration (I had plenty of time for the test...) but maybe 10 or
> 20 and you've got a fast machine you should see some results soon.
>
I will try it later.
Andreas Kupries
Gerhard Hintermayer <gerhard.h...@aon.at> writes:
> Paul Duffin wrote:
>>> Should'nt it be possible to allocate memory segments up to real
>>> mem+swap space (minus memory for active processes and some
>>> overhead) on unixes ?
>> See my other post about the process limit on memory and the ulimit
>> command. I am not sure whether Linux supports that but it is worth
>> looking at.
> ulimit says unlimited. Strange thing is, that none of the swap space
> is consumed, when the size of the string grows larger than available
> phys mem. When I do a calloc in C of approx 250M, free tells me,
> that almost no memory is available anymore, and all swap space is
> consumed too.
> Strange is also, that append needs 2 times x (plus something) memory
It doesn't `need` that much memory. This is just the strategy which
was implemented for appending. Usually each string in Tcl has some
unused memory behind the real string (overallocated before). This
makes appending faster as there is no need to reallocate the memory
for every single append. Only if that space runs out Tcl will
reallocate that string. And double the allocated space during that
process, to get more place for the additional appends it expects.
> to append to a string of length x ? Does append use "copy on write"
> instead of modifying the append var directly ?
See above.
--
Sincerely,
Andreas Kupries <a.ku...@westend.com>
<http://www.purl.org/NET/akupries/>
-------------------------------------------------------------------------------
lvi...@cas.org
According to Paul Duffin <pdu...@hursley.ibm.com>::>
:> > Tcl has no fixed limits like that. There are limits but they come
:> > from things outside Tcl's control like available memory, type
:> > sizes, ...
:> The script aborted with
:> a segfault when the string had a length of about 100.000.000 chars.
:> I also tried to load a very big file (approx. 1 GB) using read - same
:> result, segfault.
:> I have to admit I was somewhat disappointed. Everything has an end,
:> especially RAM ;-) - but a segfault isn't what I'm expecting here.
:Seg faults shouldn't happen, as far as I know Tcl should just panic. Not
:the cleanest of things but there is not a lot else that you can do.
There are, IMO, few cases where an _interpreter_ should core dump. About
the only one that comes to mind, actually, is perhaps the case when it receives
some specific signal or external event specifically documented to cause
a core dump. A second condition I guess MIGHT be the case where one
has attempted to obtain some system resource and failed, and when attempting
to continue, the interpreter finds it is unable to do so.
It seems to me that in most other cases, a core dump should indicate that
a case has arisen that was not anticipated by the code and thus indicates a
need for a code modification.
--
<URL: https://secure.paypal.com/refer/pal=lvirden%40yahoo.com>
<URL: mailto:lvi...@cas.org> <URL: http://www.purl.org/NET/lvirden/>
Unless explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.
lvi...@cas.org
According to Mark Stucky <mst...@tiac.net>:
:Are you sure there *was* enough memory???
:
:On some systems, the OS limits how much memory a given process
:can use.
Sure would be nicer though if Tcl raised an error condition, reporting
the attempted request and the failure code as the cause of the error.
lvi...@cas.org
According to Andreas Kupries <a.ku...@westend.com>:
:> Strange is also, that append needs 2 times x (plus something) memory
:
:It doesn't `need` that much memory. This is just the strategy which
:was implemented for appending. Usually each string in Tcl has some
:unused memory behind the real string (overallocated before). This
:makes appending faster as there is no need to reallocate the memory
:for every single append. Only if that space runs out Tcl will
:reallocate that string. And double the allocated space during that
:process, to get more place for the additional appends it expects.
I wonder if a improved algorithm where when the requested allocation
failed, a smaller number (size + 1/2 size or some other algorithm) might
be attempted...
Cameron Laird
>
>According to Mark Stucky <mst...@tiac.net>:
>:Are you sure there *was* enough memory???
>:
>:On some systems, the OS limits how much memory a given process
>:can use.
>
>Sure would be nicer though if Tcl raised an error condition, reporting
>the attempted request and the failure code as the cause of the error.
.
.
I happen to agree.
The historic argument on the other side is that it's expensive
to check (what amounts to) malloc() results, and that if one
of those fails, you're in such bad shape anyway that Tcl will
probably not be able to get an error out to the user's visibility.
I believe this argument has rather conclusively been shown to be
false, at least under modern circumstances, but the Tcl source
base would involve a fairly large amount of rewriting to get
right.
The conclusion: while Tcl is pleasingly robust in general, I
believe it retains vulnerabilities to memory exhaustion, and
there's no particular prospect they'll be fixed soon. It's NOT
a matter of just checking one or two particular oversights.
--
Cameron Laird <cla...@NeoSoft.com>
Business: http://www.Phaseit.net
Personal: http://starbase.neosoft.com/~claird/home.html
Jeffrey Hobbs
>
> In article <8m49mi$l07$3...@srv38.cas.org>, <lvi...@cas.org> wrote:
> >
> >According to Mark Stucky <mst...@tiac.net>:
> >:Are you sure there *was* enough memory???
> >:
> >:On some systems, the OS limits how much memory a given process
> >:can use.
> >
> >Sure would be nicer though if Tcl raised an error condition, reporting
> >the attempted request and the failure code as the cause of the error.
> .
> .
> .
> I happen to agree.
>
> The historic argument on the other side is that it's expensive
> to check (what amounts to) malloc() results, and that if one
> of those fails, you're in such bad shape anyway that Tcl will
> probably not be able to get an error out to the user's visibility.
>
> I believe this argument has rather conclusively been shown to be
> false, at least under modern circumstances, but the Tcl source
> base would involve a fairly large amount of rewriting to get
> right.
>
> The conclusion: while Tcl is pleasingly robust in general, I
> believe it retains vulnerabilities to memory exhaustion, and
> there's no particular prospect they'll be fixed soon. It's NOT
> a matter of just checking one or two particular oversights.
Actually, that's all incorrect. Tcl does the checks and has the
hooks to catch low mem conditions. Not very hard to add in. Of
course, to handle it correctly, you need to do something like
alloc and hold a good chunk of mem at the start, which you can
release when the low mem situation hits.
This doesn't negate the fact that when not done properly, if the
process is out of memory, you are most likely SOL. That is why
Tcl just drops out with a standard panic now.
Cameron Laird
Jeffrey Hobbs <jeffre...@ajubasolutions.com> wrote:
>Cameron Laird wrote:
.
.
.
>> The conclusion: while Tcl is pleasingly robust in general, I
>> believe it retains vulnerabilities to memory exhaustion, and
>> there's no particular prospect they'll be fixed soon. It's NOT
>> a matter of just checking one or two particular oversights.
>
>Actually, that's all incorrect. Tcl does the checks and has the
>hooks to catch low mem conditions. Not very hard to add in. Of
>course, to handle it correctly, you need to do something like
>alloc and hold a good chunk of mem at the start, which you can
>release when the low mem situation hits.
>
>This doesn't negate the fact that when not done properly, if the
>process is out of memory, you are most likely SOL. That is why
>Tcl just drops out with a standard panic now.
.
.
Now I'm confused.
Is Tcl pleasingly robust in general?
Is it true that one can reliably fault-out a Tcl interpreter
by banging against memory constraints? That's certainly the
symptom I see with 8.0, and it's how the sources I just glanced
at look. If so, is it also true that there are no particular
plans to change that reality soon?
What's the "all incorrect" part I need to change?
Jeffrey Hobbs
You have to make use of Tcl_SetPanicProc, and do the leg-work to
handle Tcl panic's. If you get "unable to alloc*", then Tcl
panic'ed because it was out of memory. Fairly simple. Remember
to save some extra first though, otherwise it's a pointless task.
People have successfully guarded against low-mem failure doing
just that.
Cameron Laird
Jeffrey Hobbs <jeffre...@ajubasolutions.com> wrote:
.
.
.
>You have to make use of Tcl_SetPanicProc, and do the leg-work to
>handle Tcl panic's. If you get "unable to alloc*", then Tcl
>panic'ed because it was out of memory. Fairly simple. Remember
>to save some extra first though, otherwise it's a pointless task.
>People have successfully guarded against low-mem failure doing
>just that.
.
.
Tell me if this is a correct high-level summary:
1. People writing *in* Tcl (scripting, using the
command interface, ...) are subject to segfaults
from extreme memory demands.
2. People who access the Tcl API can easily protect
themselves from these segfaults with well-known
and often-used ("[f]airly simple") idioms.
3. There is not a plan to change the existing inter-
preter (as seen in, for example, tclsh) to
lessen its vulnerability to memory-starved
segfaults.
Don Porter
>> You have to make use of Tcl_SetPanicProc, and do the leg-work to
>> handle Tcl panic's. If you get "unable to alloc*", then Tcl
>> panic'ed because it was out of memory. Fairly simple.
Cameron Laird <cla...@starbase.neosoft.com> wrote:
> Tell me if this is a correct high-level summary:
> 1. People writing *in* Tcl (scripting, using the
> command interface, ...) are subject to segfaults
> from extreme memory demands.
> 2. People who access the Tcl API can easily protect
> themselves from these segfaults with well-known
> and often-used ("[f]airly simple") idioms.
Not really. All Tcl_SetPanicProc can really do for you is let you
control *how* your app will "segfault" -- meaning immediately
terminate without returning to the logical control flow of your
program.
Routines which call panic() do not expect it to return. They
expect it to present a message to the user and terminate the
application, probably with abort(). Using Tcl_SetPanicProc to
send panic() calls to a routine which returns is not a good idea.
--
| Don Porter Mathematical and Computational Sciences Division |
| donald...@nist.gov Information Technology Laboratory |
| http://math.nist.gov/~DPorter/ NIST |
|______________________________________________________________________|
Jeffrey Hobbs
>
> Jeffrey Hobbs <jeffre...@ajubasolutions.com> wrote:
> >> You have to make use of Tcl_SetPanicProc, and do the leg-work to
> >> handle Tcl panic's. If you get "unable to alloc*", then Tcl
> >> panic'ed because it was out of memory. Fairly simple.
>
> Cameron Laird <cla...@starbase.neosoft.com> wrote:
> > Tell me if this is a correct high-level summary:
> > 1. People writing *in* Tcl (scripting, using the
> > command interface, ...) are subject to segfaults
> > from extreme memory demands.
> > 2. People who access the Tcl API can easily protect
> > themselves from these segfaults with well-known
> > and often-used ("[f]airly simple") idioms.
>
> Not really. All Tcl_SetPanicProc can really do for you is let you
> control *how* your app will "segfault" -- meaning immediately
> terminate without returning to the logical control flow of your
> program.
>
> Routines which call panic() do not expect it to return. They
> expect it to present a message to the user and terminate the
> application, probably with abort(). Using Tcl_SetPanicProc to
> send panic() calls to a routine which returns is not a good idea.
True and false. Most instances where 'panic' is used, it shouldn't
return. However, it is possible (and has been done) to override
the panic proc to capture the low-mem case. If you have set things
up properly where you can release a chunk of space to do cleanup,
then that works. Do note that you can only really do cleanup though,
because you can only release your chunk once (unless you allocate an
extra meg and release in 100K increments).
In any case, you should just be cleaning up and exiting more
gracefully. There isn't much else you can do. Running low on mem
doesn't just mean that it's the Tcl process about to choke. It
could be another ill app taking up all the mem.
Think of the simple case where you have two Tcl processes running
ad infinitum sucking up mem resources. Each may have the allocation
trick setup. However, when the low mem case hits, both are going to
do the fallback. If you aren't just cleaning up, then one of the
processes may just suck up the mem that the other released to allow
it to do something. It's a no-win situation, with a fragile way to
cleanup and that's about it.
Jeffrey Hobbs
> In article <3985BED2...@ajubasolutions.com>,
> Jeffrey Hobbs <jeffre...@ajubasolutions.com> wrote:
...
> >handle Tcl panic's. If you get "unable to alloc*", then Tcl
> >to save some extra first though, otherwise it's a pointless task.
> >People have successfully guarded against low-mem failure doing
> >just that.
...
> 1. People writing *in* Tcl (scripting, using the
> command interface, ...) are subject to segfaults
> from extreme memory demands.
Correct, unless you have a C extension to set this up for you.
> 2. People who access the Tcl API can easily protect
> themselves from these segfaults with well-known
> and often-used ("[f]airly simple") idioms.
Correct, as above.
> 3. There is not a plan to change the existing inter-
> preter (as seen in, for example, tclsh) to
> lessen its vulnerability to memory-starved
> segfaults.
No other plausible suggestions have been made. See my response
to Don on why low-mem situations are almost always lose-lose no
matter what you may try and do.
Dan Kuchler
> > 3. There is not a plan to change the existing inter-
> > preter (as seen in, for example, tclsh) to
> > lessen its vulnerability to memory-starved
> > segfaults.
>
> No other plausible suggestions have been made. See my response
> to Don on why low-mem situations are almost always lose-lose no
> matter what you may try and do.
I agree that tclsh shouldn't segfault in a low-mem situation.
If the tcl interpreter knows that a memory allocation failed,
and it is going to exit because it isn't being given any more
memory, then it should at least exit with a panic or something.
I don't think a segfault is acceptable, because when an end user
gets a segfault they are more likely to assume memory corruption
than that the interpreter ran out of memory.
Has anyone tried the latest sources 8.3.1 or 8.4a1 to see
what the interpreter does in the out of memory condition?
I believe the current interpreter panics, and doesn't segfault
(there is a distinction between the two).
One thing that you (Jeff) seem to be assuming is that the
failed malloc is unrecoverable, which isn't always true.
Since there are algorithms in the core that grow the allocation
by a multiple (2x?) of the current allocation, the failed allocation
could be an allocation of 100 MB, 200 MB, ... in which cases
there is plenty of memory to make a sane exit, or even
better, those algorithms, should be smart enough (and
be able to) back off their allocations, so if 2x fails,
it should back down to some smaller (1.75x, 1.5x, or 1.25x)
allocation, rather than panicking.
There is definite work that could be done in this area,
because I think it is entirely possible to end up in a
situation where an algorithm in tcl for minimizing
memory allocation will cause the allocation to fail well
before the system has used any where near all the memory.
--Dan
Leitgeb Andreas
circumstance"
Another one is the behaviour upon loss of X11-connection.
For many applications it would be very desireable to be able
to e.g. obtain the text from a text-window (and save it in
a session-file for later recovery) even if the X-server
has crashed, or the network between X-server and the tk-script
broke down.
I would think of an API similar to
wm protocol CRASH script
(although a broken X11-connection is not really related to the wm)
While after that event it would not be useful to open new windows, it
should still be possible to retrieve information from existent tk-widgets
(any infos that are stored on client-side), and everything from Tcl
(including fileevents for sockets & pipes,...).
If no crash-handler has been defined, then, for "compatibility"
the normal X11-crash-behaviour is ok.
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
(Note: I'm actually quite an evil virus, so delete all your *.doc files now!)
Karl Lehenbauer
where ckalloc panics if it can't return memory. The prior method was
that everywhere you did a malloc you included a check for return value
of NULL and then panicked if you got that.
There are ~800 locations where ckalloc is called in the Tcl & Tk 8.3.1
source. In as dynamic a memory environment as Tcl has, I still think
punting is the only reasonable thing to do. If whatever you're doing
failed from lack of memory, there is no recovery, because even if you
recover, there's so much memory activity in normal operation that the
next thing that happens is likely to fail, and the next thing, etc.,
even at the point of trying to assemble an error message about the
problem.
This mallocing a meg in advance can work, and you can hide the
failure-and-release inside ckalloc, so you are still presenting to all
of the C code a model that ckalloc always succeeds. But it's a kludge.
And if you need more than a meg (or whatever), you lose. And otherwise
you're always wasting a meg in every Tcl process waiting for this
(hopefully, better be, etc.) rare condition.
Better, I think, to probe the amount of available memory. Or... (this
could be cool...) it would be simple to modify ckalloc to keep track of
the amount of memory allocated. It even does this already with memory
debugging enabled. Then you could have ckalloc check against a memory
limit defined within Tcl. Passing that limit would result in a kinder,
gentler error, as long as the limit was at least somewhat less than the
program can actually allocate, so you could generate a Tcl error or
whatever instead of panicking. And that would be a platform-independent
mechanism. You'd need to use the asynchronous event C-level API to send
the error into Tcl, as mallocs occur effectively asynchronously to the
operation of Tcl_Eval. (yah - right?)
I think the guy who's hitting the SIGSEGV has found a bug... in
something (Tcl, the C library...)
Hey, Usenet's fun!
Dan Kuchler
>
> I think the guy who's hitting the SIGSEGV has found a bug... in
> something (Tcl, the C library...)
The original poster was using an older version of tcl/tk when
he got the SIGSEGV. No one has been able to reproduce it on the
latest sources yet.
I still stand by what I said earlier:
------------------------------------------------------------
Since there are algorithms in the core that grow the allocation
by a multiple (2x?) of the current allocation, the failed allocation
could be an allocation of 100 MB, 200 MB, ... in which cases
there is plenty of memory to make a sane exit, or even
better, those algorithms, should be smart enough (and
be able to) back off their allocations, so if 2x fails,
it should back down to some smaller (1.75x, 1.5x, or 1.25x)
allocation, rather than panicking.
There is definite work that could be done in this area,
because I think it is entirely possible to end up in a
situation where an algorithm in tcl for minimizing
memory allocation will cause the allocation to fail well
before the system has used any where near all the memory.
---------------------------------------------------------
I must admit that I haven't looked at the sources to
verify this, but I can think of at least one place where
this is true-- I don't know how many others there might
be.
--Dan
Gerhard Hintermayer
>
> According to Andreas Kupries <a.ku...@westend.com>:
> :> Strange is also, that append needs 2 times x (plus something) memory
> :
> :It doesn't `need` that much memory. This is just the strategy which
> :was implemented for appending. Usually each string in Tcl has some
> :unused memory behind the real string (overallocated before). This
> :makes appending faster as there is no need to reallocate the memory
> :for every single append. Only if that space runs out Tcl will
> :reallocate that string. And double the allocated space during that
> :process, to get more place for the additional appends it expects.
> :
>
> I wonder if a improved algorithm where when the requested allocation
> failed, a smaller number (size + 1/2 size or some other algorithm) might
> be attempted...
>
Sorry for the delay, was ill.
If _really_ realloc (on *nix based systems) was used, I can't
understand, why reallocating memory needs twice the mem that gets
reallocated. Unix has a syscall for reallocating memory, ther's no need
to do this "copy on write" here.
Donal K. Fellows
Gerhard Hintermayer <gerhard.h...@aon.at> wrote:
> If _really_ realloc (on *nix based systems) was used, I can't
> understand, why reallocating memory needs twice the mem that gets
> reallocated. Unix has a syscall for reallocating memory, ther's no
> need to do this "copy on write" here.
Allocated memory chunks (as returned by malloc() and realloc()) are
not necessarily page-aligned. And shouldn't be.
The doubling is a result of the algorithm used to grow some arrays
(those used in the string and list implementations) and was probably
chosen to provide reasonable performance with normal code, though the
best choice is really application dependent. This is because you can
only decide optimally based on the likelihood of needing to grow the
array further; if the distribution of allocations is roughly Poisson
or Exponential you can probably get away with increasing allocation by
a fixed amount (of around the size of the standard deviation) each
time, with the mean being the amount you initially start with. But
these are app-specific parameters... :^(
Donal.
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ fell...@cs.man.ac.uk
-- I may seem more arrogant, but I think that's just because you didn't
realize how arrogant I was before. :^)
-- Jeffrey Hobbs <jeffre...@ajubasolutions.com>
bo...@aol.com
fell...@cs.man.ac.uk (Donal K. Fellows) wrote:
> In article <39881DE6...@aon.at>,
> Gerhard Hintermayer <gerhard.h...@aon.at> wrote:
> > If _really_ realloc (on *nix based systems) was used, I can't
> > understand, why reallocating memory needs twice the mem that gets
> > reallocated. Unix has a syscall for reallocating memory, ther's no
> > need to do this "copy on write" here.
>
> Allocated memory chunks (as returned by malloc() and realloc()) are
> not necessarily page-aligned. And shouldn't be.
>
> The doubling is a result of the algorithm used to grow some arrays
> (those used in the string and list implementations) and was probably
> chosen to provide reasonable performance with normal code, though the
> best choice is really application dependent. This is because you can
> only decide optimally based on the likelihood of needing to grow the
> array further; if the distribution of allocations is roughly Poisson
> or Exponential you can probably get away with increasing allocation by
> a fixed amount (of around the size of the standard deviation) each
> time, with the mean being the amount you initially start with. But
> these are app-specific parameters... :^(
>
Of course there could be a startup option which lets you choose small or
fast. You nearly always want fast. But sometimes you yearn for small!
It just depends on what you are doing at the time.
bob
Sent via Deja.com http://www.deja.com/
Before you buy.
Gerhard Hintermayer
>
> The doubling is a result of the algorithm used to grow some arrays
> (those used in the string and list implementations) and was probably
> chosen to provide reasonable performance with normal code, though the
> best choice is really application dependent. This is because you can
> only decide optimally based on the likelihood of needing to grow the
> array further; if the distribution of allocations is roughly Poisson
> or Exponential you can probably get away with increasing allocation by
> a fixed amount (of around the size of the standard deviation) each
> time, with the mean being the amount you initially start with. But
> these are app-specific parameters... :^(
>
Donal, can you explain that more in detail. I thought when I use a
string modification command, which append certainly is, TCL only
modifies the string representation of the var, and there is no
allocation of memory for possible other types. If I use append to append
to a string, i don't want TCL to alloc memory for all possible types the
var can hold in the future, so why is TCL trying to alloc (as I posted
before) 255M, when I append to a string with length 127M ?
I do not convert the type of the variable, it is always string (see
example)
How I tested the memory outage problem:
set x "0123456789"
set s ""
for {set i 0} {$i<50000} {incr i} {append s $x}
puts "append [string length $s] bytes; hit <ENTER> to continue"
gets stdin
set string ""
while {1} {append string $s; puts [set l [string length $string]]
}
And the output is:
...
126500000
127000000
unable to alloc 255000001 bytes
Aborted
So what's going on here ?
Andre Poenitz
> so why is TCL trying to alloc (as I posted
> before) 255M, when I append to a string with length 127M ?
> I do not convert the type of the variable, it is always string (see
> example)
I have _no idea_ on what I am talking about, but anyway:
I could be (haven't checked the sources) that string-reallocation
is done with some 'look ahead into the futer', so if someone requests
50 bytes for appending it could as well reserve 100 during reallocation
and save some work for futere reallocations (to 60, 70, ... bytes).
A factor of 2 is common in such circumstances, SGI does it for instance
in its STL (C++-library that supports e.g. self-growing vectors).
I even believe this is optimal from a theoritical point of view
(giving amortized O(1) append time), although it hits you badly in
your case:
If your string is filled with 127 MB data and it is full, it
gets reallocated with doubled size, i.e. the 255 MB you observed.
As I said, just a wild guess.
Andre'
--
It'll take a long time to eat 63.000 peanuts.
André Pönitz ......................... poe...@mathematik.tu-chemnitz.de
Paul Duffin
>
> lvi...@cas.org wrote:
> >
> > According to Andreas Kupries <a.ku...@westend.com>:
> > :> Strange is also, that append needs 2 times x (plus something) memory
> > :
> > :It doesn't `need` that much memory. This is just the strategy which
> > :was implemented for appending. Usually each string in Tcl has some
> > :unused memory behind the real string (overallocated before). This
> > :makes appending faster as there is no need to reallocate the memory
> > :for every single append. Only if that space runs out Tcl will
> > :reallocate that string. And double the allocated space during that
> > :process, to get more place for the additional appends it expects.
> > :
> >
> > I wonder if a improved algorithm where when the requested allocation
> > failed, a smaller number (size + 1/2 size or some other algorithm) might
> > be attempted...
> >
>
> Sorry for the delay, was ill.
>
> understand, why reallocating memory needs twice the mem that gets
> reallocated. Unix has a syscall for reallocating memory, ther's no need
> to do this "copy on write" here.
>
If realloc cannot extend the current buffer then it has to allocate another
buffer and copy the contents of the original buffer into it and then free
the original buffer. Whether or not the buffer can be extended depends on a
lot of factors but you in general can never completely eliminate the chance
that the current buffer cannot be extended.
The choice of how much to increase the buffer by is down to Tcl, it chooses
to allocate double the amount of space that it actually needs in order to
reduce the number of future allocations. Personally I think that it is a
little bit excessive and that as the size of the block goes up the
proportion of extra space allocated should decrease.
It is alright to allocate double when you are allocating a couple of KB
but when allocating a few MB the potential waste becomes excessive.
Gerhard Hintermayer
>
> [...]
> The choice of how much to increase the buffer by is down to Tcl, it chooses
> to allocate double the amount of space that it actually needs in order to
> reduce the number of future allocations. Personally I think that it is a
> little bit excessive and that as the size of the block goes up the
> proportion of extra space allocated should decrease.
>
> It is alright to allocate double when you are allocating a couple of KB
> but when allocating a few MB the potential waste becomes excessive.
That would make sense for me too.
The length of the appended string could also be considered for the
amount of reallocated memory. Mere doubling is not a good solution.
I remember Jeff Hobbs posting:
>How much memory do you have? Subtract some overhead and that's
>about how much.
If "some overhead" is 50 %, that's not good.
Donal K. Fellows
Sure.
> I thought when I use a string modification command, which append
> certainly is, TCL only modifies the string representation of the
> var, and there is no allocation of memory for possible other
> types.
If I keep on appending items to a list, that list had better keep
growing! :^)
> If I use append to append to a string, i don't want TCL to alloc
> memory for all possible types the var can hold in the future, so why
> is TCL trying to alloc (as I posted before) 255M, when I append to a
> string with length 127M ? I do not convert the type of the
> variable, it is always string (see example)
Because every memory allocation is *slow*. Painfully so. If you have
a string that is growing over a period of time, it is far faster to
allocate exponentially larger chunks (since allocation times are
roughly constant whether you ask for a few kilobytes or half a
gigabyte) and this has reasonable performance for strings that don't
grow very large (where very large is measured against the amount of
free virtual memory!)
Maybe the existing allocation growth mechanism is too simplistic (it
wouldn't surprise me) and it should grow more slowly as the size of
block increases, but that doesn't change the fact that growing
linearly is a horribly poor strategy with most code.
The best technique is to simply know exactly how much you are going to
need each time, and allocate that (linked lists are mostly too
inefficient for use, since you usually allocate each link separately.)
This is usually not practical at all. So growing data-structures are
used instead. All of which begs the question, "How do you allocate
them so as to minimise the amount of memory used and the allocations
performed?"
This really requires a statistical approach. You want the most common
cases to be fast (one allocation) and most allocations are actually
fairly small anyway (variable names, numeric values, etc.) so you
allocate a certain amount by default that is large enough to tackle
these things. Then, when you need more, you reallocate to a larger
amount. Choosing the size of this reallocation is where things get
interesting.
If you know that it is likely that whatever it is that is growing is
not going to grow very much, you can just grow the memory block
linearly, and your growth rate should probably match the standard
deviation of your distribution (c.f. Poisson distributions.) However,
if you have a fair proportion of memory blocks that are going to grow
very large, you need to make them grow faster or you wind up doing too
many allocation actions and taking a very long time. Tcl tries to
allow for this sort of situation by making data blocks grow in size
exponentially. This mostly works reasonably well, but it can lead to
you running out of memory well before you've actually used it all.
Perhaps one technique would be to double until the memory block size
exceeded a megabyte, and then to switch to a slower growth scheme.
Whatever is done, it should be fairly fast to compute or the cost of
just figuring out how much to allocate will become significant...
Dan Kuchler
>
> Paul Duffin wrote:
> >
> > It is alright to allocate double when you are allocating a couple of KB
> > but when allocating a few MB the potential waste becomes excessive.
>
> That would make sense for me too.
> The length of the appended string could also be considered for the
> amount of reallocated memory. Mere doubling is not a good solution.
> I remember Jeff Hobbs posting:
>
> >How much memory do you have? Subtract some overhead and that's
> >about how much.
>
> If "some overhead" is 50 %, that's not good.
And Jeff agrees. The memory allocation algorithm in this situation
definitely needs work.. I suggested the other day that if an
allocation
fails, it should back off and try a smaller piece (or start increasing
at smaller increments) so that more of memory is utilized until it
is all (almost all) used.
There is definite work to be done in that area. Are you volunteering?
--Dan
Gerhard Hintermayer
>
>[...]
>
> And Jeff agrees. The memory allocation algorithm in this situation
> definitely needs work.. I suggested the other day that if an
> allocation
> fails, it should back off and try a smaller piece (or start increasing
> at smaller increments) so that more of memory is utilized until it
> is all (almost all) used.
>
> There is definite work to be done in that area. Are you volunteering?
>
Sure, was just searching the sources, the only changes needed would be
in AppendUtfToUtfRep and AppendUnicodeToUnicodeRep inside
tclStringObj.c, right ?
A simple and fast algorithm has to be found, e.g. doubling up to x bytes
would be fine for small x, and for large x e.g. x + n * appendlength.
What do I have to do ? Can you point me to a page of instructions or
email me directly ?
Gerhard
Paul Duffin
The solution is to do a lazy append.
Create a new Tcl_ObjType, e.g. "concatenated string" whose internal
representation is an array of pointers to Tcl_Objs, similar to the
internal representation of the list type.
Appending an object to a "concatenated string" simply involves adding
a pointer to the object to the end of the internal representation.
Appending 100MB is just as quick as appending one character.
Only when the string representation of a "concatenated string" object is
requested does space have to be allocated for the whole string at which
time the exact space can easily be calculated completely eliminating
waste. When the string representation is calculated the array of objects
can be freed.
Dan Kuchler
>
> Dan Kuchler wrote:
>
> Sure, was just searching the sources, the only changes needed would be
> in AppendUtfToUtfRep and AppendUnicodeToUnicodeRep inside
> tclStringObj.c, right ?
> A simple and fast algorithm has to be found, e.g. doubling up to x bytes
> would be fine for small x, and for large x e.g. x + n * appendlength.
>
> What do I have to do ? Can you point me to a page of instructions or
> email me directly ?
An alternative to the suggestion Paul made (or maybe in addition
to the suggestion Paul made) would be to add a second memory
allocation function to the Tcl C API. This would take two
arguments for size, a minimum size, and a desired size. The
desired size could be calculated using the current logic, but
then inside the memory alloc routine, when the memory alloc
failed, it would retry with increasingly smaller chunks of memory
until it either got a chunk of memory allocated, or until minsize
was reached.
If the minimum size was reached and no memory could
be allocated, it would go through the same actions as the current
memory allocation routines do whan a memory allocation fails (since
in this situation you really can't get enough memory to do what you
need to do).
This new API could be used in places where algorithms are used to
determine how much memory to allocate instead of simply getting
what is needed at the moment. The Append* commands, and I think
some of the regexp stuff would need this. I am not sure about
others.
Eric Melski wrote a good document giving some development guidelines
at:
http://dev/software/tcltk/contributing.tml
--Dan
Gerhard Hintermayer
>
>
> Sure, was just searching the sources, the only changes needed would be
> in AppendUtfToUtfRep and AppendUnicodeToUnicodeRep inside
> tclStringObj.c, right ?
> A simple and fast algorithm has to be found, e.g. doubling up to x bytes
> would be fine for small x, and for large x e.g. x + n * appendlength.
>
(Btw, i checked the 8.3.1 files)
I knew it, that would have been too easy. Tcl_SetObjLength has to be
modified, too. And after doing that, i always get a seg fault at
startup. The comment above the function declaration says
* byte is stored in the strength. If the length of the string
* representation is greater than length, the storage space is
* reallocated to the given length; a null byte is stored at the
but there is never ever reallocation done, so every time you do a append
(and the allocated memory for that string var is to small) the whole
string is copied to a new allocated memory. This seems a great waste of
performance to me. Have to get a deeper look on that (and start my work
with the latest 8.4 files from the cvs)
Gerhard Hintermayer
>
>
> The solution is to do a lazy append.
>
> Create a new Tcl_ObjType, e.g. "concatenated string" whose internal
> representation is an array of pointers to Tcl_Objs, similar to the
> internal representation of the list type.
>
> Appending an object to a "concatenated string" simply involves adding
> a pointer to the object to the end of the internal representation.
> Appending 100MB is just as quick as appending one character.
>
> Only when the string representation of a "concatenated string" object is
> requested does space have to be allocated for the whole string at which
> time the exact space can easily be calculated completely eliminating
> waste. When the string representation is calculated the array of objects
> can be freed.
Nah, why modify the core that much, when the existing commands/functions
could be modified without danger of incompatibility. The existing append
should do it's job fast and efficient. There is no need to double the
memory for large strings. What a waste of memory. See my other posting.
Dan Kuchler
>
>
> Nah, why modify the core that much, when the existing commands/functions
> could be modified without danger of incompatibility. The existing append
> should do it's job fast and efficient. There is no need to double the
> memory for large strings. What a waste of memory. See my other posting.
Quantify large. For an application that is very memory hungry and
has possibly GBs of memory, large is much different than someone who
has
16 MB or 32 MB of memory in their desktop.
--Dan
Paul Duffin
>
> Paul Duffin wrote:
> >
> >
> > The solution is to do a lazy append.
> >
> > Create a new Tcl_ObjType, e.g. "concatenated string" whose internal
> > representation is an array of pointers to Tcl_Objs, similar to the
> > internal representation of the list type.
> >
> > Appending an object to a "concatenated string" simply involves adding
> > a pointer to the object to the end of the internal representation.
> > Appending 100MB is just as quick as appending one character.
> >
> > Only when the string representation of a "concatenated string" object is
> > requested does space have to be allocated for the whole string at which
> > time the exact space can easily be calculated completely eliminating
> > waste. When the string representation is calculated the array of objects
> > can be freed.
>
> could be modified without danger of incompatibility.
There is no incompatability problem.
> The existing append
> should do it's job fast and efficient. There is no need to double the
> memory for large strings. What a waste of memory. See my other posting.
The worst case behaviour for appending to a string (continuous array of
characters) needs twice the amount of memory that the final string would
take up. There is no way that I know of to reduce that worst case.
<------- original string --------> <---- extra bit ---->
<---------------------- new string ---------------------->
Lazy evaluation is a very good solution to this problem.
Jeffrey Hobbs
>
> Dan Kuchler wrote:
> >
> >
> > And Jeff agrees. The memory allocation algorithm in this situation
> > definitely needs work.. I suggested the other day that if an
> > allocation
> > fails, it should back off and try a smaller piece (or start increasing
> > at smaller increments) so that more of memory is utilized until it
> > is all (almost all) used.
> Sure, was just searching the sources, the only changes needed would be
> in AppendUtfToUtfRep and AppendUnicodeToUnicodeRep inside
> tclStringObj.c, right ?
> A simple and fast algorithm has to be found, e.g. doubling up to x bytes
> would be fine for small x, and for large x e.g. x + n * appendlength.
To do the latter, you really have to consider a new alternative API,
so only when failing the known optimal case do you backtrack.
For the former, tclStringObj.c could make better use of ckrealloc
instead of ckalloc and copying, for example in Tcl_SetObjLength.
If you'd like to make and test the changes, especially against
something that pushes the boundaries, that'd be great.
Jeffrey Hobbs
>
> Jeffrey Hobbs wrote:
> >
> > For the former, tclStringObj.c could make better use of ckrealloc
> > instead of ckalloc and copying, for example in Tcl_SetObjLength.
> > If you'd like to make and test the changes, especially against
> > something that pushes the boundaries, that'd be great.
> >
>
> minimal effect on most applications. Platforms which allocate blocks in
> sizes which are powers of 2 would benefit slightly as there is likely to be
> extra space after the block. However I think that most (?) platforms simply
> allocate the amount of space asked for which means that there is unlikely
> to be any spare space immediately after the block for realloc to use so a
> copy is necessary.
The problem that Gerhard had discovered was that the use of
Tcl_SetObjLength, which is used by the internal AppendUtfToUtfRep
does an alloc of the new space and then copies over the data and
frees the original. This means that you can end up with 3x the
necessary mem used worst case, which is bad for large strings.
Paul Duffin
David Cuthbert
> Choosing the size of this reallocation is where things get
> interesting.
Unquestionably. As Andre noted in another reply, growing by a factor of
2 is what the SGI STL (and HP, and RogueWave, and...) uses. I've lost
the reference -- I read it on comp.lang.c++.moderated a couple years
back -- but some study of n programs (where 3 < n < 10^6) yielded a
factor in the range of 1.7 to be the ideal. 2, though, is somewhat
easier to code (or, at least, removes a floating point multiply in favor
of a bit shift).
> If you know that it is likely that whatever it is that is growing is
> not going to grow very much, you can just grow the memory block
> linearly, and your growth rate should probably match the standard
> deviation of your distribution (c.f. Poisson distributions.)
Again drawing on my STL usage experience, we usually reserve a certain
amount of space when it's even vaguely predictable. Life is too short
to try to find optimal growth algorithms.
This isn't currently possible in Tcl; however, there's no reason why it
can't be added (for variables, at least).
--
David Cuthbert
da...@kanga.org
Gerhard Hintermayer
>
> [...]
> >
> > Nah, why modify the core that much, when the existing commands/functions
> > could be modified without danger of incompatibility.
>
> There is no incompatability problem.
Got me, but the API will get more functions, don't we have enough there
?
>
> > The existing append
> > should do it's job fast and efficient. There is no need to double the
> > memory for large strings. What a waste of memory. See my other posting.
>
> The worst case behaviour for appending to a string (continuous array of
> characters) needs twice the amount of memory that the final string would
> take up. There is no way that I know of to reduce that worst case.
>
Dous your system not supply the realloc syscall ?
> <------- original string --------> <---- extra bit ---->
>
> <---------------------- new string ---------------------->
>
> Lazy evaluation is a very good solution to this problem.
Btw, what do you do, with your "concatenated string" object, if you do
not have the memory to build the string representation ? Again you need
free mem for the whole string representation, or you iterate over all
elements and try to reallocate memory every time, but then what do you
do, if memory is too fragmented and realloc don't work ?
Paul Duffin
>
> Paul Duffin wrote:
> >
> > [...]
> > >
> > > Nah, why modify the core that much, when the existing commands/functions
> > > could be modified without danger of incompatibility.
> >
> > There is no incompatability problem.
>
> Got me, but the API will get more functions, don't we have enough there
> ?
>
There are certainly API calls which need removing / streamlining but I don't
worry too much about adding a couple more.
> >
> > > The existing append
> > > should do it's job fast and efficient. There is no need to double the
> > > memory for large strings. What a waste of memory. See my other posting.
> >
> > The worst case behaviour for appending to a string (continuous array of
> > characters) needs twice the amount of memory that the final string would
> > take up. There is no way that I know of to reduce that worst case.
> >
>
> Dous your system not supply the realloc syscall ?
>
Yes it does but in the worst case behaviour of realloc is the same as
allocating a new string, copying the original, appending the extra bit and
then freeing the original and extra bits. In other words the space needed
to append is twice the final size.
> > <------- original string --------> <---- extra bit ---->
> >
> > <---------------------- new string ---------------------->
> >
> > Lazy evaluation is a very good solution to this problem.
>
> Btw, what do you do, with your "concatenated string" object, if you do
> not have the memory to build the string representation ? Again you need
> free mem for the whole string representation, or you iterate over all
> elements and try to reallocate memory every time, but then what do you
> do, if memory is too fragmented and realloc don't work ?
>
This is no different to always appending except that the error will be
reported when the string representation is generated which may be
sometime after the append but this applies to all lazy evaluations.
e.g.
set a [string repeat a 1000000]; string length $a
set l {}
for {set i 0} {$i < 1000000} {incr i} {
lappend l $a
}
string length $l
The above code will end up trying to allocate 1000000 * 1000000 + 999999
bytes which will fail.
Paul Duffin
> Tcl_SetObjLength, which is used by the internal AppendUtfToUtfRep
> does an alloc of the new space and then copies over the data and
> frees the original. This means that you can end up with 3x the
> necessary mem used worst case, which is bad for large strings.
>
Using realloc will not reduce this worst case behaviour.
Actually, I guess it would be possible if there is not enough room for
realloc to extend the current block and the block occupies a set of pages
for the physical memory to be remapped to a different virtual memory
address which has a free address range large enough to contain the
extended block.
Does anyone know whether any and if so what platforms have this sort of
realloc behaviour for large blocks ?
It is certainly better to use realloc where you can in order to take
advantage of this behaviour where it is implemented, but it does not
reduce the worst case behaviour across different platforms, unless they
all implement this behaviour.
Gerhard Hintermayer
>
> Using realloc will not reduce this worst case behaviour.
But in those cases where realloc can simply extend the piece of memory,
it will. Nevertheless I don't know in how many cases this is possible. I
also see no sense in programming realloc "by hand", if there's a
syscall, sounds like reinventing the wheel.
> Actually, I guess it would be possible if there is not enough room for
> realloc to extend the current block and the block occupies a set of pages
> for the physical memory to be remapped to a different virtual memory
> address which has a free address range large enough to contain the
> extended block.
>
If such things are possible, they would only be on expensive machines,
because you have to have a large and fast memory mapping unit.
> Does anyone know whether any and if so what platforms have this sort of
> realloc behaviour for large blocks ?
>
> It is certainly better to use realloc where you can in order to take
> advantage of this behaviour where it is implemented, but it does not
> reduce the worst case behaviour across different platforms, unless they
> all implement this behaviour.
Paul Duffin
>
> Paul Duffin wrote:
> >
> > Using realloc will not reduce this worst case behaviour.
>
> But in those cases where realloc can simply extend the piece of memory,
> it will. Nevertheless I don't know in how many cases this is possible. I
> also see no sense in programming realloc "by hand", if there's a
> syscall, sounds like reinventing the wheel.
>
You are correct.
> > Actually, I guess it would be possible if there is not enough room for
> > realloc to extend the current block and the block occupies a set of pages
> > for the physical memory to be remapped to a different virtual memory
> > address which has a free address range large enough to contain the
> > extended block.
> >
>
> If such things are possible, they would only be on expensive machines,
> because you have to have a large and fast memory mapping unit.
>
I think that any platform could do it because you are reducing the amount
of work that you have to do. If you have to allocate a new large block you
will probably have to do some paging / map more virtual addresses, anyway
so just moving the virtual address of the data is not going to involve
any extra effort in this area and will reduce the amount of copying.
> > Does anyone know whether any and if so what platforms have this sort of
> > realloc behaviour for large blocks ?
> >
Question still stands.
Donal K. Fellows
Paul Duffin <pdu...@hursley.ibm.com> wrote:
> Yes it does but in the worst case behaviour of realloc is the same as
> allocating a new string, copying the original, appending the extra bit and
> then freeing the original and extra bits. In other words the space needed
> to append is twice the final size.
But if you've only got one thing (at a time) that is growing a lot[*],
the worst case is not likely to come up too much as the memory block
will end up at the end of the heap (assuming an upward-growing heap,
which seems to be normal precisely because of this sort of thing.)
Donal.
[* A model that fits many programs. ]
Gerhard Hintermayer
>
>
> To do the latter, you really have to consider a new alternative API,
> so only when failing the known optimal case do you backtrack.
>
> instead of ckalloc and copying, for example in Tcl_SetObjLength.
> If you'd like to make and test the changes, especially against
> something that pushes the boundaries, that'd be great.
>
Tested some modifications in tclStringObj.c within Tcl_SetObjLength, but
without success. Seems that objPtr->bytes holds sometimes an address,
that was not allocated with malloc (or ckalloc), because on startup the
interpreter crashes when I try the first realloc (ckrealloc), I've
checked that. So I have no idea, where to start or why ckrealloc
crashes, btw. ckrealloc crashes in the syscall, but why ?
Paul Duffin
>
> In article <398A7DC2...@hursley.ibm.com>,
> Paul Duffin <pdu...@hursley.ibm.com> wrote:
> > Yes it does but in the worst case behaviour of realloc is the same as
> > allocating a new string, copying the original, appending the extra bit and
> > then freeing the original and extra bits. In other words the space needed
> > to append is twice the final size.
>
> But if you've only got one thing (at a time) that is growing a lot[*],
> the worst case is not likely to come up too much as the memory block
> will end up at the end of the heap (assuming an upward-growing heap,
> which seems to be normal precisely because of this sort of thing.)
>
Never thought about the block always being at the end. Will a Tcl application
have this behaviour though considering that it could be doing a lot of memory
allocations and freeing while appending to the single object.
Just to clarify realloc should be used where possible as it does allow the
system to do some optimisations. However it is not a panacea for bad
performance.
Dan Kuchler
>
> Paul Duffin wrote:
> >
> > Using realloc will not reduce this worst case behaviour.
>
> But in those cases where realloc can simply extend the piece of memory,
> it will. Nevertheless I don't know in how many cases this is possible. I
> also see no sense in programming realloc "by hand", if there's a
> syscall, sounds like reinventing the wheel.
Take a look at the function AppendUnicodeToUnicodeRep in\
generic/tclStringObj.c This is an example of a function
that uses realloc for its memory allocation (in the form
of ckrealloc)
--Dan
Paul Duffin
Look at Tcl_NewObj.
:
objPtr->refCount = 0;
objPtr->bytes = tclEmptyStringRep;
objPtr->length = 0;
:
or Tcl_InvalidateStringRep.
if (objPtr->bytes != NULL) {
if (objPtr->bytes != tclEmptyStringRep) {
ckfree((char *) objPtr->bytes);
}
objPtr->bytes = NULL;
}
Gerhard Hintermayer
When using [append var somestring] AppendUtfToUtfRep is used, which in
turn calls Tcl_SetObjLength, which doesn't use ckrealloc.
Se my other posting about my success, or better failure, to change
Tcl_SetObjLength and use ckrealloc there.
Have to leave now. Have a nice weekend.
Gerhard Hintermayer
>
> Gerhard Hintermayer wrote:
> >
> > Tested some modifications in tclStringObj.c within Tcl_SetObjLength, but
> > without success. Seems that objPtr->bytes holds sometimes an address,
> > that was not allocated with malloc (or ckalloc), because on startup the
> > interpreter crashes when I try the first realloc (ckrealloc), I've
> > checked that. So I have no idea, where to start or why ckrealloc
> > crashes, btw. ckrealloc crashes in the syscall, but why ?
> >
>
> Look at Tcl_NewObj.
>
> :
> objPtr->refCount = 0;
> objPtr->bytes = tclEmptyStringRep;
> objPtr->length = 0;
> :
>
> or Tcl_InvalidateStringRep.
>
> if (objPtr->bytes != NULL) {
> if (objPtr->bytes != tclEmptyStringRep) {
> ckfree((char *) objPtr->bytes);
> }
> objPtr->bytes = NULL;
> }
That brings me to some idea, maybe I was trying to reallocate
tclEmptyStringRep, have to check that on Sunday.
Have a nice weekend
Gerhard
Paul Duffin
>
> That brings me to some idea,
That was my intention.
> maybe I was trying to reallocate
> tclEmptyStringRep,
That is certainly a possibility.
> have to check that on Sunday.
>
Have a nice weekend.
Donal K. Fellows
<pdu...@hursley.ibm.com> writes
>Never thought about the block always being at the end. Will a Tcl application
>have this behaviour though considering that it could be doing a lot of memory
>allocations and freeing while appending to the single object.
It's fairly obvious that this will happen even in an application as
dynamic as a Tcl interpreter, since what do you think happens to all the
memory blocks that were previously unable to hold our massive growing
string/array? That's right, they now hold all the dynamic bits (and
Tcl_Objs are managed specially for high speed allocation[*], which is
why you should never use malloc() or Tcl_Alloc() to create them...)
>Just to clarify realloc should be used where possible as it does allow the
>system to do some optimisations. However it is not a panacea for bad
>performance.
Nothing is, and never was. Thank goodness for algorithms books, though
they are not quite straight-forward to use since they can be worse than
useless if you don't grasp the trade-offs involved in any particular
algorithm. (Quite often you'll find something app-specific does better
than something that is best in the general case...)
Donal.
[* In fact, it is instructive to see how it is done. ]
--
Donal K. Fellows (at home)
--
FOOLED you! Absorb EGO SHATTERING impulse rays, polyester poltroon!!
(WARNING: There is precisely one error in this message.)
Donal K. Fellows
Paul Duffin <pdu...@hursley.ibm.com> wrote:
> Using realloc will not reduce this worst case behaviour.
Nothing will. There's not much that can be done in the worst case.
But we can make the worst case come up less frequently in practical
programs.
Donal.
Gerhard Hintermayer
Ok, what did I change:
In file generic/tclStringObj.c:
inside AppendUtfToUtfRep and AppendUnicodeToUnicodeRep I changed the
algorythm to determine the new memory size if a string grows larger that
the actually allocated memory for it.
I didn't change the doubling algorythm if the needed memory is less than
1MB, if it is bigger, I do not double, but add 1024+2 times the size of
the appended string. The 1024 are just for the case the appended string
is short.
Tcl_SetObjLength was modified to first try reallocating, and only if
that fails, do allocate and copy.
The result:
The largest string I can cope with nearly doubled (~ 127M before, ~247M
now, Linux, 256MB RAM, not idle system, X11, netscape running)
Tests:
I tested by appending 500000 bytes in an endless loop to a string and
timed the append command. Every time I calculate the average over all
appends.
String length original(us) patched(us)
1M 3500 3600
2M 5650 3700
3M 5000 3800
20M 8800 3850
50M 8150 3750
100M 8450 3700
127M 7600 3750
150M - 3750
200M - 3800
247M - 21000
The steady increase when getting close to 247M is due to moving memory
pages to the swap device. So you can see, that most of the time a
realloc with simply extending the memory block is possible. But a reason
for that might be the test program, only 2 strings, and only one of the
is changed, no more variables are created, which could split the memory
heap into smaller pieces.
When appending to small string, the speed increase due to realloc-usage
is also present, but of course smaller.
I appended 100bytes/1K to a string
String length original(us) patched(us)
append 100bytes
100 52 48
200 32 29
500 23 21
append 1k
1k 61 60
5k 32 31
10k 30 27
20k 28 27
50k 25 21
100k 24 18
At least here is the diff against the 8.3.1 file. Comments welcome.
667c667
< * Not enough space in current string. Reallocate the string
---
> * Not enough space in current string. really Reallocate the string
670,675c670,684
<
< new = (char *) ckalloc((unsigned) (length+1));
< if (objPtr->bytes != NULL) {
< memcpy((VOID *) new, (VOID *) objPtr->bytes,
< (size_t) objPtr->length);
< Tcl_InvalidateStringRep(objPtr);
---
> 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);
> //printf("ckalloc OK, %d bytes copied\n",objPtr->length);
> }
> } else {
> //printf("ckrealloc %d bytes\n",length);
679c688,690
< }
---
>
> }
>
1004c1015,1016
< stringPtr->uallocated = newSize * 2;
---
> /* test algorithm, doubling under 1M, adding 1k plus 2*appendLength else*/
> stringPtr->uallocated = newSize+(newSize>=1048576 ? 1024+2*appendNumChars : newSize);
1159c1171,1172
< Tcl_SetObjLength(objPtr, 2*newLength);
---
> /* new algorithm: doubling < 1M, add 1024+2*appendlength else */
> Tcl_SetObjLength(objPtr, newLength+(newLength>=1048576 ? 1024+2*numBytes : newLength));
1169d1181
<
--
Gerhard Hintermayer
http://www.inode.at/g.hintermayer
Donal K. Fellows
In article <398A8D5B...@aon.at>, Gerhard Hintermayer
<gerhard.h...@aon.at> writes
>Paul Duffin wrote:
>> Actually, I guess it would be possible if there is not enough room for
>> realloc to extend the current block and the block occupies a set of pages
>> for the physical memory to be remapped to a different virtual memory
>> address which has a free address range large enough to contain the
>> extended block.
>
>If such things are possible, they would only be on expensive machines,
>because you have to have a large and fast memory mapping unit.
Almost every computer produced for the last ten years has a large and
fast memory mapping unit. How long is it since the introduction of the
68040 and the 80386?
Donal.
--
Gerhard Hintermayer
>
> [ Yet more continuing of threads from beyond the grave! ]
>
> In article <398A8D5B...@aon.at>, Gerhard Hintermayer
> <gerhard.h...@aon.at> writes
> >Paul Duffin wrote:
> >> Actually, I guess it would be possible if there is not enough room for
> >> realloc to extend the current block and the block occupies a set of pages
> >> for the physical memory to be remapped to a different virtual memory
> >> address which has a free address range large enough to contain the
> >> extended block.
> >
> >If such things are possible, they would only be on expensive machines,
> >because you have to have a large and fast memory mapping unit.
>
> Almost every computer produced for the last ten years has a large and
> fast memory mapping unit. How long is it since the introduction of the
> 68040 and the 80386?
>
Oh my god, I thought that one was really over. We will all get cursed
for opening the grave :) I think (actually I can't remember) somebody
requested a MMU, that does _not_ the thing normal MMU's do. Having a MMU
that can store maybe 100000 memory mappings is not possible with today's
MMU. But if things are different, I'm willing to learn.
Gerhard