Qt, thread, performance, allocator

Код, на якому заснована ця стаття, знаходиться на стадії розробки, з різними комітами на розгляді у темі «Аллокатор». Зверніть увагу, що код використовує різні функції C++17.

Кілька місяців тому розробники Qt Company працювали над виправленням того, як QHostInfo відправляє результати стороні, що призвело до невеликої оптимізації того, як виділяється пам'ять для аргументів у QMetaCallEvent. Розробники використовують об'єкти цього типу в з'єднаннях сигнал/слот з чергами, і деякий час, проведений у цьому коді, нагадав, що Qt є схема розміщення досить маленьких, недовговічних об'єктів у купі, а також у продуктивності критичного шляху коду.

Тому вони стали запитувати, чи можна розмістити екземпляри QEvent з виділеного пулу пам'яті, використовуючи спеціальний аллокатор.

Трохи статистики

Повторна реалізація QEvent::operator new(size_t)і використання QHash як структура даних гістограми показує, що більшість екземплярів QEvent у невеликому додатку Qt мають розмір всього 24 байти:

using HistogramHash = QHash<size_t, int>;
Q_GLOBAL_STATIC(HistogramHash, histogram);

void *QEvent::operator new(std::size_t size) noexcept
{
    ++(*histogram())[size];
        qDebug() << "QEvent:" << *histogram();
    return ::operator new(size);
}

Роблячи те саме для QObject, отримуємо ширший розкид, але й тут більшість екземплярів невеликі. 16 байт є найпоширенішим розміром.

Це не дивно. Примірник QObject має таблицю віртуальних функцій та d-покажчик на QObjectPrivate, де є всі реальні дані. Підкласи QObject використовують підкласи QObjectPrivate для своїх особистих даних і передають ці приватні екземпляри QObject для зберігання.

Таким чином, екземпляри QEvent і QObject досить малі, і навіть програма виділяє їх цілу купу. Наскільки складно було б реалізувати аллокатор (розподільник) пам'яті, який оптимізований для цих варіантів використання?

Аллокатор загального призначення проти спеціалізованих

За промовчанням global C++ operator new виділяє пам'ять з допомогою malloc(). malloc() - це аллокатор загального призначення, який повинен добре працювати для всіх розмірів, від кількох байтів до кількох гігабайт, тому для кожного виділення він має небагато накладних витрат на ведення бухгалтерського обліку. Існують різні реалізації malloc(), і деякі з них дійсно чудово оптимізують розподіл невеликих об'єктів та інші часті випадки використання. Проте вони все ще є аллокаторами загального призначення, тому їм доводиться приймати рішення під час виконання, які, можливо, не доведеться приймати спеціалізованому розподільнику.

Спеціалізовані алокатори зазвичай використовуються в ситуаціях, коли структури даних повинні розподілятися дуже динамічно, а створення та знищення даних мають бути високопродуктивними. Прикладна область, в якій невеликі недовговічні об'єкти часто створюються та руйнуються, є іграми: снаряди в шутері від першої особи – один із прикладів. Інші домени – це графи сцен у движках рендерингу, парсери, які створюють AST, хеш-таблиці. У всіх випадках часто заздалегідь відомо, який розподіл пам'яті знадобиться, також розробники дуже хотіли б скоротити кілька циклів ЦП.

Інша причина, через яку аллокатор може бути цінним, полягає в тому, що деякі платформи, не поставляються з блоком управління пам'яттю. Як нещодавно було оголошено, Qt тепер працює на мікроконтролерах і ці пристрої часто не мають MMU. У таких середовищах фрагментація пам'яті внаслідок частих невеликих виділень може стати серйозною проблемою.

За рахунок попереднього розподілу пам'яті та управління цим пулом способом, оптимізованим для відповідних шаблонів використання, спеціалізований аллокатор може захистити багато службових даних та циклічних звернень ядра. Проблеми фрагментації пам'яті будуть принаймні обмежені цим пулом пам'яті і з меншою ймовірністю впливатимуть на всю систему.

Основні структури даних

