使用 STL 算法缓存复杂的比较函数？

Question

我有一个很长的计算函数 f(T) -> int 和一个 T 的向量 v。任务是在应用 f 后找到最小元素。

一般来说，我会用

std::min_element(begin(v), end(v), [&f](auto a, auto b){ return f(a) < f(b); }

编译器是否尝试存储计算值（如果这有意义），还是我必须手动存储？第二种情况：用STL算法手工做，有好的解决方案吗？

编辑：请注意，实现无法确保此优化，因为它仅获取比较函数而不是比较函数的结构（在本例中为一元函数）。

这也是一个更普遍的问题，因为在使用 STL 算法时总是会出现这个问题。如果我测量一个例子，我只能为一个特定的例子买保险。我感兴趣的是编译器是否尝试在一般情况下修复此问题（启用合理的优化）。如果不是，你能在不重写算法的情况下解决这个问题吗？

编辑 2：我认为除了替换方法之外，所有问题都得到了很好的回答。这应该满足它与（未实现的）函数

具有相同的运行时间

std::min_element(begin(v), end(v), f);

存储最后访问的元素的值。此外，我想要一个适用于可以进行此优化的所有算法的解决方案。

使用 c++20，我们可以使用投影，但据我所知，建议的实现 https://en.cppreference.com/w/cpp/algorithm/ranges/min_element 并未针对缓存进行优化（我想知道为什么，它不会使任何东西变慢，对吧？）。

Answer 1

min_element 的实现无法缓存 f(a)，因为它适用于谓词。但是看看更大的实现（编译器加上它的标准库），因为你传递了一个 lambda，编译器很可能能够将 lambda 主体内联到 min_element。因此，优化器确实有机会在循环中查看 f(a)。

一个好的优化器可能只缓存 f(*returnvalue) 简单的迭代器类型，例如指针和向量迭代器。这不会专门为 min_element 编程，这将是尝试在循环内重用子表达式的通用优化的结果。

Answer 2

Do compilers try to store the computed values (if that makes sense) or do I have to do that by hand?

通常这称为 memoization 并且通常编译器无法为您完成。在特定情况下，内联可能允许优化器做一些聪明的事情。

如果您希望经常这样做，您可以编写一个自动记忆功能包装器 - 它只需要保留一些（可能是有限的）存储量来跟踪先前遇到的输入的输出。然后你可以这样写

auto mf = memoize(f);
std::min_element(begin(v), end(v), [&mf](auto a, auto b){ return mf(a) < mf(b); }

（请注意，假设当 mf 超出范围时其缓存值丢失，您仍在明确决定该特定备忘录的持续时间）。

语言不会为你做这件事，因为有很多实现权衡（多少存储空间是合理的？如果 return 值的复制构造函数在复制时抛出异常会发生什么它进入你的备忘录存储？) 没有任何明显好的默认值。

Answer 3

为了检查编译器是否能够缓存计算值，我实施了三种可能性并对其进行了基准测试：

直接最小值实现
首先计算 f(.) 个值的数组后的最小计算
一个特定的min_element函数，以单一函数作为参数

输出：

min = 9193
distance = 120
822913 micro-s

New version:
min = 9193
distance = 120
425393 micro-s

With rewriting of min_element function:
min = 9193
distance = 120
416941 micro-s

第二个版本有效地带来了真正的速度提升。

第三个版本只带来了一点点速度提升，但是有避免的好处使用的内存增加。

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

const int param = 10000;
const int N = 10000;

int slowF (int x) {
    int y = x;
    for (int i = 0; i < param; ++i) {
        y = y*y % N;
    }
    return y+2;
}


template<typename T, class ForwardIt, class Funct>
ForwardIt min_element_fct(ForwardIt first, ForwardIt last, Funct f)
{
    if (first == last) return last;
 
    ForwardIt smallest = first;
    T val_smallest = f(*first);
    ++first;
    for (; first != last; ++first) {
        T val;
        if ((val=f(*first)) < val_smallest) {
            smallest = first;
            val_smallest = val;
        }
    }
    return smallest;
}

int main() {
    std::vector<int> v(N);
    v[0] = N/2 - 7;
    for (int i = 1; i < N; ++i) v[i] = (13*v[i-1] + 27) % N;
    
    auto comp = [] (int a, int b) {return slowF(a) < slowF(b);};
    auto t1 = std::chrono::high_resolution_clock::now();
    auto adr_min = std::min_element (v.begin(), v.end(), comp);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "min = " << *adr_min << std::endl;
    std::cout << "distance = " << std::distance (v.begin(), adr_min) << std::endl;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    std::cout << duration << " micro-s" << std::endl;
    std::cout << "\nNew version: \n";
        
    v[0] = N/2 - 7;
    for (int i = 1; i < N; ++i) v[i] = (13*v[i-1] + 27) % N;
    
    t1 = std::chrono::high_resolution_clock::now();
    std::vector<int> val(N);
    for (int i = 0; i < N; ++i) val[i] = slowF(v[i]);
    
    auto adr_min2 = std::min_element (val.begin(), val.end());
    adr_min = v.begin() + std::distance (val.begin(), adr_min2);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "min = " << *adr_min << std::endl;
    std::cout << "distance = " << std::distance (val.begin(), adr_min2) << std::endl;

    duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    std::cout << duration << " micro-s" << std::endl;   
    
    std::cout << "\nWith rewriting of min_element function: \n";
    
    v[0] = N/2 - 7;
    for (int i = 1; i < N; ++i) v[i] = (13*v[i-1] + 27) % N;
    
    t1 = std::chrono::high_resolution_clock::now();
    
    adr_min = min_element_fct<int> (v.begin(), v.end(), slowF);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "min = " << *adr_min << std::endl;
    std::cout << "distance = " << std::distance (v.begin(), adr_min) << std::endl;

    duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    std::cout << duration << " micro-s" << std::endl;   

    return 0;
}

Answer 4

如果不增加一些运行时开销，替换方法通常不是那么容易实现，而对于 min_element、max_element 等的单个手工制作的解决方案则不会有这些开销。问题是为了记忆，你总是必须知道你应该记忆什么价值。 “最后访问的”在这种情况下并没有真正意义，因为您将始终访问两个元素进行比较。

因此，如果您的记忆仅适用于投影（与比较中的使用方式无关），则需要两个插槽用于缓存 return 值，两个插槽用于保存创建这些参数的参数return 个值和接下来应覆盖的指示。

即使这样可能还不够。我不确定在对 < 的调用中以何种方式存在序列点，但我认为在对 comp(_,_) 函数的调用中没有任何序列点。所以比较 a, b, c 可以使用 comp(f(a), f(b)) 和 comp(f(c), f(a)) 并且可以按 f(a)、f(b)、f(c)、f(a) 的顺序执行。在这里，用两个槽进行记忆是不够的。

已经确定我们不能真正了解比较功能，我们尝试访问它怎么样？那么，我们还有另一个问题。以记忆器的这个简单实现为例。 std::min_element 始终将当前最小值打包在比较的右侧，如果结果为假 (standard quote)，它会保留在那里。

#include <type_traits>
#include <optional>
#include <utility>
#include <algorithm>
#include <iostream>

template<class ArgType, class Func, class Comp>
struct Memoizer {
    Memoizer(Func func, Comp comp) : m_func(std::move(func)), m_comp(std::move(comp)) {}

    [[nodiscard]] constexpr bool operator()(const ArgType &lhs, const ArgType &rhs) {
        if (!m_cache) {
            m_cache = std::invoke(m_func, rhs);
        }

        auto temp = std::invoke(m_func, lhs);

        if (m_comp(temp, *m_cache)) {
            m_cache = std::move(temp);
            return true;
        }
        return false;
    }

    using result_t = std::invoke_result_t<Func, ArgType>;
    Func m_func;
    Comp m_comp;

  private:
    std::optional<result_t> m_cache;
};

template<class ArgType, class Func, class Comp>
auto make_memoizer(Func&& f, Comp&& c) -> Memoizer<ArgType, Func, Comp> {
    return {std::forward<Func>(f), std::forward<Comp>(c)};
}

int main() {
    int arr[] = {2,3,1,5,4};

    auto memo = make_memoizer<int>(std::negate{}, std::less{});

    auto min = std::min_element(std::begin(arr), std::end(arr), memo);
    auto max = std::max_element(std::begin(arr), std::end(arr), memo);

    std::cout << "Min: " << -*min << " (Should be: " << -*std::max_element(std::begin(arr), std::end(arr)) << ")\n";
    std::cout << "Max: " << -*max << " (Should be: " << -*std::min_element(std::begin(arr), std::end(arr)) << ")\n";
}

如您所见，max_element 以相反的方式进行，因此我们得到了错误的结果。现在你可以再次模板化整个事情，在哪种情况下在哪一侧记忆，但这只是一个写得很好的错误邀请，因为你将为错误的算法使用错误的变体。此外，这对 minmax_element 不起作用。在这一点上，为 min_element 和 max_element 编写单独的实现更容易也更安全。

仍然可以选择编写一个迭代器适配器，在第一个 *iter 上调用该函数并将其记忆以供进一步 *iter 调用。但我似乎没有为迭代器的调用方式提供任何保证，因此我不确定我们是否可以保证函数调用尽可能小。

这是记忆迭代器的一个非常简单的实现。您可能应该使用 boost 或类似的库来编写迭代器适配器，否则它们会让人头疼，因为它们必须转发所有内容。

#include <type_traits>
#include <optional>
#include <utility>
#include <algorithm>
#include <iostream>
#include <iterator>

template<class Func, class Iter>
struct MemoIter {
    using result_t = std::invoke_result_t<Func, decltype(*std::declval<Iter>())>;

    using iterator_category = typename std::iterator_traits<Iter>::iterator_category;

    auto operator*() {
        if(!m_cache) {
            m_cache = m_func(*m_iter);
        }
        return *m_cache;
    }

    auto operator++() {
        invalidate_cache();
        ++m_iter;
        return *this;
    }

    auto operator++(int) {
        auto ret = MemoIter(m_iter, invalidate_cache(), m_func);
        ++m_iter;
        return ret;
    }

    MemoIter(Iter iter, Func func) : m_iter(iter), m_func(func) {}
    explicit MemoIter(Iter iter) : MemoIter(iter, {}) {}

    friend bool operator==(const MemoIter& lhs, const MemoIter& rhs) {
        return lhs.m_iter == rhs.m_iter;
    }


    friend bool operator!=(const MemoIter& lhs, const MemoIter& rhs) {
        return lhs.m_iter != rhs.m_iter;
    }


private:
    auto invalidate_cache() {
        auto ret = std::move(m_cache);
        m_cache.reset();
        return ret;
    }
    MemoIter(Iter iter, std::optional<result_t>&& cache, Func func) : m_iter(iter), m_cache(std::move(cache)), m_func(func) {}
    Iter m_iter;
    std::optional<result_t> m_cache;
    Func m_func;

};

int main() {
    int arr[] = {2,3,1,5,4};
    auto begin = MemoIter(std::begin(arr), std::negate<>{});
    auto end = MemoIter(std::end(arr), std::negate<>{});

    auto min = std::min_element(begin, end);
    auto max = std::max_element(begin, end);

    std::cout << "Min: " << *min << " (Should be: " << -*std::max_element(std::begin(arr), std::end(arr)) << ")\n";
    std::cout << "Max: " << *max << " (Should be: " << -*std::min_element(std::begin(arr), std::end(arr)) << ")\n";
}

附录：关于 C++20。标准explicitly specifies投影操作的次数恰好是比较次数的两倍，所以无论是示例实现还是标准都没有给出缓存的可能性。（当然，如果编译器可以证明投影没有副作用，它可以根据 as-if-rule 进行缓存，但这是一个很大的假设）。至于原因：如您所见，记忆并不是那么容易。如果迭代器 return 是某种可能在比较之间无效的代理，您还有更多问题。因此，更频繁地调用投影更通用、更容易且更可预测（您知道对投影的调用次数为 2*range.size() - 1；如果您记忆，它可能取决于您的元素的顺序射程等等）。

使用 STL 算法缓存复杂的比较函数？

Caching for complex comparison functions with STL algorithms?

c++

c++-standard-library