Как ускорить эти функции?

#c #optimization #timing

Вопрос:

У меня есть две функции, с которыми я работаю, и я пытаюсь заставить их работать в 4 раза быстрее.

 void get_each_fifth(const matrix_t *matrix, long results[RESULTS_LEN]) {
    for (int i = 0; i < matrix->rows; i  ) {
        for (int j = 0; j < matrix->cols; j  ) {
            int q = j % RESULTS_LEN;
            results[q]  = MGET(matrix, i, j);
        }
    }
}
 

Описанную выше функцию необходимо будет оптимизировать, чтобы она была в 4 раза быстрее. В этой функции я нахожу суммы целых чисел на основе их расположения в матрице. Элементы в столбцах 0, 5, 10 и т.д. переходят в первый элемент массива результатов. Элементы в столбцах 1, 6, 11 и т.д. переходят во второй столбец массива. Этот шаблон сохраняется для остальных столбцов. Подводя итог, цифры в столбце i переходят в элемент i % 5 массива результатов.

 long get_each(const matrix_t *matrix) {
    long sum = 0;
    for (int i = 0; i < matrix->rows; i  ) {
        for (int j = 0; j < matrix->cols; j  ) {
            sum  = MGET(matrix, i, j);
        }
    }
    return sum;
}
 

Это должно быть в 2 раза быстрее; это сумма всех элементов в матрице и возврат результата.

Определены MGET и MSET:

 #define MGET(mat, i, j) ((mat)->data[((i)*((mat)->cols))   (j)])
#define MSET(mat, i, j, x) ((mat)->data[((i)*((mat)->cols))   (j)] = (x)) 
 

и структура matrix_t определена

 typedef struct {
    long rows;
    long cols;
    int *data;
} matrix_t;
 

и наделяется этой функцией:

 void set_up_matrix(matrix_t *matrix, int rows, int cols) {
    if (matrix == NULL) {
        return;
    }
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->data = malloc(sizeof(int) * rows * cols);
    srand(2021);
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < cols; j  ) {
            MSET(matrix, i, j, rand() % 100);
        }
    }
}
 

и результат len определен:

 #define RESULTS_LEN 5
 

Любая помощь будет признательна!

Комментарии:

1. Многие оптимизации зависят от структуры матрицы (например, порядка строк или столбцов), модели памяти машины и набора инструкций, ни одно из которых не включено в вопрос.

2. Модуль либо очень дорогой, либо очень дешевый. Можете ли вы сделать так, чтобы РЕЗУЛЬТАТ был в степени два?

3. как matrix это определяется?

4. Вероятно, у вас есть двойной указатель, matrix который крайне неэффективен.

5. Матрица реализована в виде одного линейного блока памяти, не могли бы вы реализовать большинство (если не все) этих вложенных циклов в виде отдельных циклов, последовательно обращающихся к элементам массива? Компилятор может пропустить эту «оптимизацию».

Ответ №1:

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

 typedef struct {
    size_t rows;
    size_t cols;
    int data[];
} matrix_t;

void get_each_fifth(const matrix_t * restrict matrix, long results[RESULTS_LEN]) 
{
    int (*array)[matrix -> cols] = (int (*)[matrix -> cols])matrix -> data;
    #pragma GCC unroll 10
    for (size_t i = 0; i < matrix->rows; i  ) {
        #pragma GCC unroll 10
        for (size_t j = 0; j < matrix->cols; j  ) {
            size_t q = j % RESULTS_LEN;
            results[q]  = array[i][j];
        }
    }
}

matrix_t *set_up_matrix(matrix_t *matrix, size_t rows, size_t cols) 
{
    int (*array)[cols];
    matrix = realloc(matrix, sizeof(*matrix)   rows * cols * sizeof(matrix -> data[0]));
    if(matrix)
    {
        matrix->rows = rows;
        matrix->cols = cols;
        srand(time(NULL));  // it should be called once in main
        array = (int (*)[cols])matrix -> data;
        for (size_t i = 0; i < rows; i  ) 
        {
            for (size_t j = 0; j < cols; j  ) 
            {
                array[i][j] = rand() % 100;
            }
        }
    }
    return matrix;
}
 

Комментарии:

1. Я не уверен, какова цель matrix параметра in set_up_matrix() . Предполагая, что он указывает на допустимую матрицу, тогда realloc будет сохранен эффективный тип matrix->data int(*)[prev_cols] , с которым, скорее всего, не совместим int(*)[cols] . В результате код, скорее всего, вызывает UB из-за нарушения строгого правила псевдонима.