Author Sergey
Recipients Ramchandra Apte, Sergey, aleax, jcea, serhiy.storchaka, terry.reedy
Date 2013-07-04.09:19:38
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1372929579.22.0.846067112129.issue18305@psf.upfronthosting.co.za>
In-reply-to
Content
This patch implements another solution to the same bug. But instead of changing default code it adds a special case optimization for lists, tuples and strings, similar to those two special cases for numbers, that are already there.

=== Lists ===
No patch:
  $ ./python -mtimeit --setup="x=[[1,2,3]]*10000" "sum(x,[])"
  10 loops, best of 3: 885 msec per loop
fastsum.patch:
  $ ./python -mtimeit --setup="x=[[1,2,3]]*10000" "sum(x,[])"
  1000 loops, best of 3: 524 usec per loop
fastsum-special.patch:
  $ ./python -mtimeit --setup="x=[[1,2,3]]*10000" "sum(x,[])"
  1000 loops, best of 3: 298 usec per loop
Result: 3000 times faster.

=== Tuples ===
No patch:
  $ ./python -mtimeit --setup="x=[(1,2,3)]*10000" "sum(x,())"
  10 loops, best of 3: 585 msec per loop
fastsum.patch:
  $ ./python -mtimeit --setup="x=[(1,2,3)]*10000" "sum(x,())"
  10 loops, best of 3: 585 msec per loop
fastsum-special.patch:
  $ ./python -mtimeit --setup="x=[(1,2,3)]*10000" "sum(x,())"
  1000 loops, best of 3: 536 usec per loop
Result: 1000 times faster.

=== Strings ===
No patch (just string check removed):
  $ ./python -mtimeit --setup="x=['abc']*100000" "sum(x,'')"
  10 loops, best of 3: 1.52 sec per loop
fastsum.patch (+ string check removed):
  $ ./python -mtimeit --setup="x=['abc']*100000" "sum(x,'')"
  10 loops, best of 3: 1.52 sec per loop
fastsum-special.patch
  $ ./python -mtimeit --setup="x=['abc']*100000" "sum(x,'')"
  10 loops, best of 3: 27.8 msec per loop
join:
  $ ./python -mtimeit --setup="x=['abc']*100000" "''.join(x)"
  1000 loops, best of 3: 1.66 msec per loop
Result: 50 times faster, but still constantly slower than join.

NB:
The string part of this patch is a Proof-of-Concept, just for tests, to demonstrate, that sum can really be O(n) for strings. It was written for python 2.7.5, won't work for python3, and is not expected to be applied to python2, as it changes the behavior of sum, allowing it to sum strings.

But! If string part is stripped from the patch it works for both python2 and python3, and does not change existing behavior, except making sum faster.
History
Date User Action Args
2013-07-04 09:19:39Sergeysetrecipients: + Sergey, aleax, terry.reedy, jcea, Ramchandra Apte, serhiy.storchaka
2013-07-04 09:19:39Sergeysetmessageid: <1372929579.22.0.846067112129.issue18305@psf.upfronthosting.co.za>
2013-07-04 09:19:39Sergeylinkissue18305 messages
2013-07-04 09:19:38Sergeycreate