Как упростить математические формулы с помощью макросов ржавчины? - PullRequest
7 голосов
/ 05 апреля 2019

Должен признать, я немного потерян с макросами. Я хочу построить макрос, который выполняет следующую задачу и Я не уверен, как это сделать. Я хочу выполнить скалярное произведение из двух массивов, скажем, х и у, которые имеют одинаковую длину N. Результат, который я хочу вычислить, имеет вид:

z = sum_{i=0}^{N-1} x[i] * y[i].

x - это const, какие элементы 0, 1, or -1 известны во время компиляции, в то время как y элементы определяются во время выполнения. Из-за структура x, многие вычисления бесполезны (термины, умноженные на 0 могут быть удалены из суммы, а умножения вида 1 * y[i], -1 * y[i] могут быть преобразованы в y[i], -y[i] соответственно).

В качестве примера, если x = [-1, 1, 0], скалярное произведение выше будет

z=-1 * y[0] + 1 * y[1] + 0 * y[2]

Чтобы ускорить мои вычисления, я могу развернуть цикл вручную и переписать все это без x[i], и я мог бы жестко кодировать приведенную выше формулу как

z = -y[0] + y[1]

Но эта процедура не элегантна, подвержена ошибкам и очень утомительно, когда N становится большим.

Я почти уверен, что смогу сделать это с помощью макроса, но я не знаю, где начать (разные книги, которые я читаю, не углубляются в макросы и Я застрял) ...

Кто-нибудь из вас знает, как (если это возможно) решить эту проблему с помощью макросов?

Заранее благодарю за помощь!

Редактировать: Как указывалось во многих ответах, компилятор достаточно умен, чтобы удалить цикл оптимизации в случае целых чисел. Я использую не только целые числа, но также и числа с плавающей запятой (массив x - это i32s, но в целом y - это f64 s), поэтому компилятор не достаточно умен (и это справедливо) для оптимизации цикла. Следующий фрагмент кода дает следующий asm.

const X: [i32; 8] = [0, 1, -1, 0, 0, 1, 0, -1];

pub fn dot_x(y: [f64; 8]) -> f64 {
    X.iter().zip(y.iter()).map(|(i, j)| (*i as f64) * j).sum()
}
playground::dot_x:
    xorpd   %xmm0, %xmm0
    movsd   (%rdi), %xmm1
    mulsd   %xmm0, %xmm1
    addsd   %xmm0, %xmm1
    addsd   8(%rdi), %xmm1
    subsd   16(%rdi), %xmm1
    movupd  24(%rdi), %xmm2
    xorpd   %xmm3, %xmm3
    mulpd   %xmm2, %xmm3
    addsd   %xmm3, %xmm1
    unpckhpd    %xmm3, %xmm3
    addsd   %xmm1, %xmm3
    addsd   40(%rdi), %xmm3
    mulsd   48(%rdi), %xmm0
    addsd   %xmm3, %xmm0
    subsd   56(%rdi), %xmm0
    retq

Ответы [ 4 ]

8 голосов
/ 06 апреля 2019

Прежде всего, макрос (proc) может просто не заглядывать внутрь вашего массива x. Все, что он получает, это токены, которые вы передаете, без всякого контекста. Если вы хотите, чтобы он знал о значениях (0, 1, -1), вам нужно передать их непосредственно в ваш макрос:

let result = your_macro!(y, -1, 0, 1, -1);

Но вам не нужен макрос для этого. Компилятор много оптимизирует, как также показано в других ответах. Однако, как вы уже упоминали в своем редактировании, он не будет оптимизировать 0.0 * x[i], в результате чего не всегда 0.0. (Это может быть -0.0 или NaN, например.) Здесь мы можем просто немного помочь оптимизатору, используя match или if, чтобы убедиться, что он ничего не делает для 0.0 * y случай:

const X: [i32; 8] = [0, -1, 0, 0, 0, 0, 1, 0];

fn foobar(y: [f64; 8]) -> f64 {
    let mut sum = 0.0;
    for (&x, &y) in X.iter().zip(&y) {
        if x != 0 {
            sum += x as f64 * y;
        }
    }
    sum
}

