Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(127)

Issues Search
    My Issues | Starred     Open | Closed | All

Issue 1948843002: [Courgette Experimental] Replace QSufSort with libdivsufsort

Created:
4 years, 7 months ago by huangs
Modified:
4 years, 5 months ago
Reviewers:
CC:
chromium-reviews
Base URL:
https://chromium.googlesource.com/chromium/src.git@master
Target Ref:
refs/pending/heads/master
Project:
chromium
Visibility:
Public.

Description

[Courgette Experimental] Replace QSufSort with libdivsufsort This is a quick-and-dirty experiment to measure the benefit of replacing QSufSort with libdivsufsort. Results are in http://crbug.com/608885 . BUG=608885

Patch Set 1 #

Patch Set 2 : Add divsufsort unittest; remove some unused parts. #

Patch Set 3 : Move #defines to where they get used; formatting. #

Patch Set 4 : Change stack-related #defines to template class. #

Patch Set 5 : Undoing changes to reduce diff with original files. #

Patch Set 6 : Refactoring to use saidx_it and const_saidx_it (depends on semantics). #

Patch Set 7 : Experiment with sa_search(). #

Patch Set 8 : Add iterators for PagedArray and using them in divsufsort. #

Patch Set 9 : Iterator cleanup. #

Patch Set 10 : Sync and merge. #

Patch Set 11 : Sync. #

Patch Set 12 : Add unittests for PagedArray iterators. #

Patch Set 13 : Cleanup, add LICENSE, try to fix std::iterator_traits compile problem. #

Patch Set 14 : Improve iterator code, another shot to fix compile error. #

Patch Set 15 : Sync. #

Patch Set 16 : Make better use of C++11 for PagedArray iterators. #

Patch Set 17 : Follow etiennep@'s suggestion to use single iterator class. #

Patch Set 18 : More cleanup. #

Patch Set 19 : Merge after committing PagedArray changes. #

Patch Set 20 : Cleanup; add README.chromium. #

Patch Set 21 : Remove QSufSort; fix comments. #

Patch Set 22 : Sync and merge. #

Unified diffs Side-by-side diffs Delta from patch set Stats (+2073 lines, -321 lines) Patch
M courgette/BUILD.gn View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 chunks +6 lines, -2 lines 0 comments Download
M courgette/courgette.gyp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 chunks +6 lines, -2 lines 0 comments Download
M courgette/third_party/bsdiff/README.chromium View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +2 lines, -3 lines 0 comments Download
M courgette/third_party/bsdiff/bsdiff_apply.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +1 line, -1 line 0 comments Download
M courgette/third_party/bsdiff/bsdiff_create.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 6 chunks +13 lines, -15 lines 0 comments Download
M courgette/third_party/bsdiff/bsdiff_search.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 chunks +2 lines, -2 lines 0 comments Download
M courgette/third_party/bsdiff/bsdiff_search_unittest.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 5 chunks +12 lines, -9 lines 0 comments Download
D courgette/third_party/bsdiff/qsufsort.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +0 lines, -226 lines 0 comments Download
D courgette/third_party/bsdiff/qsufsort_unittest.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +0 lines, -61 lines 0 comments Download
A courgette/third_party/divsufsort/LICENSE View 1 2 3 4 5 6 7 8 9 10 11 12 1 chunk +58 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/README.chromium View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +32 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/divsufsort.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 chunk +48 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/divsufsort.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 chunk +249 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/divsufsort_private.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 chunk +60 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/divsufsort_unittest.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 chunk +172 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/sssort.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 chunk +840 lines, -0 lines 0 comments Download
A courgette/third_party/divsufsort/trsort.cc View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 chunk +572 lines, -0 lines 0 comments Download

Messages

Total messages: 13 (7 generated)
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1948843002/240001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1948843002/240001
4 years, 7 months ago (2016-05-20 20:26:37 UTC) #3
commit-bot: I haz the power
Dry run: Try jobs failed on following builders: ios-device on tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device/builds/9403) ios-device-gn on ...
4 years, 7 months ago (2016-05-20 20:33:07 UTC) #5
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1948843002/300001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1948843002/300001
4 years, 7 months ago (2016-05-25 04:03:32 UTC) #7
commit-bot: I haz the power
Dry run: Try jobs failed on following builders: cast_shell_linux on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linux/builds/165885)
4 years, 7 months ago (2016-05-25 04:10:37 UTC) #9
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1948843002/340001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1948843002/340001
4 years, 7 months ago (2016-05-25 23:17:51 UTC) #11
commit-bot: I haz the power
4 years, 7 months ago (2016-05-25 23:28:05 UTC) #13 
Dry run: Try jobs failed on following builders:
  android_compile_dbg on tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_comp...)
  cast_shell_android on tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/cast_shell_a...)
  cast_shell_linux on tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)

Powered by Google App Engine
This is Rietveld 408576698