Почему мой код работает медленнее, когда я удаляю проверки границ?

Я пишу библиотеку линейных алгебр в Rust.

У меня есть функция, чтобы получить ссылку на ячейку матрицы в данной строке и столбце. Эта функция начинается с пары утверждений, что строка и столбец находятся в пределах границ:

#[inline(always)]
pub fn get(&self, row: usize, col: usize) -> &T {
    assert!(col < self.num_cols.as_nat());
    assert!(row < self.num_rows.as_nat());
    unsafe {
        self.get_unchecked(row, col)
    }
}

В тесных циклах я думал, что быстрее пропустить проверку границ, поэтому я предоставляю метод get_unchecked:

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

Причудливая вещь заключается в том, что, когда я использую эти методы для реализации умножения матриц (через итераторы строк и столбцов), мои тесты показывают, что на самом деле это происходит на 33% быстрее, когда я проверяю границы. Почему это происходит?

Я пробовал это на двух разных компьютерах: Linux и другой OSX, и оба показывают эффект.

Полный код в github. Соответствующий файл lib.rs. Интересующие функции:

get в строке 68
get_unchecked в строке 81
next в строке 551
mul в строке 796
matrix_mul (эталон) в строке 1038

Обратите внимание, что я использую номера уровня типа для параметризации моих матриц (с возможностью динамических размеров тоже с помощью фиктивных помеченных типов), поэтому эталон умножает две матрицы 100x100.

UPDATE:

Я значительно упростил код, удалив материал, который не используется непосредственно в эталонном тесте, и удаляет общие параметры. Я также написал реализацию умножения без использования итераторов, и эта версия не вызывает тот же эффект. См. здесь для этой версии кода. Клонирование ветки minimal-performance и работающей cargo bench будет оценивать две разные реализации умножения (обратите внимание, что утверждения закомментированы для начала в этой ветке).

Также следует отметить, что если я изменю функции get*, чтобы возвращать копии данных вместо ссылок (f64 вместо &f64), эффект исчезает (но код немного медленнее по кругу).

Ответ 1

Это не полный ответ, потому что я не тестировал свои претензии, но это могло бы объяснить это. В любом случае, единственный способ узнать наверняка - создать LLVM IR и выход ассемблера. Если вам требуется руководство для LLVM IR, вы можете найти его здесь: http://llvm.org/docs/LangRef.html.

В любом случае, достаточно об этом. Скажем, у вас есть этот код:

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

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

В случае проверки границ в сочетании с жесткой петлей, LLVM делает небольшой трюк. Поскольку нагрузка находится в замкнутом цикле (умножение матрицы) и потому, что результат проверки границ зависит от границ цикла, он удаляет проверку границ из цикла и помещает его вокруг цикла. Другими словами, сам цикл останется неизменным, но с дополнительной проверкой границ.

Другими словами, код точно такой же, с некоторыми незначительными отличиями.

Так что изменилось? Две вещи:

Если у нас есть дополнительная проверка границ, больше нет возможности для загрузки вне пределов. Это может вызвать оптимизацию, которая была невозможна раньше. Тем не менее, учитывая, как эти проверки обычно выполняются, это не будет моим догадкой.
Еще одна вещь, которую следует учитывать, это то, что слово "небезопасно" может вызвать некоторое поведение, например, дополнительное условие, данные о штыре или отключить GC и т.д. Я не уверен в этом точном поведении в Rust; единственный способ узнать эти детали - посмотреть на LLVM IR.