Структуры данных на практике. Глава 4: Массивы и локальность кэша

[DSSilver]

Статья на хорошую тему, спасибо за перевод! Но отмечу, что чертовски неудобно, что авторы скопировали выдачу LLM один к одному. Последняя итерация что DeepSeek, что chatGPT без персонализации объясняет хуже предыдущих. И эту выдачу по-хорошему нужно дополнительно насыщать пояснениями.

Потому что сейчас, во фрагменте с работой с кэшем - это просто нечитаемый набор разрозненных шагов, которые процесс, ну вот так, по чесноку, описывает плохо

[hard2018]

Что то конфигурации не увидел, какие размеры кэшей используются.
И кэш используется не монопольно одной задачей, каким образом сказывается этот оверхэд.

[Deosis]

Проблема: в каждой линии кэша содержатся ненужные нам данные (mass, id). Мы используем всего 24 байта из 64 (37,5%).

А даже если бы использовали все поля, то задействовали только 32 байта из 64. Вторая половина линии кеша вообще не используется.

[unreal_undead2]

Это если выровнять размер структуры на кеш линии - по умолчанию скорее всего (не скажу про все возможные компиляторы и платформы) в 64байтной кеш линии будут лежать две структуры (и процент 24/64 имеет смысл считать только при случайном доступе).

[Victor89]

Спасибо за статью, для ускорения вычисления умножений матриц еще можно разворачивать массивы (строки 20-38) как показал в примере ниже, это тоже дает небольшой прирост производительности, в моем случае с 960 мс до 718 мс (это примерно на 23% быстрее).

Входные данные для теста были: N = 1024, BLOCK_SIZE = 48

При BLOCK_SIZE = 48 у меня были немного лучше результаты чем при 64 но это уже зависит от конкретной машины где проводятся вычисления.

function mulV3_1(A, B, C, N) {

    const blockSize = 16
    for (let ii = 0; ii < N; ii += BLOCK_SIZE) {
        const iiEnd = Math.min(ii + BLOCK_SIZE, N)
        for (let kk = 0; kk < N; kk += BLOCK_SIZE) {

            const kkEnd = Math.min(kk + BLOCK_SIZE, N)
            for (let jj = 0; jj < N; jj += BLOCK_SIZE) {
                const jjEnd = Math.min(jj + BLOCK_SIZE, N)

                for (let i = ii; i < iiEnd; i++) {
                    const Ci = C[i]
                    const Ai = A[i]
                    for (let k = kk; k < kkEnd; k++) {
                        const r = Ai[k];
                        const Bk = B[k]

                        for (let j = jj; j < jjEnd; j+= blockSize) {
                            Ci[j] += r * Bk[j];
                            Ci[j+1] += r * Bk[j+1];
                            Ci[j+2] += r * Bk[j+2];
                            Ci[j+3] += r * Bk[j+3];

                            Ci[j+4] += r * Bk[j+4];
                            Ci[j+5] += r * Bk[j+5];
                            Ci[j+6] += r * Bk[j+6];
                            Ci[j+7] += r * Bk[j+7];

                            Ci[j+8] += r * Bk[j+8];
                            Ci[j+9] += r * Bk[j+9];
                            Ci[j+10] += r * Bk[j+10];
                            Ci[j+11] += r * Bk[j+11];

                            Ci[j+12] += r * Bk[j+12];
                            Ci[j+13] += r * Bk[j+13];
                            Ci[j+14] += r * Bk[j+14];
                            Ci[j+15] += r * Bk[j+15];
                        }
                    }
                }
            }
        }
    }
}