C - Матрицы как передать по значению?

Я разрабатываю функции обработки матриц для проекта C. Я рассматриваю возможность передачи матриц по значению или по ссылке. Я создал эталонный тест, передающий матрицы по значению и по ссылке, и оба они работают одинаково с флагами оптимизации -O0 и -O2 в gcc. Учитывая, что мой тест может давать неверные результаты, я хотел бы знать, как наиболее эффективно передавать матрицы в вызовы функций и из них, используя только C.

#include <stdio.h>
#include <time.h>

// Compiled on OSX 10.6.8 using: cc -o matrix matrix.c -std=c99 -O2

typedef struct {
    float m0;
    float m1;
    float m2;
    float m3;
    float m4;
    float m5;
    float m6;
    float m7;
    float m8;
    float m9;
    float m10;
    float m11;
    float m12;
    float m13;
    float m14;
    float m15;
} Matrix;

// ================================================
//                 Pass By Value
// ------------------------------------------------

Matrix PassByValue (Matrix a, Matrix b) {
    Matrix matrix;

    matrix.m0  = a.m0 * b.m0  + a.m4 * b.m1  + a.m8  * b.m2  + a.m12 * b.m3;
    matrix.m1  = a.m1 * b.m0  + a.m5 * b.m1  + a.m9  * b.m2  + a.m13 * b.m3;
    matrix.m2  = a.m2 * b.m0  + a.m6 * b.m1  + a.m10 * b.m2  + a.m14 * b.m3;
    matrix.m3  = a.m3 * b.m0  + a.m7 * b.m1  + a.m11 * b.m2  + a.m15 * b.m3;

    matrix.m4  = a.m0 * b.m4  + a.m4 * b.m5  + a.m8  * b.m6  + a.m12 * b.m7;
    matrix.m5  = a.m1 * b.m4  + a.m5 * b.m5  + a.m9  * b.m6  + a.m13 * b.m7;
    matrix.m6  = a.m2 * b.m4  + a.m6 * b.m5  + a.m10 * b.m6  + a.m14 * b.m7;
    matrix.m7  = a.m3 * b.m4  + a.m7 * b.m5  + a.m11 * b.m6  + a.m15 * b.m7;

    matrix.m8  = a.m0 * b.m8  + a.m4 * b.m9  + a.m8  * b.m10 + a.m12 * b.m11;
    matrix.m9  = a.m1 * b.m8  + a.m5 * b.m9  + a.m9  * b.m10 + a.m13 * b.m11;
    matrix.m10 = a.m2 * b.m8  + a.m6 * b.m9  + a.m10 * b.m10 + a.m14 * b.m11;
    matrix.m11 = a.m3 * b.m8  + a.m7 * b.m9  + a.m11 * b.m10 + a.m15 * b.m11;

    matrix.m12 = a.m0 * b.m12 + a.m4 * b.m13 + a.m8  * b.m14 + a.m12 * b.m15;
    matrix.m13 = a.m1 * b.m12 + a.m5 * b.m13 + a.m9  * b.m14 + a.m13 * b.m15;
    matrix.m14 = a.m2 * b.m12 + a.m6 * b.m13 + a.m10 * b.m14 + a.m14 * b.m15;
    matrix.m15 = a.m3 * b.m12 + a.m7 * b.m13 + a.m11 * b.m14 + a.m15 * b.m15;

    return matrix;
}


// ================================================
//               Pass By Reference
// ------------------------------------------------

