classification
Title: ceval: Optimize list[int] (subscript) operation similarly to CPython 2.7
Type: performance Stage: needs patch
Components: Interpreter Core Versions: Python 3.6
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Jim Fasarakis-Hilliard, pitrou, serhiy.storchaka, vstinner, yselivanov, zbyrne
Priority: normal Keywords: patch

Created on 2016-02-03 17:02 by yselivanov, last changed 2017-05-26 16:25 by Jim Fasarakis-Hilliard.

Files
File name Uploaded Description Edit
26280_stats.diff zbyrne, 2016-02-05 03:46 quick and dirty counters for a few types review
subscr_stats.txt zbyrne, 2016-02-05 17:04
subscr1.patch zbyrne, 2016-02-17 02:56 review
subscr2.patch zbyrne, 2016-02-29 23:53 Removed tuple block, inlined a few things review
Messages (19)
msg259492 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-03 17:02
See also issue #21955
msg259512 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-03 20:18
Yury,
Are you going to tackle this one, or would you like me to?
msg259514 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-02-03 20:27
Would be nice to collect statistics about arguments types during running the testsuite. May be list is not the most popular type of collection.
msg259516 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-03 20:42
Zach, first I was going to collect some stats on this (as Serhiy also suggests).  It would be interesting to collect some stats on how many times BINARY_SUBSCR receives lists, tuples, dicts, and other types.  I'd instrument the code to collect those stats and run Python tests suite and benchmarks.

I'm pretty sure that optimizing lists (and tuples?) is a great idea.  It would also be nice to optimize [-1] lookup.  I'd also measure if we should add a fast path for dicts (PyDict_CheckExact + PyDict_GetItem).

If you have time to work on this issue, then by all means go ahead.  We'll be glad to assist you and review the patch.
msg259517 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-03 20:58
Zach, BTW, you can see how I instrumented ceval for stats collection in the patch for issue #26219.  That's only for the research purposes, we won't commit that... or maybe we will, but in a separate issue :).
msg259602 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-02-04 23:00
> I'm pretty sure that optimizing lists (and tuples?) is a great idea.

I think it's a good idea indeed.

> It would also be nice to optimize [-1] lookup

How is that different from the above? :)
msg259611 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-05 01:28
Ok, I've started on the instrumenting, thanks for that head start, that would have taken me a while to figure out where to call the stats dump function from. Fun fact: BINARY_SUBSCR is called 717 starting python.
msg259625 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-05 03:46
I'll put together something comprehensive in a bit, but here's a quick preview:

$ ./python
Python 3.6.0a0 (default, Feb  4 2016, 20:08:03) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> exit()
Total BINARY_SUBSCR calls: 726
List BINARY_SUBSCR calls: 36
Tuple BINARY_SUBSCR calls: 103
Dict BINARY_SUBSCR calls: 227
Unicode BINARY_SUBSCR calls: 288
Bytes BINARY_SUBSCR calls: 68
[-1] BINARY_SUBSCR calls: 0

$ python bm_elementtree.py -n 100 --timer perf_counter
...[snip]...
Total BINARY_SUBSCR calls: 1078533
List BINARY_SUBSCR calls: 513
Tuple BINARY_SUBSCR calls: 1322
Dict BINARY_SUBSCR calls: 1063075
Unicode BINARY_SUBSCR calls: 13150
Bytes BINARY_SUBSCR calls: 248
[-1] BINARY_SUBSCR calls: 0

Lib/test$ ../../python -m unittest discover
...[snip]...^C <== I got bored waiting
KeyboardInterrupt
Total BINARY_SUBSCR calls:  4732885
List BINARY_SUBSCR calls:   1418730
Tuple BINARY_SUBSCR calls:  1300717
Dict BINARY_SUBSCR calls:   1151766
Unicode BINARY_SUBSCR calls: 409924
Bytes BINARY_SUBSCR calls:   363029
[-1] BINARY_SUBSCR calls:     26623

So dict seems to be the winner here
msg259627 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-05 04:10
Looks like we want to specialize it for lists, tuples, and dicts; as expected.  Not so sure about [-1, but I suggest to benchmark it anyways ;)
msg259628 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-05 04:13
One thing I forgot to do was count slices.
msg259632 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-02-05 05:53
Looks as statistics varies from test to test too much. Could you please collect the statistics for running all tests?
msg259651 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-02-05 09:52
The test suite is not an appropriate workload to run benchmarks or statistics. Can you run with the benchmarks suite instead?
msg259652 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-02-05 09:54
I also suggest counting the number of BINARY_SUBSCR calls that are *not* one of the builtin types under consideration. Also, it would be good to distinguish slicing from integer indexing, for lists and tuples.
msg259677 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-05 17:04
I'm attaching output from a selection of the benchmarks, I'm counting non-builtins and slices, but for everything, not just lists and tuples.

