Эффективная реализация функциональных и ленивых вычислений в C ++ - PullRequest
Новая
       73

Эффективная реализация функциональных и ленивых вычислений в C ++

0 голосов
/ 08 мая 2020

Я создаю библиотеку c ++, реализующую Java интерфейс, похожий на функциональное программирование. Вкратце, код будет выглядеть так: 

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

Теперь я хочу поддержать параллельное вычисление. В приведенном выше примере я хочу получить 100 задач выполнения и отправить их в пул потоков. Для этого я создал классы EvalOp. Поток возвращает список объектов EvalOp. Они будут выполнять фактическое вычисление только при вызове EvalOp::eval

template <typename T>
class EvalOp {
public:
    virtual T eval() = 0;
}; 

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

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

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

Мой поток теперь будет возвращать кучу объектов EvalOp, которые вы можете добавить в пул потоков.

Этот код дает мне правильный результат. Но поскольку он создает множество классов-оболочек (EvalOps), выполнение происходит медленнее. Я провел тест для следующих двух задач: 

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

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

uint32_t sum = 0;

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

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

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

Из результатов теста я вижу для каждого элемента только 1 нс тратится на фактические вычисления, а накладные расходы 40 нс тратятся на Stream и EvalOp. Я ищу предложения по созданию более эффективного дизайна. Большое спасибо!

...