В режиме выпуска цикл развернут и значения X встроены, что приводит к выбрасыванию большинства итераций, поскольку они ничего не делают. Единственное, что осталось в полученном двоичном файле (на x86_64), это:

foobar:
 xorpd   xmm0, xmm0
 subsd   xmm0, qword, ptr, [rdi, +, 8]
 addsd   xmm0, qword, ptr, [rdi, +, 48]
 ret

(Как предполагает @ lu-zero, это также можно сделать с помощью filter_map. Это будет выглядеть так: X.iter().zip(&y).filter_map(|(&x, &y)| match x { 0 => None, _ => Some(x as f64 * y) }).sum(), и дает точно такую ​​же сгенерированную сборку. Или даже без match, используя filter и map отдельно: .filter(|(&x, _)| x != 0).map(|(&x, &y)| x as f64 * y).sum().)

Довольно хорошо! Тем не менее, эта функция вычисляет 0.0 - y[1] + y[6], поскольку sum начинается с 0.0, и мы только вычитаем и добавляем к ней вещи. Оптимизатор снова не желает оптимизировать 0.0. Мы можем немного помочь, не начиная с 0.0, а начиная с None:

fn foobar(y: [f64; 8]) -> f64 {
    let mut sum = None;
    for (&x, &y) in X.iter().zip(&y) {
        if x != 0 {
            let p = x as f64 * y;
            sum = Some(sum.map_or(p, |s| s + p));
        }
    }
    sum.unwrap_or(0.0)
}

В результате:

foobar:
 movsd   xmm0, qword, ptr, [rdi, +, 48]
 subsd   xmm0, qword, ptr, [rdi, +, 8]
 ret

Что просто делает y[6] - y[1]. Бинго!

3 голосов
/ 06 апреля 2019

Во многих случаях этап оптимизации компилятора позаботится об этом за вас. Для примера приведем определение этой функции

const X: [i32; 8] = [0, 1, -1, 0, 0, 1, 0, -1];

pub fn dot_x(y: [i32; 8]) -> i32 {
    X.iter().zip(y.iter()).map(|(i, j)| i * j).sum()
}

приводит к выводу этой сборки на x86_64:

playground::dot_x:
    mov eax, dword ptr [rdi + 4]
    sub eax, dword ptr [rdi + 8]
    add eax, dword ptr [rdi + 20]
    sub eax, dword ptr [rdi + 28]
    ret

Вы не сможете получить более оптимизированную версию, чем эта, поэтому простое написание кода - лучшее решение. Неясно, будет ли компилятор развернуть цикл для более длинных векторов, и это может измениться с версиями компилятора.

Для чисел с плавающей запятой компилятор, как правило, не может выполнить все описанные выше оптимизации, поскольку не гарантируется, что числа в y конечны - они также могут быть NaN, inf или -inf. По этой причине умножение на 0.0 не обязательно снова приведет к 0.0, поэтому компилятору необходимо сохранить инструкции умножения в коде. Вы можете явно разрешить ему предполагать, что все числа конечны, используя встроенную функцию fmul_fast():

#![feature(core_intrinsics)]
use std::intrinsics::fmul_fast;

const X: [i32; 8] = [0, 1, -1, 0, 0, 1, 0, -1];

pub fn dot_x(y: [f64; 8]) -> f64 {
    X.iter().zip(y.iter()).map(|(i, j)| unsafe { fmul_fast(*i as f64, *j) }).sum()
}

В результате получается следующий код сборки:

playground::dot_x: # @playground::dot_x
# %bb.0:
    xorpd   xmm1, xmm1
    movsd   xmm0, qword ptr [rdi + 8] # xmm0 = mem[0],zero
    addsd   xmm0, xmm1
    subsd   xmm0, qword ptr [rdi + 16]
    addsd   xmm0, xmm1
    addsd   xmm0, qword ptr [rdi + 40]
    addsd   xmm0, xmm1
    subsd   xmm0, qword ptr [rdi + 56]
    ret

Это все еще избыточно добавляет нули между шагами, но я не ожидаю, что это приведет к каким-либо измеримым накладным расходам для реалистичного моделирования CFD, так как такие моделирования, как правило, ограничиваются пропускной способностью памяти, а не процессором. Если вы также хотите избежать этих дополнений, вам нужно использовать fadd_fast() для дополнений, чтобы компилятор мог оптимизировать дальше:

