How naive is Python?

[John Nagle]

How naive (in the sense that compiler people use the term)
is the current Python system? For example:

def foo() :
s = "This is a test"
return(s)

s2 = foo()

How many times does the string get copied?

Or, for example:

s1 = "Test1"
s2 = "Test2"
s3 = "Test3"
s = s1 + s2 + s3

Any redundant copies performed, or is that case optimized?

How about this?

kcount = 1000
s = ''
for i in range(kcount) :
s += str(i) + ' '

Is this O(N) or O(N^2) because of recopying of "s"?

I just want a sense of what's unusually inefficient in the
current implementation. Thanks.

John Nagle

[skip@pobox.com]

Re: How naive is Python?


JohnHow naive (in the sense that compiler people use the term) is the
Johncurrent Python system? For example:

John def foo() :
John s = "This is a test"
John return(s)

John s2 = foo()

JohnHow many times does the string get copied?

Never. s and s2 just refer to the same object (strings are immutable).
Executing this:

def foo() :
print id("This is a test")
s = "This is a test"
print id(s)
return(s)

s2 = foo()
print id(s2)

prints the same value three times.

JohnOr, for example:

John s1 = "Test1"
John s2 = "Test2"
John s3 = "Test3"
John s = s1 + s2 + s3

JohnAny redundant copies performed, or is that case optimized?

Not optimized. You can see that using the dis module:

4 0 LOAD_CONST 1 ('Test1')
3 STORE_FAST 0 (s1)

5 6 LOAD_CONST 2 ('Test2')
9 STORE_FAST 1 (s2)

6 12 LOAD_CONST 3 ('Test3')
15 STORE_FAST 2 (s3)

7 18 LOAD_FAST 0 (s1)
21 LOAD_FAST 1 (s2)
24 BINARY_ADD
25 LOAD_FAST 2 (s3)
28 BINARY_ADD
29 STORE_FAST 3 (s)
32 LOAD_CONST 0 (None)
35 RETURN_VALUE

The BINARY_ADD opcode creates a new string.

JohnHow about this?

John kcount = 1000
John s = ''
John for i in range(kcount) :
John s += str(i) + ' '

JohnIs this O(N) or O(N^2) because of recopying of "s"?

O(N). Here's a demonstration of that:

#!/usr/bin/env python

from __future__ import division

def foo(kcount):
s = ''
for i in xrange(kcount) :
s += str(i) + ' '

import time

for i in xrange(5,25):
t = time.time()
foo(2**i)
t = time.time() - t
print 2**i, t, t/2**i

On my laptop t roughly doubles for each iteration and prints around 5e-06
for t/2**i in all cases.

Skip

[Roy Smith]

Re: How naive is Python?

In article <huCqh.1309$O02 .170@newssvr11. news.prodigy.ne t>,
John Nagle <nagle@animats. comwrote:

How naive (in the sense that compiler people use the term)
is the current Python system? For example:
>
def foo() :
s = "This is a test"
return(s)
>
s2 = foo()
>
How many times does the string get copied?

All of those just move around pointers to the same (interned) string.

How about this?
>
kcount = 1000
s = ''
for i in range(kcount) :
s += str(i) + ' '
>
Is this O(N) or O(N^2) because of recopying of "s"?

This is a well-known (indeed, the canonical) example of quadratic behavior
in Python. The standard solution is to store all the strings (again,
really just pointers to the strings) in a list, then join all the elements:

temp = []
for i in range (1000):
temp.append (str(i))
s = "".join (temp)

That ends up copying each string once (during the join operation), and is
O(N) overall.

