Improve performance of MemoryView slicing

[kristjanvalur]

BPO	10227
Nosy	@mdickinson, @pitrou, @scoder, @kristjanvalur, @skrah
Files	memoryobj.patch slice-object-cache.patch slice-object-cache.patch slice-object-cache.patch: Updated patch for latest Py3.3 hg tip.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2012-02-13.15:39:53.537>
created_at = <Date 2010-10-29.08:50:27.702>
labels = ['interpreter-core', 'performance']
title = 'Improve performance of MemoryView slicing'
updated_at = <Date 2012-02-13.15:39:53.535>
user = 'https://github.com/kristjanvalur'

bugs.python.org fields:

activity = <Date 2012-02-13.15:39:53.535>
actor = 'skrah'
assignee = 'none'
closed = True
closed_date = <Date 2012-02-13.15:39:53.537>
closer = 'skrah'
components = ['Interpreter Core']
creation = <Date 2010-10-29.08:50:27.702>
creator = 'kristjan.jonsson'
dependencies = []
files = ['19410', '20639', '20650', '23727']
hgrepos = []
issue_num = 10227
keywords = ['patch', 'needs review']
message_count = 34.0
messages = ['119872', '119874', '119875', '119876', '119878', '119880', '119881', '119884', '119885', '119886', '120113', '120115', '120117', '127695', '127733', '127746', '127747', '127751', '127790', '127791', '127792', '127795', '127796', '127805', '143728', '143731', '143732', '143733', '147902', '147914', '147915', '153083', '153277', '153279']
nosy_count = 6.0
nosy_names = ['mark.dickinson', 'pitrou', 'scoder', 'kristjan.jonsson', 'skrah', 'python-dev']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue10227'
versions = ['Python 3.3']

[kristjanvalur]

In a recent email exchange on python-dev, Antoine Pitrou mentioned that slicing memoryview objects (lazy slices) wasn't necessarily very efficient when dealing with short slices. The data he posted was:

$ ./python -m timeit -s "x = b'x'*10000" "x[:100]"
10000000 loops, best of 3: 0.134 usec per loop
$ ./python -m timeit -s "x = memoryview(b'x'*10000)" "x[:100]"
10000000 loops, best of 3: 0.151 usec per loop

Actually, this is not a fair comparison. A more realistic alternative to the memoryview is the bytearray, a mutable buffer. My local tests gave these numbers:

python.exe -m timeit -n 10000000 -s "x = ((b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.14 usec per loop

python.exe -m timeit -n 10000000 -s "x = (bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.215 usec per loop

python.exe -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.163 usec per loop

In this case, lazy slicing is indeed faster than greedy slicing. However, I was intrigued by how much these cases differ. Why was slicing bytes objects so much faster? Each should just result in the generation of a single object.

