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

Question

Я пишу библиотеку линейной алгебры в 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, и оба показывают эффект.

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

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

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

UPDATE:

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

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

Answer 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 делает небольшой трюк. Поскольку нагрузка находится в замкнутом цикле (умножение матрицы) и потому, что результат проверки границ зависит от границ цикла, он удаляет проверку границ из цикла и помещает вокруг в цикл. Другими словами, сам цикл останется неизменным, но с дополнительной проверкой границ.

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

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

1. Если у нас есть дополнительная проверка границ, больше нет возможности для загрузки вне пределов. Это может вызвать оптимизацию, которая была невозможна раньше. Тем не менее, учитывая, как эти проверки обычно выполняются, я не думаю.

2. Еще одна вещь, которую следует учитывать, состоит в том, что слово «небезопасное» может вызвать некоторое поведение, например, дополнительное условие, данные о штыре или отключить GC и т. Д. Я не уверен в этом точном поведении в Rust; единственный способ узнать эти детали - посмотреть на LLVM IR.