void PassByReference (Matrix* matrix, Matrix* a, Matrix* b) {
    if (!matrix) return;
    if (!a) return;
    if (!b) return;

    matrix->m0  = a->m0 * b->m0  + a->m4 * b->m1  + a->m8  * b->m2  + a->m12 * b->m3;
    matrix->m1  = a->m1 * b->m0  + a->m5 * b->m1  + a->m9  * b->m2  + a->m13 * b->m3;
    matrix->m2  = a->m2 * b->m0  + a->m6 * b->m1  + a->m10 * b->m2  + a->m14 * b->m3;
    matrix->m3  = a->m3 * b->m0  + a->m7 * b->m1  + a->m11 * b->m2  + a->m15 * b->m3;

    matrix->m4  = a->m0 * b->m4  + a->m4 * b->m5  + a->m8  * b->m6  + a->m12 * b->m7;
    matrix->m5  = a->m1 * b->m4  + a->m5 * b->m5  + a->m9  * b->m6  + a->m13 * b->m7;
    matrix->m6  = a->m2 * b->m4  + a->m6 * b->m5  + a->m10 * b->m6  + a->m14 * b->m7;
    matrix->m7  = a->m3 * b->m4  + a->m7 * b->m5  + a->m11 * b->m6  + a->m15 * b->m7;

    matrix->m8  = a->m0 * b->m8  + a->m4 * b->m9  + a->m8  * b->m10 + a->m12 * b->m11;
    matrix->m9  = a->m1 * b->m8  + a->m5 * b->m9  + a->m9  * b->m10 + a->m13 * b->m11;
    matrix->m10 = a->m2 * b->m8  + a->m6 * b->m9  + a->m10 * b->m10 + a->m14 * b->m11;
    matrix->m11 = a->m3 * b->m8  + a->m7 * b->m9  + a->m11 * b->m10 + a->m15 * b->m11;

    matrix->m12 = a->m0 * b->m12 + a->m4 * b->m13 + a->m8  * b->m14 + a->m12 * b->m15;
    matrix->m13 = a->m1 * b->m12 + a->m5 * b->m13 + a->m9  * b->m14 + a->m13 * b->m15;
    matrix->m14 = a->m2 * b->m12 + a->m6 * b->m13 + a->m10 * b->m14 + a->m14 * b->m15;
    matrix->m15 = a->m3 * b->m12 + a->m7 * b->m13 + a->m11 * b->m14 + a->m15 * b->m15;
}

// ================================================
//                  Benchmark
// ------------------------------------------------

#define LOOPS 100000

int main () {
    Matrix result;
    Matrix a;
    Matrix b;
    clock_t begin;
    clock_t end;
    int index;

    // ------------------------------------------
    //          Pass By Reference
    // ------------------------------------------
    begin = clock();
    for (index = 0; index < LOOPS; index++) {

        PassByReference(&result,&a,&b);
        a.m0 += index;
        b.m0 += index;

    }
    end = clock();
    printf("Pass By Ref: %f\n",(double)(end - begin) / CLOCKS_PER_SEC);

    // ------------------------------------------
    //            Pass By Value
    // ------------------------------------------
    begin = clock();
    for (index = 0; index < LOOPS; index++) {

        result = PassByValue(a,b);
        a.m0 += index;
        b.m0 += index;

    }
    end = clock();
    printf("Pass By Val: %f\n",(double)(end - begin) / CLOCKS_PER_SEC);


    // The following line along with the above
    // additions in the loops hopefully prevent
    // the matrices from being optimized into
    // nothing.
    printf("%0.1f\n",result.m0);

    return 0;
}

Результаты:

Pass By Ref: 0.489226
Pass By Val: 0.488882

person user2221841    schedule 29.03.2013    source источник
comment
Почему бы не использовать массив длиной 16 вместо набора отдельных переменных-членов?   -  person Oliver Charlesworth    schedule 29.03.2013
comment
Отдельные значения в структуре являются обычным шаблоном для матриц из того, что я видел.   -  person Inisheer    schedule 29.03.2013
comment
Я просто впечатлен тем, что ты застрял со Snow Leopard =P   -  person WhozCraig    schedule 29.03.2013
comment
Я обернул значения в структуру для передачи по значению, и в то время я чувствовал, что отдельные значения были чище.   -  person user2221841    schedule 29.03.2013
comment
Передача по указателю или ссылке будет иметь одинаковую производительность, и технически это оптимальный способ сделать это. Никто не передает целые структуры в качестве параметра функции, это очень глупо, вы увидите, что нигде нет функции, делающей это. Если вы хотите сохранить данные структуры от изменения, используйте вместо этого const Matrix*.   -  person Havenard    schedule 29.03.2013
comment
@Havenard Вы должны опубликовать это как ответ, потому что это правильно.   -  person Inisheer    schedule 29.03.2013
comment
Вы все еще можете сделать то же самое с struct Matrix { double m[16]; }, если хотите. это не редкость, когда люди хотят передавать массивы по значению для этого (хотя я настоятельно рекомендую вам согласиться с предложением Хавенарда и использовать const Matrix *).   -  person WhozCraig    schedule 29.03.2013
comment
Рассмотрим трехмерные векторы в программировании. Вы никогда не увидите struct vector { float val[3] };. Вы всегда видите struct vector { float x, float y, flaot z };. Матрица — это определенный стандартизованный тип, как и вектор3. Использование синтаксиса массива почти подразумевает, что размер не является постоянным.   -  person Inisheer    schedule 29.03.2013
comment
@Havenard: ОП сравнивает по значению и по указателю (а не по ссылке, потому что это вопрос C...)   -  person Oliver Charlesworth    schedule 29.03.2013
comment
Пример матрицы: msdn.microsoft.com/en-us /библиотека/   -  person Inisheer    schedule 29.03.2013
comment
@Inisheer: Конечно, в случае 3D переменные имеют хорошо узнаваемые разные имена (хотя я бы сказал, что вы не всегда видите x,y,z вместо массива, это зависит от цели.) Но с 16 переменными , это просто беспорядок. У массива нет недостатков, но есть то преимущество, что вы можете выполнять итерацию, если хотите.   -  person Oliver Charlesworth    schedule 29.03.2013
comment
Хавенард прав, но ваш тест также синхронизирует вычисления, которые, вероятно, перекрывают накладные расходы механизма вызова, тем более что матрица довольно мала, и все данные, вероятно, остались в кеше L1/L2. Просто наблюдение.   -  person rlb    schedule 29.03.2013
comment
какао передает NSRect NSPOint NSSize по значению повсюду.   -  person Grady Player    schedule 29.03.2013


