Могут ли компиляторы (особенно rustc) действительно упростить суммирование треугольников, чтобы избежать цикла?Как? - PullRequest
Новая
       27

Могут ли компиляторы (особенно rustc) действительно упростить суммирование треугольников, чтобы избежать цикла?Как?

9 голосов
/ 22 апреля 2019

На странице 322 из Программирование Rust Бланди и Орендорффом это утверждение:

... Rust ... признает, что существует более простой способ суммирования чисел от одного до n: сумма всегда равна n * (n+1) / 2.

Это, конечно, довольно известная эквивалентность, но как ее распознает компилятор? Я предполагаю, что это проходит этап оптимизации LLVM, но LLVM каким-то образом выводит эквивалентность из первых принципов, или он просто имеет некоторый набор «вычислений общего цикла», которые можно упростить до арифметических операций?

1 Ответ

6 голосов
/ 23 апреля 2019

Прежде всего, давайте продемонстрируем, что это действительно происходит.

Начиная с этого кода: 

pub fn sum(start: i32, end: i32) -> i32 {
    let mut result = 0;
    for i in start..end {
        result += i;
    }
    return result;
}

И , компилируя в Release , мы получаем: 

; playground::sum
; Function Attrs: nounwind nonlazybind readnone uwtable
define i32 @_ZN10playground3sum17h41f12649b0533596E(i32 %start1, i32 %end) {
start:
    %0 = icmp slt i32 %start1, %end
    br i1 %0, label %bb5.preheader, label %bb6

bb5.preheader:                                    ; preds = %start
    %1 = xor i32 %start1, -1
    %2 = add i32 %1, %end
    %3 = add i32 %start1, 1
    %4 = mul i32 %2, %3
    %5 = zext i32 %2 to i33
    %6 = add i32 %end, -2
    %7 = sub i32 %6, %start1
    %8 = zext i32 %7 to i33
    %9 = mul i33 %5, %8
    %10 = lshr i33 %9, 1
    %11 = trunc i33 %10 to i32
    %12 = add i32 %4, %start1
    %13 = add i32 %12, %11
    br label %bb6

bb6:                                              ; preds = %bb5.preheader, %start
    %result.0.lcssa = phi i32 [ 0, %start ], [ %13, %bb5.preheader ]
    ret i32 %result.0.lcssa
}

Где мы действительно можем наблюдать, что петли больше нет.

Таким образом, мы проверяем утверждение Бэнди и Орендорфа.

Что касается того, как это происходитНасколько я понимаю, все это происходит в ScalarEvolution.cpp в LLVM.К сожалению, этот файл является чудовищным из 12 000 строк, поэтому навигация по нему немного сложна;тем не менее, главный комментарий намекает на то, что мы должны быть в нужном месте, и указывает на документы, которые он использовал, в которых упоминаются оптимизирующие циклы и функции замкнутой формы 1 : 

 //===----------------------------------------------------------------------===//
 //
 // There are several good references for the techniques used in this analysis.
 //
 //  Chains of recurrences -- a method to expedite the evaluation
 //  of closed-form functions
 //  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
 //
 //  On computational properties of chains of recurrences
 //  Eugene V. Zima
 //
 //  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
 //  Robert A. van Engelen
 //
 //  Efficient Symbolic Analysis for Optimizing Compilers
 //  Robert A. van Engelen
 //
 //  Using the chains of recurrences algebra for data dependence testing and
 //  induction variable substitution
 //  MS Thesis, Johnie Birch
 //
 //===----------------------------------------------------------------------===//

Согласно эта статья блога , написанная Кристером Вальфридссоном, создает цепочек повторений , которые можно использовать для получения формулы замкнутой формы для каждой индуктивной переменной.

Этосередина между полным рассуждением и полным жестким кодированием:

  • Сопоставление с образцом используется для построения цепочек повторения, поэтому LLVM может не распознавать все способы выражения определенного вычисления.
  • Можно оптимизировать большое количество формул, а не только сумму треугольника.

В статье также отмечается, что оптимизация может привести к пессимизации кода: небольшое количество итераций может быть быстрее, если "оптимизированный код требует большего числа операций по сравнению с внутренним телом цикла.

1 n * (n+1) / 2 - это закрытый фувычисление суммы чисел в [0, n].

...