А что вы понимаете под «интерпретацией» Expression-ов? Да, есть Compile(true), о которой довольно мало информации (лишь о том, что на каких-то платформах есть интерпретатор, на каких-то — компилятор, это есть и у вас в статье). Но по вашим ссылкам с пометкой «интерпретирует» нет этого вызова.
В больших проектах unit-тесты могут исчисляться тысячами и занимать десятки минут
Компиляция Expression-ов занимает десятки минут? Или какая часть из десятков минут — на компиляцию?)
Генерация делегатов для более сложных выражений сопряжено с проблемами вроде их идентификация для вызывающего кода или захвата переменных.
Так я же не критикую за недостаточный функционал, просто раз уж речь об оптимизации Expression-ов, надо понимать, каких именно, ведь без указания ограничений, может показаться, что это — для всех случаев (кстати, в Possibilities and Limitations ограничения указаны довольно скромные).
О том, что для генерации интересны только базовые фрагменты кода вроде упоминал :)
Про то, что только — речи всё же не шло в этих упоминаниях ;)
Это по сути и есть то, что решается подмодулями git. Другой вопрос, что кто-то должен заниматься такими законченными фрагментами кода (то есть, весь репозиторий и должен будет состоять из него), и я не знаю таких примеров) Но на внутрикомандном/корпоративном уровне — без проблем
Скомпилированные делегаты обычно кэшируют, чтобы переиспользовать, но это не спасает в сценариях, когда первый доступ происходит к большому количеству за раз. В таких случаях время run-time компиляции выражений становится значимым и оттягивает запуск приложения или отдельных окон.
Задумался о том, когда же такие сценарии бывают, что нужно компилировать множество Expression-ов при запуске приложения или окна (?). Смог придумать только генерацию маппинга, и сразу вспомнилось, что упомянутый в статье FastExpressionCompile не взлетел в Automapper, после чего у меня сложилось стойкое впечатление, что оптимизаторы Expression работают только на ограниченном наборе кейсов, с которым разбираться не очень-то и хочется. Уж тем более, использовать это в production.
Попробуйте отправить им реквест со своей библиотекой — это будет лучший Proof of concept.
P.S.: В статье не указано никаких ограничений на Expression-ы, но тесты только с простыми вызовами свойств, методов и конструкторов. Хочется чего-то посложнее, например фильтраци объекта по нескольким свойствам и методам, с сочетанием логических операторов.
1. IConfiguration при десериализации все равно запишет NULL в свойства, которых нет в appsettings.json так что в set все равно нужно вставить гард
Эм, нет не запишет. Выше указали ссылку на исходный код, да и я использую такой подход на практике — не перезаписывает.
2. Во всех местах, где нужно выполнять работу со свойствами придется добавлять проверку на дефолтное значение, что само по себе эквивалентно проверки на нулл. Т.к. если мы передадим «NotCertPathProvided» в метод, который работает с путями, то можем получить очень странное поведение.
Вы повторяете мой комментарий, на который отвечаете. Буквально первый абзац. И во втором абзаце я и пишу, что вместо просто не-null значений стоит использовать корректные дефолтные значения — которые не приведут к ошибкам. В таком случае, всё будет работать.
Ну и в добавок, эти дефолтные значения нужно вынести еще куда-то в константы
Да просто string.Empty как дефолтное значение. Для коллекций — пустая коллекция, и так далее. По аналогии с value types, у которых есть значение по умолчанию.
Да, но тогда нужно будет при использовании проверять наличие корректного значения для настройки — иначе вместо NRE мы получим какую-нибудь другую ошибку, которую, возможно, будет сложнее отладить.
Так что использование корректного дефолтного значения, на мой взгляд — лучший вариант.
Функция асимптотической сложности — это вы, видимо, имеете в виду О большое.
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) — это не «наперёд заданная константа».
Асимптотическая сложность алгоритма не меняется, сколько бы вы элементов не напихали.
Асимптотическая сложность хэштаблицы равна O(1) в среднем (т.е. когда мы не говорим о синтетических случаях с одинаковым хэшем для всех элементов).
Тогда ясно, что у вас имелось в виду под «идеальным сценарием» — это когда используется настоящая хэш-функция, а не одно число на все значения.
Это как раз и есть худший случай для оценки сложности алгоритма.
Если оценивать алгоритм по такому случаю, то он будет хуже полного перебора, т.е. хуже O(n) за счёт сложной внутренней структуры. Однако, в прикладных задачах нет смысла опираться на этот случай.
На миллион ключей может быть как миллион уникальных хэшей, так и множество совпадающих.
И это «множество» совпадающих всё равно будет существенно меньше исходных миллионов в коллекции. Именно потому и O(1).
Ещё раз обращу отдельное внимание: O(1) — это не выполнение за одну операцию. Даже не за пять или за десять. Это утверждение, что количество операций для выполнения алгоритма не зависит напрямую от исходной коллекции. Оно будет существенно меньше на больших коллекциях, но может быть и больше — на малых.
Да, будет у вас пять коллизий на миллион. Сто коллизий на миллион пусть будет (что уже фантастично). Пусть тысяча (если у вас коллизия-ориентированное программирование). Это всё равно существенно быстрее, чем искать полным перебором (т.е. O(n)).
P.S. Взял первую попавшуюся статью о вероятности коллизии в хэш-функции CRC32: на 20 млн записей, при использовании 64-битных ключей, вероятность одной коллизии — сравни вероятности, что вас ударит молния.
А для value типа — копирование. Которое произойдёт при изменении внутренних коллекций.
Заметка как раз об этом.
Тогда это нужно указать явно. А также описать, за счёт чего во втором варианте получился выигрыш по памяти более чем в 2 раза.
Представлен на предыдущем графике.
Я не хочу обидеть, но мне кажется, мы с вами какие-то разные графики видим. У вас там вроде как на графике и способ добавления есть, и описаны значения, используемые для ключа и значения. Я ничего этого не вижу.
Не означает. Для поиска по хэш-таблицы нет никаких гарантий, что он не выродится в пробег по всей сохраненной коллекции, есть лишь ожидание, что этого не произойдет.
Означает) Приведёте миллионную хэштаблицу, у которой поиск вырождается? Если серьёзно, то О большое по определению ограничивает алгоритм сверху. Так что это — по определению! — гарантия, что ничто никуда не выродится. Да, если у вас пять записей, можно натянуть на это «выродится». Но это по-прежнему означает «конечное количество шагов, независимо от размера коллекции».
Там написано про поиск по массиву. Это один из опытов. При определенном количестве элементов поиск по массиву быстрее. Написано, почему.
Да, я видимо решил, что та фраза связана с «помним, поиск в словаре при идеальных условиях константный». Так или иначе, нужно понимать, какой конкретно процессор имеется в виду, а также, что от процессора к процессору это значение будет меняться.
Использование явного типа вместо обобщенного позволяет уйти от callvirt, что в свою очередь увеличивает производительность поиска по словарю процентов на 10-20. В некоторых проектах это достаточно важный плюс.
Скиньте ссылку, пожалуйста, на документацию, этого я не знал. А какие именно методы перестают быть виртуальными?
Разработчик должен представлять, как устроен словарь, как он работает с памятью, насколько затратен, сколько «следов» оставит в поколениях и 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 типы тоже имеют ключ конкретного типа.
Компиляция Expression-ов занимает десятки минут? Или какая часть из десятков минут — на компиляцию?)
Так я же не критикую за недостаточный функционал, просто раз уж речь об оптимизации Expression-ов, надо понимать, каких именно, ведь без указания ограничений, может показаться, что это — для всех случаев (кстати, в Possibilities and Limitations ограничения указаны довольно скромные).Про то, что только — речи всё же не шло в этих упоминаниях ;)
Попробуйте отправить им реквест со своей библиотекой — это будет лучший Proof of concept.
P.S.: В статье не указано никаких ограничений на Expression-ы, но тесты только с простыми вызовами свойств, методов и конструкторов. Хочется чего-то посложнее, например фильтраци объекта по нескольким свойствам и методам, с сочетанием логических операторов.
Вы повторяете мой комментарий, на который отвечаете. Буквально первый абзац. И во втором абзаце я и пишу, что вместо просто не-null значений стоит использовать корректные дефолтные значения — которые не приведут к ошибкам. В таком случае, всё будет работать.
Ну разумеется, я же не весь проект сюда скидываю…
Так что использование корректного дефолтного значения, на мой взгляд — лучший вариант.
null!? Это же оксюморон и ломает всю логику nullable reference types.или другие, более осмысленные дефолтные значения?
Использовать NullGuard.
O большое — это нотация. От функции её отличает, хотя бы, то, что она учитывает только доминирующий слагаемый, отметая всё остальное. Т.е. она не даст точного результата о количестве шагов.1. Чисто из любопытства, O(n3) (в кубе) — это функция какого вида? То есть, какое максимальное количество шагов — следуя вашему определению — должно быть гарантировано алгоритмом?
2. Правильно ли я понимаю, что два любых алгоритма O(n) будут абсолютно одинаковы (т.е. гарантировать одно и то же максимальное количество шагов)?
3. Если мой алгоритм на n элементах делает 10n2 (квадрат) + 100n + 1000 шагов, я куда смогу его отнести? Я не влезаю в O(n2) — шагов будет намного больше, чем n2. Значит, O(n3)?
Хорошо. Какая, по вашему, функция асимптотической сложности у алгоритма поиска в хэштаблице? И, сразу забегая, какая — у поиска простым перебором? И что выбрать?
Ясно, по первому комментарию решил, что вы отказались от полноценной ORM и перешли на чистый SQL, а вы используете сразу и то, и то.
Ещё раз обращу отдельное внимание: O(1) — это не выполнение за одну операцию. Даже не за пять или за десять. Это утверждение, что количество операций для выполнения алгоритма не зависит напрямую от исходной коллекции. Оно будет существенно меньше на больших коллекциях, но может быть и больше — на малых.
Да, будет у вас пять коллизий на миллион. Сто коллизий на миллион пусть будет (что уже фантастично). Пусть тысяча (если у вас коллизия-ориентированное программирование). Это всё равно существенно быстрее, чем искать полным перебором (т.е. O(n)).
P.S. Взял первую попавшуюся статью о вероятности коллизии в хэш-функции CRC32: на 20 млн записей, при использовании 64-битных ключей, вероятность одной коллизии — сравни вероятности, что вас ударит молния.
И это никак не влияет на сложность алгоритма.
UPD. Посмотрел код. Во-первых, нужно сделать нормальные бенчмарки. Во-вторых, добавлять миллионы элементов по одному — ну я не знаю, для чего это тестировать и делать какие-то выводы.А какой был предыдущий опыт?Я теряю кейс статьи. Только что графики были на миллионы записей, а теперь — на десятки. И совете (выводе?) в конце тоже про «пятьдесят записей».Нет, не помним. Сложность поиска константна. И не при идеальных условиях, а всегда. Константная сложность здесь означает, что значение будет найдено за конечное количество шагов, не зависящее от размера коллекции.Да причём тут процессор вообще? Это сложность алгоритма. Можно руками всё посчитать, без процессора, с тем же успехом. Просто каждый шаг вручную будет дольше считаться.Причём тут вообще словарь и «заложенная в нём гибкость»? Просто GetHashCode и Equals — виртуальные функции...Теряюсь в догадках, что это может дать. Так как материализованные generic типы тоже имеют ключ конкретного типа.Неуправляемый тип?