[Courgette] Optimize QSufSort to speed up courgette-gen.
We apply the following optimizations to QSufSort:
- split()'s interface is changed to start/end instead of
start/length, so many unnecessary adds are removed.
- split()'s 3-way partition is now done in a single pass.
- search()'s binary search is no longer recursive.
Experiment (goo.gl/XboS1f) shows this leads to 35% speed
up in qsufsort(), and 10% speed up in courgette-gen.
search() was slightly (0.5%) slower up much, perhaps
because tail recursion was compiler-optimized.
However, the new code is cleaner and takes two fewer
params.
Review URL: https://codereview.chromium.org/1288703002
Cr-Original-Commit-Position: refs/heads/master@{#344353}
Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src
Cr-Mirrored-Commit: 21773eb242e96704d0ec486d1adf95f2da5d55f7
3 files changed
