The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Facebook открыл реализацию хэш-таблиц F14

01.05.2019 20:58

Компания Facebook объявила об открытии исходных текстов реализации хэш-таблиц F14, оптимизированной для эффективного потребления памяти. F14 используется в инфраструктуре Facebook в качестве замены большинства типов хэш-таблиц и позволяет снизить потребление памяти без потери производительности. F14 заметно превосходит по производительности хэш-таблицы google::sparse_hash_map, до сих пор считавшиеся наиболее эффективными по потреблению памяти. Код проекта написан на языке C++ и включен в состав библиотеки Folly.

F14 относится к алгоритмам с системой разрешения коллизий на основе двойного хэширования с 14 последовательностями проб (в одной ячейке хэш-таблицы хранится цепочка из 14 слотов, а интервал между ячейками вычисляется при помощи вспомогательной хеш-функции). Для ускорения операций фильтрации ячеек в реализации используются векторные инструкции SSE2 для систем x86_64 и NEON для Aarch64, которые позволяют распараллелить выполнение операций выбора слотов с цепочками ключей и отсеивания ключей внутри цепочки. За раз обрабатываются блоки в 14 слотов, что является оптимальным балансом между эффективностью использования процессорного кэша и числом коллизий.

Особенностью F14 является возможности выбора различных стратегий хранения данных:

  • F14NodeMap - потребляет меньше всего памяти для ключей большого и среднего размера. Обеспечивает косвенное сохранение элементов с вызовом при каждой вставке функции malloc;
  • F14ValueMap - обеспечивает минимальное потребление памяти для небольших ключей. Элементы хранятся в самих ячейках (inline). Для средних и больших ключей подобных подход приводит к заметным накладным расходам памяти;
  • F14VectorMap - работает быстрее для больших таблиц и сложных ключей, но медленее для простых ключей и небольших таблиц. Элементы упаковываются в непрерывно заполняемом массиве и адресуются 32-разрядным индексным указателем;
  • F14FastMap - комбинированная стратегия. Если ключ меньше 24 байтов, то выбирается F14ValueMap, а если больше - F14VectorMap.

Дополнение: Проведено масштабное тестирование производительности и потребления памяти около 100 вариантов хэш-таблиц (20 реализаций unordered_map, каждая с 5 разными методами хэширования). Судя по тестам folly::F14ValueMap и folly::F14NodeMap демонстрируют весьма средние показатели по производительности и хорошие, но не лидирующие, по потреблению памяти. Наиболее оптимальное сочетание показателей производительности и потребления памяти показали robin_hood::unordered_flat_map для числовых ключей и robin_hood::unordered_node_map для строковых значений ключей.

В тестах на создание по потреблению памяти лучшими оказались tsl::sparse_map и phmap::parallel_flat_hash_map, причём последний в некоторых тестах обгоняет F14 по производительности).

В тестах на заполнение методы robin_hood::unordered_flat_map и ska::bytell_hash_map потребляют примерно на 10% больше памяти, но в 2 раза быстрее.

В тестах на выборку показатели F14 оказались весьма посредственными, в том числе и по потреблению памяти.


В тесте по полному перебору всех элементов лидером оказался tsl::sparse_map, которые в других тестах обгонял F14 и по потреблению памяти.



  1. Главная ссылка к новости (https://code.fb.com/developer-...)
  2. OpenNews: Facebook открыл платформу для быстрого развёртывания LTE-сетей
  3. OpenNews: Facebook опубликовал Spectrum 1.0.0, библиотеку для работы с изображениями
  4. OpenNews: Facebook опубликовал открытую систему распознавания речи Wav2letter++
  5. OpenNews: Facebook открыл код для обработки ситуации нехватки памяти в системе
  6. OpenNews: Facebook открыл код C++ библиотеки Folly
Лицензия: CC-BY
Тип: Программы
Короткая ссылка: https://opennet.ru/50611-facebook
Ключевые слова: facebook, hash
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (14) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, Вася (??), 22:03, 01/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • –4 +/
    Круто, очень круто. FaceBook молодцы, очень большой вклад вносят в OpenSurce Community!
     
     
  • 2.2, Аноним (2), 22:27, 01/05/2019 [^] [^^] [^^^] [ответить]  
  • +6 +/
    Два чая этому ГоспоДину.
     
  • 2.3, онаним (?), 22:35, 01/05/2019 Скрыто модератором
  • –3 +/
     
     
  • 3.4, Аноним (4), 23:04, 01/05/2019 Скрыто модератором
  • –2 +/
     

     ....ответы скрыты модератором (3)

  • 1.7, Аноним (7), 23:50, 01/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/
     
  • 1.12, Нанобот (ok), 09:00, 02/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • –2 +/
    >позволяет снизить потребление памяти

    но зачем фейсбуку может понадобиться экономить память?

     
     
  • 2.14, Аноним (14), 09:14, 02/05/2019 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Чтобы соответствовать своей клиентуре.
     
  • 2.15, Аноним (15), 10:26, 02/05/2019 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Двухнедельная память, как у целевой аудитории, это ведь круто!
     
  • 2.16, macfaq (?), 17:43, 02/05/2019 [^] [^^] [^^^] [ответить]  
  • +4 +/
    >>позволяет снизить потребление памяти
    > но зачем фейсбуку может понадобиться экономить память?

    Деньги когда-нибудь кончаются даже если у тебя их миллиарды.

     
  • 2.17, anonymous (??), 10:17, 03/05/2019 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > но зачем фейсбуку может понадобиться экономить память?

    Ну так не на клиентских машинах запускаются, а на своих собственных. Свои машины жалко говнософтом увешивать.

     
  • 2.18, anonymous (??), 17:03, 04/05/2019 [^] [^^] [^^^] [ответить]  
  • +/
    Экономия памяти является приятным побочным эффект попытки экономии L1D кеша ЦПУ.
     

  • 1.19, Аноним (19), 12:56, 05/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Я НИЧЕГО не понял. Если какие-то реализации оптимальнее по всем параметрам тех, что в стандартной библиотеке языка C++, то логично втянуть эту реализацию в стандартную библиотеку, а ту, что была - выкинуть. Ибо нафига нам ещё одна зависимость? Почему это не было сделано?
     
     
  • 2.20, Аноним (20), 22:28, 08/05/2019 [^] [^^] [^^^] [ответить]  
  • +/
    В стандартной библиотеки обычная хэш-таблица, которая более-менее подойдет для любой ситуации, а тут разреженная, которая экономит память для огромных разреженных таблиц, но существенно проигрывает в скорости для маленьких или неразреженных. А так-то и я не против, чтобы все популярные виды хэш-массивов и деревьев были в std, но комитет хочет чтобы была только одна структура данных каждого типа
     

  • 1.21, burjui (ok), 15:07, 09/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Выглядит очень похоже на Swiss Table от Google:
    https://youtu.be/ncHmEUmJZf4
     
  • 1.22, Anonymouss (?), 16:28, 09/05/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    интересно.
    А почему F14, a не F13 ?
     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2020 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру