Непредсказуемость динамической памяти

Написал небольшую программу, демонстрирующую непредсказуемую стоимость выделения динамической памяти. Программа выделяет и освобождает N блоков одного размена и измеряет среднее время, затраченное на один вызов malloc() и один вызов free():

#include <functional>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <vector>

/*
 * Get current time reported by the monotonic clock, in seconds.
 */
double get_monotonic_time()
{
    timespec tp = {};
    clock_gettime(CLOCK_MONOTONIC, &tp);
    return double(tp.tv_sec) + double(tp.tv_nsec) / 1000000000.0;
}

/*
 * Measure the duration of `fn()` call, in seconds.
 */
double measure(std::function<void ()> fn)
{
    const double start = get_monotonic_time();
    fn();
    const double stop = get_monotonic_time();

    return stop - start;
}

/*
 * Measure the duration of a single malloc and free when allocating
 * N chunks of M bytes.
 */
void malloc_free(const size_t M, const size_t N)
{
    std::vector<void*> ptrs(N);

    auto malloc_fn = [&]
    {
        for (size_t i = 0; i < N; ++i)
        {
            ptrs[i] = malloc(M);
        }
    };
    printf("malloc %lu\t%.10fs\n", M, measure(malloc_fn) / N);

    auto free_fn = [&]
    {
        for (size_t i = 0; i < N; ++i)
        {
            free(ptrs[i]);
        }
    };
    printf("free   %lu\t%.10fs\n", M, measure(free_fn) / N);
}

int main()
{
    for (size_t i = 4; i <= 1024; i *= 2)
    {
        malloc_free(i, 1000000);
    }

    return 0;
}

Запускаем и видим вполне ожидаемую картину: выделение памяти стоит копейки, выделение маленьких блоков дешевле… Ничего особенного:

➜  taskset -c 0 ./bazel-bin/malloc_free
malloc 4        0.0000000545s
free   4        0.0000000214s
malloc 8        0.0000000328s
free   8        0.0000000172s
malloc 16       0.0000000263s
free   16       0.0000000150s
malloc 32       0.0000000267s
free   32       0.0000000142s
malloc 64       0.0000000347s
free   64       0.0000000166s
malloc 128      0.0000000464s
free   128      0.0000000354s
malloc 256      0.0000000725s
free   256      0.0000000487s
malloc 512      0.0000001146s
free   512      0.0000000621s
malloc 1024     0.0000002077s
free   1024     0.0000000791s

Однако если изменить main() как показано ниже, то получается совсем другая картина:

int main()
{
    malloc_free(4, 10000000);
    malloc_free(1024, 1);

    return 0;
}

➜  taskset -c 0 ./bazel-bin/malloc_free
malloc 4        0.0000000343s
free   4        0.0000000138s
malloc 1024     0.0512933510s
free   1024     0.0000010190s

Выделение одного блока на 1024 байт заняло 51 миллисекунду - более чем в 200000 раз дольше, чем среднее время выше. Почему так получается? Если вкратце, то glibc оптимизирует выделение блоков меньшего размера, откладывая более дорогие манипуляции с памятью до тех пор, пока не будет выделен блок памяти покрупнее. В сценарии выше, вызов, выделяющий 1024 байт, вынужден также выполнять работу отложенную 10000000 вызовами free() “на потом”.

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