C++ 中的泛型惰性求值

• 下载 lazy.zip - 1 KB

引言

我花了很长时间为学术目的编写科学计算工具集。出于研究和快速编码的考虑，C# 和 F# 是很棒的实现语言。它们功能强大且速度极快，并且得到了 .NET Framework 的强大支持。并行处理简洁明了，并且有很多免费的数据可视化组件。但过了一段时间，问题出现了。客户愿意订购一款科学分析软件，要求在单次迭代中进行海量向量计算，并且性能是关键要求。因此，我转向了性能的“老将”——C++，以及它新出生的孩子——C++11 标准。一切都很顺利。正如我所料，最棘手的难题是内存分配，因为除了内存泄漏，一系列的 `new` 和 `delete` 操作会引起很大的性能下降。内存重用和预分配非常方便，并且显著降低了运行时间。但总感觉缺少了什么，我心知肚明：**不要**计算那些**不需要**的，并且要**一次**计算，**且仅一次**。

背景

在本文中，为了简单起见，我将使用一个基础示例——`vector` 类，但读者需要意识到更复杂的问题。我第一个 `vector` 类的实现大概是这样的

class vector {
  private:
    float _x, _y;
  public:
    vector(float x, float x) : _x(x), _y(y) { }
    float  get_x() const { return _x; }
    float  get_y() const { return _y; } 
    float  get_length() const { return sqrtf(_x * _x + _y * _y); }
    vector get_unit() const { return *this / get_length(); }
    // Some operator overloading for vector computations.
};   

这是一个简单的实现，但可以看出，存在一个问题：`get_length` 和 `get_unit` 方法在计算过程中可能会为单个向量对象调用多次，因此，它们的值会被反复计算。由于 `vector` 类是不可变的，简单的解决方案是预先计算值。所以，我将 `vector` 类修改如下：

class vector {
  private:
    float _x, _y;
    float _length; 
    vector _unit; 
    void precompute() {
      _length = sqrtf(_x * _x + _y * _y);
      _unit = *this / _length; 
    }  
  public: 
    vector(float x, float y) : _x(x), _y(y) {
      precompute(); 
    }
    float   get_x() const { return _x; }
    float   get_y() const { return _y; }
    float   get_length() const { return _length; }
    vector& get_unit() const { return _unit; }
    // Some operator overloading for vector computations.
}; 

现在它运行起来了，并且好多了。但这里有一个问题：有必要一次性计算所有这些值吗？尤其是在类构造过程？然而，我们如何自动化预计算过程并使代码更整洁呢？

这时，我考虑到了 C# 语言中的**惰性求值**以及 `Lazy` 类。但 C++ 中没有这样的特性，甚至标准模板库（STL）也没有。我在 **boost** 库中找到了一些类似的惰性求值实现，但我选择不为了一个小的功能而使用如此庞大的库，然后，我决定自己实现一个小的库。

惰性求值

我需要一个 .NET `Lazy` 类的等价物，我之前经常使用它，并且我需要它是通用的。我一想，这并不难，我很快就写出了 `lazy` 类。

template<typename T>
class lazy {
  public:
    lazy() : m_initiator(default_initiator), m_initialized(false) { }
    lazy(std::function<T()> initiator) : m_initiator(initiator), m_initialized(false) { }
    T& getValue() {
      if (!m_initialized) {
        m_value = m_initiator();
        m_initialized = true;
      }
      return m_value;
    }
    operator T() {
      return getValue();
    }
    T& operator* () {
      return getValue();
    }
    lazy<T>& operator= (const lazy<T>& other) {
      m_initiator   = other.m_initiator;
      m_initialized = false;
      return *this;
    }
  private:
    static T default_initiator() {
      throw std::runtime_error("No lazy evaluator given.");
    }
    std::function<T()> m_initiator;
    T    m_value;
    bool m_initialized;
}; 

这样，我就可以使用 lambda 表达式作为求值器来定义一个惰性求值变量。

auto pi        = lazy<float>([]() { return 3.141592; });
auto area      = *pi * r * r;
auto perimeter = *pi * 2 * r;  

由于 `area` 被计算了，`pi` 的值并没有被计算。而 `perimeter` 使用了它之前计算过的值，不会再次计算。最后，我用 `lazy` 类简单地重写了 `vector` 类。

class vector {
  private:
    float _x, _y;
    lazy<float>  _length; 
    lazy<vector> _unit; 
    void initialize() {
      _length = lazy<float>([this]() { return sqrtf(_x * _x + _y * _y); });
      _unit   = lazy<vector>([this]() { return *this / _length; });
    }  
  public: 
    vector(float x, float y) : _x(x), _y(y) {
      initialize(); 
    }
    float   get_x() const { return _x; }
    float   get_y() const { return _y; }
    float   get_length()  { return *_length; }
    vector& get_unit()    { return *_unit; }
    // Some operator overloading for vector computations.
};    

