Информация об изменениях

Сообщение Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад от 13.01.2021 1:19

Изменено 13.01.2021 2:06 xma

Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад
Здравствуйте, watchmaker, Вы писали:

W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.

а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад
Здравствуйте, watchmaker, Вы писали:

W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.

а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..

при n = 1000, sum1 более чем на четверть быстрее sum0

  Скрытый текст 
int op = 0;

int sum0(int n, int* A) {
    int s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int Aij = A[i * n + j]; //op++;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k]; 
                int Aki = A[k * n + i]; //op += 2;
                int v = Ajk < Aki ? Ajk : Aki;
                v = Aij < v ? Aij : v;
                s += v;
            }
        }
    }
    return s;
}

int sum1(int n, int* A) {
    int  s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int Aij = A[i * n + j]; //op++; 
            if (Aij <= 0) continue;
            int Cij = 0;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k]; //op++; 
                if (Aij > Ajk) continue;
                int Aki = A[k * n + i]; //op++; 
                if (Aij > Aki) continue;
                if (Aij < Ajk && Aij < Aki) Cij += 3;
                else if (Aij == Ajk && Aij < Aki) Cij += 2;
                else if (Aij <= Ajk && Aij == Aki) Cij++;
            }
            s += Aij * Cij;
        }
    }
    return s;
}

int sum0_v2(int n, int* A, int *At) {
    int s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int Aij = A[i * n + j]; //op++;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k];
                //int Aki = A[k * n + i]; 
                int Aki = At[k + n * i];
                //op += 2;
                int v = Ajk < Aki ? Ajk : Aki;
                v = Aij < v ? Aij : v;
                s += v;
            }
        }
    }
    return s;
}

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

#include <chrono>
#include <iostream>

int main(int argc, char const* argv[]) {
    enum { n = 1000 };
    int A[n * n];
    int At[n * n];
    srand(time(0));

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            int v = rand() % 1000;
            A[i * n + j] = i == j ? 0 : v;
        }
    }

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            At[j * n + i] = A[i * n + j];
        }
    }

    //for (i = 0;i < n;i++) {
    //    for (j = 0;j < n;j++) printf("%4d", A[i * n + j]);
    //    printf("\n");
    //}

    //printf("sum0=%d", sum0(n, A));printf(" op=%d\n", op);
    //printf("sum1=%d", sum1(n, A));printf(" op=%d\n", op);

    auto start = std::chrono::high_resolution_clock::now();
    int sum = sum0(n, A);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    std::cout << "sum0("<< n << ", A) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";

    start = std::chrono::high_resolution_clock::now();
    sum = sum0_v2(n, A, At);
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "sum0_v2(" << n << ", A, At) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";

    ///*
    start = std::chrono::high_resolution_clock::now();
    sum = sum1(n, A);
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "sum1(" << n << ", A) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";
    //*/

    getchar();

    return 0;
}


W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно

да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицнй) в 12 раз над sum0, (код выше) ..

при n=3000, sum0 — не дождался

P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..