[Steven D'Aprano]

Re: How naive is Python?

On Mon, 15 Jan 2007 03:25:01 +0000, John Nagle wrote:

How naive (in the sense that compiler people use the term)
is the current Python system? For example:
>
def foo() :
s = "This is a test"
return(s)
>
s2 = foo()
>
How many times does the string get copied?

Let's find out. Results below for Python 2.3 -- other versions may vary.

>>def foo():

.... s = "This is a test"
.... return s
....

>>def foo2():

.... return "This is a test"
....

>>import dis
>>dis.dis(foo )

2 0 LOAD_CONST 1 ('This is a test')
3 STORE_FAST 0 (s)

3 6 LOAD_FAST 0 (s)
9 RETURN_VALUE
10 LOAD_CONST 0 (None)
13 RETURN_VALUE

>>dis.dis(foo 2)

2 0 LOAD_CONST 1 ('This is a test')
3 RETURN_VALUE
4 LOAD_CONST 0 (None)
7 RETURN_VALUE

foo and foo2 functions compile to different byte-code. foo does a little
more work than foo2, but it is likely to be a trivial difference.

>>s1 = foo()
>>s2 = foo()
>>s1 == s2, s1 is s2

(True, True)

So the string "This is a test" within foo is not copied each time the
function is called. However, the string "This is a test" is duplicated
between foo and foo2 (the two functions don't share the same string
instance):

>>s3 = foo2()
>>s3 == s1, s3 is s1

(True, False)

Or, for example:
>
s1 = "Test1"
s2 = "Test2"
s3 = "Test3"
s = s1 + s2 + s3
>
Any redundant copies performed, or is that case optimized?

I don't believe it is optimized. I believe that in Python 2.5 simple
numeric optimizations are performed, so that "x = 1 + 3" would compile to
"x = 4", but I don't think that holds for strings. If you are running 2.5,
you could find out with dis.dis.

How about this?
>
kcount = 1000
s = ''
for i in range(kcount) :
s += str(i) + ' '
>
Is this O(N) or O(N^2) because of recopying of "s"?

That will be O(N**2), except that CPython version 2.4 (or is it 2.5?) can,
sometimes, optimize it. Note that this is an implementation detail, and
doesn't hold for other Pythons like Jython, IronPython or PyPy.



--
Steven D'Aprano

[John Machin]

Re: How naive is Python?


skip@pobox.com wrote:

JohnHow naive (in the sense that compiler people use the term) is the
Johncurrent Python system? For example:
>
John def foo() :
John s = "This is a test"
John return(s)
>
John s2 = foo()
>
JohnHow many times does the string get copied?
>
Never. s and s2 just refer to the same object (strings are immutable).
Executing this:
>
def foo() :
print id("This is a test")
s = "This is a test"
print id(s)
return(s)
>
s2 = foo()
print id(s2)
>
prints the same value three times.
>
JohnOr, for example:
>
John s1 = "Test1"
John s2 = "Test2"
John s3 = "Test3"
John s = s1 + s2 + s3
>
JohnAny redundant copies performed, or is that case optimized?
>
Not optimized. You can see that using the dis module:
>
4 0 LOAD_CONST 1 ('Test1')
3 STORE_FAST 0 (s1)
>
5 6 LOAD_CONST 2 ('Test2')
9 STORE_FAST 1 (s2)
>
6 12 LOAD_CONST 3 ('Test3')
15 STORE_FAST 2 (s3)
>
7 18 LOAD_FAST 0 (s1)
21 LOAD_FAST 1 (s2)
24 BINARY_ADD
25 LOAD_FAST 2 (s3)
28 BINARY_ADD
29 STORE_FAST 3 (s)
32 LOAD_CONST 0 (None)
35 RETURN_VALUE
>
The BINARY_ADD opcode creates a new string.
>
JohnHow about this?
>
John kcount = 1000
John s = ''
John for i in range(kcount) :
John s += str(i) + ' '
>
JohnIs this O(N) or O(N^2) because of recopying of "s"?
>
O(N). Here's a demonstration of that:
>
#!/usr/bin/env python
>
from __future__ import division
>
def foo(kcount):
s = ''
for i in xrange(kcount) :
s += str(i) + ' '
>
import time
>
for i in xrange(5,25):
t = time.time()
foo(2**i)
t = time.time() - t
print 2**i, t, t/2**i
>
On my laptop t roughly doubles for each iteration and prints around 5e-06
for t/2**i in all cases.

Sorry, Skip, but I find that very hard to believe. The foo() function
would take quadratic time if it were merely adding on pieces of
constant size -- however len(str(i)) is not a constant, it is
O(log10(i)), so the time should be super-quadratic. Following are the
results I got with Python 2.5, Windows XP Pro, 3.2Ghz Intel dual-core
processor with the last line changed to print i, 2**i, t, t/2**i coz I
can't do log2() in my head :-)

[snip]
18 262144 0.889999866486 3.39508005709e-006
19 524288 3.21900010109 6.13975544184e-006
20 1048576 12.2969999313 1.17273330034e-005
21 2097152 54.25 2.58684158325e-005
22 4194304 229.0 5.45978546143e-005
[k/b interrupt]

Cheers,
John

[Duncan Booth]

Re: How naive is Python?

Roy Smith <roy@panix.comw rote:

All of those just move around pointers to the same (interned) string.

Correct about the pointers, but the string is not interned:

Steven D'Aprano <steve@REMOVEME .cybersource.co m.auwrote:

>>>s1 = foo()
>>>s2 = foo()
>>>s1 == s2, s1 is s2

(True, True)
>
So the string "This is a test" within foo is not copied each time the
function is called. However, the string "This is a test" is duplicated
between foo and foo2 (the two functions don't share the same string
instance):
>

>>>s3 = foo2()
>>>s3 == s1, s3 is s1

(True, False)
>

In this specific example the two functions don't share the same string, but
that won't always be the case: if the string had been interned this would
have printed (True, True).

e.g. Removing all the spaces from the string produces a string which is
interned.

>>def foo():

s = "Thisisates t"
return s

>>def foo2():

return "Thisisates t"

>>s1 = foo()
>>s2 = foo2()
>>s1 is s2

True

Bottom line, never make assumptions about when two literal strings will
share the same object and when they won't.

[skip@pobox.com]

Re: How naive is Python?


JohnSorry, Skip, but I find that very hard to believe. The foo()
Johnfunction would take quadratic time if it were merely adding on
Johnpieces of constant size -- however len(str(i)) is not a constant,
Johnit is O(log10(i)), so the time should be
Johnsuper-quadratic.

Sorry, I should have pointed out that I'm using the latest version of
Python. I believe += for strings has been optimized to simply extend s when
there is only a single reference to it.

Skip

[skip@pobox.com]

Re: How naive is Python?


JohnSorry, Skip, but I find that very hard to believe. The foo()
Johnfunction would take quadratic time if it were merely adding on
Johnpieces of constant size -- however len(str(i)) is not a constant,
Johnit is O(log10(i)), so the time should be super-quadratic.

meSorry, I should have pointed out that I'm using the latest version
meof Python. I believe += for strings has been optimized to simply
meextend s when there is only a single reference to it.

Actually, it isn't until I work my way back to 2.3 that I start to see
quadratic behavior:

% python2.6 strcopy.py
32 0.0002229213714 6 6.96629285812e-06
64 0.0009078979492 19 1.41859054565e-05
128 0.0006499290466 31 5.0775706768e-06
256 0.0011179447174 1 4.36697155237e-06
512 0.0026080608367 9 5.09386882186e-06
1024 0.0043799877166 7 4.27733175457e-06
2048 0.0092160701751 7 4.50003426522e-06
4096 0.0191979408264 4.68699727207e-06
8192 0.0694131851196 8.47328919917e-06
16384 0.0976829528809 5.96209429204e-06
32768 0.194766998291 5.94381708652e-06
% python2.5 strcopy.py
32 0.0004391670227 05 1.37239694595e-05
64 0.0003030300140 38 4.73484396935e-06
128 0.0006318092346 19 4.93600964546e-06
256 0.0011231899261 5 4.38746064901e-06
512 0.0027930736541 7 5.45522198081e-06
1024 0.0044639110565 2 4.35928814113e-06
2048 0.0095310211181 6 4.65381890535e-06
4096 0.0198018550873 4.83443727717e-06
8192 0.175454854965 2.14178289752e-05
16384 0.103327989578 6.30663998891e-06
32768 0.191411972046 5.84142981097e-06
% python2.4 strcopy.py
32 0.0002300739288 33 7.18981027603e-06
64 0.0003070831298 83 4.79817390442e-06
128 0.0011410713195 8 8.91461968422e-06
256 0.0011601448059 1 4.53181564808e-06
512 0.0023131370544 4 4.51784580946e-06
1024 0.0045900344848 6 4.48245555162e-06
2048 0.0097417831420 9 4.75673004985e-06
4096 0.019122838974 4.66866185889e-06
8192 0.0717267990112 8.75571276993e-06
16384 0.112125873566 6.84362021275e-06
32768 0.188065052032 5.73928991798e-06
% python2.3 strcopy.py
32 0.0002238750457 76 6.99609518051e-06
64 0.0003859996795 65 6.03124499321e-06
128 0.0007660388946 53 5.98467886448e-06
256 0.0015430450439 5 6.02751970291e-06
512 0.0030918121337 9 6.03869557381e-06
1024 0.0065929889679 6.43846578896e-06
2048 0.0147500038147 7.20215030015e-06
4096 0.14589214325 3.56181990355e-05
8192 0.778324127197 9.50102694333e-05
16384 3.20213103294 0.0001954425679 29
32768 14.7389230728 0.0004497962363 53
% python2.2 strcopy.py
32 0.0003159046173 1 9.87201929092e-06
64 0.0004940032958 98 7.71880149841e-06
128 0.0009021759033 2 7.04824924469e-06
256 0.0017321109771 7 6.76605850458e-06
512 0.0036261081695 6 7.08224251866e-06
1024 0.0071160793304 4 6.94929622114e-06
2048 0.0158200263977 7.7246222645e-06
4096 0.152237892151 3.71674541384e-05
8192 0.89648604393 0.0001094343315 34
16384 3.14483094215 0.0001919452479 34
32768 13.3367011547 0.0004070038194 19

Skip

[John Nagle]

Re: How naive is Python?

skip@pobox.com wrote:

JohnSorry, Skip, but I find that very hard to believe. The foo()
Johnfunction would take quadratic time if it were merely adding on
Johnpieces of constant size -- however len(str(i)) is not a constant,
Johnit is O(log10(i)), so the time should be
Johnsuper-quadratic.
>
Sorry, I should have pointed out that I'm using the latest version of
Python. I believe += for strings has been optimized to simply extend s when
there is only a single reference to it.

I'd heard that, but wasn't sure. That's the kind of answer I was
looking for.

That kind of optimization is a huge win.

John Nagle

[John Machin]

Re: How naive is Python?


skip@pobox.com wrote:

JohnSorry, Skip, but I find that very hard to believe. The foo()
Johnfunction would take quadratic time if it were merely adding on
Johnpieces of constant size -- however len(str(i)) is not a constant,
Johnit is O(log10(i)), so the time should be super-quadratic.
>
meSorry, I should have pointed out that I'm using the latest version
meof Python. I believe += for strings has been optimized to simply
meextend s when there is only a single reference to it.

Sorry, I should have pointed out that you need to read up about
time.time() -- what is its resolution on your box? -- and time.clock()
and the timeit module.

>
Actually, it isn't until I work my way back to 2.3 that I start to see
quadratic behavior:
>
% python2.6 strcopy.py
32 0.0002229213714 6 6.96629285812e-06
64 0.0009078979492 19 1.41859054565e-05
128 0.0006499290466 31 5.0775706768e-06
256 0.0011179447174 1 4.36697155237e-06
512 0.0026080608367 9 5.09386882186e-06
1024 0.0043799877166 7 4.27733175457e-06
2048 0.0092160701751 7 4.50003426522e-06
4096 0.0191979408264 4.68699727207e-06
8192 0.0694131851196 8.47328919917e-06
16384 0.0976829528809 5.96209429204e-06
32768 0.194766998291 5.94381708652e-06
% python2.5 strcopy.py
32 0.0004391670227 05 1.37239694595e-05
64 0.0003030300140 38 4.73484396935e-06
128 0.0006318092346 19 4.93600964546e-06
256 0.0011231899261 5 4.38746064901e-06
512 0.0027930736541 7 5.45522198081e-06
1024 0.0044639110565 2 4.35928814113e-06
2048 0.0095310211181 6 4.65381890535e-06
4096 0.0198018550873 4.83443727717e-06
8192 0.175454854965 2.14178289752e-05
16384 0.103327989578 6.30663998891e-06
32768 0.191411972046 5.84142981097e-06

[snip]

Your ability to "see" quadratic behavoiur appears to be impaired by (1)
the low resolution and/or erratic nature of time.time() on your system
(2) stopping the experiment just before the results become interesting.

Try this with the latest *production* release (2.5):

C:\junk>cat fookount.py
def foo(kcount):
s = ''
for i in xrange(kcount) :
s += str(i) + ' '

C:\junk>for /L %n in (10,1,19) do \python25\pytho n -mtimeit -s"from
fookount import foo" "foo(2**%n) "

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**10) "
100 loops, best of 3: 1.1 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**11) "
100 loops, best of 3: 2.34 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**12) "
100 loops, best of 3: 4.79 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**13) "
10 loops, best of 3: 9.57 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**14) "
10 loops, best of 3: 19.8 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**15) "
10 loops, best of 3: 40.7 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**16) "
10 loops, best of 3: 82.1 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**17) "
10 loops, best of 3: 242 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**18) "
10 loops, best of 3: 886 msec per loop