It turns out that the slicing operation for strings (and sequences is very streamlined in the core. To address this to some extent I provide a patch with three main components:

1. There is now a single object cache of slice objects. These are generated by the core when slicing and immediately released. Reusing them if possible is very beneficial.
2. The PySlice_GetIndicesEx couldn't be optimized because of aliasing. Fixing that function sped it up considerably.
3. Creating a new api to create a memory view from a base memory view and a slice is much faster. The old way would do two copies of a Py_buffer with adverse effects on cache performance.

Applying this patch provides the following figures:
python.exe -m timeit -n 10000000 -s "x = ((b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.125 usec per loop

python.exe -m timeit -n 10000000 -s "x = (bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.202 usec per loop

python.exe -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.138 usec per loop

in memoryobject.c there was a comment stating that there should be an API for this. Now there is, only internal.

[pitrou]

You forgot to attach your patch.

[kristjanvalur]

Oh dear. Here it is.

[kristjanvalur]

But then, perhaps implementing the sequence protocol for memoryviews might be more efficient still.

[pitrou]

The sequence protocol (if I'm not confused) only work with a PyObject ** array.

[kristjanvalur]

As an additional point: the PyMemoryObject has a "base" member that I think is redundant. the "view.obj" should be sufficient.

[pitrou]

As an additional point: the PyMemoryObject has a "base" member that I
think is redundant. the "view.obj" should be sufficient.

Yes, that's what I think as well.

[kristjanvalur]

In 2.x, strings are sliced using PySequence_GetSlice(). ceval.c in 3.0 is different, there is no apply_slice there (despite comments to that effect). I'd have to take another look with the profiler to figure out how bytes slicing in 3.0 works, but I suspect that it is somehow fasttracked passed the creation of slice objects, etc.

[pitrou]

I'd have to take another look with the profiler to figure out how
bytes slicing in 3.0 works, but I suspect that it is somehow
fasttracked passed the creation of slice objects, etc.

I don't think it is fasttracked at all.
Even plain indexing is not fasttracked either.

[kristjanvalur]

Well then, its back to the profiler for 3.2. I did all of the profiling with 2.7 for practical reasons (it was the only version I had available at the time) and then ported the change to 3.2 today. But obviously there are different rules in 3.2 :)

[scoder]

I find it a lot easier to appreciate patches that implement a single change than those that mix different changes. There are three different things in your patch, which I would like to see in at least three different commits. I'd be happy if you could separate the changes into more readable feature patches. That makes it easier to accept them.

I'm generally happy about the slice changes, but you will have to benchmark the equivalent changes in Py3.2 to prove that they are similarly worth applying there.

[kristjanvalur]

The benchmarks are from 3.2
Also, I'll do a more relevant profiling session for 3.2. This patch is based on profiling results from 2.7 so there might be more relevant optimization cases in 3.2

[kristjanvalur]

In case I'm not clear enough:
The patch is for 3.2, the benchmarks are 3.2, but it was created based on 2.7 results, which may not fully apply for 3.2

[scoder]

I've extracted and fixed the part of this patch that implements the slice object cache. In particular, PySlice_Fini() was incorrectly implemented. This patch applies cleanly for me against the latest py3k branch.

[pitrou]

Any benchmark numbers for the slice cache?
Also, is the call to PyObject_INIT necessary?

[scoder]

Any benchmark numbers for the slice cache?

I ran the list tests in pybench and got this:

Test minimum run-time average run-time
this other diff this other diff
--------------------------------------------------------------------
ListSlicing: 66ms 67ms -2.2% 67ms 68ms -2.7%
SmallLists: 61ms 64ms -4.5% 61ms 65ms -5.6%
--------------------------------------------------------------------
Totals: 127ms 131ms -3.3% 128ms 133ms -4.1%

Repeating this gave me anything between 1.5% and 3.5% in total, with >2% for the small lists benchmark (which is the expected best case as slicing large lists obviously dominates the slice object creation).

IMHO, even 2% would be pretty good for such a small change.

Also, is the call to PyObject_INIT necessary?

In any case, the ref-count needs to be re-initialised to 1. A call to _Py_NewReference() would be enough, though, following the example in listobject.c. So you can replace

         PyObject_INIT(obj, &PySlice_Type);

by

     _Py_NewReference((PyObject *)obj);

in the patch. New patch attached.

[pitrou]

I ran the list tests in pybench and got this:

Test minimum run-time average run-time
this other diff this other diff
--------------------------------------------------------------------
ListSlicing: 66ms 67ms -2.2% 67ms 68ms -2.7%
SmallLists: 61ms 64ms -4.5% 61ms 65ms -5.6%
--------------------------------------------------------------------
Totals: 127ms 131ms -3.3% 128ms 133ms -4.1%

Repeating this gave me anything between 1.5% and 3.5% in total, with
>2% for the small lists benchmark (which is the expected best case as
slicing large lists obviously dominates the slice object creation).

IMHO, even 2% would be pretty good for such a small change.

Well, 3% on such micro-benchmarks (and, I assume, 0% on the rest) is
generally considered very small.
On the other hand, I agree the patch itself is quite simple.

by

     \_Py_NewReference((PyObject \*)obj);

in the patch. New patch attached.

Don't you also need a _Py_ForgetReference() at the other end? Or have I
missed it?

[scoder]

There's a "PyObject_Del(obj)" in all code paths.

[scoder]

Here are some real micro benchmarks (note that the pybench benchmarks actually do lots of other stuff besides slicing):

base line:

$ ./python -m timeit -s 'l = list(range(100)); s=slice(None)' 'l[s]'
1000000 loops, best of 3: 0.464 usec per loop
$ ./python -m timeit -s 'l = list(range(10)); s=slice(None)' 'l[s]'
10000000 loops, best of 3: 0.149 usec per loop
$ ./python -m timeit -s 'l = list(range(10)); s=slice(None,1)' 'l[s]'
10000000 loops, best of 3: 0.135 usec per loop

patched:

$ ./python -m timeit -s 'l = list(range(100))' 'l[:1]'
10000000 loops, best of 3: 0.158 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[:]'
1000000 loops, best of 3: 0.49 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[1:]'
1000000 loops, best of 3: 0.487 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[1:3]'
10000000 loops, best of 3: 0.184 usec per loop

$ ./python -m timeit -s 'l = list(range(10))' 'l[:]'
10000000 loops, best of 3: 0.185 usec per loop
$ ./python -m timeit -s 'l = list(range(10))' 'l[1:]'
10000000 loops, best of 3: 0.181 usec per loop

original:

$ ./python -m timeit -s 'l = list(range(100))' 'l[:1]'
10000000 loops, best of 3: 0.171 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[:]'
1000000 loops, best of 3: 0.499 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[1:]'
1000000 loops, best of 3: 0.509 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[1:3]'
10000000 loops, best of 3: 0.198 usec per loop

$ ./python -m timeit -s 'l = list(range(10))' 'l[:]'
10000000 loops, best of 3: 0.188 usec per loop
$ ./python -m timeit -s 'l = list(range(10))' 'l[1:]'
1000000 loops, best of 3: 0.196 usec per loop

So the maximum impact seems to be 8% for very short slices (<10) and it quickly goes down for longer slices where the copy impact clearly dominates. There's still some 2% for 100 items, though.

I find it interesting that the base line is way below the other timings. That makes me think it's actually worth caching constant slice instances, as CPython already does for tuples. Cython also caches both now. I would expect that constant slices like [:], [1:] or [:-1] are extremely common. As you can see above, caching them could speed up slicing by up to 30% for short lists, and still some 7% for a list of length 100.

Stefan

[scoder]

Here's another base line test: slicing an empty list

patched:

$ ./python -m timeit -s 'l = []' 'l[:]'
10000000 loops, best of 3: 0.0847 usec per loop

original:

$ ./python -m timeit -s 'l = []' 'l[:]'
10000000 loops, best of 3: 0.0977 usec per loop

That's about 13% less overhead.

[pitrou]

I find it interesting that the base line is way below the other
timings. That makes me think it's actually worth caching constant
slice instances, as CPython already does for tuples.

Indeed. I have never touched it, but I suppose it needs an upgrade of
the marshal format to support slices.
(of course, this will not help for other common cases such as l[x:x+2]).

[scoder]

of course, this will not help for other common cases such as l[x:x+2]

... which is exactly what this slice caching patch is there for. ;-)

