[Courgette] Optimize QSufSort to speed up courgette-gen.

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

Committed: https://crrev.com/21773eb242e96704d0ec486d1adf95f2da5d55f7
Cr-Commit-Position: refs/heads/master@{#344353}

[huangs, 2015-08-12 19:44:20]

huangs@chromium.org changed reviewers:
+ wfh@chromium.org

[huangs, 2015-08-12 19:44:20]

Here are the optimization that http://crrev.com/1272453003/ referred to. I'm
also running better benchmarks to measure improvements. PTAL.

[Will Harris, 2015-08-12 23:33:55]

On 2015/08/12 19:44:20, huangs wrote:
> Here are the optimization that http://crrev.com/1272453003/ referred to. I'm
> also running better benchmarks to measure improvements. PTAL.

are there plans to take the ever take latest version of bsdiff/qufsort? It looks
like this change might make importing latest version harder? Have you tested
with the latest versions?

[huangs, 2015-08-13 01:06:48]

Qsufsort does not appear to be under active development.  This CL implements
some low-hanging fruit optimizations that popped up while I was wrapping my head
around Courgette.

If we wish to spend more effort improving, there are other suffix array
algorithms as seen by this benchmark:
https://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks

Another possibility is to benchmark/port the Golang
https://golang.org/src/index/suffixarray/qsufsort.go .

Personally, I'd like to move to memory and patch size optimizations after this
CL.

[huangs, 2015-08-13 17:21:55]

Benchmark data: goo.gl/XboS1f . So we have 35% speed-up in qsufsort and 10% for
courgette-gen. The non-recursive change to search() slowed things down a little
(0.5% for courgette-gen).

[Will Harris, 2015-08-19 20:55:09]

we chatted about this in person and huangs ran through the algorithm.

lgtm and thanks for these continued improvements in courgette.

[huangs, 2015-08-19 21:43:09]

The CQ bit was checked by huangs@chromium.org

[huangs, 2015-08-19 21:43:09]

The patchset sent to the CQ was uploaded after l-g-t-m from wfh@chromium.org
Link to the patchset: https://codereview.chromium.org/1288703002/#ps60001
(title: "Fix comments and spacing.")

[commit-bot: I haz the power, 2015-08-19 21:43:26]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1288703002/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1288703002/60001

[commit-bot: I haz the power, 2015-08-19 22:34:05]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-08-19 22:34:42]

Patchset 4 (id:??) landed as
https://crrev.com/21773eb242e96704d0ec486d1adf95f2da5d55f7
Cr-Commit-Position: refs/heads/master@{#344353}

[zsnmhd, 2015-08-20 12:34:19]

On 2015/08/19 22:34:42, commit-bot: I haz the power wrote:
> Patchset 4 (id:??) landed as
> https://crrev.com/21773eb242e96704d0ec486d1adf95f2da5d55f7
> Cr-Commit-Position: refs/heads/master@{#344353}

Is there a way to build and run Courgette project standalone?

[huangs, 2015-08-20 17:26:58]

Download the Chrome repository and "ninja -C out/Release courgette" builds
Courgette. I haven't tried building this without Chrome. Courgette directly
depends on //base and //third_party/lzma_sdk, so in principle if you download
just these (and transitive deps) you should be able to build "stand alone"
Courgette. However, you might encounter problem trying to generate the build
files ("gclient runhooks"), so some more tweaking might be required.