Время против памяти на примере хеш-таблиц на Java

    Эта статья иллюстрирует т. н. компромисс скорости и памяти — правило, которое выполняется во многих областях CS, — на примере разных реализаций хеш-таблиц на Java. Чем больше памяти занимает хеш-таблица, тем быстрее выполняются операции над ней (например, взятие значения по ключу).



    Как мерялось


    Тестировались хеш-мапы с интовыми ключами и значениями.

    Мера использования памяти — относительное количество дополнительно занимаемой памяти сверх теоретического минимума для мапы заданного размера. Например, 1000 интовых пар ключ-значение занимают (4 (размер инта) + 4) * 1000 = 8000 байт. Если мапа такого размера занимает 20 000 байт, ее мера использования памяти будет равняться (20 000 — 8000) / 8000 = 1,5.

    Каждая реализация была протестирована на 9 уровнях загруженности (load factors). Каждая реализация на каждом уровне прогонялась на 10 размерах, логарифмически равномерно распределенных между 1000 и 10 000 000. Потом показатели использования памяти и средние времена выполнения операций независимо усреднялись: по трем наименьшим размерам («small sizes» на графиках), трем наибольшим (large sizes) и всем десяти от 1000 до 10 000 000 (all sizes).

    Реализации:


    Взятие значения по ключу (успешный поиск)


    Только глядя на эти картинки, можно предположить, что HFTC, Trove и Mahout с одной стороны, fastutil, HPPC и GS с другой используют один алгоритм хеширования. (На самом деле это не совсем так.) Более разреженные хеш-таблицы в среднем проверяют меньше слотов, прежде чем найти ключ, поэтому происходит меньше чтений из памяти, поэтому операция выполняется быстрее. Можно заметить, что на маленьких размерах самые разгруженные мапы — они же и самые быстрые для всех шести реализаций, но на больших размерах и при усреднении по всем размерам начиная с показателя переиспользования памяти ~4 ускорения не видно. Это происходит потому, что если общий размер мапы превышает вместимость кеша какого-нибудь уровня, кеш-промахи учащаются по мере дальнейшего роста размера мапы. Этот эффект компенсирует теоретический выигрыш от меньшего количества проверяемых слотов.




    Обновление (инкремент) значения по ключу


    Обновление довольно похоже на взятие по ключу. Реализация fastutil не тестировалась, потому что в ней нет специального оптимизированного метода для этой операции (по этой же причине некоторые реализации отсутствуют при тестировании других операций).




    Запись пары ключ-значение (ключ отсутствовал в мапе)


    Для замеров этой операции, мапы заполнялись с нуля до целевого размера (1000 — 10 000 000). Перестроения хеш-таблиц не должны были случаться, потому что мапы были инициализированы целевым размером в конструкторах.

    На маленьких размерах графики по-прежнему похожи на гиперболы, но у меня нет четкого объяснения такого резкого изменения картинки при переходе к большим размерам и разницы между HFTC и другими примитивными реализациями.




    Внутренняя итерация (forEach)


    Итерация становится медленнее с уменьшением эффективности использования памяти, в отличие от операций по отдельным ключам. Еще интересно, что для всех реализаций с открытым хешированием скорость зависит только от показателя переиспользования памяти, а не теоретической загруженности таблицы, потому что она различается для разных реализаций на одном уровне переиспользования. Также, в отличие от других операций, скорость forEach практически не зависит от размера таблицы.




    Внешняя итерация (через итератор или курсор)


    Скорость внешней итерации пляшет куда больше, чем внутренней, потому что тут больше пространства для оптимизаций (точнее сказать, больше возможностей сделать что-то неоптимально). HFTC и Trove используют собственные интерфейсы, другие реализации — обычный java.util.Iterator.






    Сырые результаты замеров, по которым были построены картинки в этом посте. Там же, в описании, есть ссылка на код бенчмарков и информация о среде выполнения.

    P. S. Эта статья на английском.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      +1
      Стало откровением, что forEach только от памяти зависит. Интересно так же, что по всем графикам видно, что hftc самая оптимальная для использования коллекция. Совпадение ли, но Вы и есть автор этих коллекций:)

      Спасибо за статью, обязательно попробую hftc в своем проекте.
        +9
        Это называется ошибкой выжившего. Я пилю эти коллекции больше года, а серьезно быстрее других они стали только пару недель назад. Пока бы не стали, я бы не публиковал эту статью :)
          0
          быстрее других они стали только пару недель назад

          А что случилось пару недель назад, учитывая что последний коммит 3 мес. назад?
            0
            Последний коммит сегодня
              0
              Точно, перепутал с HPPC.
            0
            где можно точно посмотреть сорцы hftc мапы? качать лень, на гитхабе черт ногу сломит ;)
              0
              В репе их по сути нет, только генераторы кода, которые давно прошли точку невозврата по запутанности. Я в таких случаях кидаю зависимость в проект и делаю go-to-definition в Идее.
                0
                Это то я понял. В генераторах лень разбираться. ;) Билдить тоже. Кинь сюда сгенерированный код для метода get() из мапы ;)
                  0
                  LHash? QHash? Тип ключа и значения? Изменяемость мапы (Immutable, Updatable или Mutable)?
                    0
                    Интересует выражение — путь от хэшкода до индекса ;)
                      0
                      Приведу код, который участвует в замерах выше, то есть интовые ключ и значение.

                      На лоадах вплоть до 0,6 используется линейный кеш:
                      UpdatableLHashParallelKVIntIntMapGO#get
                      @Override
                      public int get(int key) {
                          int free;
                          if (key != (free = freeValue)) {
                              long[] tab = table;
                              int capacityMask, index;
                              int cur;
                              long entry;
                              if ((cur = (int) (entry = tab[index = ParallelKVIntKeyMixing.mix(key) & (capacityMask = tab.length - 1)])) == key) {
                                  // key is present
                                  return (int) (entry >>> 32);
                              } else {
                                  if (cur == free) {
                                      // key is absent
                                      return defaultValue();
                                  } else {
                                      while (true) {
                                          index = (index - 1) & capacityMask;
                                          if ((cur = (int) (entry = tab[index])) == key) {
                                              // key is present
                                              return (int) (entry >>> 32);
                                          } else if (cur == free) {
                                              // key is absent
                                              return defaultValue();
                                          }
                                      }
                                  }
                              }
                          } else {
                              // key is absent
                              return defaultValue();
                          }
                      }
                      

                      Где ParallelKVIntKeyMixing это статический внутренний класс, который в данном случае выглядит так:
                      /** = round(2 ^ 32 * (sqrt(5) - 1)), Java form of unsigned 2654435769 */
                      static final int INT_PHI_MAGIC = -1640531527;
                      ...
                      static class ParallelKVIntKeyMixing {
                          static int mix(int key) {
                              int h = key * INT_PHI_MAGIC;
                              return h ^ (h >> 16);
                          }
                      }
                      


                      На лоадах от 0,7 и выше — квадратичный:
                      UpdatableQHashParallelKVIntIntMapGO#get
                      @Override
                      public int get(int key) {
                          int free;
                          if (key != (free = freeValue)) {
                              long[] tab = table;
                              int capacity, index;
                              int cur;
                              long entry;
                              if ((cur = (int) (entry = tab[index = ParallelKVIntKeyMixing.mix(key) % (capacity = tab.length)])) == key) {
                                  // key is present
                                  return (int) (entry >>> 32);
                              } else {
                                  if (cur == free) {
                                      // key is absent
                                      return defaultValue();
                                  } else {
                                      int bIndex = index, fIndex = index, step = 1;
                                      while (true) {
                                          if ((bIndex -= step) < 0) bIndex += capacity;
                                          if ((cur = (int) (entry = tab[bIndex])) == key) {
                                              // key is present
                                              return (int) (entry >>> 32);
                                          } else if (cur == free) {
                                              // key is absent
                                              return defaultValue();
                                          }
                                          int t;
                                          if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                                          if ((cur = (int) (entry = tab[fIndex])) == key) {
                                              // key is present
                                              return (int) (entry >>> 32);
                                          } else if (cur == free) {
                                              // key is absent
                                              return defaultValue();
                                          }
                                          step += 2;
                                      }
                                  }
                              }
                          } else {
                              // key is absent
                              return defaultValue();
                          }
                      }
                      

                      ParallelKVIntKeyMixing тут такой:
                      static class ParallelKVIntKeyMixing {
                          static int mix(int key) {
                              return (key * INT_PHI_MAGIC) & Integer.MAX_VALUE;
                          }
                      }
                      

                        0
                        По первому куску вопросов нет.
                        А во втором — длина таблицы не выводится до степени двойки? Чтобы избавится от '%'.
                          0
                          Так в этом весь смысл. Иначе зачем вообще нужен второй алгоритм. Он работает только с простыми длинами определенного вида. Размер степени двойки не позволяют гарантировать лоад больше 0,5, да и вообще в этом случае лоад слабоуправляем, поэтому для таких конфигураций выбирается второй алгоритм.
                            0
                            Тогда можно поймать «division trolling effect» :)
                            www.youtube.com/watch?v=RGFJjQKChNQ примерно с 50 по 65 минуты ;)
                              0
                              Кстати, на хасвелле каком-нибудь эффект сохраняется?

                              И все-таки QHash в либе не для чистой скорости, а для ультранизкого потребления памяти, которое не достигается ни Trove, ни Mahout, ни тем более всеми остальными.
                                0
                                да, на хасвелле тоже есть. ;)
                                Ну и да — на памяти можно выиграть гораздо больше.
                                0
                                И, кстати, в QHash одно деление на операцию, а не два, как в Trove и Mahout, где обычный двойной хеш.
            0
            «Взятие значения по ключу (успешный поиск)» — это взятие всех ключей в порядке их укладки в мап? Даёт среднее 100 нс?
              0
              Порядок не имеет значения. Только на java.util.HashMap. Посмотрите в сырые результаты, там отклонение неправдоподобное, я чувствую, в замер подмешивается сборка мусора.
              0
              А какую картину даёт сравнение объектных мапов в той же конфигурации?
                0
                Не мерил.
                0
                Основание логарифма ~2.78, а рост таблицы ~x2. Значит для любой из 10 точек может легко получиться разница в 2 раза по памяти из-за разного алгоритма перестроения таблицы.
                  0
                  может легко получиться разница в 2 раза по памяти

                  Разница чего с чем? Не понял. В любом случае, код бенчмарков доступен, если считаете, что есть ошибка в методологии, укажите, или исправьте или перемеряйте.
                    0
                    При заданном количестве элементов и лоад факторе «memory overuse» может легко поменяться в 2 раза, если например сравнивать одну и ту же структуру, но с условиями перестроения (N > threshold) и (N >= threshold).
                    Кроме того, логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.
                    Ещё действительно интересно, что улучшилось в hftc пару недель назад.
                      0
                      Наверное. Но это же проблемы реализаций, а не мои.

                      логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.

                      Целиком эти замеры занимали часов 12, кажется. Для такого насилия мне доступен только один сервер с одной конфигурацией CPU, L2 и L3.

                      что улучшилось в hftc пару недель назад

                      github.com/OpenHFT/hftc/issues/23
                        0
                        А вариант раздельного хранения таблиц оставлен для случая гетерогенных данных или есть случаи, когда он даёт лучшие результаты?
                          0
                          Я таких случаев не нашел. Кстати, int-float и long-double тоже идут в параллель. Есть даже идея адаптировать схему для пар ключ-значение, которые различаются в 2 раза по ширине, например int-long, int-short.
                  0
                  Koloboke нельзя использовать, там критическая дыра в алгоритме, переодически портятся данные: github.com/leventov/Koloboke/issues/66

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

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