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.

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).

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.

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

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).

Oh, forget my comment. sorted() never changes the input list, so the microbenchmark is ok.

Unless we use recent PyPy with ordered dicts.

> 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.

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.

"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.

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).

Could you measure the effect on json.encode()?

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?

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?

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.

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

I am wondering why the change was not backported to 3.6 and 3.7?
It introduces different behavior.

For instance, I need to keep duplicate keys from JSON data (because it is allowed by the RFC and it is a missing feature for tools such like HTTPie).

Have a look at repro-sorting.py.

On Python 3.6 and 3.7, the output is not sorted:

    {
        "dps": {
            "1630064726": 5.0,
            "1630064726": 3.0,
            "1630064726": 6.0
        }
    }

Starting with Python 3.8, the output is sorted as expected:

    {
        "dps": {
            "1630064726": 3.0,
            "1630064726": 5.0,
            "1630064726": 6.0
        }
    }

I could open pull requests for both 3.6 and 3.7 branches, if you think it is worth and allowed by the current maintenance status.

> I am wondering why the change was not backported to 3.6 and 3.7?

These branches no longer accept optimizations or bugfixes, only security fixes:
https://devguide.python.org/#status-of-python-branches