Comments 28
Это перевод моей же статьи на медиуме.
Вопросы, фидбек приветствуются!
Меня посетила интересная мысль - а откуда берётся выигрыш в производительности? 1Кб в куче выделяет стандартный LINQ, видимо столько же, но на стеке выделяет ваша версия. Выделение в куче стоит почти столько же, сколько и на стеке. Выделенную в куче память GC, скорее всего, никогда не увидит, то есть стоимость очистки памяти тоже равна стеку.
Дальше теория - львиная доля из 4 и 8 мс это выделение памяти. Если увеличить размер коллекции, то это время станет незначительно на общем фоне и разница станет незаметной.
Дальше теория - львиная доля из 4 и 8 мс это выделение памяти
На самом деле нет, память, как вы же сами сказали, стоит очень мало. Правда все-таки побольше, чем на стеке, но все равно немного.
А вот виртуальные вызовы на каждом шагу - вот это я думаю и занимает все время. Если сделать цепочку из N операций в LINQ, то каждый Move.Next это будет N виртуальных вызовов, то есть хождений по случайным местам памяти.
А тут нет виртуальных вызовов, и многие вызовы заинлайнены.
Неужели компилятор настолько глупый, что не может заинлайнить все эти виртуальные вызовы? Он же видит всю Linq-цепочку (в вашем примере).
Также непонятно, откуда такой дикий оверхед по памяти в типе? Все заинлайненные лямбды должен же иметь нулевой размер, они не используют состояние, а размер конечной структуры по идее должен быть максимальным размером всех этих переходных структур? Они же все в одном месте памяти находятся, а после инлайнинга так вообще должна остаться только пара ссылок на источник данных и конечную функцию преобразования.
Неужели компилятор настолько глупый, что не может заинлайнить все эти виртуальные вызовы? Он же видит всю Linq-цепочку (в вашем примере).
Пока да. Чтобы девиртуализировать такую длинную цепочку, ему придется буквально выполнить весь код и убедиться, что у нас всегда создаются одни и те же типы, и заинлайнить огромное количество кода. Для подобных вещей это бессмысленно и стоит очень много времени джита (а он, конечно, должен работать очень быстро).
Все заинлайненные лямбды должен же иметь нулевой размер, они не используют состояние
В моем примере я использую тип PureValueDelegate. Это такой value delegate, только для ленивых, потому что в нем я использую обычный Func :). В идеале туда можно передавать настоящий функтор вручную реализуя IValueDelegate, но кажется это никому из пользователей LINQ-а неинтересно такой ужас городить. Вот. То есть это как минимум 8 байт на каждый такой делегат.
а размер конечной структуры по идее должен быть максимальным размером всех этих переходных структур?
Ну, размер каждой следующей - сумма ее полей, то есть "личных" полей и предыдущего енумератора.
Плюс еще инлайнер джита мог уже выйти из бюджета и перестать инлайнить некоторые методы - тогда у нас еще и копирование будет.
В идеале туда можно передавать настоящий функтор вручную реализуя
IValueDelegate, но кажется это никому из пользователей LINQ-а
неинтересно такой ужас городить.
В крайнем случае можно подумать в сторону кодогенерации в рантайме и избавиться от косвенного вызова делегата, ведь Func — это Method + Target. Заводится словарик, и для каждого метода создаётся своя структура-обёртка, но с прямым вызовом.
Это значительно увеличит время создания объекта, но в случае больших коллекций даже выигрыш. Например, я такое проворачивал для обработки изображений, и оно работало весьма неплохо.
А в чем смысл этого PureValueDelegate?
Во всех методах ожидается структа-делегат реализующая IValueDelegate.
По идее, чтобы выжать максимально скорости работы, нужно написать структуру, реализовав интерфейс и в методе Invoke написать ваш делегат.
Но так как это не слишком интересно никому, я предварительно сделал PureValueDelegate и CapturingValueDelegate, которые работают без аллокаций, но используют обычный дотнетовский делегат.
Лучше приложите результат сравнения в BenchmarkDotNet для входых массивов размера 10, 100, 1000.
Сразу будет видно, сколько времени отъедают вызовы.
Хорошо. Сделал бенчмарк для сравнения простого Select + Where для RefLinq против классического.
Собственно, примерное отношение 1:2 по времени так и сохраняется, как и предполагалось ;).
Исходники бенчмарка тут.
cc @Mingun , @andreyverbin
Блин, есть же компилируемые деревья, они для этого созданы, ускорить стандартный Linq
Вовсе нет. Стандартный LINQ работает вполне "обычно", без Linq.Expression. Вот здесь можно посмотреть исходники LINQ-а.
Но для работы со всякими базами данных используется IQueryable, и вот там используются Linq.Expression, чтобы переделать лямбду на сишарпе в SQL-запрос (или как это в БД работает). Но это уже совсем другая история.
А еще знакомый пилит компилятор LINQ в обычные циклы/условия и т. д., вот там он использует компиляцию Linq.Expression.
Деталей я не знаю, но на меня они чутка поругивались за то что я в своей реализации реактивности их много куда напихал.
Это хороший вопрос, но я не изучал. Вообще, code bloating — это причина почему, например, CLR не генерирует типы и методы на каждый тип, а только на разные value type. То есть такая проблема явно есть. Но какое именно потребление — наверное можно попробовать померить через EventListener, отследив момент когда JIT специализирует тип
CLR не генерирует типы и методы на каждый тип, а только на разные value type.
Потому, что для ссылочных типов там одной реализации достаточно, т.к. переменные ссылочных типов, по сути, представляют с собой адрес постоянной длины, тогда как value type могут существенно отличаться по размерности и для них в случае обобщений должен генерироваться разный машинный код реализации.
Благодарю, очень интересно. Так же посмотрел ваше репо и был весьма удивлен - неужели один человек на такое способен? К примеру, скачал ваш проект AsmToDelegate на основе icedland/iced - весьма.
Расскажите как у вас хватает времени на это все, откуда берете мотивацию, энергию? Является ли это вашей личной инициативой или кто-то курирует? Так же является ли это вашей основной деятельностью и удалось ли найти финансирование, чтобы этим заниматься на постоянной основе?
Расскажите как у вас хватает времени на это все, откуда берете мотивацию, энергию?
Позитивный фидбек пользователей и читателей дает мотивацию.
Является ли это вашей личной инициативой или кто-то курирует?
Личная. Никто не финансирует.( Но надо сказать, что многие проекты не так-то и много заняли времени. Например, проект, про который эта статья, я сделал наверное дня за два. AsmToDelegate — там моей работы вовсе немного, по сути все, что я делаю, это пишу закодированный машинный код от Iced-а в исполняемую память и возвращаю делегат.
Хотя есть конечно и большие проекты, которые уже не первый год делаю, например этот
Еще могли бы рассказать как получили бэкграунд в низкоуровневой разработке? Помогло ли образование (наше или зарубежное?) или же достигали самостоятельно? Возможно порекомендуете какие-либо книги?
Вот реально редко встретишь людей из наших, которые так глубоко копают.
по сути все, что я делаю, это пишу закодированный машинный код от Iced-а в исполняемую память и возвращаю делегат
Да, это понятно. Но могу оценить ваш уровень компетентности, так как сам уже больше 10 лет занимаюсь разработкой. Работы не много - можно сказать один удар молотком. Но вот знать куда ударить - дорогого стоит.
Еще могли бы рассказать как получили бэкграунд в низкоуровневой разработке? Помогло ли образование (наше или зарубежное?) или же достигали самостоятельно? Возможно порекомендуете какие-либо книги?
Самостоятельно, но не без помощи других людей и проектов. В основном это
C# сервер в дискорде - тут куча крутых людей, очень много чего низкоуровнего можно узнать
Шарплаб
Ну и несколько книжек:
CLR via C# 4-th edition
Pro .NET Memory Management
Pro .NET Benchmarking
Вот реально редко встретишь людей из наших, которые так глубоко копают.
А ведь на том сишарп сервере есть люди, которые в этом шарят на порядки больше меня! Вот это реально клад
А почему linq в F# почти не генерит мусор и работает быстро?
Да генерит вроде... не мерил, если честно. Точнее мерил, вот здесь, но не сравнивал с LINQ.
Как LINQ, только быстрый и без аллокаций