Маленький словарь #скорость #память
Часто бывает, что мы получаем данные из внешнего источника или БД, создаём временный словарь, ищем по нему, а потом про него забываем. Часто бывает, что приходящих данных мало, например, 10-15 элементов.
При этом, многие помнят, что поиск по словарю при небольшом количестве элементов не всегда эффективен (поиск по массиву будет быстрее). Также, те коллеги, которые помнят устройство Dictionary, могут вспомнить, что эта структура данных имеет два внутренних массива, выделение которых на горячих направлениях кода может вызвать неплохой memory pressure. Например, создание одного словаря размером в 10 элементов - почти 1кб памяти.
В принципе, решение задачи лежит на поверхности.
Необходимо создать такую структуру данных, которая бы с самого начала хранила данные в массиве, а, в случае большого количества элементов, переходила на честный словарь, чтобы избежать потерь производительности. Также, было бы неплохо переиспользовать массив и сам словарь, так как представляется, что сценарий "заполнили, поискали и бросили/материализовали во что-то другое" весьма распространён.
Я набросал небольшой пример, который проще прочитать, чем пояснять. Из интересного там только Enumerator, который хранит сразу два Enumerator'a для разных случаев (массив и словарь). Не реализовано удаление, на которое у меня просто не хватило времени, и специальные методы для превращения в ToDictionary, ToList, ToArray - их можно написать эффективнее, чем те, которые есть в классе Enumerable. Но, я думаю, что это не проблема для тех, кто понял концепцию.
Сам 'https://t.me/csharp_gepard/156?comment=1889' rel='nofollow'>бенчмарк охватывает сценарий, который описан выше: создаём словарь, ищем ключи, используем словарь для linq операции. В моём примере, возвращение переиспользуемого массива и словаря реализовано через Dispose, который нужно не забывать вызывать, либо просто использовать using.
Как видно из прикреплённой картинки, прирост производительности для количества элементов < 20 что-то около 20%. Ну и zero-allocation, конечно. Почему при 50 элементах всё равно существует опережение по скорости - я оставлю на самостоятельное исследование. Не исключена банальная ошибка.
Часто бывает, что мы получаем данные из внешнего источника или БД, создаём временный словарь, ищем по нему, а потом про него забываем. Часто бывает, что приходящих данных мало, например, 10-15 элементов.
При этом, многие помнят, что поиск по словарю при небольшом количестве элементов не всегда эффективен (поиск по массиву будет быстрее). Также, те коллеги, которые помнят устройство Dictionary, могут вспомнить, что эта структура данных имеет два внутренних массива, выделение которых на горячих направлениях кода может вызвать неплохой memory pressure. Например, создание одного словаря размером в 10 элементов - почти 1кб памяти.
В принципе, решение задачи лежит на поверхности.
Необходимо создать такую структуру данных, которая бы с самого начала хранила данные в массиве, а, в случае большого количества элементов, переходила на честный словарь, чтобы избежать потерь производительности. Также, было бы неплохо переиспользовать массив и сам словарь, так как представляется, что сценарий "заполнили, поискали и бросили/материализовали во что-то другое" весьма распространён.
Я набросал небольшой пример, который проще прочитать, чем пояснять. Из интересного там только Enumerator, который хранит сразу два Enumerator'a для разных случаев (массив и словарь). Не реализовано удаление, на которое у меня просто не хватило времени, и специальные методы для превращения в ToDictionary, ToList, ToArray - их можно написать эффективнее, чем те, которые есть в классе Enumerable. Но, я думаю, что это не проблема для тех, кто понял концепцию.
Сам 'https://t.me/csharp_gepard/156?comment=1889' rel='nofollow'>бенчмарк охватывает сценарий, который описан выше: создаём словарь, ищем ключи, используем словарь для linq операции. В моём примере, возвращение переиспользуемого массива и словаря реализовано через Dispose, который нужно не забывать вызывать, либо просто использовать using.
Как видно из прикреплённой картинки, прирост производительности для количества элементов < 20 что-то около 20%. Ну и zero-allocation, конечно. Почему при 50 элементах всё равно существует опережение по скорости - я оставлю на самостоятельное исследование. Не исключена банальная ошибка.