classification
Title: array.array constructor very slow when passed an array object.
Type: performance Stage: resolved
Components: Extension Modules Versions: Python 3.2
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: belopolsky Nosy List: LambertDW, belopolsky, georg.brandl, malcolmp, mark.dickinson, meador.inge, rhettinger
Priority: high Keywords: patch

Created on 2009-01-30 12:33 by malcolmp, last changed 2011-01-11 22:36 by belopolsky. This issue is now closed.

Files
File name Uploaded Description Edit
array_test.py malcolmp, 2009-01-30 12:33 Test program for the array.array constructor,
issue5109.diff belopolsky, 2010-07-27 18:14 Patch for py3k branch, revision 83179.
Messages (12)
msg80815 - (view) Author: Malcolm Purvis (malcolmp) Date: 2009-01-30 12:33
Copying an array.array object via the array constructor is some 100x
slower than using slicing or even converting the array to a string and
then passing that string to the array constructor.

Running the attached program on a 2.2GHz MacBook Pro (OSX 10.5.5, 4GB
RAM) produces this output:

$ python2.6 array_test.py
Constructor:  18.5617749691
Slice:  0.169251918793
String:  0.375015974045

From a look at arraymodule.c it seems that array_new() does not have a
special case for the array type and therefore uses the generic sequence
copy code rather than using memcpy(), like it can for slicing.
msg80821 - (view) Author: David W. Lambert (LambertDW) Date: 2009-01-30 15:31
memcpy won't work if the data type changes.  (possibly signed <-> 
unsigned same-byte-count works).
msg81136 - (view) Author: Malcolm Purvis (malcolmp) Date: 2009-02-04 11:22
It's true that memcpy won't work when the data type changes, but I would
assume (with no evidence to back me up) that the most common case for
passing an array into the array's constructor would be when data types
are the same.  That case would be case to detect especially and use
memcpy for.
msg86441 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-04-25 00:22
When the datatype is the same, memcpy() should be used.
msg104691 - (view) Author: Alexander Belopolsky (Alexander.Belopolsky) Date: 2010-05-01 04:06
Attached patch makes array(t, a) use memcpy when t == a.typecode.

The code array_new can probably be refactored to eliminate redundant checks, but with a good C compiler this probably have no performance effect.  While refactoring can simplify the code, it will probably complicate the patch.
msg111708 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-27 18:14
I am replacing issue5109.diff with an updated version (white space only changes).  Does anyone object to this change or need more time to review?
msg115376 - (view) Author: Meador Inge (meador.inge) * (Python committer) Date: 2010-09-02 14:16
Overall, this patch look reasonable.  I tested on py3k and the the tests pass.  I also did a few micro-benchmarks to verify the speedup.  

One question I do have, though, is whether the 'len' calculation modifications are necessary?  This looks like an attempt to optimize more by taking advantage of a particular type's 'len' implementation, but in practice I am not sure it pays off.  In addition, it complicates the patch slightly.  I did the micro-benchmarks with the old 'len' calculation and the results where more-or-less the same as with the new 'len' calculation.  However, perhaps there are other cases where it would pay off that this simple micro-benchmark will not show.

# Micro-benchmarks
# python --with-pydebug
# OS X 10.6
# 2.26 GHz Core 2 Duo

# without patch
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10)))"
100000 loops, best of 3: 17.7 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100)))"
10000 loops, best of 3: 106 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 1000)))"
1000 loops, best of 3: 1.57 msec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10000)))"
100 loops, best of 3: 17.4 msec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100000)))"
10 loops, best of 3: 178 msec per loop

# with patch
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10)))"
100000 loops, best of 3: 11.9 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100)))"
10000 loops, best of 3: 56.1 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 1000)))"
1000 loops, best of 3: 785 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10000)))"
100 loops, best of 3: 8.69 msec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100000)))"
10 loops, best of 3: 88.7 msec per loop

# with patch, but 'len' mods removed
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10)))"
100000 loops, best of 3: 11.2 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100)))"
10000 loops, best of 3: 54.6 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 1000)))"
1000 loops, best of 3: 782 usec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 10000)))"
100 loops, best of 3: 8.66 msec per loop
motherbrain:py3k minge$ ./python.exe -m timeit -s 'import array' "array.array('i', array.array('i', range(0, 100000)))"
10 loops, best of 3: 88.3 msec per loop
msg126014 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2011-01-11 15:48
Georg,

Is it too late to commit this for 3.2?
msg126031 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2011-01-11 18:46
Should be fine to apply.  I trust all the different code paths for different types are tested?
msg126040 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2011-01-11 22:07
Committed in revision 87942.

@Georg: Yes, I ran coverage and all branches are covered.

@Meador: I don't think the old len calculation could handle the case of array object in initial.  In any case, I don't find the new code much more complicated than the old one.  To the contrary, a chain of simple if-else looks cleaner than the original 2-line boolean expression.
msg126041 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2011-01-11 22:17
Committed to 2.7 in revision 87944.
msg126042 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2011-01-11 22:36
Reverted backport in r87945.
History
Date User Action Args
2011-01-11 22:36:56belopolskysetnosy: georg.brandl, rhettinger, mark.dickinson, belopolsky, LambertDW, malcolmp, meador.inge
messages: + msg126042
versions: - Python 2.7
2011-01-11 22:17:10belopolskysetstatus: open -> closed

messages: + msg126041
nosy: georg.brandl, rhettinger, mark.dickinson, belopolsky, LambertDW, malcolmp, meador.inge
stage: commit review -> resolved
2011-01-11 22:07:39belopolskysetnosy: georg.brandl, rhettinger, mark.dickinson, belopolsky, LambertDW, malcolmp, meador.inge
messages: + msg126040
2011-01-11 18:46:57georg.brandlsetnosy: georg.brandl, rhettinger, mark.dickinson, belopolsky, LambertDW, malcolmp, meador.inge
messages: + msg126031
2011-01-11 15:48:55belopolskysetnosy: + georg.brandl
messages: + msg126014
2010-09-02 14:16:33meador.ingesetnosy: + meador.inge
messages: + msg115376
2010-07-27 18:14:38belopolskysetfiles: - issue5109.diff
2010-07-27 18:14:30belopolskysetfiles: + issue5109.diff

components: + Extension Modules, - Library (Lib)
versions: + Python 3.2
nosy: rhettinger, mark.dickinson, belopolsky, LambertDW, malcolmp
messages: + msg111708
resolution: accepted
stage: patch review -> commit review
2010-06-26 03:13:21belopolskysetstage: patch review
2010-06-26 03:13:05belopolskysetassignee: belopolsky

nosy: + belopolsky, mark.dickinson, - Alexander.Belopolsky
2010-05-01 04:06:25Alexander.Belopolskysetfiles: + issue5109.diff
versions: + Python 2.7, - Python 2.6
nosy: + Alexander.Belopolsky

messages: + msg104691

keywords: + patch
2009-04-25 00:22:56rhettingersetpriority: high
nosy: + rhettinger
messages: + msg86441

2009-02-04 11:22:30malcolmpsetmessages: + msg81136
2009-01-30 15:31:49LambertDWsetnosy: + LambertDW
messages: + msg80821
2009-01-30 12:33:25malcolmpcreate