Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1272453003:
[Courgette] Extract qsufsort module and add tests. (Closed)
Description[Courgette] Extract qsufsort module and add tests.
This is to prepare for a follow-up CL to optimize qsufsort(), which
reduces run time by ~40%, and "courgette -gen" run time by ~10%.
Committed: https://crrev.com/c1de821fbf6dbefdc8eaf8db9e47e1b9ad20d0a9
Cr-Commit-Position: refs/heads/master@{#342883}
Patch Set 1 #Patch Set 2 : Fix compile errors on Linux. #Patch Set 3 : Sync. #Patch Set 4 : Fix signed-unsigned comparison. #Patch Set 5 : Update docs and checklicenses.py. #Patch Set 6 : Sync. #
Total comments: 2
Patch Set 7 : Fix comment re. checklicenses.py UNKNOWN usage. #
Total comments: 5
Patch Set 8 : Use size_t to store ::strlen() returns. #Patch Set 9 : Fix signed/unsigned issues from size_t usage. #Patch Set 10 : Using int, but with explicit cast from ::strlen(). #
Messages
Total messages: 50 (19 generated)
huangs@chromium.org changed reviewers: + dgarrett@chromium.org
PTAL.
dgarrett@chromium.org changed reviewers: + wfh@chromium.org - dgarrett@chromium.org
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/1272453003/40001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/40001
huangs@chromium.org changed reviewers: + dgarrett@chromium.org
PTAL.
The CQ bit was unchecked by commit-bot@chromium.org
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_linu...) linux_android_rel_ng on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_android_r...) linux_chromium_gn_dbg on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...) linux_chromium_rel_ng on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
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/1272453003/60001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/60001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_chromium_rel_ng on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
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/1272453003/80001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/80001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2015/08/05 20:54:52, commit-bot: I haz the power wrote: > Dry run: This issue passed the CQ dry run. I think this is straight forward. LGTM
huangs@chromium.org changed reviewers: + thestig@chromium.org
Thanks! ONWER review to thestig@ for: tools/checklicenses/checklicenses.py I'm splitting module from Courgette's third_party library qsufsort, before upcoming optimization. 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/1272453003/100001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/100001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Is this third party code really Google written code? If so, can we just fix the license headers?
The third party code bsdiff is from here: http://www.daemonology.net/bsdiff/ It contains an implementation of qsufsort where is from here: http://www.larsson.dogma.net/qsufsort.c I found the "split()" routine inefficient (double-scan for tri-partition, when one would suffice) and optimized it (follow-up). The optimization uses a nice trick I thought up, but probably figured out by somebody somewhere already. In the grand scheme of things this is still derivative work, hence desire to keep original license.
https://codereview.chromium.org/1272453003/diff/100001/tools/checklicenses/ch... File tools/checklicenses/checklicenses.py (right): https://codereview.chromium.org/1272453003/diff/100001/tools/checklicenses/ch... tools/checklicenses/checklicenses.py:132: 'courgette/third_party/qsufsort.h': [ Care to also pile this in with http://crbug.com/98095 ?
Updated, PTAL. https://chromiumcodereview.appspot.com/1272453003/diff/100001/tools/checklice... File tools/checklicenses/checklicenses.py (right): https://chromiumcodereview.appspot.com/1272453003/diff/100001/tools/checklice... tools/checklicenses/checklicenses.py:132: 'courgette/third_party/qsufsort.h': [ On 2015/08/10 19:31:05, Lei Zhang wrote: > Care to also pile this in with http://crbug.com/98095 ? Done -- unless you mean to fix the bug?
lgtm
Thanks! Submitting.
The CQ bit was checked by huangs@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dgarrett@google.com Link to the patchset: https://chromiumcodereview.appspot.com/1272453003/#ps120001 (title: "Fix comment re. checklicenses.py UNKNOWN usage.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1272453003/120001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/120001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: chromium_presubmit on tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)
lgtm with size_t/int nits. https://codereview.chromium.org/1272453003/diff/120001/courgette/third_party/... File courgette/third_party/qsufsort_unittest.cc (right): https://codereview.chromium.org/1272453003/diff/120001/courgette/third_party/... courgette/third_party/qsufsort_unittest.cc:33: int len = ::strlen(test_cases[idx]); strlen returns size_t, should int mostly be replaced by size_t in this function? https://codereview.chromium.org/1272453003/diff/120001/courgette/third_party/... courgette/third_party/qsufsort_unittest.cc:68: int old_size = ::strlen(old_str); same as above
https://chromiumcodereview.appspot.com/1272453003/diff/120001/courgette/third... File courgette/third_party/qsufsort_unittest.cc (right): https://chromiumcodereview.appspot.com/1272453003/diff/120001/courgette/third... courgette/third_party/qsufsort_unittest.cc:33: int len = ::strlen(test_cases[idx]); On 2015/08/11 17:31:36, Will Harris (slow at offsite) wrote: > strlen returns size_t, should int mostly be replaced by size_t in this function? Done. Gonna try if this causes signed-unsigned compare error in Linux. https://chromiumcodereview.appspot.com/1272453003/diff/120001/courgette/third... courgette/third_party/qsufsort_unittest.cc:68: int old_size = ::strlen(old_str); On 2015/08/11 17:31:36, Will Harris (slow at offsite) wrote: > same as above Done.
https://codereview.chromium.org/1272453003/diff/120001/courgette/third_party/... File courgette/third_party/qsufsort_unittest.cc (right): https://codereview.chromium.org/1272453003/diff/120001/courgette/third_party/... courgette/third_party/qsufsort_unittest.cc:33: int len = ::strlen(test_cases[idx]); On 2015/08/11 17:46:03, huangs wrote: > On 2015/08/11 17:31:36, Will Harris (slow at offsite) wrote: > > strlen returns size_t, should int mostly be replaced by size_t in this > function? > > Done. Gonna try if this causes signed-unsigned compare error in Linux. sorry if I wasn't clear; I meant change all the ints to size_t in the function - it is likely you will get compile warnings otherwise.
Another problem is that qsufsort has "int oldsize". Also, I and V need to be signed, since the algorithm uses -1 as marker. I want to avoid changing qsufsort() innards in this CL, so I'll just use casting all over the place in the CL.
On 2015/08/11 18:03:01, huangs wrote: > Another problem is that qsufsort has "int oldsize". Also, I and V need to be > signed, since the algorithm uses -1 as marker. I want to avoid changing > qsufsort() innards in this CL, so I'll just use casting all over the place in > the CL. Hmm that sounds like a lot of work for not much benefits. I'm happy with you leaving it with int if that is what the library already uses.
Ah oops, uploaded patch. Okay, reverting to using int, but with explicit cast from ::strlen().
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/1272453003/180001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/180001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by huangs@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from thestig@chromium.org, dgarrett@google.com, wfh@chromium.org Link to the patchset: https://chromiumcodereview.appspot.com/1272453003/#ps180001 (title: "Using int, but with explicit cast from ::strlen().")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1272453003/180001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1272453003/180001
Message was sent while issue was closed.
Committed patchset #10 (id:180001)
Message was sent while issue was closed.
Patchset 10 (id:??) landed as https://crrev.com/c1de821fbf6dbefdc8eaf8db9e47e1b9ad20d0a9 Cr-Commit-Position: refs/heads/master@{#342883} |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
