New submission from David Wyde <david.w...@gmail.com>:
Python's Timsort sometimes makes the same comparison twice. This leads to extra compares, which can hurt performance. Python sorts several length-3 permutations in 4 steps, and the problem accumulates with bigger data. There are ~9,800 duplicate less-than checks when sorting a million randomly ordered numbers, and 24,386 wasted comparisons when sorting all permutations of length 8. I've attached a patch to fix this issue. Feedback and improvements are appreciated. Speed seems roughly comparable, and should be much improved for expensive comparison functions. The same problem occurs in the Chromium Browser, and probably other ports of Python's Timsort implementation. ---------- files: sort-fix.diff keywords: patch messages: 330839 nosy: dwyde, tim.peters priority: normal severity: normal status: open title: List sorting makes duplicate comparisons type: performance versions: Python 3.8 Added file: https://bugs.python.org/file47962/sort-fix.diff _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue35369> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