Аллокатор пулів Qt повинен дати швидке розподілення та звільнення для різних об'єктів, але зазвичай невеликих розмірів, про які відомо під час компіляції. Аллокатор повинен працювати з пулом пам'яті, досить великим, щоб вимагати дуже рідкісних звернень до ядра. Розподіли та звільнення мають бути можливі у випадковому порядку.

Швидка структура даних управління вільними порціями пам'яті без зайвих витрат - це стек дома: попередньо виділена сторінка пам'яті ділиться на порції однакового розміру, кожна у вузлі, що вказує на попередню порцію. Для виділених вузлів не потрібно знати попередній вузол, тому можна використовувати об'єднання і весь блок для даних користувача. Виділення витягують вузол зі стека, звільнення переміщує вузол назад у стек.

template<size_t ChunkSize>
class PoolAllocator
{
    struct Page
    {
        char memory[4096];
    };

    union Node
    {
         Node *previous;
         char chunk[ChunkSize];
    };
public:
    PoolAllocator()
    {
        initPage(&m_page);
    }
    void *allocate(size_t size)
    {
        Q_ASSERT(size <= ChunkSize);
        if (!stack)
            return nullptr;
        Node *top = stack;
        stack = stack->previous;
        return top->chunk;
    }
    void free(void *ptr)
    {
        Node *top = static_cast<Node*>(ptr);
        top->previous = stack;
        stack = top;
    }

private:
    void initPage(Page *page)
    {
        Node *newStack = reinterpret_cast<Node*>(page->memory);
        newStack->previous = stack;

        const size_t numChunks = sizeof(Page) / sizeof(Node);
        for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
            newStack[1].previous = newStack;
        stack = newStack;
    }

    Node *stack = nullptr;
    Page m_page;
};

Це дає O(1) складність для розподілу та звільнення, і практично 100% ефективності пам'яті. Все, що потрібно зберегти аллокатор - це покажчик на вершину стека (для сторінки пам'яті 4K це означає 8 байтів службової інформації в 64-бітній системі. Це дуже добре!) Але поки аллокатор Qt може працювати тільки з фіксованим обсягом пам'яті.

Замість того, щоб обмежуватися однією сторінкою пам'яті та повертати nullptr, коли вона витрачена, можна було б виділити іншу сторінку та додати шматки у стек. Таким чином, пул пам'яті може збільшуватись настільки, наскільки це необхідно, і не потрібно буде турбуватися про те, щоб зробити пул пам'яті досить великим під час компіляції. Як і раніше, можна буде розміщувати більше ста 40-бітних об'єктів на одній сторінці пам'яті розміром 4 КБ, і, коли потрібно буде зростати, достатньо зробити одне звернення до ядра. Однак тепер необхідно підтримувати вектор покажчиків на сторінках пам'яті, щоб можна було звільняти сторінки під час руйнування аллокатора.

template<size_t ChunkSize>
class PoolAllocator
{
    struct Page
    {
        char memory[4096];
    };

    union Node
    {
         Node *previous;
         char chunk[ChunkSize];
    };
public:
    PoolAllocator()
    {
    }
    ~PoolAllocator()
    {
        for (auto page : pages)
            ::free(page);
    }
    void *allocate(size_t size)
    {
        Q_ASSERT(size <= ChunkSize);
        if (!stack && !grow())
            return nullptr;
        Node *top = stack;
        stack = stack->previous;
        return top->chunk;
    }
    void free(void *ptr)
    {
        Node *top = static_cast<Node*>(ptr);
        top->previous = stack;
        stack = top;
    }

private:
    bool grow()
    {
        Page *newPage = static_cast<Page*>(::malloc(sizeof(Page)));
        if (!newPage)
            return false;
        initPage(newPage);
        pages.append(newPage);
        return true;
    }
    void initPage(Page *page)
    {
        Node *newStack = reinterpret_cast<Node*>(page->memory);
        newStack->previous = stack;

        const size_t numChunks = sizeof(Page) / sizeof(Node);
        for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
            newStack[1].previous = newStack;
        stack = newStack;
    }

    Node *stack = nullptr;
    QVector<Page*> pages;
};

Тепер аллокатор може збільшуватись по одній сторінці за раз до необхідного розміру.

Бенчмаркінг

