Быстрый кэш на C/C++, потокобезопасность

Сравнительное тестирование многопоточных кэшей реализованных на C/C++ и описание как устроен LRU/MRU кэш серии O(n)Cache**RU


За десятки лет было разработано множество алгоритмов кэширования: LRU, MRU, ARC, и другие…. Однако когда понадобился кэш для многопоточной работы, гугление на эту тему дало полтора варианта, а вопрос на StackOverflow вообще остался без ответа. Нашел решение от Facebook которое опирается на потокобезопасные контейнеры репозитория Intel TBB. У последнего также есть многопоточный LRU кеш пока ещё в стадии бета-тестирования и поэтому для его использования требуется явно указать в проекте:


#define TBB_PREVIEW_CONCURRENT_LRU_CACHE true

Иначе компилятор покажет ошибку так как в Intel TBB коде стоит проверка:


#if ! TBB_PREVIEW_CONCURRENT_LRU_CACHE
    #error Set TBB_PREVIEW_CONCURRENT_LRU_CACHE to include concurrent_lru_cache.h
#endif

Захотелось как-то сравнить производительность кэшей — какой выбрать? Или написать свой? Ранее, когда сравнивал однопоточные кэши (ссылка), получил предложения попробовать в других условиях с другими ключами и понял, что требуется более удобный расширяемый стенд для тестирования. Для того, чтобы было удобнее добавлять в тесты конкурирующие алгоритмы, решил оборачивать их в стандартный интерфейс:


class IAlgorithmTester  {
 public:
  IAlgorithmTester()  =  default;
  virtual ~IAlgorithmTester()  {  }
  virtual void  onStart(std::shared_ptr<IConfig>  &cfg)  =  0;
  virtual void  onStop()  =  0;
  virtual void  insert(void  *elem)  =  0;
  virtual bool  exist(void  *elem)  =  0;
  virtual const char *  get_algorithm_name()  =  0;
 private:
  IAlgorithmTester(const  IAlgorithmTester&)  =  delete;
  IAlgorithmTester& operator=(const  IAlgorithmTester&)  =  delete;
};

Аналогично в интерфейсы обвёрнуты: работа с операционной системой, получение настроек, тест-кейсы и др. Исходники выложены в репозиторий. Сейчас на стенде два тест-кейса: вставка/поиск до 1000000 элементов с ключом из случайно сгенерированных чисел и до 100000 элементов со строковым ключом (берётся из 10Мб строк wiki.train.tokens). Для оценки времени выполнения каждый тестируемый кэш сперва прогревается на целевой объем без временных замеров, затем семафор спускает с цепи потоки по добавлению и поиску данных. Количество потоков и настройки тест-кейсов задаются в assets/settings.json. Пошаговые инструкции по компиляции и описание JSON настроек описано в WiKi репозитория. Время засекается с момента спуска семафора и до остановки последней нити. Вот что получилось:


Тест-кейс1 — ключ в виде массива случайных чисел uint64_t keyArray[3]:


TestCase1.Nthread


Тест-кейс2 — ключ в виде строки:


TestCase2.Nthread


Обратите внимание на то что объём вставляемых/искомых данных на каждом шаге тест-кейса увеличивается в 10 раз. Затем время, которое ушло на обработку очередного объёма, я делю соответственно на 10, 100, 1000… Если алгоритм по временной сложности ведёт себя как O(n), то график времени будет оставаться примерно параллельным оси Х. Дальше раскрою сакральные знания, как удалось получить 3-5 кратное превосходство над кешем Facebook в алгоритмах серии O(n)Cache**RU при работе со строковым ключом:


  1. Хеш функция вместо того, чтобы считать каждую букву строки, просто кастит указатель на данные строки к uint64_t keyArray[3] и считает сумму целых чисел. То есть работает подобно передаче "Угадай мелодию" — а я угадаю мелодию по 3 нотам… 3 * 8 = 24 буквам если латиница, и это уже позволяет достаточно хорошо раскидать строки по хэш-корзинам. Да, в хэш-корзине может собраться много строк, и тут начинает давать ускорение алгоритм:
  2. Skip List в каждой корзине позволяет быстро двигаться скачками сперва по различающимся хэшам (id корзины = хэш % количество корзин, поэтому в одной корзине могут появиться разные хэши), затем в рамках одного хэша по вершинам:
    skip
  3. Узлы в которых хранятся ключи и данные берутся из предварительно аллоцированного массива узлов, количество узлов совпадает с ёмкостью кэша. Atomic идентификатор указывает, какой узел брать следующим — если доходит до конца пула узлов, то начинает с 0 = так аллокатор ходит по кругу перезатирая старые узлы (LRU кэш в OnCacheMLRU).

