Эффективно обходят стороной производительности, используя доходность возврат с вложенных циклов?
Некоторая предыстория - и почему я избегаю выхода в определенном библиотечном коде, который пишу:
Все Об Итераторах – Еще Один Языковой Гик[^]
Проблема вот в чем:
Скажем, мне нужно сделать простые комбинации наборов с использованием циклов. В моде LINQ-ish я просто буду рассматривать прямую итеративную последовательность как коллекцию или col, ниже.
так что для Союза Коль и коль б я А|Б
чтобы уступить это выглядело бы так
Союз(а,б) реализован как Рисунок 1, производительность которого в настоящее время значительно снизилась из-за внутренних особенностей того, как это работает.
достаточно плохо, что более яркие умы, чем мои, предложили добавить в C# функцию yield foreach, как показано на рис. 2, чтобы одновременно повысить читабельность и обойти требуемое снижение производительности (потому что она может составлять классы итераторов в один)
Прямо сейчас я раздаю много перечислений, потому что производительность LINQ неприемлема для широкого использования в таких вещах, как Парсеры GLR, и отчасти это ограничение доходности.
Я почти хотел вообще уйти из .NET, потому что F# - это странная утка, а c# просто заставляет меня много работать. До такой степени, что я подумываю о том, чтобы вернуться к своему старому доброму C++
Речь идет не о том, чтобы немного покрутить. Я не собираюсь брить тактовые циклы. Это проблема дизайна, которая влияет на то, где я могу даже использовать LINQ и yield в C# конкретно - она ограничивает то, где я могу практически использовать ее, из-за природы проектов, над которыми я работаю, которые имеют дело с большим количеством синтаксического анализа, деревьев решений и распознавания образов, и используют их с диким отказом везде, и вложенность-типичный случай.
Я работаю над этим прямо сейчас, довольно много кодируя вручную.
Кто-нибудь еще знаком с этой проблемой, и если да, то есть ли у них какие-нибудь хорошие предложения, где я могу продолжать использовать C# с LINQ или без него и современные парадигмы C#, не сталкиваясь с барьерами производительности, как только я захочу использовать функциональное программирование на основе наборов?
Что я уже пробовал:
// Figure 1: union a|b PERFORMANCE SUCKS
IEnumerable Union(IEnumerable a,IEnumerable b) {
foreach(var x in a) yield return x;
foreach(var y in b) yield return b;
}
// Figure 2: union a|b basically as good as
// hand rolled, but requires something C# doesn't have
IEnumerable Union(IEnumerable a,IEnumerable b) {
yield foreach a;
yield foreach b;
}
PIEBALDconsult
Не вините фреймворк или язык. Я избегаю Linq, foreach и многих других бесполезных вещей, которые предназначены для того, чтобы не дать неопытным практикам стать опытными.
Вы не можете победить цикл for-особенно для тех вещей, которые вы упоминаете.
honey the codewitch
дело не в том, чтобы кого-то обвинять.
речь идет о том, чтобы больше не писать классы перечислителей вручную, если есть лучший способ избежать этого.
считайте меня нигилистом, когда дело доходит до рамок и обвинений.
мне все равно, кто виноват. я просто ищу способ продолжать использовать C#, даже если мне в основном приходится вручную свернуть значительное подмножество того, что linq и yield предоставляют с нуля гораздо больше, чем мне бы хотелось.
Alex Schunk
если вы посмотрите на код IL, то увидите, что foreach имеет накладные расходы. Если вам нужна производительность, используйте for (;;), потому что это в основном просто прыжки.
Все, что делает ваш код красивым, чистым и легким для чтения, обычно связано с накладными расходами.
Вы всегда должны выбирать между ремонтопригодностью, повторным использованием и производительностью. Вы не можете иметь одно, не влияя на другое.
yield показывает свою силу на больших коллекциях, где вы не проходите через все его элементы.
Вы можете найти то, что вам нужно, в "небезопасном" мире C#.
honey the codewitch
Мне наплевать на то, что они крутятся у меня над головой.
Посмотрите на статью по ссылке. Дело не в небольшой накладке.
Речь идет о временной сложности O(m+n) , где m - количество элементов в первой последовательности, а n-количество элементов во второй последовательности. И это становится еще хуже, когда вы гнездитесь, самый внешний вызов-O(m+1). Следующий вызов имеет O((m-1)+1), затем O((m-2)+1),... О(1+1). Существует m таких вызовов, поэтому время выполнения должно быть O(m^2). По сути, сочинение concats вместе, как это приводит к О(М^2) доход должен быть казнен.
(из статьи, с графиками производительности)
Alex Schunk
Что ж... Реализация доходности выглядит так.. Это накладные расходы, о которых я говорю...
bool IEnumerator.MoveNext()
{
bool result;
try
{
switch (this.<>1__state)
{
case 0:
this.<>1__state = -1;
this.<>s__1 = this.sequence1.GetEnumerator();
this.<>1__state = -3;
break;
case 1:
this.<>1__state = -3;
this.<item>5__2 = default(T);
break;
case 2:
this.<>1__state = -4;
this.<item>5__4 = default(T);
goto IL_101;
default:
return false;
}
if (this.<>s__1.MoveNext())
{
this.<item>5__2 = this.<>s__1.Current;
this.<>2__current = this.<item>5__2;
this.<>1__state = 1;
return true;
}
this.<>m__Finally1();
this.<>s__1 = null;
this.<>s__3 = this.sequence2.GetEnumerator();
this.<>1__state = -4;
IL_101:
if (!this.<>s__3.MoveNext())
{
this.<>m__Finally2();
this.<>s__3 = null;
result = false;
}
else
{
this.<item>5__4 = this.<>s__3.Current;
this.<>2__current = this.<item>5__4;
this.<>1__state = 2;
result = true;
}
}
catch
{
this.System.IDisposable.Dispose();
throw;
}
return result;
}
Но, глядя на этот код, я не могу толком объяснить, откуда берется O(m2).
honey the codewitch
вы можете поспорить с парнем из команды разработчиков C#, который написал статью, на которую я ссылался.
но я не вижу необходимости в том, чтобы перевоспитывать его.
Alex Schunk
Зачем мне это делать?.. Ты сам задал этот вопрос... Вы в основном говорите, что хотите альтернативу, но нет, потому что вы хотите уступить... Я не знаю, чего ты на самом деле хочешь.
Каждый сахар, который вы получаете, вы получаете некоторые недостатки... Потому что выход-это не что иное, как синтаксический сахар.
Если вы хотите, чтобы он был эффективным, создайте свой собственный.
Это похоже на ObservableCollection в WPF... он очень медленный, и добавление к нему 1000000 элементов убьет ваше приложение. Я создал свой собственный, который может справиться с этим. Без проблем.
honey the codewitch
вы спорили с выводами Уэса Дайера, а не с моими. Вот почему я сказал, чтобы вы с ним поспорили.
honey the codewitch
кроме того, причина накладных расходов заключается в том, что эти два внутренних итератора - также выходы, могли бы быть свернуты в этот класс. вместо этого у вас есть 3 класса, каждый из которых работает со своими собственными государственными машинами. это приводит к всплескам на графике perf, как уже показывает Уэс Дайер по ссылке.
если только вы не хотите назвать его perf графики ложью
Richard Deeming
Если вы посмотрите на график, он будет довольно плоским, пока вы не начнете объединять ~1500 одноэлементных последовательностей.
Как часто ваш код делает это?
honey the codewitch
как это типично для большого количества запросов LINQ, так и мой код глубоко вкладывает эти операции.
так что да, это проблема.
да, и в зависимости от коллекции мы имеем дело с такими вещами, как правила LR, так что 1500-это даже не редкость
Alex Schunk
Общеизвестно, что создание большого количества счетчиков сильно бьет по производительности.
Вот почему вы разрабатываете свой код мудро. В тех местах, где вам нужна производительность, вы в основном делаете это сами.
Рекурсивные вызовы, например с LINQ, в большинстве случаев не очень хорошая идея.
honey the codewitch
я не использую LINQ именно из-за этого.
> прямо сейчас я раздаю много перечислений, потому что производительность LINQ неприемлема для широкого использования в таких вещах, как Парсеры GLR, и отчасти это ограничение доходности.
Но это просто много работы *не*, чтобы использовать его.
Вот почему мне кажется все более привлекательным отойти от C# и вернуться к неуправляемому коду.
мех
Alex Schunk
На самом деле вы можете создать универсальное расширение, которое имеет дело с этим.
honey the codewitch
не обошлось и без переписывания почти всего linq и выполнения кода gen на всех итераторах вместо того, чтобы полагаться на yield.
я уже думал об этом.
Alex Schunk
Так что ваш вариант был бы... Дождитесь нового выпуска C#... Или перейти на другие, более эффективные языки.
honey the codewitch
именно это я и предполагал.
вопрос состоял в том, чтобы проверить это предположение.
я предпочитаю задавать вопросы, прежде чем делать выводы.
Richard Deeming
Не обращайте внимания на производительность - Ваш метод не делает того, что он утверждает. Предполагается, что объединение двух последовательностей должно вернуться уникальный элемент из обеих последовательностей. Ваш метод возвращает все элементы, и их следует называть Concat.
honey the codewitch
ладно, это называется конкат.
вопрос остается в силе. потому что Союз - это не главное. перф-это главное.
переименуйте его в concat, если это поможет вам ответить на вопрос, который я задал.
и если у вас нет ответа, это прекрасно.
Richard Deeming
Как я уже сказал в своем другом комментарии, это довольно нишевый случай. Большинство кодов не объединяют 1500+ небольших последовательностей, так что это обычно не проблема.
Если из-за этого ваш код сталкивается с проблемами производительности, вы мало что можете с этим поделать. Вы могли бы увидеть, если бы Команда C# [^] заинтересованы в том, чтобы забрать yield foreach идея; но даже если это так, может пройти много месяцев, прежде чем это войдет в основной компилятор.
В противном случае вы застряли в написании конкретных итераторов, чтобы уменьшить узкие места производительности в вашем коде.
honey the codewitch
что я и делаю. в настоящий момент.
и это побочный эффект программирования вещей, которые сильно зависят от операций на основе наборов, как, например, большинство генераторов синтаксических анализаторов.
и да, будь то LALR(1), LL(x) или даже FAs, там будет много итераций и функций набора.
Природа зверя.
обычно я использую STL в C++, чтобы делать такие вещи.
но по причинам, которые выходят за рамки этого, я перенес много исследовательского кода на C#. Это включает в себя компилятор/синтаксический анализатор.
Как я уже сказал, Если у вас нет ответа, это нормально.
Честно говоря, я и не ожидал, что у кого-то он будет.
Но это хорошая идея, чтобы проверить ожидания, особенно учитывая, что я обычно не путаюсь с новыми функциями языка C#.
поэтому я и задал этот вопрос.
Alex Schunk
Что ж... Я часто использую LINQ и компенсирую потерю производительности в некоторых местах с помощью "Parallel.Инструкция foreach".
honey the codewitch
если бы я писал бизнес-логику или что-то в этом роде, они, вероятно, были бы в порядке, даже на стороне сервера.
но то, что я делаю, ближе подходит к инструментам компилятора/синтаксического анализа и системам обучения (вместе) - которые, к сожалению, имеют тенденцию вкладывать гораздо больше и, как правило, требуют немного большей скорости реагирования "в реальном времени" по сравнению с отображением веб-поиска или чего-то еще.
(разные типы производительности в основном из-за разных проблемных областей)
и хотя мой код не делает что-то вроде DSP/цифровой обработки сигналов, где действительно необходима быстрая потоковая передача, он в основном находится где-то между этим и более крупными, более короткими проблемами производительности при работе с большинством приложений, особенно с приложениями, основанными на бизнес-данных, такими как многие веб-приложения, для чего предназначены многие функции .NETs.
Alex Schunk
Не лучше ли использовать Rust или другой язык, который не использует виртуальную машину?
honey the codewitch
я не думаю, что проблема заключается в виртуальной машине.
это больше похоже на то, как работают iterator/yield и linq.
материал прекрасно работает, когда я его раскатываю вручную.
honey the codewitch
одна из причин, по которой я задаю этот вопрос, заключается в том, чтобы определить, насколько полезно было бы выпустить инструменты генерации, которые я создал и использую для решения этой проблемы. они ужасно неполированные и работают для моих узких сценариев. но они помогают мне обойти эту проблему.
другая причина, по которой я задаю этот вопрос, заключается в том, что мне не нравится использовать сгенерированный код для этого в определенных областях моего источника, поэтому я разработал некоторые шаблоны для работы с использованием foreach/yield everwhere, но эти шаблоны выглядят "глупо", если вы не знаете, почему я это делаю. они выглядят как анти-паттерны. Мне не нравится код, который выглядит как анти-паттерны. Я начинаю подозревать даже свой собственный код. =) Я также склонен предполагать, что я немного глуп по сравнению с людьми, которые разработали этот язык. это держит меня достаточно скромным, чтобы делать предположения в правильном порядке, а именно, сначала предполагать ошибку или невежество с моей стороны, поскольку это наиболее вероятно.
Richard Deeming
Похоже, это уже было запрошено:
Запрос функции: рекурсивные итераторы (неквадратичные)[^]
Еще одна проблема, связанная с производительностью итератора:
ValueEnumerables (быстро кодировать и запускать)[^]
honey the codewitch
полезно! спасибо