Blimp: add delta encoding family of functions

blimp/net/delta_encoding.h

Index: blimp/net/delta_encoding.h
diff --git a/blimp/net/delta_encoding.h b/blimp/net/delta_encoding.h
new file mode 100644
index 0000000000000000000000000000000000000000..23ccd21cbeda756aa9db1efafc9774f32a0666f2
--- /dev/null
+++ b/blimp/net/delta_encoding.h
@@ -0,0 +1,108 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BLIMP_NET_DELTA_ENCODING_H_
+#define BLIMP_NET_DELTA_ENCODING_H_
+
+#include <algorithm>
+#include <functional>
+
+// This file contains utility functions to concisely compute and apply
+// delta encodings of arbitrarily-typed sequences of values. Delta-encoded
+// numeric values tend to be smaller in magnitude than their source values
+// which, when combined with variable integer encoding (a la protobuf), results
+// in a smaller wire size.
+//
+// e.g. DeltaEncode([4, 1, 5]) => [4, -3, 4]
+//      DeltaDecode([4, -3, 4]) => [4, 1, 5]
+//
+// If ordering doesn't matter, then the function SortAndDeltaEncode()
+// can be used to compute a delta encoding with the smallest possible values.
+//
+// e.g. DeltaEncode([4, 1, 5]) => [1, 3, 1]

[Wez, 2016/08/29 23:25:23]

nit: You mean SortAndDeltaEncode here?

[Kevin M, 2016/08/30 19:06:33]

Done.

+//      DeltaDecode([1, 3, 1]) => [1, 4, 5]
+//
+// Delta encodings can also be computed for structured or non-numeric data
+// types as well, so long as functions are provided for differencing and
+// reconstituting the data. Some interesting things that can be done by these

[Wez, 2016/08/29 23:25:23]

nit: Wording seems verbose. How about "This can also be applied to delta encode
or elide across fields of a struct, for example."?

[Kevin M, 2016/08/30 19:06:33]

Done.

+// functions include elision of redundant data or delta encoding subfields.
+// See the unit test "DeltaEncodeStruct" for an example.
+
+namespace blimp {
+
+template <typename T>
+inline T minus(const T& lhs, const T& rhs) {

[Wez, 2016/08/29 23:25:23]

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?

[Kevin M, 2016/08/30 19:06:33]

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 :\

[Wez, 2016/09/02 20:01:09]

OK, but can we rename it to something less generic than minus(), still?

[Kevin M, 2016/09/02 21:12:44]

Done: 

"minus" => "default_compute_delta"
"plus" => "default_apply_delta"

+  return lhs - rhs;
+}
+
+template <typename T>
+inline T plus(const T& lhs, const T& rhs) {
+  return lhs + rhs;
+}
+
+template <typename T>
+using BinaryFunction = T (*)(const T&, const T&);

[Wez, 2016/08/29 23:25:23]

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.

[Kevin M, 2016/08/30 19:06:33]

The same signature is used for computing and merging deltas, though. Added
comment.

+
+// Delta-encodes a iterated sequence of values in-place.
+// |begin|: An iterator pointing to the beginning of the sequence.
+// |end|: An iterator pointing to the end of the sequence.
+// |compute_delta_fn|: Optional binary function which computes the delta between
+// every element and its next successor.

[Wez, 2016/08/29 23:25:23]

Why is that a run-time rather than a template parameter?

[Kevin M, 2016/08/30 19:06:33]

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.

+template <typename Iterator,
+          typename Type = typename std::iterator_traits<Iterator>::value_type>
+void DeltaEncode(Iterator begin,
+                 Iterator end,
+                 BinaryFunction<Type> compute_delta_fn = &minus<Type>) {
+  if (begin == end) {
+    return;
+  }
+
+  Iterator current = begin;
+  auto current_value = *current;

[Wez, 2016/08/29 23:25:23]

nit: Don't use auto here, or below, since the type of *current is not
immediately obvious.

[Kevin M, 2016/08/30 19:06:33]

Done.

+  ++current;
+  for (; current != end; ++current) {
+    auto next_value = *current;
+    *current = (*compute_delta_fn)(next_value, current_value);
+    current_value = next_value;
+  }

[Wez, 2016/08/29 23:25:23]

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

[Kevin M, 2016/08/30 19:06:33]

Done.

+}
+
+// Delta-decodes a iterated sequence of values in-place.
+// |begin|: An iterator pointing to the beginning of the sequence.
+// |end|: An iterator pointing to the end of the sequence.
+// |merge_fn|: Optional binary function which combines the value of every
+// element with that of its immediate predecessor.
+template <typename Iterator,
+          typename Type = typename std::iterator_traits<Iterator>::value_type>
+void DeltaDecode(Iterator begin,
+                 Iterator end,
+                 BinaryFunction<Type> merge_fn = &plus<Type>) {
+  if (begin == end) {
+    return;
+  }
+
+  Iterator current = begin;
+  auto current_value = *current;

[Wez, 2016/08/29 23:25:23]

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?

[Kevin M, 2016/08/30 19:06:33]

Done.

+  ++current;
+  for (; current != end; ++current) {
+    *current = (*merge_fn)(current_value, *current);
+    current_value = *current;
+  }
+}
+
+// Convenience function for sorting and delta-encoding a sequence of values.
+// The value type must support less-than inequality comparisons (operator<).

[Wez, 2016/08/29 23:25:23]

nit: Safer to simply state that it must support std::sort() :P

[Kevin M, 2016/08/30 19:06:33]

Done.

+template <typename Iterator,
+          typename Type = typename std::iterator_traits<Iterator>::value_type>
+inline void SortAndDeltaEncode(
+    Iterator begin,
+    Iterator end,
+    BinaryFunction<Type> compute_delta_fn = &minus<Type>) {
+  std::sort(begin, end);
+  DeltaEncode(begin, end, compute_delta_fn);
+}
+
+}  // namespace blimp
+
+#endif  // BLIMP_NET_DELTA_ENCODING_H_