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

Спасибо за статью, для ускорения вычисления умножений матриц еще можно разворачивать массивы (строки 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];
                        }
                    }
                }
            }
        }
    }
}

Black-White Array: новая структура данных с O(log N) аллокаций

Спасибо за статью. Тут отдельное внимание было уделено коллекции памяти но практически ничего не было сказано про выделение памяти и ее уничтожение для черных массивов, если я правильно понимаю они создаются временно при копировании (слияние) одного белого массива в другой + новые данные из черного массива, а это происходит каждую вторую вставку + когда белые массивы переходят на уровни выше тоже выделяется память под новые черные массивы с большими размера и все это нагрузка на сборщик мусора и задержки при выделении памяти. Или я что-то не так понял? Спасибо.