C:\junk>\python 25\python -mtimeit -s"from fookount import foo"
"foo(2**19) "
10 loops, best of 3: 3.21 sec per loop

Cheers,
John

[John Bauman]

Re: How naive is Python?

skip@pobox.com wrote:

Actually, it isn't until I work my way back to 2.3 that I start to see
quadratic behavior:

Yes, that's because the behavior was changed for 2.4, so it wouldn't be
quadratic in this case.

[skip@pobox.com]

Re: How naive is Python?

>>>>"John" == John Machin <sjmachin@lexic on.netwrites:

Johnskip@pobox.com wrote:
JohnSorry, Skip, but I find that very hard to believe. The foo()
Johnfunction would take quadratic time if it were merely adding on
Johnpieces of constant size -- however len(str(i)) is not a constant,
Johnit is O(log10(i)), so the time should be super-quadratic.

>>

meSorry, I should have pointed out that I'm using the latest version
meof Python. I believe += for strings has been optimized to simply
meextend s when there is only a single reference to it.

JohnSorry, I should have pointed out that you need to read up about
Johntime.time() -- what is its resolution on your box? -- and
Johntime.clock( ) and the timeit module.

time.time() should be plenty good enough for this particular task on my
machine (Mac OSX). time.time() has plenty of resolution:

