1

假设我有一个 A 类型的对象。对于 A -> A 类型的任何函数考虑这种情况（即获取 A 类型的对象并返回另一个 A 类型的对象）：

foo = func(foo)

在这里，最简单的情况是将 的结果func(foo)复制到foo. 是否有可能对此进行优化，以便：

  • foo就地修改func

使用的语言没有限制。我想知道的是语言必须具有哪些约束和属性才能实现这种优化。是否有任何现有的语言可以执行这种优化？

示例（在伪代码中）：

type Matrix = List<List<int>>

Matrix rotate90Deg(Matrix x):
   Matrix result(x.columns, x.rows) #Assume it has a constructor which takes as args the num of rows, and num of cols.
   for (int i = 0; i < x.rows; i++):
       for (int j = 0; j < x.columns; j++):
           result[i][j] = x[j][i]
   return result

Matrix a = [[1,2,3],[4,5,6],[7,8,9]]
a = rotate90Deg(a)

在这里，是否可以优化代码，使其不为新矩阵（结果）分配内存，而只是修改传递的原始矩阵。

4

2 回答 2

2

首先，您必须意识到某些操作本质上不可能就地计算。矩阵-矩阵乘法就是一个例子，rotate90Deg属于这一类，因为这样的操作实际上是矩阵乘以适当的乘法矩阵。

现在，对于您的示例，您实际上编写了一个矩阵转置函数。矩阵转置可以就地完成，因为您正在交换成对的数字，但我怀疑任何编译器都可以自动检测到这一点并为您优化它。确实，可以做很多很多的技巧来优化矩阵转置，以便缓存友好，从而获得巨大的性能提升。然而，通过一个简单的实现，您几乎肯定会得到与 Aditya Kumar 在他的回答中描述的非常相似的东西。

正如我之前使用“朴素”这个词所预示的那样，程序员可以通过高级模板和其他元编程技术以极其优化的方式诱使编译器内联很多东西。（至少在 C++ 中，可能还有其他允许您重载的语言operator =。）对于任何对如何完成以及所涉及内容的案例研究感兴趣的人，请查看Eigen 矩阵库，以及它如何处理简单的操作就像u = v + w;三个变量都是浮点矩阵一样。以下是关键点的简要概述。

一个简单的实现会重载operator+以返回一个临时operator=文件并将该临时文件复制到结果中。当然，在 C++11 中，很容易通过移动构造函数在赋值期间避免最终复制，但如果你有一些更复杂的东西，右手边有多个运算符，比如u = 3.15f * u.transposed() + 5.0f;因为每个操作符/方法都会返回一个临时值，并且必须循环该临时值才能处理下一个操作符。

长话短说，Eigen 所做的不是在发生相应的函数调用时执行每个操作，而是调用返回一个模板化的函子，它仅描述需要发生的操作，所有实际工作最终都发生在 中operator =，因此使编译器能够发出一个单一的内联循环，用于仅遍历一次数据并真正就地执行操作。

于 2013-07-05T23:56:05.860 回答
1

是的，这是可能的，并且这种优化至少由 C++11（内联）提供。

稍微解释一下优化。

例如

foo_t foo;
foo = func(foo); // #1
foo_t func(foo_t foo1) {
   foo_t new_foo;
   // operate on new_foo by using foo1
   return new_foo;
}

制作的实例有以下三种foo_t：

  1. foo被复制并传递foo1给func
  2. new_foo被建造。
  3. new_foofoo通过复制new_foointo的内容来分配foo；

如果存在一些不变量，则可以消除所有三个副本。

  1. foo（要传递给函数的参数以后永远不会使用相同的原始值。这相当于foo在第 1 行说 that is 'dead'。这是在这里建立的，因为foo是重新分配的。
  2. new_foo函数中对象的范围func有它的生命周期，它不会延长函数的生命周期func。这也是在创建方式时在这里new_foo建立的，它将在堆栈上，并且堆栈中对象的生命周期与创建对象的函数的生命周期相同。

在 C++ 中，可以使用内联函数来实现func。内联后，代码基本上会是这个样子。

`foo_t foo;`
`foo_t new_foo;`
`// operate on new_foo by using foo`
`foo = new_foo;`

虽然，C++ 提供内联作为一种语言特性，但如今几乎所有优化编译器都进行内联。

现在这取决于您执行的操作类型new_foo以及foo这些额外的操作是否new_foo会被优化掉。对于某些数据类型，这是微不足道的（编译器可以执行“复制传播”，然后执行“死代码消除”以new_foo完全删除。

于 2013-07-04T18:37:08.213 回答