Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
Если свободное место в словаре закончилось, то алгоритм обычно решает удвоить текущую емкость
Таким образом вроде работает List.
А в словаре же вроде выбирается следующее простое число для размера коллекции?
Размер коллекции является делителем хэш-кода, и для того, чтобы было минимум коллизий, выбирается именно простое число.
То есть для хранения такой сущности не выделяется отдельное место в куче, она помещается по месту объявления, то есть в данном случае в области памяти, занимаемой массивом _entries.
Память, занимаемая массивом, уже находится в куче. А память под указанную структуру аллоцируется вместе с массивом на куче.
Разработчик должен представлять, как устроен словарь, как он работает с памятью, насколько затратен, сколько «следов» оставит в поколениях и LOH, вызывая излишнюю нагрузку на сборщик мусора; как его лучше инициализировать, в каких случаях вместо него лучше использовать коллекцию пар ключ-значение, в каких – сортированную коллекцию и т.д.И помнить, разумеется, наизусть IL код для него. Скажу сразу, такие заявления — повод подробно пройтись по статье.
Это заметно лучше, чем в реализации ConcurrentDictionary, где аналогичная сущность представлена ссылочным типом.Что значит «лучше»? Почему лучше?
То есть для хранения такой сущности не выделяется отдельное место в куче, она помещается по месту объявления, то есть в данном случае в области памяти, занимаемой массивом _entries.… а на массив выдаеляется место в куче.
По графику видно, что стратегия заполнения словаря по умолчанию привела к резервированию 400МБ памяти для хранения 10млн. значений (80МБ полезных данных). Но если задать емкость при вызове конструктора new Dictionary<int, int>(10001000), то для хранения этих же данных будет зарезервировано всего 190МБ.Нет, по графику этого не видно. Вообще неясно, какая там стратегия была. И что вообще значит «стратегия по умолчанию»? И зачем её использовать для инициализации больших списков?
UPD. Посмотрел код. Во-первых, нужно сделать нормальные бенчмарки. Во-вторых, добавлять миллионы элементов по одному — ну я не знаю, для чего это тестировать и делать какие-то выводы.
Модифицируем предыдущий опыт такА какой был предыдущий опыт?
Как видно, время поиска с перебором элементов массива линейно растет от 18 наносекунд при count=10 до 134 нс при count=190Я теряю кейс статьи. Только что графики были на миллионы записей, а теперь — на десятки. И совете (выводе?) в конце тоже про «пятьдесят записей».
помним, поиск в словаре при идеальных условиях константныйНет, не помним. Сложность поиска константна. И не при идеальных условиях, а всегда. Константная сложность здесь означает, что значение будет найдено за конечное количество шагов, не зависящее от размера коллекции.
Причиной такого поведения является упорядоченность перебора при поиске по массиву, что делает этот поиск предсказуемым для процессораДа причём тут процессор вообще? Это сложность алгоритма. Можно руками всё посчитать, без процессора, с тем же успехом. Просто каждый шаг вручную будет дольше считаться.
Другой причиной можно назвать заложенную в словарь гибкость, с использованием вызова виртуальных функций (callvirt для GetHashCode и Equals)Причём тут вообще словарь и «заложенная в нём гибкость»? Просто GetHashCode и Equals — виртуальные функции...
Кстати, в некоторых случаях, если требования к скорости работы алгоритма высоки, можно рассмотреть вопрос о самостоятельной переработке словаря с заменой обобщенного (generic) ключа на ключ конкретного типа.Теряюсь в догадках, что это может дать. Так как материализованные generic типы тоже имеют ключ конкретного типа.
ключ неуправляемого значимого типаНеуправляемый тип?
Во-вторых, добавлять миллионы элементов по одному — ну я не знаю, для чего это тестировать и делать какие-то выводы.
А в словарь по-другому их и не добавить же. Даже копирующий конструктор так работает.
Да причём тут процессор вообще?
Притом, что исполнение кода на процессоре имеет свои особенности, которых не возникает если считать "руками" и без процессора.
Спасибо за комментарий.
В следующем предложении это раскрывается. Хранение ссылочного типа накладно.
Само собой.
Использование явного типа вместо обобщенного позволяет уйти от callvirt, что в свою очередь увеличивает производительность поиска по словарю процентов на 10-20. В некоторых проектах это достаточно важный плюс.
Так написано на сайте Майкрософта.
Согласен, часть мыслей выразил скомкано и невнятно. Постараюсь в следующий раз быть внимательней.
Что значит «лучше»? Почему лучше?
В следующем предложении это раскрывается. Хранение ссылочного типа накладно.
… а на массив выдаеляется место в куче.
Само собой.
И зачем её использовать для инициализации больших списков?Заметка как раз об этом. Не все разработчики понимают, что стоит за некоторыми внешне вполне безобидными строчками кода.
Во-вторых, добавлять миллионы элементов по одному — ну я не знаю, для чего это тестировать и делать какие-то выводы.А почему нет? Со словарем обычно именно так и работают.
А какой был предыдущий опыт?Представлен на предыдущем графике.
Я теряю кейс статьи. Только что графики были на миллионы записей, а теперь — на десятки. И совете (выводе?) в конце тоже про «пятьдесят записей».Угу. Невнятно написал, согласен. В заметке привел несколько наглядных опытов и выводов по ним. Общих выводов в конце нет, только по последнему опыту.
Нет, не помним. Сложность поиска константна. И не при идеальных условиях, а всегда. Константная сложность здесь означает, что значение будет найдено за конечное количество шагов, не зависящее от размера коллекции.Не означает. Для поиска по хэш-таблицы нет никаких гарантий, что он не выродится в пробег по всей сохраненной коллекции, есть лишь ожидание, что этого не произойдет.
Да причём тут процессор вообще?Там написано про поиск по массиву. Это один из опытов. При определенном количестве элементов поиск по массиву быстрее. Написано, почему.
Теряюсь в догадках, что это может дать. Так как материализованные generic типы тоже имеют ключ конкретного типа.
Использование явного типа вместо обобщенного позволяет уйти от callvirt, что в свою очередь увеличивает производительность поиска по словарю процентов на 10-20. В некоторых проектах это достаточно важный плюс.
Неуправляемый тип?
Так написано на сайте Майкрософта.
Согласен, часть мыслей выразил скомкано и невнятно. Постараюсь в следующий раз быть внимательней.
Хранение ссылочного типа накладно.А для value типа — копирование. Которое произойдёт при изменении внутренних коллекций.
Заметка как раз об этом.Тогда это нужно указать явно. А также описать, за счёт чего во втором варианте получился выигрыш по памяти более чем в 2 раза.
Представлен на предыдущем графике.Я не хочу обидеть, но мне кажется, мы с вами какие-то разные графики видим. У вас там вроде как на графике и способ добавления есть, и описаны значения, используемые для ключа и значения. Я ничего этого не вижу.
Не означает. Для поиска по хэш-таблицы нет никаких гарантий, что он не выродится в пробег по всей сохраненной коллекции, есть лишь ожидание, что этого не произойдет.Означает) Приведёте миллионную хэштаблицу, у которой поиск вырождается? Если серьёзно, то О большое по определению ограничивает алгоритм сверху. Так что это — по определению! — гарантия, что ничто никуда не выродится. Да, если у вас пять записей, можно натянуть на это «выродится». Но это по-прежнему означает «конечное количество шагов, независимо от размера коллекции».
Там написано про поиск по массиву. Это один из опытов. При определенном количестве элементов поиск по массиву быстрее. Написано, почему.Да, я видимо решил, что та фраза связана с «помним, поиск в словаре при идеальных условиях константный». Так или иначе, нужно понимать, какой конкретно процессор имеется в виду, а также, что от процессора к процессору это значение будет меняться.
Использование явного типа вместо обобщенного позволяет уйти от callvirt, что в свою очередь увеличивает производительность поиска по словарю процентов на 10-20. В некоторых проектах это достаточно важный плюс.Скиньте ссылку, пожалуйста, на документацию, этого я не знал. А какие именно методы перестают быть виртуальными?
А для value типа — копирование. Которое произойдёт при изменении внутренних коллекций.Ну значит желательно проектировать архитектуру так, чтоб таких изменений было меньше. Заметка как раз об этом.
Тогда это нужно указать явно. А также описать, за счёт чего во втором варианте получился выигрыш по памяти более чем в 2 раза.Это все указано и написано
Приведёте миллионную хэштаблицу, у которой поиск вырождается?Да хоть миллиардную). Банально переопределите у ключа
public override int GetHashCode()
{
return 1;
}
и выродится. Это как раз и есть худший случай для оценки сложности алгоритма.
Если же говорить о более реальной ситуации, то распределение ключей для алгоритма всегда имеет вероятностную, внешнюю природу, алгоритм это не контролирует, как и выбор хэш-функции. Соответственно нет никаких гарантий уникальности хэшей для разных ключей. На миллион ключей может быть как миллион уникальных хэшей, так и множество совпадающих. Дальше степень уникальности еще снижается делением на длину массива _buckets. Опять же нет никаких гарантий, что значения даже для уникальных хэшей в конце концов не попадут на одну позицию в этом массиве. Есть только ожидание, что в большинстве случаев произойдет именно так.
Так или иначе, нужно понимать, какой конкретно процессор имеется в виду, а также, что от процессора к процессору это значение будет меняться.Исследование разных конфигураций не является темой этой заметки. В остальном же для актуальных процессоров это правило.
Скиньте ссылку, пожалуйста, на документацию, этого я не знал. А какие именно методы перестают быть виртуальными?Я такой не знаю. Вроде было что-то когда-то в msdn, но кануло. А специально эту тему не исследовал. Просто посмотрел на IL код FindEntry для framework и core. Во втором случае есть определенные оптимизации для типов значений и они действительно дают измеримый эффект (впрочем это не тема данной заметки, просто увидел во время тестов).
и выродитсяТогда ясно, что у вас имелось в виду под «идеальным сценарием» — это когда используется настоящая хэш-функция, а не одно число на все значения.
Это как раз и есть худший случай для оценки сложности алгоритма.Если оценивать алгоритм по такому случаю, то он будет хуже полного перебора, т.е. хуже O(n) за счёт сложной внутренней структуры. Однако, в прикладных задачах нет смысла опираться на этот случай.
На миллион ключей может быть как миллион уникальных хэшей, так и множество совпадающих.И это «множество» совпадающих всё равно будет существенно меньше исходных миллионов в коллекции. Именно потому и O(1).
Ещё раз обращу отдельное внимание: O(1) — это не выполнение за одну операцию. Даже не за пять или за десять. Это утверждение, что количество операций для выполнения алгоритма не зависит напрямую от исходной коллекции. Оно будет существенно меньше на больших коллекциях, но может быть и больше — на малых.
Да, будет у вас пять коллизий на миллион. Сто коллизий на миллион пусть будет (что уже фантастично). Пусть тысяча (если у вас коллизия-ориентированное программирование). Это всё равно существенно быстрее, чем искать полным перебором (т.е. O(n)).
P.S. Взял первую попавшуюся статью о вероятности коллизии в хэш-функции CRC32: на 20 млн записей, при использовании 64-битных ключей, вероятность одной коллизии — сравни вероятности, что вас ударит молния.
Не хочу спорить с субъективными высказываниями, но, что касается объективного, то
Нет. Только если у Вас количество коллизий = 0. В худшем же случае — линейная. Сложность поиска в Dictionary линейно зависит от количества коллизий для конкретного ключа. Больше елементов — больше коллизий.
Сложность поиска константна. И не при идеальных условиях, а всегда.
Нет. Только если у Вас количество коллизий = 0. В худшем же случае — линейная. Сложность поиска в Dictionary линейно зависит от количества коллизий для конкретного ключа. Больше елементов — больше коллизий.
Вы пытаетесь опровергнуть O(1) для поиска в хэштаблице? Наверняка вы знаете, что есть методы решения коллизий, позволяющие избегать линейности.
Тут скорее надо говорить не о количестве коллизий, а о том, сложность чего определяется. Теоретического алгоритма в некоторой идеальной хэш-таблице или некоторой конкретной реализации с определёнными ограничениями.
Для любой реализации с ограничением количества бакетов асимптотическая сложность среднего или максимального времени поиска не в лучшем случае не будет константной. Просто потому, что всегда можно запихать такое количество элементов, что это среднее превысит наперёд заданную константу.
А вот если мы наложим другие ограничения (максимальный объём памяти, качество хэша) — вот тут уже надо подходить индивидуально к любом случаю. Тут уже не теоретическая сложность алгоритма, а вполне конкретная статистика будет.
Для любой реализации с ограничением количества бакетов асимптотическая сложность среднего или максимального времени поиска не в лучшем случае не будет константной. Просто потому, что всегда можно запихать такое количество элементов, что это среднее превысит наперёд заданную константу.
А вот если мы наложим другие ограничения (максимальный объём памяти, качество хэша) — вот тут уже надо подходить индивидуально к любом случаю. Тут уже не теоретическая сложность алгоритма, а вполне конкретная статистика будет.
Для любой реализации с ограничением количества бакетов асимптотическая сложность среднего или максимального времени поиска не в лучшем случае не будет константной. Просто потому, что всегда можно запихать такое количество элементов, что это среднее превысит наперёд заданную константу.Я ещё раз, на всякий случай, повторю.
- Асимптотическая сложность О(1) — это не «наперёд заданная константа».
- Асимптотическая сложность алгоритма не меняется, сколько бы вы элементов не напихали.
- Асимптотическая сложность хэштаблицы равна O(1) в среднем (т.е. когда мы не говорим о синтетических случаях с одинаковым хэшем для всех элементов).
Определение функции асимптотической сложности — заранее определённая от нужного параметра функция количества шагов, которая не будет превышена алгоритмом, работающим с этим параметром (строгое определение, естественно, через машину Тьюринга и длину входных данных — можно найти в учебнике).
В нашем случае O(1) — это функция вида y=C. Согласно этому определению, если у алгоритма такая сложность — то найдётся такое C (константа), что при любом количестве элементов количество шагов алгоритма не превысит C. Что очевидно неверно по указанным выше соображениям в случае теоретического алгоритма.
В нашем случае O(1) — это функция вида y=C. Согласно этому определению, если у алгоритма такая сложность — то найдётся такое C (константа), что при любом количестве элементов количество шагов алгоритма не превысит C. Что очевидно неверно по указанным выше соображениям в случае теоретического алгоритма.
Функция асимптотической сложности — это вы, видимо, имеете в виду О большое.
O большое — это нотация. От функции её отличает, хотя бы, то, что она учитывает только доминирующий слагаемый, отметая всё остальное. Т.е. она не даст точного результата о количестве шагов.
2. Правильно ли я понимаю, что два любых алгоритма O(n) будут абсолютно одинаковы (т.е. гарантировать одно и то же максимальное количество шагов)?
3. Если мой алгоритм на n элементах делает 10n2 (квадрат) + 100n + 1000 шагов, я куда смогу его отнести? Я не влезаю в O(n2) — шагов будет намного больше, чем n2. Значит, O(n3)?
O большое — это нотация. От функции её отличает, хотя бы, то, что она учитывает только доминирующий слагаемый, отметая всё остальное. Т.е. она не даст точного результата о количестве шагов.
В нашем случае O(1) — это функция вида y=C.1. Чисто из любопытства, O(n3) (в кубе) — это функция какого вида? То есть, какое максимальное количество шагов — следуя вашему определению — должно быть гарантировано алгоритмом?
2. Правильно ли я понимаю, что два любых алгоритма O(n) будут абсолютно одинаковы (т.е. гарантировать одно и то же максимальное количество шагов)?
3. Если мой алгоритм на n элементах делает 10n2 (квадрат) + 100n + 1000 шагов, я куда смогу его отнести? Я не влезаю в O(n2) — шагов будет намного больше, чем n2. Значит, O(n3)?
В нашем случае O(1) — это функция вида y=C. Согласно этому определению, если у алгоритма такая сложность — то найдётся такое C (константа), что при любом количестве элементов количество шагов алгоритма не превысит C. Что очевидно неверно по указанным выше соображениям в случае теоретического алгоритма.Хорошо. Какая, по вашему, функция асимптотической сложности у алгоритма поиска в хэштаблице? И, сразу забегая, какая — у поиска простым перебором? И что выбрать?
1. Известная асимптотическая функция не гарантирует количество шагов. Она гарантирует, что число условных шагов алгоритма (повторю, что определение вольное, за формальной точностью стоит обратиться к учебнику) от количественно измеренного входа с некоторого момента не превысит (если про ограничение сверху говорить) значение этой функции от того же аргумента. Насколько асимптота будет выше — никаких указаний и гарантий нет.
2. Нет.
3. Функция 100000000000000n^2, насколько я вижу, начиная с 1, везде выше функции количества шагов. По определению она — асиптотическая, и можно говорить о квадратичной сложности. N^3, не позднее миллиона тоже выше данной функции, она тоже асимптота. Равно как и все функции более высоких степеней. Но лучшая оценка, пожалуй — n^2.
Я уже говорил, что это зависит от того, какие ограничения есть у этого алгоритма. У поиска перебором лучшей оценкой будет линейная функция. Выбрать надо то, что в конкретном случае применения в реальной жизни даст лучший результат. Для поиска среди двух элементов я бы, вероятно, выбрал перебор.
2. Нет.
3. Функция 100000000000000n^2, насколько я вижу, начиная с 1, везде выше функции количества шагов. По определению она — асиптотическая, и можно говорить о квадратичной сложности. N^3, не позднее миллиона тоже выше данной функции, она тоже асимптота. Равно как и все функции более высоких степеней. Но лучшая оценка, пожалуй — n^2.
Какая, по вашему, функция асимптотической сложности у алгоритма поиска в хэштаблице?
Я уже говорил, что это зависит от того, какие ограничения есть у этого алгоритма. У поиска перебором лучшей оценкой будет линейная функция. Выбрать надо то, что в конкретном случае применения в реальной жизни даст лучший результат. Для поиска среди двух элементов я бы, вероятно, выбрал перебор.
Уточнение. Та часть, что "не будет превышена", входит не в определение сложности, а в определение "O большого".
Существуют ещё символы Ω и Θ для оценки снизу и для точной оценки, и их тоже применяют для асимптотической сложности.
Подозреваю, что те, кто бьётся за абсолютную эффективность по памяти и скорости на миллионных коллекциях данных, просто пишут на C++. Именно из-за этих людей C++ до сих пор весьма популярен. Хотя понимать, как это всё происходит в C#, безусловно, полезно. Но кто любит тотальный контроль над всем, тот пишет на C++.
Необязательно. Разница на самом деле не такая существенная, даже с оптимизациями. Во всяком случае не настолько большая, чтоб писать большой и сложный проект на C++.
Тем более в .NET уже даже интринсики перенесли.
Другое дело, что черной магии в платформе многовато. Например, последний опыт (сравнение производительности поиска по словарю и массиву) дал в общем-то аномальный результат, при прямом сравнении у меня обычно получается примерное равенство при 20-30 элементах (оттого и вывел границу в 50), а тут вышло много больше.
Тем более в .NET уже даже интринсики перенесли.
Другое дело, что черной магии в платформе многовато. Например, последний опыт (сравнение производительности поиска по словарю и массиву) дал в общем-то аномальный результат, при прямом сравнении у меня обычно получается примерное равенство при 20-30 элементах (оттого и вывел границу в 50), а тут вышло много больше.
Ну я лично поэтому и пишу на C#.NET, что в нём всё как-то гораздо проще и понятнее, а проблемы со скоростью и памятью обычно не настолько критичны даже для больших проектов, как возможность их поддерживать и развивать.
Но вот в конторах, где борются за любые миллисекунды, как в Яндексе, например, там по-прежнему пишут на C++.
А вот с магией да, хорошо бы разобраться и понять, в чём прикол. Всякое бывает.
Но вот в конторах, где борются за любые миллисекунды, как в Яндексе, например, там по-прежнему пишут на C++.
А вот с магией да, хорошо бы разобраться и понять, в чём прикол. Всякое бывает.
Почему разработчики Microsoft не разделили _entries на четыре массива, соответствующих полям Entry?
Чтобы оптимизировать локальность данных — снизить число кэш-миссов.
Добавлю и свои пять копеек в обсуждение.
1. Моё личное мнение — все подобные статьи надо предварять большим дисклеймером, что все технические подробности приведены исключительно для ознакомления и диагностики сложных случаев и не могут сами по себе являться критерием построения алгоритма.
2. Аналогично, общих выводов, типа «хорошо, что тут структура, а не ссылка» тоже лучше избегать. Это доказывается сугубо практикой в сугубо конкретном кейсе, а не теоретическими размышлениями, хотя теория позволит в том или ином случае предположить вероятный сценарий.
3. Очень полезное замечание про предварительное задание размера по возможности затерялось в общей массе статьи. :(
4. Выводы из бенчмарков, как было указано выше, в текущем виде не верифицируемы. Для сравнительной статистики всегда требуется указывать не только среднюю, но и отклонение, как минимум. Эксперименты строить в разных условиях, по возможности сохраняя неизменным только исследуемое свойство, чтобы исключить ложные корреляции. У меня стойкое ощущение, что на первом графике все кривые одинаковы с учётом погрешности измерения. Рекомендую (странно, что никто выше не рекомендовал) использовать Benchmark.NET.
5. Все относительные характеристики типа «достаточно долгий» должны иметь эталон сравнения. По сравнению с чем долог вызов callvirt и насколько? В каких случаях об этом вообще имеет смысл говорить? А «взрывной рост памяти» учитывает только ссылки на объекты? Насколько часто ссылка на объект будет достаточно значима по сравнению с самим объектом? Это не значит, что об этом не надо писать, это значит, что лучше отметать все инсинуации. Эту статью могут читать дети, которые могут это всё немедленно воспринять как универсальное руководство к действию.
1. Моё личное мнение — все подобные статьи надо предварять большим дисклеймером, что все технические подробности приведены исключительно для ознакомления и диагностики сложных случаев и не могут сами по себе являться критерием построения алгоритма.
2. Аналогично, общих выводов, типа «хорошо, что тут структура, а не ссылка» тоже лучше избегать. Это доказывается сугубо практикой в сугубо конкретном кейсе, а не теоретическими размышлениями, хотя теория позволит в том или ином случае предположить вероятный сценарий.
3. Очень полезное замечание про предварительное задание размера по возможности затерялось в общей массе статьи. :(
4. Выводы из бенчмарков, как было указано выше, в текущем виде не верифицируемы. Для сравнительной статистики всегда требуется указывать не только среднюю, но и отклонение, как минимум. Эксперименты строить в разных условиях, по возможности сохраняя неизменным только исследуемое свойство, чтобы исключить ложные корреляции. У меня стойкое ощущение, что на первом графике все кривые одинаковы с учётом погрешности измерения. Рекомендую (странно, что никто выше не рекомендовал) использовать Benchmark.NET.
5. Все относительные характеристики типа «достаточно долгий» должны иметь эталон сравнения. По сравнению с чем долог вызов callvirt и насколько? В каких случаях об этом вообще имеет смысл говорить? А «взрывной рост памяти» учитывает только ссылки на объекты? Насколько часто ссылка на объект будет достаточно значима по сравнению с самим объектом? Это не значит, что об этом не надо писать, это значит, что лучше отметать все инсинуации. Эту статью могут читать дети, которые могут это всё немедленно воспринять как универсальное руководство к действию.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Некоторые аспекты работы с Dictionary при разработке нагруженных приложений