[Python-checkins] python/dist/src/Modules arraymodule.c,2.83,2.84

[Tim Peters]

[Tim]
> Code:
>
> """
> import sys
> import array
> from time import clock as now
>
> print sys.version
>
> for exponent in range(7):
>     n = 10**exponent
>     a = array.array('i')
>
>     start = now()
>     for i in xrange(n):
>         a.append(i)
>     finish = now()
>
>     print "%8d %.2f" % (n, finish - start)
> """
>
> Timings on Win2K under MSVC6:
>
> 2.3a2+ (#39, Feb 24 2003, 09:34:58) [MSC v.1200 32 bit (Intel)]
>        1 0.00
>       10 0.00
>      100 0.00
>     1000 0.00
>    10000 0.02
>   100000 0.27
>  1000000 2.90
>
> 2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)]
>        1 0.00
>       10 0.00
>      100 0.00
>     1000 0.00
>    10000 0.03
>   100000 0.30
>  1000000 35.56
>
> I don't have time to try 10 million under 2.2.2.  "Before" timings are
> undoubtedly much worse under Win9x (because they were for list appends
> before adding mildly exponential over-allocation for list growth).

Heh.  They're actually better under Win98SE:

2.3a2+ (#39, Feb 21 2003, 21:38:18) [MSC v.1200 32 bit (
       1 0.00
      10 0.00
     100 0.00
    1000 0.00
   10000 0.03
  100000 0.26
 1000000 2.61

2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)]
       1 0.00
      10 0.00
     100 0.00
    1000 0.00
   10000 0.06
  100000 0.72
 1000000 3.71

However, boosting it 10,000,000 elements on Win98SE, 2.3a2+ shows the
hoped-for linear-time growth, but 2.2.2 dies with a MemoryError.  As the
comments in listobject.c imply, on Win9x fatal address-space fragmentation
is a much worse problem with many repeated reallocs than is quadratic-time
degeneration.  The situation on Win2K is entirely different.

Linux is generally well-behaved with repeated realloc, but not all flavors
of Unix are (or, at least, weren't, when I was trying to improve list
allocation).