>>import time
>>t = time.time() ; print time.time()-t

3.79085540771e-05

>>t = time.time() ; print time.time()-t

5.00679016113e-06

>>t = time.time() ; print time.time()-t

5.96046447754e-06

>>t = time.time() ; print time.time()-t

5.00679016113e-06

It's time.clock() on Unix-y systems that is too coarse:

>>t = time.clock() ; print time.clock()-t

0.0

>>t = time.clock() ; print time.clock()-t

0.0

>>t = time.clock() ; print time.clock()-t

0.0

>>t = time.clock() ; print time.clock()-t

0.0

>>t = time.clock() ; print time.clock()-t

0.0

I ran the size of the loop to 2**24 and still only saw linear growth in the
later versions of Python. The machine (my Mac laptop) was otherwise idle.
I only reduced the loop length in what I posted before because of the
quadratic growth in Python 2.2 and 2.3. It took so long to run my script
using 2.2 and 2.3 I made a slight change so that it bailed out of the larger
loops:

#!/usr/bin/env python

from __future__ import division

def foo(kcount):
s = ''
for i in xrange(kcount) :
s += str(i) + ' '

import time

for i in xrange(5,25):
t = time.time()
foo(2**i)
t = time.time() - t
print "2**%d"%i, 2**i, t, t/2**i
if t 200:
break