请注意，你不能为 `get_length` 和 `get_unit` 方法使用 `const` 关键字，因为它们的值在第一次访问时会发生变化。这非常简洁优美，也是我想要的。我当时觉得自己像个英雄一样自豪，但突然间，我的喜悦并未持续多久。当我尝试用 Visual Studio 的构建工具编译它时，编译器报了一个 `C2079` 错误：‘`lazy`’使用了未定义的类‘`vector`’。

我感到非常困惑。根据我的 C# 背景，一切都做对了，但错误本身并没有提供足够的信息来解决它。

解决方案

我花了些时间与代码搏斗，我非常沮丧。我甚至决定退而求其次，在整个项目中使用最简单的方法。我做了最后的尝试，并抱着希望，在 stackoverflow.com 网站上的一篇文章的提示下找到了问题的根源。你看到了吗？嗯，这并不那么简单。它与变量的栈分配和依赖有关。

在 C++ 中，我非常倾向于静态（栈）分配而不是动态分配，我向你保证，`new` 和 `delete` 是邪恶的。所以，我宁愿将成员变量和类实例定义为自动变量，而不是指针。现在，我们来看看会发生什么。C++ 编译器将自动类实例及其成员作为一个整体分配在栈上，因此，它们在编译时需要类大小（字节）的信息。以 `vector` 类为例，我们来计算它的大小。`vector` 类有四个成员：两个 `float` 类型，一个 `lazy` 类型，以及一个 `lazy` 类型。两个 `float` 类型成员的大小是已知的。对于 `lazy` 类型，我们还需要计算一个通用的 `lazy` 类，并将 `T` 定义为 `float`。这也不是问题。现在，还剩下 `lazy` 类。问题就在这里。`lazy` 的大小取决于 `vector`，反之亦然，`vector` 的大小取决于 `lazy`。所以这里存在一个双重依赖，这会直接导致无限递归。现在很容易理解为什么 C# 和 Java 等语言不会遇到这种问题，因为在托管语言中，类实例始终是引用类型，并且是动态分配的。

当问题明确后，解决方案就很简单了。微软提供的方案是简单地使用指针和动态分配，这意味着更多的 `new` 和 `delete` 操作，而这正是我不想要的。所以我选择了艰难的道路，需要通过打破 `vector` 类来打破其中一个依赖项。以下是结果：

class __vector {
  public: 
    __vector(float x, float y) : m_x(x), m_y(y) { initialize(); } 
    float get_x() const { return m_x; }  
    float get_y() const { return m_y; } 
    float get_length() { return *m_length; } 
    // Some operator overloading for vector computations. 
  private: 
    void initialize() { 
      m_length = lazy<float>([this]() { return sqrtf(m_x * m_x + m_y * m_y); });
    }
    float       m_x, m_y;
    lazy<float> m_length;
};
         
class vector : public __vector {  
  public: 
    vector(float x, float y) : __vector(x, y) { initialize(); }  
    vector get_unit() { return vector(*m_unit); }
    // Some operator overloading for vector computations. 
  private: 
    void initialize() { 
      m_unit = lazy<__vector>([this]() { return *this / get_length(); }); 
    } 
    lazy<__vector> m_unit; 
}; 

现在，`lazy` 和 `vector` 类都依赖于 `__vector` 类来计算它们的大小。这段代码可以成功编译并按预期工作。

嗯，它不如我想要的那么简洁，但它足够简单，可以考虑，特别是当你习惯了它之后。顺便说一下，不要责怪 C++，请记住：不劳无获！

线程安全

上面实现的 `lazy` 类适用于单线程应用程序。为了克服线程安全问题，需要做一些小的改动。这里，我使用了 STL 的 `mutex` 类来控制对私有成员的访问。

lazy<T>& operator= (const lazy<T>& other) { 
  m_lock.lock();
  m_initiator   = other.m_initiator;
  m_initialized = false;
  m_lock.unlock();
  return *this;
} 

T& get_value() {
  if (!m_initialized) {
    m_lock.lock();
    if (!m_initialized) {
      m_value       = m_initiator();
      m_initialized = true;
    }
    m_lock.unlock();
  }
  return m_value;
} 

关注点

永远倾听你的心声。永远不要做你不喜欢或觉得不对的事情。听专业人士的意见，但不要害怕超越陈词滥调。使用开源组件是做事的正确方式，但如果没有摔倒很多次，就学不会走路。这些是让你在成为一名好程序员之后，还能成为一名有价值的程序员的关键。

我希望这篇文章对您有所帮助，但请始终考虑更大的问题。欢迎分享您的观点。批评也备受欢迎。

历史

• 首次撰写于 2013 年 11 月 14 日
• 感谢 Stefan_Lang 于 2013 年 11 月 19 日修复了 bug
• 于 2013 年 11 月 19 日添加了线程安全章节
• 于 2013 年 11 月 20 日修复了一些拼写错误和 bug