The OpenNET Project / Index page

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



"Facebook открыл реализацию хэш-таблиц F14"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от opennews (??), 01-Май-19, 22:03 
Компания Facebook объявила (https://code.fb.com/developer-tools/f14/) об открытии исходных текстов реализации хэш-таблиц F14 (https://github.com/facebook/folly/blob/master/folly/containe...), оптимизированной для эффективного потребления памяти. F14 используется в инфраструктуре Facebook в качестве замены большинства типов хэш-таблиц и позволяет снизить потребление памяти без потери производительности. F14 заметно превосходит по производительности хэш-таблицы google::sparse_hash_map, до сих пор считавшиеся наиболее эффективными по потреблению памяти. Код проекта написан на языке C++ и включен в состав библиотеки Folly (https://github.com/facebook/folly/).


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

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


-  F14NodeMap - потребляет меньше всего памяти для ключей большого и среднего размера. Обеспечивает косвенное сохранение элементов с вызовом при каждой вставке функции malloc;

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


URL: https://code.fb.com/developer-tools/f14/
Новость: https://www.opennet.ru/opennews/art.shtml?num=50611

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения [Сортировка по времени | RSS]


1. "Facebook открыл реализацию хэш-таблиц F14"  –4 +/
Сообщение от Вася (??), 01-Май-19, 22:03 
Круто, очень круто. FaceBook молодцы, очень большой вклад вносят в OpenSurce Community!
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

2. "Facebook открыл реализацию хэш-таблиц F14"  +6 +/
Сообщение от Аноним (2), 01-Май-19, 22:27 
Два чая этому ГоспоДину.
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

3. Скрыто модератором  –3 +/
Сообщение от онаним (?), 01-Май-19, 22:35 
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

4. Скрыто модератором  –2 +/
Сообщение от Аноним (4), 01-Май-19, 23:04 
Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

7. "Facebook открыл реализацию хэш-таблиц F14"  +1 +/
Сообщение от Аноним (7), 01-Май-19, 23:50 
https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o.../
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

12. "Facebook открыл реализацию хэш-таблиц F14"  –2 +/
Сообщение от Нанобот (ok), 02-Май-19, 09:00 
>позволяет снизить потребление памяти

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

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

14. "Facebook открыл реализацию хэш-таблиц F14"  +1 +/
Сообщение от Аноним (14), 02-Май-19, 09:14 
Чтобы соответствовать своей клиентуре.
Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

15. "Facebook открыл реализацию хэш-таблиц F14"  +2 +/
Сообщение от Аноним (15), 02-Май-19, 10:26 
Двухнедельная память, как у целевой аудитории, это ведь круто!
Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

16. "Facebook открыл реализацию хэш-таблиц F14"  +4 +/
Сообщение от macfaq (?), 02-Май-19, 17:43 
>>позволяет снизить потребление памяти
> но зачем фейсбуку может понадобиться экономить память?

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

Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

17. "Facebook открыл реализацию хэш-таблиц F14"  +1 +/
Сообщение от anonymous (??), 03-Май-19, 10:17 
> но зачем фейсбуку может понадобиться экономить память?

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

Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

18. "Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от anonymous (??), 04-Май-19, 17:03 
Экономия памяти является приятным побочным эффект попытки экономии L1D кеша ЦПУ.
Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

19. "Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от Аноним (19), 05-Май-19, 12:56 
Я НИЧЕГО не понял. Если какие-то реализации оптимальнее по всем параметрам тех, что в стандартной библиотеке языка C++, то логично втянуть эту реализацию в стандартную библиотеку, а ту, что была - выкинуть. Ибо нафига нам ещё одна зависимость? Почему это не было сделано?
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

20. "Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от Аноним (20), 08-Май-19, 22:28 
В стандартной библиотеки обычная хэш-таблица, которая более-менее подойдет для любой ситуации, а тут разреженная, которая экономит память для огромных разреженных таблиц, но существенно проигрывает в скорости для маленьких или неразреженных. А так-то и я не против, чтобы все популярные виды хэш-массивов и деревьев были в std, но комитет хочет чтобы была только одна структура данных каждого типа
Ответить | Правка | ^ к родителю #19 | Наверх | Cообщить модератору

21. "Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от burjui (ok), 09-Май-19, 15:07 
Выглядит очень похоже на Swiss Table от Google:
https://youtu.be/ncHmEUmJZf4
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

22. "Facebook открыл реализацию хэш-таблиц F14"  +/
Сообщение от Anonymoussemail (?), 09-Май-19, 16:28 
интересно.
А почему F14, a не F13 ?
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




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

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