classification
Title: optimize sort_keys in json module by using operator.itemgetter()
Type: performance Stage: resolved
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: Arfrever, ezio.melotti, inada.naoki, josh.r, rhettinger, serhiy.storchaka, vstinner, wbolster
Priority: low Keywords: patch

Created on 2015-02-20 16:25 by wbolster, last changed 2018-07-06 23:55 by inada.naoki. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 8131 merged inada.naoki, 2018-07-06 07:52
Messages (16)
msg236302 - (view) Author: wouter bolsterlee (wbolster) * Date: 2015-02-20 16:25
The JSON encoder uses a lambda function for the sort(key=...) invocation used to sort the keys in a JSON object in case sort_keys=True is passed:

https://hg.python.org/cpython/file/46bfddb14cbe/Lib/json/encoder.py#l352

Instead of having a lambda, operator.itemgetter(0) can be used here, which is a minor performance gain. It should be noted that many other internals of the JSON encoder have also been fine-tuned (manually) for performance reasons.
msg236345 - (view) Author: Josh Rosenberg (josh.r) * (Python triager) Date: 2015-02-21 00:43
Is it even legal to have non-string keys in a JSON object? If they must be strings, and they must be unique, I don't think a key argument is necessary (and it would save the generation of the key array; not doing the work is faster than doing the work more efficiently after all), since the default tuple comparison would work fine; the first element would always be unequal, so the second elements would never be compared, right?

I'm not 100% on this with the rich comparison operator approach, but my attempts to trigger a failure haven't worked (TimSort or the tuple comparison, or both, are probably smarter about this than I am).
msg236423 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-02-23 01:13
I'm -0 on this proposal.

There is a small speed-up to be had here:

  $ python3.4 -m timeit -s 'f=lambda kv: kv[0]' -s 's=[10, 20]' 'f(s)'
  10000000 loops, best of 3: 0.105 usec per loop

  $ python3.4 -m timeit -s 'import operator' -s 'f=operator.itemgetter(0)' -s 's=[10, 20]' 'f(s)'
  10000000 loops, best of 3: 0.0717 usec per loop

That said, it is applied only n-times and is likely insignificant when compared to the O(n log n) sort.   I think it is better to not add an intermodule dependency when we don't have to.

Also if you're using CPython, then the C version of JSON is used instead of this code.  So, any timings or optimizations should be tested against the other implementations (Jython or PyPy) that use them.   In those implementations, I don't think itemgetter() has any performance benefit over the lambda.
msg236434 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-23 10:44
CPython:

$ python3.4 -m timeit -s 'f = lambda kv: kv[0]' -s 's = list(dict.fromkeys(range(1000)).items())' -- 'sorted(s, key=f)'
1000 loops, best of 3: 904 usec per loop
$ python3.4 -m timeit -s 'import operator' -s 'f = operator.itemgetter(0)' -s 's = list(dict.fromkeys(range(1000)).items())' -- 'sorted(s, key=f)'
1000 loops, best of 3: 462 usec per loop

PyPy:

$ pypy -m timeit -s 'f = lambda kv: kv[0]' -s 's = list(dict.fromkeys(range(1000)).items())' -- 'sorted(s, key=f)'
1000 loops, best of 3: 1.23 msec per loop
$ pypy -m timeit -s 'import operator' -s 'f = operator.itemgetter(0)' -s 's = list(dict.fromkeys(range(1000)).items())' -- 'sorted(s, key=f)'
1000 loops, best of 3: 1.27 msec per loop
msg236435 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-02-23 10:56
If I remember correctly, the complexity and performance of sort/sorted depends if the data set is sorted or not. You may recreated the list/dictionary at each iteration to get performances closer to "items = sorted(dct.items(), key=lambda kv: kv[0])" (dict keys are not sorted by their content, especially with strings).
msg236436 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-02-23 11:09
Oh, forget my comment. sorted() never changes the input list, so the microbenchmark is ok.
msg236437 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-23 11:10
Unless we use recent PyPy with ordered dicts.
msg236438 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-02-23 11:15
> That said, it is applied only n-times and is likely insignificant when compared to the O(n log n) sort. (...)

904 usec => 462 usec is very significant: it's 49% faster. So I'm ok for the change.

Note: PyPy JIT may not be able to optimize operator.itemgetter, whereas it optimizes the simple lambda function. You may report this performance issue to PyPy. PyPy may use different code in json for best performances.
msg236439 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-23 11:26
My interpretation of the results. In CPython using operator.itemgetter() makes sorting up to 2 times faster (only 25% faster with string keys), in PyPy it make sorting slightly slower (because operator.itemgetter() is implemented in Python, but the lambda is more specialized and could be better optimized).