I then ran it using this shell command:

for v in 2.6 2.5 2.4 2.3 2.2 ; do
echo $v
time python$v strcopy.py
done 2>&1 \
| tee strcopy.out

The output is:

2.6
2**5 32 0.0002408027648 93 7.52508640289e-06
2**6 64 0.0002789497375 49 4.3585896492e-06
2**7 128 0.0005991458892 82 4.68082726002e-06
2**8 256 0.0087897777557 4 3.43350693583e-05
2**9 512 0.0022158622741 7 4.32785600424e-06
2**10 1024 0.0043358802795 4 4.23425808549e-06
2**11 2048 0.0089728832244 9 4.38129063696e-06
2**12 4096 0.0197570323944 4.82349423692e-06
2**13 8192 0.0359501838684 4.38845017925e-06
2**14 16384 0.0721030235291 4.40081930719e-06
2**15 32768 0.146120071411 4.45923069492e-06
2**16 65536 0.292731046677 4.46672129328e-06
2**17 131072 0.692205905914 5.28111195308e-06
2**18 262144 1.20644402504 4.60221872345e-06
2**19 524288 3.34210991859 6.37456878394e-06
2**20 1048576 6.86596488953 6.54789437249e-06
2**21 2097152 10.0534589291 4.79386278585e-06
2**22 4194304 21.4015710354 5.1025321568e-06
2**23 8388608 40.8173680305 4.86580944425e-06
2**24 16777216 84.5512800217 5.039649011e-06

