Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1914303002:
[Courgette] Fix sorting in QSufSort's split(). (Closed)
Description[Courgette] Fix sorting in QSufSort's split().
BSDiff implements Quicksort in its adaptation of QSufSort. To improve
robustness, we reverted the simplified pivot selection algorithm to
the original one due to Bentley & McIlroy used in QSufSort:
http://www.larsson.dogma.net/qsufsort.c
Also reverting split() selection sort threshold from 6 back to 16.
Resulting Courgette-gen and QSufSort has same performance as before
(preliminary: ~1% faster).
BUG=605565
Committed: https://crrev.com/a937d0438bab5dc41c6cfc571a4b16c0d68a6312
Cr-Commit-Position: refs/heads/master@{#390134}
Patch Set 1 #Patch Set 2 : Redo: Improve pivoting to match original QSufSort's. #
Total comments: 1
Patch Set 3 : Update comments; put helper into namespace { }. #Patch Set 4 : Comment nit. #Messages
Total messages: 27 (13 generated)
huangs@chromium.org changed reviewers: + grt@chromium.org, wfh@chromium.org
This fixes the bug, but makes Courgette-gen 8% slower! If this is fine, please consider this as-is. In any case, I'll look into optimizations: - Keep old split() and don't use std::sort(), but make pivot computation more robust. - Use std::vector instead of PagedArray. - Step up the effort to use libdivsufsort, as suggested by deymo@. PTAL. Thanks!
The CQ bit was checked by huangs@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1914303002/1 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1914303002/1
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: cast_shell_android on tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/cast_shell_a...)
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements its own Quicksort in QSufSort. To improve robustness, we change it to use std::sort(), followed by a resolution step to fix I[] and V[]. To get std::sort() to work with PagedArray, we need to implement PagedArray::iterator as RandomAccessIterator. Also added tests. The resulting algorithm, although more robust, made Courgette-gen about 8% slower because QSufSort became 30% slower. This is likely due to overhead in std::sort() pivoting and in PagedArray::iterator. BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivoting algorithm to the original pivoting algorithm due to Bentley & McIlroy. Preliminary experiment saw ~3% speedup in Courgette-gen, from ~6% speedup in QSufSort. BUG=605565 ==========
Using std::sort() followed by I[] V[] resolution was a neat idea, but it was more complex than originally thought, and made things worse! Implemented the less ambitious change of fixing the pivot function based on the original QSufSort: http://www.larsson.dogma.net/qsufsort.c Now we see modest speed-up (~3% overall Courgette-gen, ~6% QSufSort), and the code change is much smaller. PTAL.
The CQ bit was checked by huangs@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1914303002/20001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1914303002/20001
https://codereview.chromium.org/1914303002/diff/20001/courgette/third_party/q... File courgette/third_party/qsufsort.h (right): https://codereview.chromium.org/1914303002/diff/20001/courgette/third_party/q... courgette/third_party/qsufsort.h:50: if (end - start < 16) { Changing this back to the original BSDiff value.
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivoting algorithm to the original pivoting algorithm due to Bentley & McIlroy. Preliminary experiment saw ~3% speedup in Courgette-gen, from ~6% speedup in QSufSort. BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivoting algorithm to the original pivoting algorithm due to Bentley & McIlroy. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ==========
Ran the baseline again for better comparison: Only saw ~1% speed up. Well the point is it didn't get worse, so let's just say performance is same.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm % can you link where you got this code from in the CL? Also is this CL a partial revert of crrev.com/1288703002 or is this new/changed code?
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivoting algorithm to the original pivoting algorithm due to Bentley & McIlroy. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one used in QSufSort due to Bentley & McIlroy: http://www.larsson.dogma.net/qsufsort.c Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ==========
This is reverting the simplification made by BSDiff to choose middle element as pivot. Patch Set 1 attempts to revert http://crrev.com/1288703002, but I abandoned it due to complexity and performance. Patch Set 2 keeps the CL's modifications, while upgrading the pivot code. I have to fix comments at top of file.
But I suppose changing selection sort threshold from 6 back to 16 is a partial revert, and should be mentioned in comment. Committing soon. Thanks!
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one used in QSufSort due to Bentley & McIlroy: http://www.larsson.dogma.net/qsufsort.c Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one due to Bentley & McIlroy used in QSufSort: http://www.larsson.dogma.net/qsufsort.c Also reverting split() selection sort threshold from 6 back to 16. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ==========
The CQ bit was checked by huangs@chromium.org
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/1914303002/#ps60001 (title: "Comment nit.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1914303002/60001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1914303002/60001
Message was sent while issue was closed.
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one due to Bentley & McIlroy used in QSufSort: http://www.larsson.dogma.net/qsufsort.c Also reverting split() selection sort threshold from 6 back to 16. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one due to Bentley & McIlroy used in QSufSort: http://www.larsson.dogma.net/qsufsort.c Also reverting split() selection sort threshold from 6 back to 16. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ==========
Message was sent while issue was closed.
Committed patchset #4 (id:60001)
Message was sent while issue was closed.
Patchset 4 (id:??) landed as https://crrev.com/a937d0438bab5dc41c6cfc571a4b16c0d68a6312 Cr-Commit-Position: refs/heads/master@{#390134}
Message was sent while issue was closed.
Description was changed from ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one due to Bentley & McIlroy used in QSufSort: http://www.larsson.dogma.net/qsufsort.c Also reverting split() selection sort threshold from 6 back to 16. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 ========== to ========== [Courgette] Fix sorting in QSufSort's split(). BSDiff implements Quicksort in its adaptation of QSufSort. To improve robustness, we reverted the simplified pivot selection algorithm to the original one due to Bentley & McIlroy used in QSufSort: http://www.larsson.dogma.net/qsufsort.c Also reverting split() selection sort threshold from 6 back to 16. Resulting Courgette-gen and QSufSort has same performance as before (preliminary: ~1% faster). BUG=605565 Committed: https://crrev.com/a937d0438bab5dc41c6cfc571a4b16c0d68a6312 Cr-Commit-Position: refs/heads/master@{#390134} ========== |
