From c9ce99c0a1e8e96bdc7f79e040305263597dd922 Mon Sep 17 00:00:00 2001 From: Tom Jackson Date: Wed, 31 Oct 2012 17:58:37 -0700 Subject: [PATCH] Composed, for lightweight operator composition Summary: Sometimes it'll be handy to have a custom operator which is little more than the composition of a few base operators. This makes that really easy to do, as shown in examples, tests, and benchmarks. Test Plan: Unit tests, benchmarks Reviewed By: rsagula@fb.com FB internal diff: D617152 --- folly/experimental/Gen-inl.h | 43 ++++++++++++++++ folly/experimental/Gen.h | 2 + folly/experimental/test/GenBenchmark.cpp | 62 ++++++++++++++++++------ folly/experimental/test/GenTest.cpp | 13 +++++ 4 files changed, 105 insertions(+), 15 deletions(-) diff --git a/folly/experimental/Gen-inl.h b/folly/experimental/Gen-inl.h index c213f138..037c330c 100644 --- a/folly/experimental/Gen-inl.h +++ b/folly/experimental/Gen-inl.h @@ -92,6 +92,16 @@ class Operator : public FBounded { class Value, class ResultGen = void> ResultGen compose(const GenImpl& source) const; + + /** + * operator|() - For composing two operators without binding it to a + * particular generator. + */ + template> + Composed operator|(const Operator& op) const { + return Composed(this->self(), op.self()); + } protected: Operator() = default; Operator(const Operator&) = default; @@ -779,6 +789,39 @@ class Order : public Operator> { } }; +/** + * Composed - For building up a pipeline of operations to perform, absent any + * particular source generator. Useful for building up custom pipelines. + * + * This type is usually used by just piping two operators together: + * + * auto valuesOf = filter([](Optional& o) { return o.hasValue(); }) + * | map([](Optional& o) -> int& { return o.value(); }); + * + * auto valuesIncluded = from(optionals) | valuesOf | as(); + */ +template +class Composed : public Operator> { + const First first_; + const Second second_; + public: + Composed() {} + Composed(const First& first, const Second& second) + : first_(first) + , second_(second) {} + + template() + .compose(std::declval())), + class SecondRet = decltype(std::declval() + .compose(std::declval()))> + SecondRet compose(const GenImpl& source) const { + return second_.compose(first_.compose(source.self())); + } +}; + /* * Sinks */ diff --git a/folly/experimental/Gen.h b/folly/experimental/Gen.h index 0797637d..9126d59b 100644 --- a/folly/experimental/Gen.h +++ b/folly/experimental/Gen.h @@ -194,6 +194,8 @@ class Skip; template class Order; +template +class Composed; /* * Sinks diff --git a/folly/experimental/test/GenBenchmark.cpp b/folly/experimental/test/GenBenchmark.cpp index ad9bf7f1..18435c26 100644 --- a/folly/experimental/test/GenBenchmark.cpp +++ b/folly/experimental/test/GenBenchmark.cpp @@ -128,7 +128,6 @@ BENCHMARK(Fib_Sum_NoGen, iters) { }; for (auto& v : fib(testSize.load())) { s += v; - v = s; } } folly::doNotOptimizeAway(s); @@ -166,7 +165,7 @@ BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) { int s = 0; while (iters--) { auto fib = generator(FibYielder()); - s += fib | take(30) | sum; + s += fib | take(testSize.load()) | sum; } folly::doNotOptimizeAway(s); } @@ -239,31 +238,64 @@ BENCHMARK_RELATIVE(Concat_Gen, iters) { folly::doNotOptimizeAway(s); } +BENCHMARK_DRAW_LINE() + +BENCHMARK(Composed_NoGen, iters) { + int s = 0; + while (iters--) { + for (auto& i : testVector) { + s += i * i; + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Composed_Gen, iters) { + int s = 0; + auto sumSq = map(square) | sum; + while (iters--) { + s += from(testVector) | sumSq; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Composed_GenRegular, iters) { + int s = 0; + while (iters--) { + s += from(testVector) | map(square) | sum; + } + folly::doNotOptimizeAway(s); +} + // Results from a dual core Xeon L5520 @ 2.27GHz: // // ============================================================================ // folly/experimental/test/GenBenchmark.cpp relative time/iter iters/s // ============================================================================ // Sum_Basic_NoGen 301.60ns 3.32M -// Sum_Basic_Gen 103.20% 292.24ns 3.42M +// Sum_Basic_Gen 104.27% 289.24ns 3.46M // ---------------------------------------------------------------------------- // Sum_Vector_NoGen 200.33ns 4.99M -// Sum_Vector_Gen 99.44% 201.45ns 4.96M +// Sum_Vector_Gen 99.81% 200.70ns 4.98M +// ---------------------------------------------------------------------------- +// Count_Vector_NoGen 12.37us 80.84K +// Count_Vector_Gen 103.09% 12.00us 83.33K // ---------------------------------------------------------------------------- -// Count_Vector_NoGen 19.07fs 52.43T -// Count_Vector_Gen 166.67% 11.44fs 87.38T +// Fib_Sum_NoGen 3.66us 273.21K +// Fib_Sum_Gen 43.06% 8.50us 117.65K +// Fib_Sum_Gen_Static 87.81% 4.17us 239.89K // ---------------------------------------------------------------------------- -// Fib_Sum_NoGen 4.15us 241.21K -// Fib_Sum_Gen 48.75% 8.50us 117.58K -// Fib_Sum_Gen_Static 113.24% 3.66us 273.16K +// VirtualGen_0Virtual 10.04us 99.61K +// VirtualGen_1Virtual 29.59% 33.93us 29.47K +// VirtualGen_2Virtual 20.45% 49.10us 20.37K +// VirtualGen_3Virtual 15.49% 64.82us 15.43K // ---------------------------------------------------------------------------- -// VirtualGen_0Virtual 10.05us 99.48K -// VirtualGen_1Virtual 29.63% 33.93us 29.47K -// VirtualGen_2Virtual 20.47% 49.09us 20.37K -// VirtualGen_3Virtual 15.30% 65.68us 15.23K +// Concat_NoGen 2.50us 400.37K +// Concat_Gen 102.50% 2.44us 410.37K // ---------------------------------------------------------------------------- -// Concat_NoGen 2.34us 427.15K -// Concat_Gen 90.04% 2.60us 384.59K +// Composed_NoGen 549.54ns 1.82M +// Composed_Gen 101.39% 542.00ns 1.85M +// Composed_GenRegular 99.66% 551.40ns 1.81M // ============================================================================ int main(int argc, char *argv[]) { diff --git a/folly/experimental/test/GenTest.cpp b/folly/experimental/test/GenTest.cpp index bb85abab..06499877 100644 --- a/folly/experimental/test/GenTest.cpp +++ b/folly/experimental/test/GenTest.cpp @@ -166,6 +166,19 @@ TEST(Gen, Until) { EXPECT_EQ(31, gen | count); } +TEST(Gen, Composed) { + // Operator, Operator + auto valuesOf = + filter([](Optional& o) { return o.hasValue(); }) + | map([](Optional& o) -> int& { return o.value(); }); + std::vector> opts { + none, 4, none, 6, none + }; + EXPECT_EQ(4 * 4 + 6 * 6, from(opts) | valuesOf | map(square) | sum); + // Operator, Sink + auto sumOpt = valuesOf | sum; + EXPECT_EQ(10, from(opts) | sumOpt); +} TEST(Gen, Chain) { std::vector nums {2, 3, 5, 7}; -- 2.34.1