real 2m50.195s
user 2m26.258s
sys 0m2.998s
2.5
2**5 32 0.0002050399780 27 6.40749931335e-06
2**6 64 0.0002748966217 04 4.29525971413e-06
2**7 128 0.0005941390991 21 4.64171171188e-06
2**8 256 0.0011069774627 7 4.32413071394e-06
2**9 512 0.0023698806762 7 4.62867319584e-06
2**10 1024 0.0045051574707 4.39956784248e-06
2**11 2048 0.0093810558319 1 4.58059366792e-06
2**12 4096 0.0197520256042 4.82227187604e-06
2**13 8192 0.0375790596008 4.58728754893e-06
2**14 16384 0.0780160427094 4.76172135677e-06
2**15 32768 0.148911952972 4.54443215858e-06
2**16 65536 0.307368040085 4.69006408821e-06
2**17 131072 0.703125953674 5.36442530574e-06
2**18 262144 1.22114300728 4.6582908908e-06
2**19 524288 2.62232589722 5.00168971485e-06
2**20 1048576 5.06462287903 4.83000076201e-06
2**21 2097152 10.3055510521 4.9140696774e-06
2**22 4194304 24.6841719151 5.88516519429e-06
2**23 8388608 42.5984380245 5.07812953288e-06
2**24 16777216 89.6156759262 5.34151052989e-06

real 2m58.236s
user 2m29.354s
sys 0m2.978s
2.4
2**5 32 0.0002319812774 66 7.24941492081e-06
2**6 64 0.0003168582916 26 4.95091080666e-06
2**7 128 0.0005719661712 65 4.46848571301e-06
2**8 256 0.0011270046234 1 4.40236181021e-06
2**9 512 0.0022888183593 8 4.47034835815e-06
2**10 1024 0.0061938762664 8 6.04870729148e-06
2**11 2048 0.0092771053314 2 4.52983658761e-06
2**12 4096 0.0188140869141 4.593282938e-06
2**13 8192 0.0386338233948 4.71604289487e-06
2**14 16384 0.0761170387268 4.64581535198e-06
2**15 32768 0.153247117996 4.67673089588e-06
2**16 65536 0.306257009506 4.67311110697e-06
2**17 131072 0.724220991135 5.52536766918e-06
2**18 262144 1.23747801781 4.7206040108e-06
2**19 524288 2.69648981094 5.1431461543e-06
2**20 1048576 5.20070004463 4.9597740599e-06
2**21 2097152 10.6776590347 5.09150459038e-06
2**22 4194304 21.149684906 5.04247782374e-06
2**23 8388608 46.8901240826 5.58973837883e-06
2**24 16777216 110.079385042 6.56124264253e-06

real 3m19.593s
user 2m32.932s
sys 0m3.100s
2.3
2**5 32 0.0002231597900 39 6.97374343872e-06
2**6 64 0.0003499984741 21 5.46872615814e-06
2**7 128 0.0007379055023 19 5.76488673687e-06
2**8 256 0.0015060901641 8 5.88316470385e-06
2**9 512 0.0030798912048 3 6.01541250944e-06
2**10 1024 0.0064239501953 1 6.27338886261e-06
2**11 2048 0.0161211490631 7.87165481597e-06
2**12 4096 0.110109090805 2.68821022473e-05
2**13 8192 0.787949800491 9.61852783803e-05
2**14 16384 3.3133919239 0.0002022333937 93
2**15 32768 14.3907749653 0.0004391715992 82
2**16 65536 60.2394678593 0.0009191813333 02
2**17 131072 295.17253089 0.0022519876929 4

real 6m15.110s
user 1m54.907s
sys 3m26.747s
2.2
2**5 32 0.0003030300140 38 9.46968793869e-06
2**6 64 0.0004518032073 97 7.05942511559e-06
2**7 128 0.0008730888366 7 6.82100653648e-06
2**8 256 0.0023369789123 5 9.12882387638e-06
2**9 512 0.0034480094909 7 6.73439353704e-06
2**10 1024 0.0073010921478 3 7.12997280061e-06
2**11 2048 0.017196893692 8.39692074805e-06
2**12 4096 0.112847805023 2.75507336482e-05
2**13 8192 0.840929031372 0.0001026524696 5
2**14 16384 3.05718898773 0.0001865960075 52
2**15 32768 13.0093569756 0.0003970140678 58
2**16 65536 57.9497959614 0.0008842437127 9
2**17 131072 294.361263037 0.0022457982104 2

real 6m9.514s
user 1m55.257s
sys 3m26.943s

It's clear that the behavior of the 2.4, 2.5 and 2.6 (cvs) versions is
substantially different than the 2.2 and 2.3 versions, and grows linearly as
the string length grows. I believe any slight nonlinearity in the 2.4-2.6
versions is just due to quadratic behavior in the Mac's realloc function.

Skip