[scoder]

A quick test against the py3k stdlib:

find -name "*.py" | while read file; do egrep '\[[-0-9]:[-0-9]\]' "$file"; done | wc -l

This finds 2096 lines in 393 files.

[scoder]

Created follow-up bpo-11107 for caching constant slice objects.

[skrah]

Kristján, could you check out the new implementation over at bpo-10181?
I have trouble reproducing a big speed difference between bytearray
and memoryview (Linux, 64-bit). Here are the timings I get for the
current and the new version:

Slicing
-------

1. ./python -m timeit -n 10000000 -s "x = bytearray(b'x'*10000)" "x[:100]"

2. ./python -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[:100]"

3. cpython: 0.137 usec pep-3118: 0.138 usec

4. cpython: 0.132 usec pep-3118: 0.132 usec

Slicing with overhead for multidimensional capabilities:
--------------------------------------------------------

1. ./python -m timeit -n 10000000 -s "import _testbuffer; x = _testbuffer.ndarray([ord('x') for _ in range(10000)], shape=[10000])" "x[:100]"

2. ./python -m timeit -n 10000000 -s "import numpy; x = numpy.ndarray(buffer=bytearray(b'x'*10000), shape=[10000], dtype='B')" "x[:100]"

3. _testbuffer.c: 0.198 usec

4. numpy: 0.415 usec
   Slice assignment
   ----------------

5. ./python -m timeit -n 10000000 -s "x = bytearray(b'x'*10000)" "x[5:10] = x[7:12]"

6. ./python -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[5:10] = x[7:12]"

7. cpython: 0.242 usec pep-3118: 0.240 usec

8. cpython: 0.282 usec pep-3118: 0.287 usec

Slice assignment, overhead for multidimensional capabilities
------------------------------------------------------------

1. ./python -m timeit -n 10000000 -s "import _testbuffer; x = _testbuffer.ndarray([ord('x') for _ in range(10000)], shape=[10000], flags=_testbuffer.ND_WRITABLE)" "x[5:10] = x[7:12]"

2. ./python -m timeit -n 10000000 -s "import numpy; x = numpy.ndarray(buffer=bytearray(b'x'*10000), shape=[10000], dtype='B')" "x[5:10] = x[7:12]"

_testbuffer.c: 0.469 usec
numpy: 1.37 usec

tolist
------

1. ./python -m timeit -n 10000 -s "import array; x = array.array('B', b'x'*10000)" "x.tolist()"

2. ./python -m timeit -n 10000 -s "x = memoryview(bytearray(b'x'*10000))" "x.tolist()"

