Repository navigation
sorted(range(1000)) is slower in Python 3.7 than in 3.5 #73038
Description
| BPO | 28852 |
|---|---|
| Nosy | @vstinner, @ericvw, @serhiy-storchaka |
| Files |
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 2016-12-05.16:31:44.105>
created_at = <Date 2016-12-01.16:21:27.674>
labels = ['3.7', 'invalid', 'performance']
title = 'sorted(range(1000)) is slower in Python 3.7 than in 3.5'
updated_at = <Date 2016-12-05.16:31:44.104>
user = 'https://github.com/vstinner'bugs.python.org fields:
activity = <Date 2016-12-05.16:31:44.104>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2016-12-05.16:31:44.105>
closer = 'vstinner'
components = []
creation = <Date 2016-12-01.16:21:27.674>
creator = 'vstinner'
dependencies = []
files = ['45727']
hgrepos = []
issue_num = 28852
keywords = []
message_count = 3.0
messages = ['282194', '282196', '282213']
nosy_count = 3.0
nosy_names = ['vstinner', 'ericvw', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue28852'
versions = ['Python 3.7']
Activity
vstinner commentedon Dec 1, 2016
Follow-up of my comment http://bugs.python.org/issue23507#msg282187 :
"sorted(list): Median +- std dev: [3.5] 17.5 us +- 1.0 us -> [3.7] 19.7 us +- 1.1 us: 1.12x slower (+12%)"
"(...) sorted(list) is slower. I don't know why sorted(list) is slower. It doesn't use a key function, and so should not be impacted by FASTCALL changes made since Python 3.6."
vstinner commentedon Dec 1, 2016
Benchmark:
./python -m perf timeit -s 'x=list(range(1000))' 'sorted(x)'
Python 3.6 and 3.7 compared to Python 3.5:
I compiled Python with "./configure && make". The benchmark should be run again using LTO+PGO compilation to get more reliable benchmark results.
It seems like the benchmark is not very stable even with system tune (python3 -m perf system tune, isolcpus and rcu_nocbs in the Linux command line). I ran the benchmark 3 times using --append to concatenate all runs to get enough samples.
Histograms:
[ 3.6.json ]
15.0 us: 0 |
15.2 us: 0 |
15.5 us: 0 |
15.7 us: 0 |
16.0 us: 0 |
16.2 us: 0 |
16.5 us: 0 |
16.7 us: 0 |
17.0 us: 0 |
17.2 us: 0 |
17.4 us: 2 ###
17.7 us: 2 ###
17.9 us: 3 #####
18.2 us: 4 #######
18.4 us: 3 #####
18.7 us: 7 ############
18.9 us: 5 ########
19.2 us: 8 #############
19.4 us: 6 ##########
19.7 us: 7 ############
19.9 us: 9 ###############
20.1 us: 24 ########################################
20.4 us: 16 ###########################
20.6 us: 47 ###############################################################################
20.9 us: 27 #############################################
21.1 us: 10 #################
[ 3.7.json ]
15.0 us: 0 |
15.2 us: 0 |
15.5 us: 0 |
15.7 us: 0 |
16.0 us: 0 |
16.2 us: 1 ##
16.5 us: 0 |
16.7 us: 2 ###
17.0 us: 4 ######
17.2 us: 6 #########
17.4 us: 4 ######
17.7 us: 11 #################
17.9 us: 10 ################
18.2 us: 14 ######################
18.4 us: 10 ################
18.7 us: 5 ########
18.9 us: 3 #####
19.2 us: 10 ################
19.4 us: 6 #########
19.7 us: 13 #####################
19.9 us: 50 ###############################################################################
20.1 us: 10 ################
20.4 us: 19 ##############################
20.6 us: 2 ###
20.9 us: 0 |
21.1 us: 0 |
vstinner commentedon Dec 2, 2016
On my laptop, the revision introducing the performance regression is:
---
changeset: 101858:5a62d682636e
user: Brett Cannon <[email protected]>
date: Fri Jun 10 14:37:21 2016 -0700
files: Doc/library/os.rst Lib/test/test_os.py Misc/NEWS Modules/posixmodule.c
description:
Issue bpo-27186: Add os.PathLike support to DirEntry
Initial patch thanks to Jelle Zijlstra.
---
This change is unrelated to sorted(list). It looks more like a "random performance" caused by code placement:
According to perf record/perf report, the benchmark spends most of its time in PyObject_RichCompareBool() and long_richcompare():
Overhead Command Shared Object Symbol
41,98% python python [.] PyObject_RichCompareBool
35,36% python python [.] long_richcompare
8,52% python python [.] listsort
6,29% python python [.] listextend
5,31% python python [.] list_dealloc
So I guess that the exact code placement of these two functions has a "signifiant" impact on performance. "Significant":
The revision 5a62d682636e makes sorted(list) 9% slower.
--
Enabling PGO on compilation should help to get a more reliable code placement, and so more stable performances.
I suggest to close this issue as NOTABUG: ./configure --with-pgo should already fix this issue.
[-]sorted(range(1000)) is slower in Python 3.7 compared to Python 3.5[/-][+]sorted(range(1000)) is slower in Python 3.7 than in 3.5[/+]