Є основний аллокатор пулів як клас шаблону, створений з використанням розміру фрагмента даних. Це дозволяє компілятор генерувати дуже ефективний код. Як це швидко насправді? Тривіальний бенчмарк просто розподіляє та звільняє пам'ять у циклі. Необхідно оптимізувати роботу з невеликими об'єктами, тому потрібно порівняти швидкість для 16, 32 і 64 байтів пам'яті, виділити 100, 200 та 400 блоків за раз, а потім звільнити ці блоки у два цикли, звільнивши спочатку непарні, а потім парні індекси. Щоб отримати досить стабільні та порівняні результати запускаємо 250 000 ітерацій.

void *pointers[allocations];
    QBENCHMARK {
        for (int i = 0; i < 250000; ++i) {
            for (int j = 0; j < allocations; ++j)
                pointers[j] = ::malloc(allocSize);
            for (int j = 0; j < allocations; j += 2)
                ::free(pointers[j]);
            for (int j = 1; j < allocations; j += 2)
                ::free(pointers[j]);
        }
    }

Алокатори, які порівнюються, є реалізаціями malloc за замовчуванням на настільних платформах – macOS 10.14 (платформа розробника), Windows 10 з VC++17 та система malloc у Linux (Ubuntu 18.04, яка використовує ptmalloc2). У Linux також порівнювалися Google tcmalloc, Microsoft mimalloc та jemalloc з FreeBSD та Firefox. Тривіально використовувати ці алокатори замість malloc () з glibc в Linux, де вони можуть бути просто LD_PRELOAD.

$ LD_PRELOAD=LD_PRELOAD=/usr/local/lib/libtcmalloc.so ./tst_bench_allocator

Ці результати досить перспективні:

Усі алокатори мають досить стабільну поведінку для цього тесту. Розмір виділеного блоку навряд чи має значення, а подвоєння кількості виділень займає вдвічі більше.

Враховуючи простоту реалізації, не дивно, що спеціалізований аллокатор пулів Qt перевершує навіть найшвидші алокатори загального призначення у 3 рази порівняно з mimalloc та у 70 разів у порівнянні з системним malloc у macOS 10.14.

Багатопотокові моделі

Один з варіантів використання, для якого розробники Qt хочуть спроектувати аллокатор - це виділення QEvent загалом та виділення QMetaCallEvent зокрема. QEvents можуть бути створені з декількох потоків, тому аллокатор повинен бути безпечним. Більш того, QMetaCallEvent використовується для передачі сигналів/слотів між потоками, і події зазвичай можна публікувати на об'єктах різних потоках. Таким чином, потік, який виділяє, не обов'язково буде потоком, що звільняє об'єкт, і потік, який виділений, міг навіть перерватися до того, як об'єкт був оброблений та видалений у потоці, що приймає.

Але, безумовно, будуть випадки, коли клієнтський код може гарантувати, що той самий потік, який виділяє пам'ять, є також потоком, який звільняє цю пам'ять, або коли все відбувається в одному потоці (наприклад, робота з графом сцени). В ідеалі можна створити оптимізовану реалізацію для кожної з цих ситуацій, не дублюючи весь код.

Блокування

Варіанти створення потокового аллокатора є безпечними, якщо ввести блокування або використовувати реалізацію стека без блокувань, використовуючи атомарні інструкції. Атомна реалізація зробить саму реалізацію стека вільного від блокування, але це не допоможе нам рости, коли вичерпаємо стек. З м'ютексом, проте, конкуренція за перегляд буде дуже високою, якщо кілька потоків намагаються виділити та звільнити пам'ять.

Можна зменшити конфлікт блокувань, виділяючи фрагмент даних із вільного стека, але повертаючи фрагмент в інший стек «бэклога». Потім можна використовувати інший м'ютекс для захисту бэклога, коли закінчуються вільні фрагменти даних, можна помінятися місцями в бэклоге. Для цієї операції потрібно тримати обидва м'ютекси.

void *allocate()
{
    auto stack_guard = lock_stack();
    // try to adopt backlog
    if (!stack) {
        auto backlog_guard = lock_backlog();
        stack = backlog;
        backlog = nullptr;
    }
    if (!stack && !grow())
        return nullptr;
    Node *top = stack;
    stack = stack->previous;
    return top->chunk;
}