Для случая, когда необходимо, чтобы в кэше сохранялись самые популярные в поисковых запросах элементы, создан второй класс OnCacheMMRU, алгоритм следующий: в конструктор класса кроме ёмкости кэша передаётся вторым параметром uint32_t uselessness граница популярности — если количество поисковых запросов возжелавших текущий узел из циклического пула меньше границы uselessness, то узел переиспользуется под следующую операцию вставки (будет evicted). Если на данном круге популярность узла (std::atomic<uint32_t> used { 0 }) высока, то в момент запроса аллокатора из циклического пула узел сможет выжить, но счётчик популярности будет сброшен в 0. Так узел будет существовать ещё один круг прохода аллокатора по пулу узлов и получит шанс снова набрать популярность, чтобы продолжить существование. То есть это смесь алгоритмов MRU (где самые популярные зависают в кэше навечно) и MQ (где отслеживается время жизни). Кэш постоянно обновляется и при этом работает очень быстро — вместо 10 серверов можно будет поставить 1..


По-крупному алгоритм кэширования тратит время на следующее:


  1. Поддержание инфраструктуры кэша (контейнеры, аллокаторы, отслеживание времени жизни и популярности элементов)
  2. Расчёт хэша и операции сравнения ключа при добавлении/поиске данных
  3. Алгоритмы поиска: Red-Black Tree, Hash Table, Skip List, ...

Требовалось просто уменьшить время работы каждого из этих пунктов, учитывая тот факт, что максимально простой алгоритм оказывается по временной сложности зачастую максимально эффективным, так как любая логика занимает такты CPU. То есть что бы Вы ни написали — это операции, которые должны окупиться во времени в сравнении с методом простого перебора: пока происходит вызов очередной функции, перебор успеет пройти ещё сотню-другую узлов. В этом свете многопоточные кэши будут всегда проигрывать однопоточным, так как защита корзин через std::shared_mutex и узлов через std::atomic_flag in_use — это не бесплатно. Поэтому для выдачи на сервере я использую однопоточный кэш OnCacheSMRU в главном потоке Epoll сервера (в параллельные рабочие потоки вынесены только длительные операции по работе с СУБД, диском, криптография). Для сравнительной оценки используется однопоточный вариант тест-кейсов:


Тест-кейс1 — ключ в виде массива случайных чисел uint64_t keyArray[3]:


TestCase1.1thread


Тест-кейс2 — ключ в виде строки:


TestCase2.1thread