Ответы (4)


у вас есть 2 конкурирующих интереса здесь:

  1. передача структуры по значению, это типизируется как класс хранения данных и помещается в стек в соответствии с соглашением о вызовах x86, это немного медленнее, чем вызов по ссылке, который застревает в регистре.

  2. это почти точно сбалансировано кучей разыменований указателя...

отделить и профилировать каждую часть отдельно

если вы пытаетесь сделать этот код быстрее, вы можете написать более быструю реализацию в каком-то коде SIMD, AltiVec, SSE или OpenCL в зависимости от

person Grady Player    schedule 29.03.2013
comment
Я последовал вашему совету в № 2 и протестировал функцию передачи по указателю, используя массив из 16 чисел с плавающей запятой. Теперь передача по ссылке (которую я, вероятно, должен был назвать передачей по указателю из комментариев) отображается в 3-4 раза быстрее. - person user2221841; 29.03.2013
comment
@user2221841 user2221841 в c++ есть такая вещь, как по ссылке... которая передается по указателю, когда компилятор выполняет за вас волшебное разыменование, но в стандартном C, я думаю, люди обычно понимают, что вы имеете в виду, даже если семантически это не 100 % верный. - person Grady Player; 29.03.2013
comment
Использование вызова icc 13.1 по ссылке опережает вызов по значению прибл. 14%, если вы используете каждое значение матрицы (проверено для размеров до 2048), если вы используете только одно значение, вызов по ссылке на величину лучше (~ 5000%) - person hroptatyr; 29.03.2013
comment
@hroptatyr да, вы ожидаете, что проблема будет усугубляться по мере того, как они становятся больше, поскольку передача по ref в основном bigO 1, а по значению - big O n в лучшем случае ... для фактической конструкции предиката функции ... - person Grady Player; 29.03.2013

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

Я бы предложил использовать передачу по ссылке с модификатором const для любых нескалярных данных. Задача компилятора — оптимизировать ваш код для конкретных платформ.

person Eser Aygün    schedule 29.03.2013

Из эффективного С++:

Предпочитайте передачу по ссылке на константу, а не передачу по значению, как правило, это более эффективно и позволяет избежать проблемы нарезки. Правило не применяется к встроенным типам, итераторам STL и типам объектов-функций. Для них обычно подходит передача по значению.

Я понимаю, что вы программируете на C, а не на C++, но я думаю, что это правило все еще применимо. Причина, по которой ваш пример с этими двумя работает очень близко, может заключаться в том, что структура содержит только число с плавающей запятой и недорога для копирования, поскольку она передается по значению.

Однако, как сказал автор Эффективного С++

некоторые компиляторы отказываются помещать в регистр объекты, состоящие только из двойников, даже если они с радостью помещают туда голые двойники на регулярной основе. Когда такое происходит, вам лучше передавать такие объекты по ссылке, потому что компиляторы обязательно поместят указатели в регистры». Unsubscribe-lgm-thur

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

person Yong Lai    schedule 29.03.2013

Технически у нас есть только «передача по значению» в C. Вы должны передавать указатели матриц (по значению) в функцию. Это уменьшит количество данных, «скопированных» в функцию, и, следовательно, станет более эффективным.

person Bao Bui    schedule 29.03.2013