3. cpython, array: 104.0 usec

4. pep-3118, memoryview: 90.5 usec

tolist, struct module overhead
------------------------------

1. ./python -m timeit -n 10000 -s "import _testbuffer; x = _testbuffer.ndarray([ord('x') for _ in range(10000)], shape=[10000])" "x.tolist()"
2. ./python -m timeit -n 10000 -s "import numpy; x = numpy.ndarray(buffer=bytearray(b'x'*10000), shape=[10000], dtype='B')" "x.tolist()"

_testbuffer.c: 1.38 msec (yes, that's microseconds!)
numpy: 104 usec

[kristjanvalur]

I'm afraid I had put this matter _far_ out of my head :) Seeing the amount of discussion on that other defect (stuff I had already come across and scrathced my head over) I think there is a lot of catching up that I'd need to do and I am unable to give this any priority at the moment.
My original patch sought to even out the slicing performance difference between bytes and bytearray. bytes objects were very streamlined while other were not.

python.exe -m timeit -n 10000000 -s "x = ((b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.125 usec per loop

python.exe -m timeit -n 10000000 -s "x = (bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.202 usec per loop

Did you take a look at this at all?

[skrah]

I see. I thought this was mainly about memoryview performance, so
I did not specifically look at bytearray. The poor performance seems
to be Windows specific:

C:\Users\stefan\hg\pep-3118\PCbuild>amd64\python.exe -m timeit -n 10000000 -s "x = ((b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.118 usec per loop

C:\Users\stefan\hg\pep-3118\PCbuild>amd64\python.exe -m timeit -n 10000000 -s "x = (bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.191 usec per loop

C:\Users\stefan\hg\pep-3118\PCbuild>amd64\python.exe -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[:100]"
10000000 loops, best of 3: 0.146 usec per loop

Linux:

bytes: 10.9 usec bytearray: 0.14 usec memoryview: 0.14 usec

[skrah]

With Stefan Behnel's slice-object-cache.patch, I get this (PEP-3118 branch):

Linux: bytes: 0.097 usec bytearray: 0.127 usec memoryview: 0.12 usec
Windows: bytes: 0.11 usec bytearray: 0,184 usec memoryview: 0.139 usec

On Linux, that's quite a nice speedup.

[scoder]

Updated single slice caching patch for latest Py3.3 hg tip.

[python-dev]

New changeset fa2f8dd077e0 by Antoine Pitrou in branch 'default':
Issue bpo-10227: Add an allocation cache for a single slice object.
http://hg.python.org/cpython/rev/fa2f8dd077e0

[pitrou]

Thanks Stefan. I'm leaving the issue open since the original topic is a bit different.

[skrah]

Kristján, I ran the benchmarks from http://bugs.python.org/issue10227#msg143731
in the current cpython and pep-3118 repos. In both cases the differences between
Linux and Windows are far less pronounced than they used to be. All benchmarks
were run with the x64 builds.

I also ran the profile guided optimization build for Visual Studio. The
results are equal to (or better than) the non-pgo gcc results. In my
experience Visual Studio relies heavily on PGO for x64 builds. The
default optimizer is just not as good as gcc's.

If you can reproduce similar results, I think we can close this issue.

./python -m timeit -n 10000000 -s "x = ((b'x'*10000))" "x[:100]"

linux-cpython (4244e4348362): 0.102 usec
linux-pep-3118 (memoryview:534f6bbe5422): 0.098 usec

windows-cpython: 0.109 usec
windows-pep-3118: 0.112 usec usec
windows-pep-3118-pgo: 0.103 usec

./python -m timeit -n 10000000 -s "x = (bytearray(b'x'*10000))" "x[:100]"

linux-cpython (4244e4348362): 0.107 usec
linux-pep-3118 (memoryview:534f6bbe5422): 0.109 usec

windows-cpython: 0.127 usec
windows-pep-3118: 0.128 usec
windows-pep-3118-pgo: 0.106 usec

./python -m timeit -n 10000000 -s "x = memoryview(bytearray(b'x'*10000))" "x[:100]"

linux-cpython (4244e4348362): 0.127 usec
linux-pep-3118 (memoryview:534f6bbe5422): 0.12 usec

windows-cpython: 0.145 usec
windows-pep-3118: 0.14 usec
windows-pep-3118-pgo: 0.0984 usec

[kristjanvalur]

Sure. Flagging this as fixed. Can´t close it until 10181 is closed due to some dependency thing. (perhaps someone else knows what to do?)

[skrah]

Great. I removed the dependency since it's fixed in both cpython
and pep-3118.