Эта статья иллюстрирует т. н. компромисс скорости и памяти — правило, которое выполняется во многих областях CS, — на примере разных реализаций хеш-таблиц на Java. Чем больше памяти занимает хеш-таблица, тем быстрее выполняются операции над ней (например, взятие значения по ключу).
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/c6c/b25/12a/c6cb2512a8eff31783d346a39be52b23.png)
Тестировались хеш-мапы с интовыми ключами и значениями.
Мера использования памяти — относительное количество дополнительно занимаемой памяти сверх теоретического минимума для мапы заданного размера. Например, 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 ускорения не видно. Это происходит потому, что если общий размер мапы превышает вместимость кеша какого-нибудь уровня, кеш-промахи учащаются по мере дальнейшего роста размера мапы. Этот эффект компенсирует теоретический выигрыш от меньшего количества проверяемых слотов.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/41d/c91/4b4/41dc914b41ce54693c26e2e4840e8715.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/9a1/a6b/10f/9a1a6b10f27bb0dd02d92be0a92d4f6e.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/526/ac6/ac6/526ac6ac610e48ed148ad3cba1261135.png)
Обновление довольно похоже на взятие по ключу. Реализация fastutil не тестировалась, потому что в ней нет специального оптимизированного метода для этой операции (по этой же причине некоторые реализации отсутствуют при тестировании других операций).
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/009/a57/ef4/009a57ef463d95b0e7273477b0c19428.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/c51/dea/45a/c51dea45a84ed0be8cbef3dc9f3bd488.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/766/62f/273/76662f2736151746807e276a729274ba.png)
Для замеров этой операции, мапы заполнялись с нуля до целевого размера (1000 — 10 000 000). Перестроения хеш-таблиц не должны были случаться, потому что мапы были инициализированы целевым размером в конструкторах.
На маленьких размерах графики по-прежнему похожи на гиперболы, но у меня нет четкого объяснения такого резкого изменения картинки при переходе к большим размерам и разницы между HFTC и другими примитивными реализациями.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/339/c1d/256/339c1d256cf80f5b42d444468605be3c.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/0fa/f88/175/0faf88175fe3688d77c6f82d1e3fcf24.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/4eb/02a/3b9/4eb02a3b970d74c57f523c20449a2706.png)
Итерация становится медленнее с уменьшением эффективности использования памяти, в отличие от операций по отдельным ключам. Еще интересно, что для всех реализаций с открытым хешированием скорость зависит только от показателя переиспользования памяти, а не теоретической загруженности таблицы, потому что она различается для разных реализаций на одном уровне переиспользования. Также, в отличие от других операций, скорость forEach практически не зависит от размера таблицы.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/262/25d/809/26225d809e9c8710e5d57b526fd3b8cc.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/37a/7fd/b11/37a7fdb116a8846d8293f1225345f8ff.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/6e2/e46/04d/6e2e4604d0bb7b202b1564817578a79d.png)
Скорость внешней итерации пляшет куда больше, чем внутренней, потому что тут больше пространства для оптимизаций (точнее сказать, больше возможностей сделать что-то неоптимально). HFTC и Trove используют собственные интерфейсы, другие реализации — обычный
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/ded/0d3/740/ded0d3740efbb4c93100c9d3095d0313.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/72f/4bf/de8/72f4bfde82c864b07a82a0f0888fbaf1.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/d5e/949/a16/d5e949a169a55d56b51cca770dcdf674.png)
Сырые результаты замеров, по которым были построены картинки в этом посте. Там же, в описании, есть ссылка на код бенчмарков и информация о среде выполнения.
P. S. Эта статья на английском.
![](https://habrastorage.org/getpro/habr/post_images/c6c/b25/12a/c6cb2512a8eff31783d346a39be52b23.png)
Как мерялось
Тестировались хеш-мапы с интовыми ключами и значениями.
Мера использования памяти — относительное количество дополнительно занимаемой памяти сверх теоретического минимума для мапы заданного размера. Например, 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).
Реализации:
- Higher Frequency Trading Collections (HFTC)
- High Performance Primitive Collections (HPPC)
- fastutil collections
- Goldman Sachs Collections (GS)
- Trove Collections
- Mahout Collections
java.util.HashMap
для сравнения. Все остальные реализации — примитивные специализации, аHashMap
боксит значения, поэтому сравнение заведомо нечестное, но тем не менее.
Взятие значения по ключу (успешный поиск)
Только глядя на эти картинки, можно предположить, что HFTC, Trove и Mahout с одной стороны, fastutil, HPPC и GS с другой используют один алгоритм хеширования. (На самом деле это не совсем так.) Более разреженные хеш-таблицы в среднем проверяют меньше слотов, прежде чем найти ключ, поэтому происходит меньше чтений из памяти, поэтому операция выполняется быстрее. Можно заметить, что на маленьких размерах самые разгруженные мапы — они же и самые быстрые для всех шести реализаций, но на больших размерах и при усреднении по всем размерам начиная с показателя переиспользования памяти ~4 ускорения не видно. Это происходит потому, что если общий размер мапы превышает вместимость кеша какого-нибудь уровня, кеш-промахи учащаются по мере дальнейшего роста размера мапы. Этот эффект компенсирует теоретический выигрыш от меньшего количества проверяемых слотов.
![](https://habrastorage.org/getpro/habr/post_images/41d/c91/4b4/41dc914b41ce54693c26e2e4840e8715.png)
![](https://habrastorage.org/getpro/habr/post_images/9a1/a6b/10f/9a1a6b10f27bb0dd02d92be0a92d4f6e.png)
![](https://habrastorage.org/getpro/habr/post_images/526/ac6/ac6/526ac6ac610e48ed148ad3cba1261135.png)
Обновление (инкремент) значения по ключу
Обновление довольно похоже на взятие по ключу. Реализация fastutil не тестировалась, потому что в ней нет специального оптимизированного метода для этой операции (по этой же причине некоторые реализации отсутствуют при тестировании других операций).
![](https://habrastorage.org/getpro/habr/post_images/009/a57/ef4/009a57ef463d95b0e7273477b0c19428.png)
![](https://habrastorage.org/getpro/habr/post_images/c51/dea/45a/c51dea45a84ed0be8cbef3dc9f3bd488.png)
![](https://habrastorage.org/getpro/habr/post_images/766/62f/273/76662f2736151746807e276a729274ba.png)
Запись пары ключ-значение (ключ отсутствовал в мапе)
Для замеров этой операции, мапы заполнялись с нуля до целевого размера (1000 — 10 000 000). Перестроения хеш-таблиц не должны были случаться, потому что мапы были инициализированы целевым размером в конструкторах.
На маленьких размерах графики по-прежнему похожи на гиперболы, но у меня нет четкого объяснения такого резкого изменения картинки при переходе к большим размерам и разницы между HFTC и другими примитивными реализациями.
![](https://habrastorage.org/getpro/habr/post_images/339/c1d/256/339c1d256cf80f5b42d444468605be3c.png)
![](https://habrastorage.org/getpro/habr/post_images/0fa/f88/175/0faf88175fe3688d77c6f82d1e3fcf24.png)
![](https://habrastorage.org/getpro/habr/post_images/4eb/02a/3b9/4eb02a3b970d74c57f523c20449a2706.png)
Внутренняя итерация (forEach)
Итерация становится медленнее с уменьшением эффективности использования памяти, в отличие от операций по отдельным ключам. Еще интересно, что для всех реализаций с открытым хешированием скорость зависит только от показателя переиспользования памяти, а не теоретической загруженности таблицы, потому что она различается для разных реализаций на одном уровне переиспользования. Также, в отличие от других операций, скорость forEach практически не зависит от размера таблицы.
![](https://habrastorage.org/getpro/habr/post_images/262/25d/809/26225d809e9c8710e5d57b526fd3b8cc.png)
![](https://habrastorage.org/getpro/habr/post_images/37a/7fd/b11/37a7fdb116a8846d8293f1225345f8ff.png)
![](https://habrastorage.org/getpro/habr/post_images/6e2/e46/04d/6e2e4604d0bb7b202b1564817578a79d.png)
Внешняя итерация (через итератор или курсор)
Скорость внешней итерации пляшет куда больше, чем внутренней, потому что тут больше пространства для оптимизаций (точнее сказать, больше возможностей сделать что-то неоптимально). HFTC и Trove используют собственные интерфейсы, другие реализации — обычный
java.util.Iterator
.![](https://habrastorage.org/getpro/habr/post_images/ded/0d3/740/ded0d3740efbb4c93100c9d3095d0313.png)
![](https://habrastorage.org/getpro/habr/post_images/72f/4bf/de8/72f4bfde82c864b07a82a0f0888fbaf1.png)
![](https://habrastorage.org/getpro/habr/post_images/d5e/949/a16/d5e949a169a55d56b51cca770dcdf674.png)
Сырые результаты замеров, по которым были построены картинки в этом посте. Там же, в описании, есть ссылка на код бенчмарков и информация о среде выполнения.
P. S. Эта статья на английском.