Dudochkin Victor
Как копирование int сделало мой код в 11 раз быстрее
Перевод | Автор оригинала: Robert Grosse
Недавно, после рефакторинга кода Rust, я заметил, что он внезапно стал в четыре раза медленнее. Однако странно то, что я даже не коснулся той части кода, которая стала медленнее. Более того, после комментирования изменений он все еще был медленнее. Из любопытства я решил продолжить расследование.
Первым шагом было использование git diff для отображения всех изменений с момента предыдущей фиксации, что было нормальной скоростью. Затем я начал удалять их один за другим, какими бы несущественными они ни были, и тестировать, чтобы убедиться, что после внесения изменений все еще было медленным.
В конце концов, я остался с различием только одного оператора печати, добавленного для несвязанных целей отладки, и, конечно же, комментирование оператора печати снова ускорило код. Обратите внимание, что этот оператор печати выполняется только один раз, и это даже не часть медленного кода. Единственное, о чем я мог думать, это то, что это каким-то образом нарушает оптимизацию компилятора, поэтому я решил попытаться свести его к минимальному примеру, чтобы сообщить об ошибке.
В конце концов, я сократил код до следующего:
fn main() {
let size = 1usize << 25; // Adding this line causes program to go from 0.16 seconds to 1.7 seconds
println!("{}", size); let mut ints = vec![0u32; size];
for i in 0..size {
for c in 0..8usize {
ints[(i ^ c) % size] += 1;
}
}
}
Добавление оператора печати приводит к тому, что код увеличивается с 0,16 секунды до 1,7 секунды, то есть замедление в 11 раз (в режиме выпуска). Затем я разместил его на IRC-канале rustc, где eddyb и bluss предложили обходной путь и объяснили, что происходит.
Исправление заключалось в изменении строки печати на следующую, что действительно устраняет замедление.
println!("{}", {size});
{x} объявляет блок операторов, который вычисляет последнее выражение, в данном случае x. Это означает, что {x} совпадает с x с дополнительным перемещением / копией. Обычно это полезно только для обхода неявного повторного заимствования при передаче изменяемых ссылок. Однако здесь нет никаких заемных средств. Все, что он делает, - это копирование простого int, что кажется бесполезным.
Хитрость в том, что, как и все универсальные интерфейсы в Rust, печать принимает аргументы по ссылке, независимо от того, являются они копией или нет. Печать! макрос скрывает это от вас, неявно заимствуя аргументы, что вы можете увидеть, если rustc распечатает расширения макроса (обратите внимание на (&size,). Если вам интересно, вот почему вы можете печатать не копируемые значения без явного заимствования им, в кажущемся нарушении системы собственности.
#![feature(prelude_import)]
#![no_std]
#[prelude_import]
use std::prelude::v1::*;
#[macro_use] extern crate std as std;
fn main() {
let size = 1usize << 25;
// Adding this line causes program to go from 0.16 seconds to 1.7 seconds
::io::_print(::std::fmt::Arguments::new_v1({
static __STATIC_FMTSTR:
&'static [&'static str]
=
&["", "\n"];
__STATIC_FMTSTR
},
&match (&size,) {
(__arg0,) =>
[::std::fmt::ArgumentV1::new(__arg0,
::std::fmt::Display::fmt)],
}));
let mut ints = ::vec::from_elem(0u32, size);
for i in 0..size { for c in 0..8usize { ints[(i ^ c) % size] += 1; } }
}
Передача {size} вместо size предотвращает println! от размера займа. Вместо этого он заимствует временную копию. Однако это все еще не объясняет, как заимствование вызывает такое сильное замедление. Другая половина истории заключается в том, что, хотя Rust знает, что заимствование неизменяемо, эта информация, к сожалению, не передается в LLVM. Это означает, что оптимизатор LLVM видит, что указатель на размер передается некоторой функции, и просто отказывается, оставив следующий код, предполагающий, что размер содержит произвольное значение. Вместо этого заимствование копии позволяет оптимизатору выполнять свою работу.
Вы также можете увидеть это, явно сбросив значение размера после возврата из вызова печати. Это снова делает код быстрым, потому что оптимизатор видит постоянное значение размера.
fn main() {
let mut size = 1usize << 25;
println!("{}", size);
size = 1usize << 25; let mut ints = vec![0u32; size];
for i in 0..size {
for c in 0..8usize {
ints[(i ^ c) % size] += 1;
}
}
}
На этом этапе загадка была раскрыта, но мне было любопытно посмотреть, какие фактические различия в генерации кода вызывали разницу в скорости. Оказывается, можно попросить rustc распечатать и сборку.
rustc -O --emit asm src/main.rs -C llvm-args=-x86-asm-syntax=intel
Определить внутренний цикл в сборке довольно легко, тем более что код в этом примере очень мал. Для оптимизированной версии {size} внутренний цикл выглядит следующим образом.
.LBB0_3:
mov r14d, dword ptr [rbx + 4*rax + 4]
inc rax
.LBB0_2:
inc r14d
mov dword ptr [rbx + 4*rax], r14d
mov rcx, rax
xor rcx, 1
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 2
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 3
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 4
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 5
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 6
inc dword ptr [rbx + 4*rcx]
mov rcx, rax
xor rcx, 7
inc dword ptr [rbx + 4*rcx]
cmp rax, 33554431
jne .LBB0_3
Код практически настолько оптимален, насколько это возможно, если не считать удаления обращений к памяти (оптимизатор теоретически мог бы вычислить, что в этом игрушечном примере для int установлено значение 8, но, к счастью, это не так). В частности, операция% size и проверки границ во внутреннем цикле полностью оптимизированы, а условие внешнего цикла просто сравнивается с константой. Это возможно, потому что оптимизатор понимает, что размер является а) постоянным и б) степенью двойки, и, таким образом, поиск по небольшому значению не выйдет за пределы.
Напротив, соответствующий код для версии размера не оптимизирован, кроме разворачивания цикла. Он выполняет проверку по модулю и границам при каждом доступе, поскольку не знает, какой размер.
.LBB0_6:
xor edx, edx
mov rax, rsi
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 1
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 2
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 3
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 4
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 5
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 6
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc dword ptr [r14 + 4*rdx]
mov rax, rsi
xor rax, 7
xor edx, edx
div rbx
cmp rcx, rdx
jbe .LBB0_7
inc rsi
inc dword ptr [r14 + 4*rdx]
cmp rsi, rbx
jb .LBB0_6
Бонус: непостоянный размер
Увидев приведенный выше код, мне стало любопытно, будет ли оптимизация работать, когда размер - это неизвестная степень двойки. В конце концов, в реальном коде размер часто бывает переменным. Я не мог понять, как заставить rustc печатать красивую сборку при использовании зависимости от внешнего контейнера, поэтому вместо этого я смоделировал параметр opaque с помощью функции extern. Очевидно, это не связано, но для генерации сборки это не имеет значения.
extern {
fn opaque() -> usize;
}fn main() {
let bits = 14 + (unsafe{opaque()} & 15);
let size = 1usize << bits;
println!("{}", {size}); let mut ints = vec![0u32; size];
for i in 0..size {
for c in 0..8usize {
ints[(i ^ c) % size] += 1;
}
}
}
В любом случае, оказывается, что полученный код в основном неоптимизирован, хотя все же лучше, чем в предыдущем случае, когда размер мысли оптимизатора был неизвестен.
.LBB0_2:
mov rsi, rbx
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 1
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 2
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 3
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 4
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 5
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 6
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc dword ptr [r15 + 4*rsi]
mov rsi, rbx
xor rsi, 7
and rsi, r13
cmp r12, rsi
jbe .LBB0_3
inc rbx
inc dword ptr [r15 + 4*rsi]
cmp rbx, r12
jb .LBB0_2
В частности, он по-прежнему проверяет границы и по-прежнему выполняет часть размера %. Однако, по крайней мере, достаточно умен, чтобы выполнять побитовое деление по модулю вместо операции полного деления. С другой стороны, проверка границ далека от идеала. Это заставляет меня задуматься, стоит ли мономорфизировать критический для производительности код, подобный этому, и дублировать его для каждой возможной степени двойки, а затем включать размер для вызова одной из этих функций во время выполнения, чтобы получить полный потенциал оптимизации.