The lambda looks more clear to me, and I think there is the possibility to optimize CPython to replace the body of such functions with builtins from the operator module.
msg236440 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-02-23 11:30
"My interpretation of the results. In CPython using operator.itemgetter() makes sorting up to 2 times faster"

If I remember correctly, Python functions implemented in C don't create a Python frame. The Python frame is an important cost in term of performances.
msg236441 - (view) Author: wouter bolsterlee (wbolster) * Date: 2015-02-23 12:57
Using IPython and CPython 3.4:

>>> d = dict.fromkeys(map(str, range(1000)))


Current implementation:

>>> %timeit sorted(d.items(), key=lambda kv: kv[0])
1000 loops, best of 3: 605 µs per loop
>>> %timeit sorted(d.items(), key=lambda kv: kv[0])
1000 loops, best of 3: 614 µs per loop

Proposed change:

>>> %timeit sorted(d.items(), key=operator.itemgetter(0))
1000 loops, best of 3: 527 µs per loop
>>> %timeit sorted(d.items(), key=operator.itemgetter(0))
1000 loops, best of 3: 523 µs per loop

Alternative without 'key' arg, since all keys in a JSON object must be strings, so the tuples from .items() can be compared directly.:

>>> %timeit sorted(d.items())
1000 loops, best of 3: 755 µs per loop
>>> %timeit sorted(d.items())
1000 loops, best of 3: 756 µs per loop

As you can see, the operator approach seems the fastest on CPython 3.4, even faster than not having a 'key' arg at all (possibly because it avoids doing a tuple compare, which descends into a string compare for the first item).
msg236442 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-23 13:13
Could you measure the effect on json.encode()?
msg236545 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-24 21:05
May be there is a time to optimize creating Python frames (at least for the 
case when one frame is created and destroyed multiple times). May be frame 
pool? Or cached one frame per function?
msg321157 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2018-07-06 07:47
In C version, we don't use key func.

    items = PyMapping_Items(dct);
    if (items == NULL)
        goto bail;
    if (s->sort_keys && PyList_Sort(items) < 0) {

Like that, how about removing key function completely?
msg321171 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2018-07-06 12:32
I can't confirm significant performance benefit.
sort_keys is not bottleneck of pure Python encoder.

BTW, benefit from C encoder is more significant.  It's about 3x faster.
Adding `indent` option support to C encoder may be good target for new contributors who want to write C.
msg321195 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2018-07-06 23:55
New changeset e25399b40cd15620e77c9ad2ed24549006ae9b47 by INADA Naoki in branch 'master':
bpo-23493: json: Change sort_keys in Python encoder same to C (GH-8131)
https://github.com/python/cpython/commit/e25399b40cd15620e77c9ad2ed24549006ae9b47
History
Date User Action Args
2018-07-06 23:55:06inada.naokisetmessages: + msg321195
2018-07-06 12:32:12inada.naokisetstatus: open -> closed
resolution: rejected
messages: + msg321171

stage: patch review -> resolved
2018-07-06 07:52:44inada.naokisetkeywords: + patch
stage: patch review
pull_requests: + pull_request7709
2018-07-06 07:47:44inada.naokisetnosy: + inada.naoki
messages: + msg321157
2015-03-02 07:58:25ezio.melottisetnosy: + ezio.melotti
2015-02-24 21:05:40serhiy.storchakasetmessages: + msg236545
2015-02-24 01:09:43Arfreversetnosy: + Arfrever
2015-02-23 13:13:05serhiy.storchakasetmessages: + msg236442
2015-02-23 13:09:10serhiy.storchakasetstatus: languishing -> open
2015-02-23 12:57:49wbolstersetmessages: + msg236441
2015-02-23 11:30:10vstinnersetmessages: + msg236440
2015-02-23 11:26:40serhiy.storchakasetpriority: normal -> low
status: open -> languishing
messages: + msg236439
2015-02-23 11:15:16vstinnersetmessages: + msg236438
2015-02-23 11:10:40serhiy.storchakasetmessages: + msg236437
2015-02-23 11:09:48vstinnersetmessages: + msg236436
2015-02-23 10:56:11vstinnersetnosy: + vstinner
messages: + msg236435
2015-02-23 10:44:11serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg236434
2015-02-23 01:13:16rhettingersetversions: - Python 2.7, Python 3.2, Python 3.3, Python 3.4, Python 3.6
nosy: + rhettinger

messages: + msg236423

type: performance
2015-02-21 00:43:21josh.rsetnosy: + josh.r
messages: + msg236345
2015-02-20 16:25:56wbolstercreate