#![feature(core_intrinsics)]
use std::intrinsics::{fadd_fast, fmul_fast};

const X: [i32; 8] = [0, 1, -1, 0, 0, 1, 0, -1];

pub fn dot_x(y: [f64; 8]) -> f64 {
    let mut result = 0.0;
    for (&i, &j) in X.iter().zip(y.iter()) {
        unsafe { result = fadd_fast(result, fmul_fast(i as f64, j)); }
    }
    result
}

В результате получается следующий код сборки:

playground::dot_x: # @playground::dot_x
# %bb.0:
    movsd   xmm0, qword ptr [rdi + 8] # xmm0 = mem[0],zero
    subsd   xmm0, qword ptr [rdi + 16]
    addsd   xmm0, qword ptr [rdi + 40]
    subsd   xmm0, qword ptr [rdi + 56]
    ret

Как и во всех вариантах, вы должны начать с самой читаемой и поддерживаемой версии кода. Если производительность становится проблемой, вы должны профилировать свой код и найти узкие места. В качестве следующего шага попытайтесь улучшить фундаментальный подход, например, используя алгоритм с лучшей асимптотической сложностью. Только тогда вы должны обратиться к микрооптимизации, подобной той, которую вы предложили в вопросе.

3 голосов
/ 06 апреля 2019

Если вы можете сэкономить #[inline(always)], вероятно, с помощью явного filter_map () должно быть достаточно, чтобы компилятор сделал то, что вы хотите.

3 голосов
/ 06 апреля 2019

Вы можете достичь своей цели с помощью макроса, который возвращает функцию.

Сначала напишите эту функцию без макроса. Этот принимает фиксированное количество параметров.

fn main() {
    println!("Hello, world!");
    let func = gen_sum([1,2,3]);
    println!("{}", func([4,5,6])) // 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
}

fn gen_sum(xs: [i32; 3]) -> impl Fn([i32;3]) -> i32 {
    move |ys| ys[0]*xs[0] + ys[1]*xs[1] + ys[2]*xs[2]
}

Теперь полностью переписайте его, потому что предыдущий дизайн не работает как макрос. Нам пришлось отказаться от массивов фиксированного размера, так как макросы не могут выделить массивы фиксированного размера .

Rust Playground

fn main() {
    let func = gen_sum!(1,2,3);
    println!("{}", func(vec![4,5,6])) // 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
}

#[macro_export]
macro_rules! gen_sum {
    ( $( $x:expr ),* ) => {
        {
            let mut xs = Vec::new();
            $(
                xs.push($x);
            )*
            move |ys:Vec<i32>| {
                if xs.len() != ys.len() {
                    panic!("lengths don't match")
                }
                let mut total = 0;
                for i in 0 as usize .. xs.len() {
                    total += xs[i] * ys[i];
                }
                total
            } 
        }
    };
}

Что это делает / Что оно должно делать

Во время компиляции он генерирует лямбду. Эта лямбда принимает список чисел и умножает его на вектор, который был сгенерирован во время компиляции. Я не думаю, что это было именно то, что вы были после, так как это не оптимизирует нули во время компиляции. Вы могли бы оптимизировать удаление нулей во время компиляции, но вы обязательно понесли бы некоторые затраты во время выполнения, если бы пришлось проверять, где нули были в x, чтобы определить, на какие элементы умножить на y. Вы можете даже сделать этот процесс поиска в постоянное время, используя хэш-сет. Это все еще вероятно не стоит вообще (где я предполагаю, что 0 не так уж часто встречается). Компьютеры лучше делают одну вещь, которая «неэффективна», чем они обнаруживают, что то, что они собираются сделать, это «неэффективно», а затем пропускают эту вещь. Эта абстракция разрушается, когда значительная часть операций, которые они выполняют, «неэффективна»

Последующий

Это стоило того? Это улучшает время выполнения? Я не измерял, но кажется, что понимание и поддержка написанного мной макроса не стоит того, чтобы просто использовать функцию. Написание макроса с нулевой оптимизацией, о которой вы говорили, вероятно, будет еще менее приятным.

...