Quick observation: math workloads seem list heavy, text workloads seem dict heavy, and tuples are usually somewhere in the middle.
msg259711 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-02-06 01:51
Oh, I just created a duplicate with a patch for list[int]: issue #26301.
msg260376 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-17 02:56
Here's a patch that looks likes Victor's from the duplicate, but with tuples covered as well. I ran some straight forward micro benchmarks but haven't bothered running the benchmark suite yet. Unsurprisingly, optimized paths are faster, and the others take a penalty.

[0]byrnez@byrnez-laptop:~/git/python$ ./python.orig -m timeit -s "l = [1,2,3,4,5,6]" "l[3]"
10000000 loops, best of 3: 0.0306 usec per loop
[0]byrnez@byrnez-laptop:~/git/python$ ./python -m timeit -s "l = [1,2,3,4,5,6]" "l[3]"
10000000 loops, best of 3: 0.0243 usec per loop

[0]byrnez@byrnez-laptop:~/git/python$ ./python.orig -m timeit -s "l = (1,2,3,4,5,6)" "l[3]"
10000000 loops, best of 3: 0.0291 usec per loop
[0]byrnez@byrnez-laptop:~/git/python$ ./python -m timeit -s "l = (1,2,3,4,5,6)" "l[3]"
10000000 loops, best of 3: 0.0241 usec per loop

[0]byrnez@byrnez-laptop:~/git/python$ ./python.orig -m timeit -s "l = 'asdfasdf'" "l[3]"
10000000 loops, best of 3: 0.034 usec per loop
[0]byrnez@byrnez-laptop:~/git/python$ ./python -m timeit -s "l = 'asdfasdf'" "l[3]"
10000000 loops, best of 3: 0.0366 usec per loop

[0]byrnez@byrnez-laptop:~/git/python$ ./python.orig -m timeit -s "l = [1,2,3,4,5,6]" "l[:3]"
10000000 loops, best of 3: 0.124 usec per loop
[0]byrnez@byrnez-laptop:~/git/python$ ./python -m timeit -s "l = [1,2,3,4,5,6]" "l[:3]"
10000000 loops, best of 3: 0.125 usec per loop
msg260377 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-02-17 07:07
I suggest to try to inline PyList_GetItem: use PyList_GET_ITEM and raise
the exception manually if needed.

I'm not sure that it's ok to add PyLong_AsSize_t() to the slow path. Copy
the code in each if? A macro can help.
msg260497 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-19 02:19
Is it worth handling the exception, or just let it take the slow path and get caught by PyObject_GetItem()? We're still making sure the index is in bounds.

Also, where would be an appropriate place to put a macro for adjusting negative indices?
msg261034 - (view) Author: Zach Byrne (zbyrne) * Date: 2016-02-29 23:53
The new patch "subscr2" removes the tuple block, and addresses Victor's comments. This one looks a little faster, down to 0.0215 usec for the same test.
History
Date User Action Args
2017-05-26 16:25:22Jim Fasarakis-Hilliardsetnosy: + Jim Fasarakis-Hilliard
2016-03-01 01:36:27vstinnersettitle: ceval: Optimize list -> ceval: Optimize list[int] (subscript) operation similarly to CPython 2.7
2016-02-29 23:53:30zbyrnesetfiles: + subscr2.patch

messages: + msg261034
2016-02-19 02:19:51zbyrnesetmessages: + msg260497
2016-02-17 07:07:21vstinnersetmessages: + msg260377
title: ceval: Optimize list[int] (subscript) operation similarly to CPython 2.7 -> ceval: Optimize list
2016-02-17 02:56:22zbyrnesetfiles: + subscr1.patch

messages: + msg260376
2016-02-06 02:26:07vstinnerlinkissue26301 superseder
2016-02-06 01:51:49vstinnersetmessages: + msg259711
2016-02-06 01:51:03vstinnersettitle: ceval: Optimize [] operation similarly to CPython 2.7 -> ceval: Optimize list[int] (subscript) operation similarly to CPython 2.7
2016-02-05 17:04:45zbyrnesetfiles: + subscr_stats.txt

messages: + msg259677
2016-02-05 09:54:07pitrousetmessages: + msg259652
2016-02-05 09:52:53pitrousetmessages: + msg259651
2016-02-05 05:53:03serhiy.storchakasetmessages: + msg259632
2016-02-05 04:13:56zbyrnesetmessages: + msg259628
2016-02-05 04:10:03yselivanovsetmessages: + msg259627
2016-02-05 03:46:19zbyrnesetfiles: + 26280_stats.diff
keywords: + patch
messages: + msg259625
2016-02-05 01:28:24zbyrnesetmessages: + msg259611
2016-02-04 23:00:40pitrousetnosy: + pitrou
messages: + msg259602
2016-02-03 20:58:10yselivanovsetmessages: + msg259517
2016-02-03 20:42:36yselivanovsetmessages: + msg259516
2016-02-03 20:27:35serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg259514
2016-02-03 20:18:16zbyrnesetmessages: + msg259512
2016-02-03 17:02:18yselivanovcreate