void free(void *ptr)
{
    auto guard = lock_backlog();
    Node *top = static_cast<Node*>(ptr);
    top->previous = backlog;
    backlog = top;
}

Це трохи допомагає, але виконання цього тесту з кількома потоками швидко показує, що це не може бути успішною стратегією.

Арени

Більш складною архітектурою було б, якби кожен потік працював на своїй власній «arena». Кожен потік повинен мати власний пул пам'яті для роботи, тому будуть деякі накладні витрати. Можна використовувати змінну thread_local для специфічної потоку arena. Час життя arena пов'язані з часом життя потоку з допомогою std::unique_ptr.

private:
    struct Arena
    {
        void push(void *ptr);
        void *pop();
        void grow();
        void initPage();

        QVector<page*> pages;
        Node *stack = nullptr;
    };

    inline thread_local static std::unique_ptr<Arena> current_thread;

    Arena *arena()
    {
        Arena *a = current_thread.get();
        if (!a) {
            a = new Arena;
            current_thread.reset(a);
        }
        return a;
    }

public:
    void *allocate(size_t size)
    {
        Q_ASSERT(size <= ChunkSize);
        Node *node = return arena()->pop();
        return node ? node->chunk : nullptr;
    }
    void free(void *ptr)
    {
        Node *node = static_cast<Node*>(ptr);
        arena()->push(node);
    }

І поки клієнтський код може гарантувати, що пам'ять звільняється тим самим потоком, який її виділив, не потрібно використовувати блокування для синхронізації операцій у стеку арени.

Якщо об'єднати два підходи, то отримаємо аллокатор, в якому кожен потік витягує фрагменти зі своєї власної арени без блокування. Потоки, що звільняють пам'ять, що прийшла з арени іншого потоку, виштовхуватимуть шматки в стек невиконаної роботи вихідної arena, тому вони конкурують тільки з іншими такими ж звільняючими потоками за необхідне блокування. Коли стек вичерпаний, беклог змінюється, але тоді потік, що розподіляє, також повинен буде конкурувати за блокування. Однак потрібно мати можливість відобразити частину пам'яті, яку клієнтський код передає free () на правильну arena, так як більше немає можливості просто використовувати покажчик arena thread_local, інакше отримаємо звільняючий потік, що приймає всю пам'ять з розподільчих потоків. Наявність вказівника на arena для кожного фрагмента пам'яті в стеку була б одним із варіантів, але вносить чимало витрат на розподіл ресурсів. Необхідність записати 8 байт для фрагмента розміром 40 байт означає, що у своїй витрачається 20% пам'яті.

Натомість можна використовувати той факт, що сторінки пам'яті, які виділяють за допомогою mmap(), завжди мають 4K байтове вирівнювання. В адресі сторінки, виділеної за допомогою mmap (або VirtualAlloc у Windows), нижні 12 біт (4096 = 2^12) завжди дорівнюватимуть нулю, тобто 0x123456789abcd000. Адреси фрагментів даних на сторінці будуть мати однакові верхні 52 біти, тому можна застосувати просту бітову маску до адреси фрагмента даних, і отримати адресу сторінки. Потім можна зробити так, щоб сторінка пам'яті містила вказівник на arena, якій вона належить, тому потрібно буде жертвувати лише 8 байт для кожної сторінки 4K.

