Author Adrian Wielgosik
Recipients Adrian Wielgosik, josh.r, lou1306, swanson
Date 2017-08-06.19:05:37
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1502046338.14.0.672249189256.issue24700@psf.upfronthosting.co.za>
In-reply-to
Content
Added a PR with a fast path that triggers when compared arrays store values of the same type. In this fast path, no Python objects are created. For big arrays the runtime reduction can reach 50-100x.

It's possible to optimize the comparison loop a bit more - for example array('B') comparison could use memcmp and become extra 10x faster, and other types could receive similar treatment - but I wanted to keep the code relatively simple.
Code duplication with macros is a bit ugly, but that's the best I could come up with so far.

Benchmark results:

Test                                Before      After       % of old time
Equal, same stored type (new fast path)
array('i', range(0))                20.4ns      22.07ns     108.15%
array('i', range(1))                33.39ns     22.32ns     66.86%
array('i', range(10))               152.0ns     31.21ns     20.54%
array('i', range(10000))            447.7us     6.571us     1.47%
array('i', range(100000))           4.626ms     67.24us     1.45%
array('i', [1<<30]*100000))         5.234ms     65.8us      1.26%
array('B', range(10))               151.8ns     28.53ns     18.79%
array('B', range(250))              3.14us      194.5ns     6.19%
array('B', [1,2,3]*1000)            37.76us     2.088us     5.53%
array('d', range(10))               311.9ns     31.22ns     10.01%
array('d', range(100000))           2.889ms     99.3us      3.44%
Equal, different types (slow path)
array('X', range(0))                20.37ns     19.45ns     95.48%
array('X', range(1))                34.87ns     34.42ns     98.72%
array('X', range(10))               169.1ns     169.0ns     99.97%
array('X', range(10000))            462.2us     444.8us     96.23%
array('X', range(100000))           4.752ms     4.571ms     96.20%
Not equal: first element (X) different
array('i', [X] + [1,2,3]*10000)     42.77ns     21.84ns     51.06%
Not equal: last element (X) different
array('i', [1,2,3]*10000 + [X])     375.4us     19.8us      5.27%
History
Date User Action Args
2017-08-06 19:05:38Adrian Wielgosiksetrecipients: + Adrian Wielgosik, josh.r, swanson, lou1306
2017-08-06 19:05:38Adrian Wielgosiksetmessageid: <1502046338.14.0.672249189256.issue24700@psf.upfronthosting.co.za>
2017-08-06 19:05:38Adrian Wielgosiklinkissue24700 messages
2017-08-06 19:05:37Adrian Wielgosikcreate