Структуры данных на практике. Глава 9: Двоичные деревья поиска

Шаг 1: проверка среднего элемента [40] @ 0x1020 → ПРОМАХ кэша (100 тактов) → CPU получает линию кэша, содержащую [30][40][50][60]Шаг 2: проверка [60] @ 0x1030 → ПОПАДАНИЕ в кэш (1 такт) — уже находится в линии кэша!Шаг 3: проверка [70] @ 0x1038 → ПОПАДАНИЕ в кэш (1 такт) — всё ещё в кэшеВсего: ~102 такта, 1 промах кэша

И тут в примере ошибка. На третьем шаге где мы ищем 70, сказано что мы попадаем в кэш - судя по примеру мы не попадаем в него потому что в первом шаге где мы этот кеш загружали числа 70 нет.

Структуры данных на практике. Глава 9: Двоичные деревья поиска

Благодаря этому становятся эффективными запросы в диапазоне. Если нам нужны «все ключи от 100 до 200», то можно пропускать целые поддеревья, находящиеся вне этого диапазона.

В случае отсортированного массива мы находим 100 при помощи двоичного поиска, а затем выполняем линейное сканирование до 200. Если диапазон большой, это происходит медленнее.

Тут противоречие, тут как раз отсортированный массив отработает быстро и легко, потому что после того как мы нашли 100 нам нужно идти последовательно по массиву до 200, а это значит минимум промахов кэша и префетчинг отрабатывает хорошо.

Структуры данных на практике. Глава 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) аллокаций

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