Efficient Implementation of functional and Lazy evaluation in C++ I am creating a c++ library implementing Java Functional Programming alike interface. In short, the code will look like this:

vector&lt;string&gt; buffer = ... ; // A buffer contains some strings
new IntStream(0, 100).map([](int a){
    return (a * 0x2344DDEF) &amp; 0xF;
}).map([=](int a) {
    return buffer[a];
}).foreach([](string a) {
    cout &lt;&lt; a &lt;&lt; '\n';
});


Now I want to support parallel evaluation. For the example above, I want to get 100 execution tasks and send them to a thread pool. To do this, I have created EvalOp classes. The stream returns a list of EvalOp objects. They will only perform the actual computation when you invoke EvalOp::eval

template &lt;typename T&gt;
class EvalOp {
public:
    virtual T eval() = 0;
}; 

template &lt;typename FROM, typename TO&gt;
class TransformOp : public EvalOp&lt;TO&gt; {
public:
    TO eval() override {
        return mapper_(previous_-&gt;eval());
    }
protected:
    unique_ptr&lt;EvalOp&lt;FROM&gt;&gt; previous_;
    function&lt;TO(FROM&amp;)&gt; mapper_;
};

template &lt;typename T&gt;
class Stream {
public:
    virtual bool isEmpty() = 0;
    virtual EvalOp&lt;T&gt; next() = 0;
    Stream&lt;N&gt; map(function&lt;N(T)&gt; mapper) {
        return new MapStream&lt;N,T&gt;(this, mapper);
    }
}

template &lt;typename FROM, typename TO&gt;
class MapStream : public Stream&lt;TO&gt; {
protected:
    Stream&lt;FROM&gt;* previous_;
    function&lt;TO(FROM)&gt; mapper_;
public:
    EvalOp&lt;TO&gt; next() override {
        return new TransformOp&lt;FROM, TO&gt;(previous_-&gt;next(), mapper_);
    }
}


My stream will now return a bunch of EvalOp objects, which you can throw in a thread pool.

This code gets me the correct result. But as it creates many wrapper classes (the EvalOps), the execution is slower. I did a benchmark of the following two tasks:

uint32_t __attribute__ ((noinline)) hash1(uint32_t input) {
    return input * 0x12345768;
}

uint32_t __attribute__ ((noinline)) hash2(uint32_t input) {
    return ((input * 0x2FDF1234) &lt;&lt; 12) * 0x23429459;
}

uint32_t sum = 0;

void summer(uint32_t input) {
    sum += input;
}

BENCHMARK(StreamBenchmark, Serial)(State&amp; state) {
    for(auto _:state) {
        for(int i = 0 ; i &lt; 10000; ++i)
            sum += hash2(hash1(i));
        }
    }
}

BENCHMARK(StreamBenchmark, Wrapper)(State&amp; state) {
    for(auto _:state) {
        IntStream stream(0, 10000);
        stream.map(hash1).map(hash2).foreach(summer);
    }
}


From the benchmark result, I see for each element, only 1ns is spent on actual computation and 40ns overhead is spent on the Stream and EvalOp. I am looking for some suggestions to make a more efficient design. Thank you very much!
I think this question may be off-topic, as it does not consist of complete working code to be reviewed. I spent (too long) trying to get it to compile, and got as far as this: https://godbolt.org/z/qCE9S8

But you have a lot of problems with the current design. Most notably, you're using raw new all over the place, which creates pointers to the heap; but you aren't actually using the correct syntax to refer to those pointers. For example:

Stream&lt;N&gt; map(function&lt;N(T)&gt; mapper) {
    return new MapStream&lt;N,T&gt;(this, mapper);
}


Here new MapStream&lt;...&gt;() yields a value of type MapStream&lt;N,T&gt;*, but you're trying to return it as if it were a Stream&lt;N&gt; object. This flatly will not compile.

You could consider changing this return type to std::unique_ptr&lt;Stream&lt;N&gt;&gt; (and using make_unique), but that still won't really work for your use-case, because then you'll have to change this line:

stream.map(hash1).map(hash2).foreach(summer);


to:

stream.map(hash1)-&gt;map(hash2)-&gt;foreach(summer);


because now map returns a pointer. And worse, there's no way for the MapStream object itself to transfer its own ownership into the previous_ member of the next MapStream object in the chain. You end up with a bunch of temporary unique_ptrs, all linked together by raw pointers which will dangle as soon as the current full-expression finishes. That's okay for your benchmark, but it won't work at all in practice.

You might consider looking at a type erasure design, so that you could keep using Stream&lt;int&gt; as a value type (not a polymorphic base class, no visible pointers) but give it behavior that appeared polymorphic at run time.