pivate:
    struct Page
    {
        char memory[4096 - sizeof(Arena*)];
        Arena *arena;

        static Page *fromNode(Node *node)
        {
            return reinterpret_cast<Page*>(uintptr_t(node) & ~(sizeof(Page) - 1));
        }
    };

    struct Arena
    {
        bool grow()
        {
            void *ptr = ::mmap(NULL, sizeof(Page), PROT_READ | PROT_WRITE,
                               MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
            Q_ASSERT_X(!(uintptr_t(ptr) % sizeof(Page)),
                       "PoolAllocator", "Page Alignment Error!");
            if (!ptr)
                return false;

            Page *newPage = static_cast<Page*>(ptr);
            initPage(newPage);
            newPage->arena = this;
            pages.append(newPage);
            return true;
        }
    };

public:
    void *allocate(size_t size)
    {
        Q_ASSERT(size <= ChunkSize);
        Node *node = arena()->pop();
        return node ? node->chunk : nullptr;
    }

    void free(void *ptr)
    {
        Node *node = static_cast<Node*>(ptr);
        Arena *arena = Page::fromNode(node)->arena;
        arena->push(node);
    }

Додаткову складність додає можливість того, що виділення потік завершується, поки об'єкти з його арени ще живі. Для цього потрібно відокремити час життя пула пам'яті від arena (яка за допомогою сховища thread_local пов'язана із часом життя потоку). Аллокатор може подбати про такі застарілі пули пам'яті. Майбутні потоки приймуть їх.

Щоб реалізувати це потрібно з'ясувати, чи є ще виділена пам'ять. Структура даних нічого не знає про виділену пам'ять, тільки про вільну пам'ять. Отже, найшвидший спосіб перевірити - це перебрати весь стек і порахувати, скільки є вузлів. Якщо вузлів менше, ніж уміщується на всіх виділених сторінках, пам'ять все ще використовується.

Порівняння моделей потоків

Отже, тепер є чотири моделі багатопоточності, з різними компромісами щодо продуктивності, накладних витрат пам'яті та паралелізму.

• Однопотоковий (single-threaded), як тривіальний випадок з однієї арени та без блокувань.
• Модель загального пулу (shared pool model), у якій всі потоки працюють на одній arena з двома блокуваннями.
• Модель з кількома пулами (multi-pool model), де кожен потік повинен залишатися в межах своєї власної arena і не потребує будь-яких блокувань.
• Нарешті, багатопотокова модель (multi-threaded model), в якій потоки виділяються зі своєї власної arena, але пам'ять може бути звільнена будь-яким потоком, і потоки можуть завершуватися, поки пам'ять, виділена з їхньої arena, все ще використовується.

У перших трьох моделей буде багато варіантів використання, але для випадку QEvent знадобиться багатопотокова модель.

Виконання попереднього тесту з використанням цих різних реалізацій, але без використання потоків дозволяє виміряти чисті накладні витрати, які представляють різні стратегії:

Здається, що додатковий код, необхідний реалізації стратегії arena, вносить дуже мало накладних витрат. Модель загального пулу, з іншого боку, не матиме великої переваги в порівнянні з простим використанням malloc, хоча вона все ще може бути корисною при розгляді фрагментації пам'яті.

Многопоточний бенчмаркінг

Порівняльний аналіз аллокаторів у реалістичному, багатопотоковому сценарії не простий. Навіть система malloc працює дуже швидко, тому виконання чогось нетривіального, крім виділення та звільнення пам'яті в тесті, ускладнює вимірювання реального впливу аллокатора. Проте, якщо пам'ять лише виділяємо і звільняємо, вплив конкуренції за блокування в аллокаторах стає сильно перебільшеним. З іншого боку, розробникам, можливо, доведеться використовувати примітиви синхронізації, такі, як м'ютекс або умови очікування, для моделювання потоку даних в реалістичних сценаріях виробника/споживача (наприклад, коли Qt використовує QMetaCallEvent для з'єднань сигналу/слота, що перетинають потоки). Це приховуватиме вплив блокувань в аллокаторі.

Тим не менш, відносні числа повинні дати деяке уявлення про те, наскільки ефективний аллокатор Qt, який значно швидше, ніж інші, що перебувають у стані стресу, з великою ймовірністю вплине на продуктивність реального додатка. Грунтуючись на спостереженні з першого тесту, що це алокатори мають однакові характеристики продуктивності, незалежно від цього, наскільки великі об'єкти. Тепер просто запускаємо один тест для 16-байтових об'єктів, але з такою кількістю потоків, як у нас процесорів.

Використовувана тут модель потоків - це повна багатопотокова реалізація, в якій аллокатор Qt, як і раніше, перевершує найшвидшу альтернативу загального призначення в 2,5 рази, а malloc система за замовчуванням відповідає коефіцієнту не менше 7.
У наступній статті розглянемо методи тестування та налагодження пам'яті. Покажемо, як можна використовувати ідеї, розроблені досі при розподілі об'єктів різних розмірів. І, можливо, дізнаємося, як можна звільнити порожні сторінки.