diff options
| author | embg <elliot.gorokhovsky@gmail.com> | 2018-01-28 20:03:23 -0700 |
|---|---|---|
| committer | Raymond Hettinger <rhettinger@users.noreply.github.com> | 2018-01-28 19:03:23 -0800 |
| commit | 1e34da49ef22004ca25c517b3f07c6d25f083ece (patch) | |
| tree | 7266686f1ae6545a9501b18daaec69baa8e9fe0c /Objects/listsort.txt | |
| parent | 6c6ddf97c402709713d668d0ed53836a7749ba99 (diff) | |
| download | cpython-git-1e34da49ef22004ca25c517b3f07c6d25f083ece.tar.gz | |
bpo-28685: Optimize sorted() list.sort() with type-specialized comparisons (#582)
Diffstat (limited to 'Objects/listsort.txt')
| -rw-r--r-- | Objects/listsort.txt | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/Objects/listsort.txt b/Objects/listsort.txt index 17d27973f8..8c877515c7 100644 --- a/Objects/listsort.txt +++ b/Objects/listsort.txt @@ -753,3 +753,11 @@ example, with the region of uncertainty B[4], B[5], B[6], there are 4 locations: before B[4], between B[4] and B[5], between B[5] and B[6], and after B[6]. In general, across 2**(k-1)-1 elements, there are 2**(k-1) locations. That's why k-1 binary searches are necessary and sufficient. + +OPTIMIZATION OF INDIVIDUAL COMPARISONS +As noted above, even the simplest Python comparison triggers a large pile of +C-level pointer dereferences, conditionals, and function calls. This can be +partially mitigated by pre-scanning the data to determine whether the data is +homogenous with respect to type. If so, it is sometimes possible to +substitute faster type-specific comparisons for the slower, generic +PyObject_RichCompareBool. |