Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2275763002:
Blimp: add delta encoding family of functions (Closed)
|
Created:
4 years, 4 months ago by Kevin M Modified:
4 years, 2 months ago CC:
chromium-reviews, cbentzel+watch_chromium.org, anandc+watch-blimp_chromium.org, maniscalco+watch-blimp_chromium.org, sriramsr+watch-blimp_chromium.org, gcasto+watch-blimp_chromium.org, nyquist+watch-blimp_chromium.org, marcinjb+watch-blimp_chromium.org, jessicag+watch-blimp_chromium.org, kmarshall+watch-blimp_chromium.org, lethalantidote+watch-blimp_chromium.org, dtrainor+watch-blimp_chromium.org, shaktisahu+watch-blimp_chromium.org, khushalsagar+watch-blimp_chromium.org Base URL:
https://chromium.googlesource.com/chromium/src.git@master Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionBlimp: add delta encoding family of functions
Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode),
which compute and apply deltas from sequences of arbitrary differentiable values.
R=wez@chromium.org
BUG=
Committed: https://crrev.com/ce9e82beb97b01d15eaaf36db6deab6d19d31e0b
Cr-Commit-Position: refs/heads/master@{#421889}
Patch Set 1 #Patch Set 2 : using iterators! #Patch Set 3 : . #Patch Set 4 : compound structz! #Patch Set 5 : comments, function pointers, renaming, oh my #Patch Set 6 : clean up includes #
Total comments: 25
Patch Set 7 : wez feedback #
Total comments: 2
Patch Set 8 : wez feedback #Patch Set 9 : fix overzealous search and replace #Patch Set 10 : rebase #
Messages
Total messages: 36 (15 generated)
Description was changed from ========== Blimp: add wire_format for common wire format data optimizations. Add DeltaEncode, DeltaDecode, SortAndDeltaEncode functions, which work on arbitrary random access containers of differentiable values. Add unit tests. R=wez@chromium.org BUG= ========== to ========== Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ==========
kmarshall@chromium.org changed reviewers: + nyquist@chromium.org
PTAL!
kmarshall@chromium.org changed reviewers: + lethalantidote@chromium.org
lgtm Nifty. Thanks for writing this up!
ping
https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding_unittest.cc (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding_unittest.cc:20: struct CompoundStruct { Could you add a clarifying comment as to how strings are encoded here so I wouldn't necessarily have to fine-parse the code? I think that would help me read the tests later. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding_unittest.cc:109: TEST_F(TestDeltaEncoding, DeltaDecodeStruct) { How does a sortable compound struct work? Could you add a test for that so it's easy to understand how to do something like that?
Handy stuff! https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:23: // e.g. DeltaEncode([4, 1, 5]) => [1, 3, 1] nit: You mean SortAndDeltaEncode here? https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:28: // reconstituting the data. Some interesting things that can be done by these nit: Wording seems verbose. How about "This can also be applied to delta encode or elide across fields of a struct, for example."? https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:35: inline T minus(const T& lhs, const T& rhs) { Suggest renaming this to GetDeltaBetween(from, to) and ApplyDelta(base, delta). Isn't the case of the value and the delta both being of type T specific to certain types, e.g. integers? e.g. if T is a list of items then I can't express the delta as a single list of items since I can't then express removal of an item. Or do we prefer to restrict this to situations in which the delta encoded type can be the same as the value type? https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:45: using BinaryFunction = T (*)(const T&, const T&); nit: Type name is too generic - what's important is _what_ this is, not _how_ it's implemented, e.g. calling it ComputeDeltaFn would be more appropriate. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:51: // every element and its next successor. Why is that a run-time rather than a template parameter? https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:62: auto current_value = *current; nit: Don't use auto here, or below, since the type of *current is not immediately obvious. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:68: } Naming of the intermediates makes this harder to read, IMO - specifically |current_value| is actually |previous_value| at the point at which the delta is calculated. Since you are effectively wanting to swap out the value in-place, perhaps it would be cleaner / more efficient to use std::swap, e.g: value = *current; // Store the first value as our initial delta base. for (...) { value = (*compute_delta_fn)(value, *current); // Note from, to order of parameters :) std::swap(*current, value); // Put the delta in place and store the actual value into |value|, ready for the next iteration. } https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:86: auto current_value = *current; Again, this naming is confusing, since by the time you call merge_fn, it's the previous value, not the current one! Alternatively, rather than use terms like previous and next, consider referring to it as the |base_value| for the delta to be applied to? https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:95: // The value type must support less-than inequality comparisons (operator<). nit: Safer to simply state that it must support std::sort() :P https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding_unittest.cc (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding_unittest.cc:20: struct CompoundStruct { On 2016/08/26 20:43:42, nyquist wrote: > Could you add a clarifying comment as to how strings are encoded here so I > wouldn't necessarily have to fine-parse the code? > I think that would help me read the tests later. +1 :)
https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:23: // e.g. DeltaEncode([4, 1, 5]) => [1, 3, 1] On 2016/08/29 23:25:23, Wez wrote: > nit: You mean SortAndDeltaEncode here? Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:28: // reconstituting the data. Some interesting things that can be done by these On 2016/08/29 23:25:23, Wez wrote: > nit: Wording seems verbose. How about "This can also be applied to delta encode > or elide across fields of a struct, for example."? Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:35: inline T minus(const T& lhs, const T& rhs) { On 2016/08/29 23:25:23, Wez wrote: > Suggest renaming this to GetDeltaBetween(from, to) and ApplyDelta(base, delta). > > Isn't the case of the value and the delta both being of type T specific to > certain types, e.g. integers? e.g. if T is a list of items then I can't express > the delta as a single list of items since I can't then express removal of an > item. > > Or do we prefer to restrict this to situations in which the delta encoded type > can be the same as the value type? I would prefer to constrain the types. It seems to me that allowing for type variations between the input and output would complicate the decode interface. We'd need two types: one for the initial absolute value, and another type for specifying the deltas. Complicated :\ https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:45: using BinaryFunction = T (*)(const T&, const T&); On 2016/08/29 23:25:23, Wez wrote: > nit: Type name is too generic - what's important is _what_ this is, not _how_ > it's implemented, e.g. calling it ComputeDeltaFn would be more appropriate. The same signature is used for computing and merging deltas, though. Added comment. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:51: // every element and its next successor. On 2016/08/29 23:25:23, Wez wrote: > Why is that a run-time rather than a template parameter? It's really clunky. The computed function signature depends on the iterator's value type, which means it must come after the iterator in the template parameter list. The nasty result is that if the caller wishes to override the function pointer, then she must also specify the iterator type as well, because types are inferred from left to right. ie. DeltaEncode<&MyFunc>(c.begin(), c.end()); // does not work, can't infer iterator type. DeltaEncode<std::vector<int>::iterator, &MyFunc>(c.begin(), c.end()); // works, but requiring that the caller specify the iterator is gross This is nicer because it doesn't require any explicit template args at all: DeltaEncode(c.begin(), c.end(), &MyFunc); The function argument-based approach is more consistent with how functions and functors are passed in common libraries like the STL. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:62: auto current_value = *current; On 2016/08/29 23:25:23, Wez wrote: > nit: Don't use auto here, or below, since the type of *current is not > immediately obvious. Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:68: } On 2016/08/29 23:25:23, Wez wrote: > Naming of the intermediates makes this harder to read, IMO - specifically > |current_value| is actually |previous_value| at the point at which the delta is > calculated. > > Since you are effectively wanting to swap out the value in-place, perhaps it > would be cleaner / more efficient to use std::swap, e.g: > > value = *current; // Store the first value as our initial delta base. > for (...) { > value = (*compute_delta_fn)(value, *current); // Note from, to order of > parameters :) > std::swap(*current, value); // Put the delta in place and store the actual > value into |value|, ready for the next iteration. > } Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:86: auto current_value = *current; On 2016/08/29 23:25:23, Wez wrote: > Again, this naming is confusing, since by the time you call merge_fn, it's the > previous value, not the current one! > > Alternatively, rather than use terms like previous and next, consider referring > to it as the |base_value| for the delta to be applied to? Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:95: // The value type must support less-than inequality comparisons (operator<). On 2016/08/29 23:25:23, Wez wrote: > nit: Safer to simply state that it must support std::sort() :P Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding_unittest.cc (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding_unittest.cc:20: struct CompoundStruct { On 2016/08/26 20:43:42, nyquist wrote: > Could you add a clarifying comment as to how strings are encoded here so I > wouldn't necessarily have to fine-parse the code? > I think that would help me read the tests later. Done. https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding_unittest.cc:109: TEST_F(TestDeltaEncoding, DeltaDecodeStruct) { On 2016/08/26 20:43:42, nyquist wrote: > How does a sortable compound struct work? Could you add a test for that so it's > easy to understand how to do something like that? You would pick some kind of key field and sort using that. I added a test that sorts based on |CompoundStruct::number|.
ping
kmarshall@chromium.org changed reviewers: + steimel@chromium.org
lgtm
https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:35: inline T minus(const T& lhs, const T& rhs) { On 2016/08/30 19:06:33, Kevin M wrote: > On 2016/08/29 23:25:23, Wez wrote: > > Suggest renaming this to GetDeltaBetween(from, to) and ApplyDelta(base, > delta). > > > > Isn't the case of the value and the delta both being of type T specific to > > certain types, e.g. integers? e.g. if T is a list of items then I can't > express > > the delta as a single list of items since I can't then express removal of an > > item. > > > > Or do we prefer to restrict this to situations in which the delta encoded type > > can be the same as the value type? > > I would prefer to constrain the types. It seems to me that allowing for type > variations between the input and output would complicate the decode interface. > We'd need two types: one for the initial absolute value, and another type for > specifying the deltas. Complicated :\ OK, but can we rename it to something less generic than minus(), still? https://codereview.chromium.org/2275763002/diff/120001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/120001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:45: inline bool less(const T& lhs, const T& rhs) { nit: this would be lessthan, I think. But, again, we should give these less generic names, to avoid naming clashes.
https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/100001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:35: inline T minus(const T& lhs, const T& rhs) { On 2016/09/02 20:01:09, Wez wrote: > On 2016/08/30 19:06:33, Kevin M wrote: > > On 2016/08/29 23:25:23, Wez wrote: > > > Suggest renaming this to GetDeltaBetween(from, to) and ApplyDelta(base, > > delta). > > > > > > Isn't the case of the value and the delta both being of type T specific to > > > certain types, e.g. integers? e.g. if T is a list of items then I can't > > express > > > the delta as a single list of items since I can't then express removal of an > > > item. > > > > > > Or do we prefer to restrict this to situations in which the delta encoded > type > > > can be the same as the value type? > > > > I would prefer to constrain the types. It seems to me that allowing for type > > variations between the input and output would complicate the decode interface. > > We'd need two types: one for the initial absolute value, and another type for > > specifying the deltas. Complicated :\ > > OK, but can we rename it to something less generic than minus(), still? Done: "minus" => "default_compute_delta" "plus" => "default_apply_delta" https://codereview.chromium.org/2275763002/diff/120001/blimp/net/delta_encodi... File blimp/net/delta_encoding.h (right): https://codereview.chromium.org/2275763002/diff/120001/blimp/net/delta_encodi... blimp/net/delta_encoding.h:45: inline bool less(const T& lhs, const T& rhs) { On 2016/09/02 20:01:09, Wez wrote: > nit: this would be lessthan, I think. > > But, again, we should give these less generic names, to avoid naming clashes. Done.
The CQ bit was checked by kmarshall@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
lgtm
Oh, by the way, could you fix the CL description by copying the subject of the code review to the first line? It seems to have gotten lost at some point, so the first line is way longer than 70 characters.
Description was changed from ========== Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ========== to ========== Blimp: add delta encoding family of functions Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ==========
Done. Wez? :)
The CQ bit was checked by kmarshall@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
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 kmarshall@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from lethalantidote@chromium.org, steimel@chromium.org, nyquist@chromium.org Link to the patchset: https://codereview.chromium.org/2275763002/#ps180001 (title: "rebase")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Description was changed from ========== Blimp: add delta encoding family of functions Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ========== to ========== Blimp: add delta encoding family of functions Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ==========
Message was sent while issue was closed.
Committed patchset #10 (id:180001)
Message was sent while issue was closed.
Description was changed from ========== Blimp: add delta encoding family of functions Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= ========== to ========== Blimp: add delta encoding family of functions Defines a suite of functions (DeltaEncode, DeltaDecode, SortAndDeltaEncode), which compute and apply deltas from sequences of arbitrary differentiable values. R=wez@chromium.org BUG= Committed: https://crrev.com/ce9e82beb97b01d15eaaf36db6deab6d19d31e0b Cr-Commit-Position: refs/heads/master@{#421889} ==========
Message was sent while issue was closed.
Patchset 10 (id:??) landed as https://crrev.com/ce9e82beb97b01d15eaaf36db6deab6d19d31e0b Cr-Commit-Position: refs/heads/master@{#421889} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
