Комментарии 19
Чисто из спортивного интереса: любопытно, какое место по производительности заняли бы switch-expressions из девятого C#.
switch-expressions это сахар для обычного switch и перед компиляцией преобразуется в него
В сишарпе что классический switch, что новый switch expression, что блок последовательных if + return — абсолютно одно и то же. Байт-код генерируется практически идентичный, производительность абсолютно не отличается.
Я почему спросил — меня несколько смущает намеренный автором результат, что набор if быстрее словаря в полтора раза. Набор if — это скорее всего аналог бинарного поиска. В определенных условиях хеш таблица выигрывает у бинарного поиска (и сильно), в каких-то — проигрывает, но как правило не сильно.
Да и вообще, правильно померять быстродействие — дело тонкое, не учесть какой-то фактор — это бывало многократно, у людей с любым уровнем квалификации и опыта.
Это правильное замечание, но в данном случае не зря sixsigma. В данном случае за финальными цифрами стоит и планирование эксперимента показывающее что условия измерения соответствуют реальному использованию, и учет размера кванта измерения, и проверка серией запусков с доказательством n-test что отклонение результатов одного запуска от среднеквадратичного значения меньше статистически значимого.
Выигрыш хэш таблицы дело вполне себе предсказуемое если знать как она устроена внутри.
1) выигрыш по сравнению сложных ключей за счет того что тяжелая операция сравнения заменяется на одноразовое вычисление хеш и серию легких сравнений хеш-значения и вызов тяжелого сравнения значений уже только на небольшую корзину (как правило размер выбирается такой, где линейный поиск оказывается не дольше двоичного дерева, до 6-8 элементов в bucket.
2) Ну и поиск в значительных объемах данных — после N > 10000 никаким сокращением одного O преодолеть разницу между 1 условной операцией и пусть логарифмическим, но ростом в другой — нельзя.
Но статья не про структуры данных, а про то что возможность динамического создания кода открывает возможность воспользоваться динамической модификацией, реализовав выигрыш, который возникает от набора данных, а не заложен изначально в алгоритм. В данном случае, как я и написал в начале — задача просто оказалась возможностью показать на простом примере, обычно кейсы применения Linq генерации кода куда запутаннее, там только на несколько страниц контекст объяснять пришлось бы.
Я в общем и не имел в виду, что вы что-то неверно померяли. Просто этот процесс измерения не был тут достаточно подробно описан, а допустить в нем ошибку — ну это вполне типично. Хотя бы — описать данные, на которых меряли, много ли их было или мало.
А сам процесс генерации кода из Expression — он без сомнения интересный (хотя такие статьи тут уже и были), и тема в целом неисчерпаемая.
Исходный код можно посмотреть тут
github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/dictionary.cs
Ваш вопрос в другом комментарии по поводу сравнения хэш-таблицы с двоичным деревом правильный. Но чтобы понять логику надо учесть один момент — у словаря поиск O(1), у дерева O(log2). Это все помнят и знают, но вот что O говорит только о количестве неких попугаев в которых мериться операция, а не о длительность в выраженной в единицах времени — забывают.
Собственно на размышления как раз и наводят цифры что по O соотношение количество операций 1 к log2(300) примерно 8, а реальное исполнение всего в 4. Именно более тяжелое O словаря и возможность ускорить O двоичного дерева за счет исключения обращения к памяти и открывают окно возможности для оптимизации здесь.
Я правильно понял, что заменили поиск по хэш-таблице с линейной памятью (300 элементов) и константным количеством случайного доступа на код линейного объёма (хотя бы 300 ифов) и логарифмическим количеством операций, но как бы без доступа к памяти? И при этом стало сильно быстрее?
Если да, то это немного удивительно. Возможно, конечно, лучше работает условный branch prediction или кэш для кода больше, чем для данных, или просто так данные уложились компактнее, чем в хэш-таблице.
А чем удивительно? Обращение к памяти всегда стоило дорого, по сравнению с теми же самыми операциями, но с аргументами в виде константы с команде. Посмотрите первые две строки в таблице, которые натолкнули меня на мысль — там тоже сравнение совершенно аналогичное, только сравнивается линейный поиск в массиве с линейной же цепочкой if.
к сожалению, “отладчиком в IDE” по такому коду не походишь
Это не совсем так. Если добавить код для сохранения отладочной информации, то становится возможной пошаговая отладка в псевдокоде. Пример кода. Конечно, вручную привязывать выражения к номерам строк — сомнительное удовольствие, но это вполне поддаётся автоматизации. Не так давно появилась библиотека ExpressionDebugger, позволяющая добавить отладку одной строкой кода.
Публикации
Когда программисту нечего делать или оптимизируем код при помощи Linq.Expression