Можно ли написать быструю функцию InvSqrt () Quake на Rust?
Это просто для удовлетворения моего любопытства.
Есть ли реализация этого:
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}
в Rust? Если он существует, опубликуйте код.
Я попробовал и потерпел неудачу. Я не знаю, как закодировать число с плавающей запятой в целочисленном формате. Вот моя попытка:
fn main() {
println!("Hello, world!");
println!("sqrt1: {}, ",sqrt2(100f64));
}
fn sqrt1(x: f64) -> f64 {
x.sqrt()
}
fn sqrt2(x: f64) -> f64 {
let mut x = x;
let xhalf = 0.5*x;
let mut i = x as i64;
println!("sqrt1: {}, ", i);
i = 0x5f375a86 as i64 - (i>>1);
x = i as f64;
x = x*(1.5f64 - xhalf*x*x);
1.0/x
}
Ссылка:
1. Происхождение Fast InvSqrt() в Quake3 - страница 1
2. Что такое быстрый обратный квадратный корень в Quake
3. БЫСТРЫЙ ОБРАТНЫЙ КВАДРАТНЫЙ КОРНЕЙ.pdf
4. исходный код: q_math.C#L552-L572
3 ответа
Я не знаю, как закодировать число с плавающей запятой в целочисленном формате.
Для этого есть функция: f32::to_bits который возвращает u32. Также есть функция для другого направления: f32::from_bits что требует u32как аргумент. Эти функции предпочтительнееmem::transmute как последний unsafe и сложно использовать.
При этом вот реализация InvSqrt:
fn inv_sqrt(x: f32) -> f32 {
let i = x.to_bits();
let i = 0x5f3759df - (i >> 1);
let y = f32::from_bits(i);
y * (1.5 - 0.5 * x * y * y)
}
Эта функция компилируется в следующую сборку на x86-64:
.LCPI0_0:
.long 3204448256 ; f32 -0.5
.LCPI0_1:
.long 1069547520 ; f32 1.5
example::inv_sqrt:
movd eax, xmm0
shr eax ; i << 1
mov ecx, 1597463007 ; 0x5f3759df
sub ecx, eax ; 0x5f3759df - ...
movd xmm1, ecx
mulss xmm0, dword ptr [rip + .LCPI0_0] ; x *= 0.5
mulss xmm0, xmm1 ; x *= y
mulss xmm0, xmm1 ; x *= y
addss xmm0, dword ptr [rip + .LCPI0_1] ; x += 1.5
mulss xmm0, xmm1 ; x *= y
ret
Я не нашел ни одной эталонной сборки (если есть, скажите, пожалуйста!), Но мне она кажется довольно хорошей. Я просто не уверен, почему поплавок был перемещен вeaxпросто сделать сдвиг и целочисленное вычитание. Может быть, регистры SSE не поддерживают эти операции?
clang 9.0 с -O3компилирует код C в основном в ту же сборку. Так что это хороший знак.
Стоит отметить, что если вы действительно хотите использовать это на практике: пожалуйста, не делайте этого. Как указал benrg в комментариях, современные процессоры x86 имеют специальную инструкцию для этой функции, которая быстрее и точнее, чем этот хак. К сожалению,1.0 / x.sqrt() не похоже, чтобы оптимизировать эту инструкцию. Так что, если вам действительно нужна скорость, используя _mm_rsqrt_psintrinsics, вероятно, лучший вариант. Однако это опять же требуетunsafeкод. Я не буду вдаваться в подробности в этом ответе, так как это действительно понадобится меньшинству программистов.
Этот реализован с помощью менее известных union в Rust:
union FI {
f: f32,
i: i32,
}
fn inv_sqrt(x: f32) -> f32 {
let mut u = FI { f: x };
unsafe {
u.i = 0x5f3759df - (u.i >> 1);
u.f * (1.5 - 0.5 * x * u.f * u.f)
}
}
Сделал несколько микротестов с использованием criterionящик на бокс x86-64 Linux. Удивительно собственный Rustsqrt().recip()самый быстрый. Но, конечно, к любому результату микротеста следует относиться с недоверием.
inv sqrt with transmute time: [1.6605 ns 1.6638 ns 1.6679 ns]
inv sqrt with union time: [1.6543 ns 1.6583 ns 1.6633 ns]
inv sqrt with to and from bits
time: [1.7659 ns 1.7677 ns 1.7697 ns]
inv sqrt with powf time: [7.1037 ns 7.1125 ns 7.1223 ns]
inv sqrt with sqrt then recip
time: [1.5466 ns 1.5488 ns 1.5513 ns]
Вы можете использовать std::mem::transmute чтобы произвести необходимое преобразование:
fn inv_sqrt(x: f32) -> f32 {
let xhalf = 0.5f32 * x;
let mut i: i32 = unsafe { std::mem::transmute(x) };
i = 0x5f3759df - (i >> 1);
let mut res: f32 = unsafe { std::mem::transmute(i) };
res = res * (1.5f32 - xhalf * res * res);
res
}
Живой пример вы можете посмотреть здесь: здесь