В завершение хочу рассказать, чего ещё интересного можно извлечь из исходников тестового стенда:


  • Библиотека парсинга JSON, состоящая из одного файла specjson.h — маленький простой быстрый алгоритм для тех, кто не хочет тащить в свой проект несколько мегабайт чужого кода ради того, чтобы распарсить файл настроек или входящие JSON известного формата.
  • Подход с инжектированием реализации платформенно-зависимых операций в виде ( class LinuxSystem: public ISystem {… } ) вместо традиционного ( #ifdef _WIN32 ). Так удобнее оборачивать, например, семафоры, работу с динамически подключаемыми библиотеками, сервисами — в классах только код и заголовки от конкретной операционной системы. Если нужна другая операционная система — инжектируешь другую реализацию (class WindowsSystem: public ISystem {… } ).
  • Стенд собирается CMake — проект CMakeLists.txt удобно открывать в Qt Creator или Microsoft Visual Studio 2017. Работа с проектом через CmakeLists.txt позволяет автоматизировать некоторые подготовительные операции — например скопировать файлы тест-кейсов и настроечные файлы в инсталляционный каталог:

     # Coping assets (TODO any change&rerun CMake to copy):
     FILE(MAKE_DIRECTORY ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets)
     FILE(GLOB_RECURSE SpecAssets
         ${CMAKE_CURRENT_SOURCE_DIR}/assets/*.*
         ${CMAKE_CURRENT_SOURCE_DIR}/assets/*
     )
     FOREACH(file ${SpecAssets})
         FILE(RELATIVE_PATH
             ITEM_PATH_REL
             ${CMAKE_CURRENT_SOURCE_DIR}/assets
             ${file}
         )
         GET_FILENAME_COMPONENT(dirname ${ITEM_PATH_REL} DIRECTORY)
         FILE(MAKE_DIRECTORY ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets/${dirname})
         FILE(COPY ${file} DESTINATION ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets/${dirname})
     ENDFOREACH()

  • Для тех, кто осваивает новые возможности C++17, это пример работы с std::shared_mutex, std::allocator<std::shared_mutex>, static thread_local в шаблонах (есть нюансы — где аллоцировать?), запуск большого числа тестов в потоках разными способами с замером времени исполнения:

    //Prepare insert threads:
    for (i  = cnt_insert_threads;  i;  --i)  {
      std::promise<InsertResults>  prom;
      fut_insert_results.emplace_back(prom.get_future());
      threads.emplace_back(std::thread (&TestCase2::insert_in_thread,
          this,  curSize,  std::move(prom),  p_tester));
    } // for insert

    //Prepare find threads:
    for (i  = cnt_find_threads;  i;  --i)  {
      std::packaged_task<FindResults(TestCase2  *i, int,  IAlgorithmTester  *)> ta(
            [](TestCase2  *i, int  count,  IAlgorithmTester  *p_tester){
         return i->find_in_thread(count,  p_tester);
      });

      fut_find_results.emplace_back(ta.get_future());
      threads.emplace_back(
        std::thread (std::move(ta),  this,  curSize,  p_tester));
    } // for find

    //Banzai!!!
    auto  start  =  std::chrono::high_resolution_clock::now();
    l_cur_system.get()->signal_semaphore(cnt_find_threads  +  cnt_insert_threads);
    std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));
    auto  end  =  std::chrono::high_resolution_clock::now();

  • Пошаговая инструкция как скомпилировать, настроить и запустить этот тестовый стенд — WiKi.
    Если для удобной Вам операционной системы ещё нет пошаговой инструкции, то буду признателен за вклад в репозиторий за реализацию ISystem и пошаговую инструкцию по компиляции (для WiKi)… Или просто напишите мне — постараюсь найти время, чтобы поднять виртуалку и описать шаги по сборке.
  • +14
  • 6,4k
  • 9
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 9

    +1
    Хеш функция вместо того чтобы считать каждую букву строки, просто кастит указатель на данные строки к uint64_t keyArray[3] и считает сумму целых чисел.

    … и вылетает по ошибке «доступ к невыровненной памяти» на процессоре ARM.
      0
      так компилятор же вполне способен положить строки с выравниванием по 8 байт. Если только специально не размещать их невыровненными, проблем не будет.
        0
        Компилятор-то тут при чем? Строки — это часть стандартной библиотеки. А стандарт не дает никаких гарантий того, что адрес начала строки будет выровнен (в стандарте С++11 это раздел 21.4.7.1 basic_string accessors [string.accessors]).
        Если же вы об ASCIIZ-строках, то да, можно выравнивать их через прагмы, атрибуты или опции компилятора, но зачем?

        ADD: Кроме того, подразумевается, что «быстрый хэш» будет использоваться как библиотека. Требовать от пользователя, чтобы все строки были выровнены на границу 8 байт — это перебор.
          0
          Хм, железке DMA-контроллеру, значит, от меня можно требовать, а автору библиотеки — нет?! Дискриминационненько как-то… ))))
            0
            Ну, например, иногда при парсинге json-файла в целях ускорения работы вместо выделения памяти под каждую найденную строковую константу просто записывается '\0' на месте закрывающей кавычки и используется указатель на адрес начала подстроки. Или, например, схожим образом работает lazy_bdecode в libtorrent (но там используется указатель на начало и длина, по которым в случае необходимости создается std::string). Так что кейс довольно популярный на самом деле.
            0
            во-первых, если говорить именно про std::string, то выравнивание буфера зависит от реализации аллокатора, но едва ли оно будет меньше 8 байт. Во-вторых, речь в статье не о хеш-функции (взятой, судя по всему, от балды), а об алгоритме кеширования. Эти вещи практически невисимы (производительность алгоритма кеширования может падать в случае плохой хеш-функции).
              0
              во-первых, если говорить именно про std::string, то выравнивание буфера зависит от реализации аллокатора, но едва ли оно будет меньше 8 байт.

              Закладываться на особенности конкретной реализации — это прямой путь к большим проблемам в будущем.

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

              В-третьих, об алгоритме я вообще ни слова не сказал.
              Предложенная реализация алгоритма кэширования имеет потенциальный баг, о котором я и сообщаю.
                0

                Друзья,
                спасибо за активную переписку, которая навела меня на понимание сути ваших сомнений.
                Вчера просто утром увидел коммент про проблемы на ARM процессорах (а такие у меня только на телефонах с Android есть), и решил сочетая полезное с полезным поднять стенд для Android (https://github.com/DimaBond174/android_cache — тут пока ещё только заголовок).


                Вот, сегодня утром прочитал комментарии… и отвечаю:
                Поведение ключа будь то числовой, строковый (или по музыке/видео/изображению/неведомому сферическому коню в вакууме) — это не вопрос библиотеки кеширования. Библиотеке кеширования (которая шаблон в одном .h файле) просто требуется от ключа реализация функций inline int compare (...) и inline uint64_t get_hash(...).


                То как ключ себя ведёт со строками — частное личное внутреннее дело ключа и алгоритму кеширования до него дела нет. В частности предложенный расчёт хэш-а строки по uint64_t[3] в файле ikey2.h реализован так что при установке в ключ строки вызывается метод который гарантирует расширение строки до требуемого размера:


                static constexpr int key_ElemNSizeKey_size = 3 * sizeof(uint64_t);
                    void setKey() {
                      len = data.length();
                      if (data.capacity()  <  key_ElemNSizeKey_size)  {
                        data.reserve(key_ElemNSizeKey_size);
                      }
                      key.setKey(data.data());
                    }

                Если по каким-либо причинам компилятор решит оптимизировать расширение строки, то всегда можно сделать memcpy в обнулённый массив uint64_t[3] на минимальное
                из текущего размера строки и key_ElemNSizeKey_size.

                  0
                  Друзья, я протестировал строковые ключи на Android, ARM процессор — всё работает замечательно:

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое