tyrotoxin Jan 14 2013 at 14:03

Предельная производительность: C#

56 min

261K

High performance*Programming*Concurrent computing*

From sandbox

+45

289

Comments 289

dixx Jan 14 2013 at 14:10

Пункт 5 про if для простых арифметических операций некорректен.

Точнее, когда-то давно всё было действительно так, но тот же x86 давно поддерживает инструкции CMOVxx (conditional move), которые не приводят к сбрасыванию конвейера, в отличие от инструкций переходов, и выполняются быстро. В результате, например, конструкция условного вида max(a, b) { if (a > b) { return a } else { return b } } выполняется примерно вдвое быстрее её аналога без if. Хотя раньше подобная оптимизация имела бы смысл. Не далее как вчера это проверял :)

tyrotoxin Jan 14 2013 at 14:32

Не могу не согласится насчёт CMOVxx, но не забывайте что статья про C# — здесь код компилируется в IL, а потом в инструкции (причём JIT должен делать это быстро). Будет ли там CMOV — нужно смотреть от случая к случаю.
Насчёт примера «int CompareBytes(byte a, byte b)», я проверял на практике при написании статьи — на моей машине работало ровно в 2 раза быстрее, не обманываю :) А если с CMOV — ещё раз этак в 2,5 быстрее (точно уже не помню). Поэтому и написал «определённых местах может», а не «всегда будет лучше» :)

dixx Jan 14 2013 at 14:37

Это говорит не в пользу C# :) Я это проверял на JVM и просто на коде на Си и в обоих случаях всё заканчивалось именно CMOVxx. Причём, с точки зрения разработки компилятора (в том числе и JIT) оптимизация короткого if'а в CMOVxx есть куда более тривиальная задача, чем оптимизация арифметического аналога.

mejedi Jan 20 2013 at 11:08

Линус считает, что CMOV не очень хорош.

Ringess Jan 14 2013 at 14:11

«в % раз быстрее» — это как? Оо

tyrotoxin Jan 14 2013 at 14:14

Вместо "%" подставляете число в колонке. Это лучшее сокращение, которое я мог придумать для названия :)

OpenMinded Jan 14 2013 at 15:29

Как насчет X?

tyrotoxin Jan 14 2013 at 15:49

Ну вы уже знаете, что такое "%", зачем вам «Х»? :)

ad1Dima Jan 15 2013 at 01:41

Что бы те, кто ещё не до читал до комментов, не перечитывали по три раза заголовок столбца, например?

tyrotoxin Jan 15 2013 at 01:53

Надо устроить опрос «Кому понятно что такое % ?». Неужели «X» внесёт ясность? :)

-3

ad1Dima Jan 15 2013 at 02:02

Ясность внесёт «во сколько раз быстрее». X, по крайней мере, не напоминает о процентах.

shai_hulud Jan 14 2013 at 14:55

>Никаких «foreach»
Неверно, foreach для массивов генерирует такой IL который потом 100% оптимизируется GIT копилятором. Можно написать такой код руками, но многие ли знают условия при которых сработает оптимизатор?

>эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable
И это тоже не верно. Он создает объект/структуру который возвращает метод GetEnumerator, и это не обязательно должен быть класс реализующий IEnumerable. Только с аналогичной сигнатурой. Такой вот duck typing.

>Единственный способ избежать этих проверок, написать «for» таким образом
И опять неправильный пример. Переменная с массивом должна быть локальной и неизменяемой.

>volatile
igoro.com/archive/volatile-keyword-in-c-memory-model-explained/

>Структуры, поля которых – только value types, легко сериализовать в массив байт и обратно.
Так делать нельзя по двум причинам:
а) это валидно только для blittable типов
б) разное выравнивание структур на разных архитектурах

в остальном у вас хорошие, годные советы.

+17

tyrotoxin Jan 14 2013 at 15:48

>Никаких «foreach»
Зачем надеятся на оптимизацию при каких-то условиях, если можно руками чётко написать именно то, что хочешь. Тем более, JIT compiler может быть разный (для Windows, XBox, Linux, и пр.) от разных производителей. Кто сказал что все они одинаково работают?

>эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable
Вы неправильно поняли пункт. Это уже уточнения как можно использовать «foreach». Смысл в том, что в итоге у вас всё-равно 2 метода: MoveNext и Current. Именно об вызове методов я писал, ссылаясь на пункт 23 (я в тексте ссылаюсь на 24, сейчас исправлю, простите).

>Единственный способ избежать этих проверок, написать «for» таким образом
Вы ссылку смотрели на блог от Microsoft на словах «таким образом»? Там детально объясняется как можно. Что ж здесь неверного?

>volatile
Это детальное разъяснение к описанию? Не совсем понял.

>Структуры, поля которых – только value types, легко сериализовать в массив байт и обратно.
Почему нельзя? Туда можно ещё приписать Big/Little Endian, но всё это проблемы характерные для конкретных задач, о которых не шла речь. Если использовать такой подход для какого-нибудь временного кэша, то почему нельзя?

Я везде пытался как можно проще и короче пояснить основную суть, не вдаваясь в детали (а их очень много), о чём честно предупредил в начале статьи :)

-4

shai_hulud Jan 14 2013 at 16:39

Зачем надеятся на оптимизацию при каких-то условиях, если можно руками чётко написать именно то, что хочешь

Но ваше «руками чётко написать», будет почти всегда хуже того кода который генерирует компилятор foreach по массиву, и всегда хуже по читабельности. И в довесок сгенерированный компилятором код будет оптимизирован в .NET Framework, скорее всего и в моно.
Итого, foreach это не всегда зло, что противоположно вашему «Никаких foreach»

MoveNext и Current

Они не виртуальные и могут принадлежать структуре. т.е. нет будет замусоривания GC и лишней нагрузки от виртуальных методов. Единственный оверхед который можно учитывать это слежение за версией коллекции. Что может быть и плюсом.

Вы ссылку смотрели на блог от Microsoft на словах «таким образом»

Вы скопировали только кусок кода, причем вырванного из контекта. По нему можно сделать неправильные выводы и написать плохой код. Самый лучший способ попасть под оптимизацию проверок границ в цикле это использовать foreach

Это детальное разъяснение к описанию?

Нет, там пояснение зачем нужен(или кому-то ненужен) volatile. Причем эта тема нужна только о-о-о-очень небольшому кругу людей и должна быть освещена полностью а не одним абзацем. Можно к примеру обжечься думая что доступ к volatile переменной линеаризуемый.

Почему нельзя?

Ну я уже писал, ограничения на список возможных типов и то что было сериализованно на одной платформе не будет десериализованно на другой. Так что это не сериализация, а дамп(копия) представления в памяти.

centur Jan 14 2013 at 15:16

А можно не рассказывать про foreach такие страшилки про IEnumerable. Оно там ни разу не объязательное.
Это разжевывалось много раз. Вот еще один разок stackoverflow.com/questions/3679805/how-does-foreach-call-getenumerator-via-ienumerable-reference-or-via.

Jholinar Jan 14 2013 at 15:35

Иногда код упрощается не от незнания или неумения, а для простоты чтения и восприятия разработчиками. В общем, везде должен быть баланс, углубляться в в совсем уж жесткую оптимизацию и канонические правила разработки может привести к тому, что кд станет просто нк читабельным. Тем более, что благо сейчас системы мощные и часто выигрыш в производительности не всегда оправдывается затраченным на его цену временем разработчика.

lair Jan 14 2013 at 15:21

Начните с … 1. Хороший алгоритм.

Нет, начинать надо с того, что определить, где именно у вас боттлнек (и есть ли он вообще).

В данном примере метод «PrintInternal» вызывается только из метода «Print», где уже есть проверка. Это значит, что вторая такая же проверка не только не имеет смысла, но и негативно влияет на производительность.

Вторая такая проверка имеет смысл, потому что один и тот же код регулярно пишут разные люди. Другое дело, что, поскольку это находится внутри безопасной зоны, это должен быть не if, а Debug.Assert, который по очевидным причинам не влияет на скорость релизного кода. Более общий случай — все покрыть Code Contracts, а в рерайтере для релизной версии оставить проверки только на public surface.

Никаких «foreach» – эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable (чем плохо, описано в принципах 16 и 24).

Во-первых, «никаких foreach» — это уже смешно, большая часть кода внутри BCL построена на foreach, особенно в части доступа к данным. А уж весь LINQ без этого просто невозможен.

Во-вторых, смотрим в принципы 16 («Структуры, а не классы») и 24 («Виртуальные функции»). Не знаю, при чем тут виртуальные функции, а вот в части принципа 16 вы не правы. Во-первых, экземпляр IEnumerable не создается, а используется. Наверное, вы имели в виду IEnumerator? Так нет, это тоже не так, потому что это не обязан быть класс, а может быть и структура (что регулярно используется внутри BCL), и она не обязана реализовывать IEnumerator. Так что оба ваших принципа тут не при чем. Подробности — у Липперта.

Существует такой класс как ThreadPool, который является менеджером потоков, и вы с лёгкостью можете делегировать задачи без надобности постоянно создавать новые потоки, что в очередной раз хорошо для производительности. Здесь нельзя не согласиться, если речь идёт о простеньких приложениях, но если требуется серьёзная оптимизация – забудьте! Вам нужен либо свой менеджер асинхронных задач, либо готовые решения.

Вы про TPL слышали?

Представьте что у вас всего 2 ядра у процессора, и размер пула потоков тоже 2. Вы хотите выполнить 3 асинхронные задачи:

первая считает общее количество бит в большом массиве данных в памяти

вторая читает данные из сетевого протокола, и пишет на диск

а третья шифрует небольшое значение с помощью AES-256

… а про Producer/Consumer и TPL Dataflow?

Для устранения этих задержек достаточно создать свой класс Stream, который накапливает данные в буфер, а потом ставит его в очередь на запись в отдельном потоке. [...] А для конечного пользователя это будет тот же прозрачный интерфейс класса Stream.

Извините, но у Stream есть сразу два интерфейса — синхронный и асинхронный. И «прозрачно» подменять синхронный асинхронным нельзя, потому что сразу появляются неожиданные ошибки.

У структур есть ряд преимуществ перед классами

Во-первых, не все они корректны (в частности, структура не обязательно хранится на стеке). Во-вторых, давно уже написано: используйте структуры только в том случае, если вы очень хорошо понимаете, что делаете. В частности, не используйте mutable struct (как и вообще mutable value types), потому что это приводит к трудно отлавливаемым багам. Собственно, вот хороший ответ про это.

Поэтому в таких языках, как C++ есть модификатор метода inline, который указывает компилятору, что тело метода необходимо вставить в вызывающий метод. Правда, и в .NET Framework только с версии 4.5 наконец-то можно делать inline методы.

А вы не в курсе, что в .net компилятор сам делает инлайнинг методов, если это возможно? И существенно раньше, чем в 4.5?

Приведу реальный пример, SqlDataReader в методе GetValue для колонки с типом данных «xml» в конечном итоге вернёт вам String либо XmlReader. А задача состоит в том, чтобы сравнить два значения типа «xml» из двух разных источников. Вроде бы ничего особенного – взял да и сравнил две строки, да ещё можно использовать StringComparison.Oridnal чтоб вообще быстро было.

Ну вообще — нет. xml нельзя сравнивать как строки, у него свои алгоритмы нормализации и каноникализации. И уж тем более — как байтовые массивы, которые приходят из БД. Не надо нарушать семантику.

Организовать список всех ключевых слов проще всего в Hashset. Тогда, чтоб проверить является ли токен ключевым словом, достаточно написать:
HashSet<string> keywords;
String tokenText;
bool isKeyword = keywords.Contains(tokenText.ToUpperInvariant());

Про new HashSet<T>(IEqualityComparer<T>) вы не в курсе?

Ну и так далее.

В общем, возвращаясь к началу: сначала надо найти боттлнек. Потом оптимизировать его стандартными средствами платформы. И только потом заниматься битьем в бубен.

+36

tyrotoxin Jan 14 2013 at 16:04

Можете рассуждать сколь угодно в рамках своих познаний, но всё работает на практике, причём есть реальное приложение, которое работает лучше всех. Всё было кропотливо проверено за 3 года работы в этой области. А вы лично проверяли то, о чём сейчас написали? Есть доказательства высокопроизводительных приложений?

-21

lair Jan 14 2013 at 16:08

есть реальное приложение, которое работает лучше всех

Не «лучше всех», а в лучшем случае «быстрее всех». Да и то не факт.

Всё было кропотливо проверено за 3 года работы в этой области.

Утверждение с новым экземпляром IEnumerable — тоже? А доказать вы его можете? Для любого использования foreach?

А вы лично проверяли то, о чём сейчас написали?

Да.

PS Сперва добейся?

+18

shai_hulud Jan 14 2013 at 17:36

Ну вообще, у lair есть кое-какая репутация на хабре.
И в добавок я могу подтвердить его пост.

Есть доказательства высокопроизводительных приложений?

senchadotnet.codeplex.com
там есть JSON сериализатор, tip ревизия делает популярный JSON.NET на 15-20% по производительности. Тест внутренний, но довольно простой: сериализуется один и тот же большой объект, сериализатору дают генератор(yield) и пишет он в Null поток. В этом проекте полно оптимизаций, вплоть до генерации IL для сериализации конктретных объектов.

Причем как и написал lair в первую очередь был запущен профайлер, и потом уже пошли фиксы.

VladVR Jan 14 2013 at 23:42

Хочу не согласиться про XML. Поскольку речь идет о синхронизации/клонировании/репликации данных, то побайтовое сравнение перед полным сравнением имеет смысл. Контекст использования определяет валидность этой оптимизации. На основе этого сравнения можно сделать очень быстрый вывод о равенстве. А для вывода о неравенстве уже полное сравнение. Кстати это сравнение схоже со сравнением хэша во всяких HashSet, HashTable и т.п., только там наоборот, сравнение хэша может дать вывод неравенства, а для вывода равенства нужна полная проверка.
Мне больше интересно, почему никто на «поверьте, коллизий не будет» не обращает внимания. Вот это точно оптимизация за гранью приличий. Что тем более с применением оптимизаций с индексированием и асинхронным разбором теряет смысл.

lair Jan 15 2013 at 00:17

Хочу не согласиться про XML. Поскольку речь идет о синхронизации/клонировании/репликации данных, то побайтовое сравнение перед полным сравнением имеет смысл

Нет. Потому что байтовое представление xml внутри колонки соответствующего типа — это личное дело SQL Server, и оно имеет право отличаться между двумя инстансами.

Сравнивать нужно именно семантическое представление данных. Если мы храним данные как xml (т.е., разобранное), значит, нам интересно именно дерево (более того, SQL может возвращать разные варианты строкового представления этого дерева в разных случаях); а если бы нам было интересно именно строковое представление (например, для некоторых видов ЭЦП), то надо было бы хранить nvarchar.

Мне больше интересно, почему никто на «поверьте, коллизий не будет» не обращает внимания.

Я обратил. Но поскольку я вообще всю эту оптимизацию считаю ересью (а делать надо через свою реализацию сравнения), я не стал на этом заострять.

tyrotoxin Jan 15 2013 at 00:33

Нет. Потому что байтовое представление xml внутри колонки соответствующего типа — это личное дело SQL Server, и оно имеет право отличаться между двумя инстансами.

Т.е. вы утверждаете, что два одинаковых массива байт могут представлять различные XML данные? Вот это новость!

Но поскольку я вообще всю эту оптимизацию считаю ересью...

Мне нечего сказать, кроме как «Статья явно не для Вас». Вы даже не проверяли ни капли сказанного (ну и не будете — зачем это вам надо), а заявляете что это ересь. Ваши выводы основываются на субъективной оценке, и не несут никакой пользы.

-3

lair Jan 15 2013 at 00:46

Т.е. вы утверждаете, что два одинаковых массива байт могут представлять различные XML данные?

Нет, я утверждаю, что два разных массива байт могут представлять одни и те же xml-данные.

Вы даже не проверяли ни капли сказанного (ну и не будете — зачем это вам надо), а заявляете что это ересь.

Во-первых, вы не можете доказать, что я проверял, а что нет (равно как и не можете доказать своих собственных слов, смотри пример с экземпляром IEnumerable). А во-вторых, это вы зачем-то предлагаете в качестве бейзлайна вариант с string.ToUpperInvariant (и расписываете его недостатки), хотя любому грамотному программисту известно, что использовать надо вариант со своим компарером (в котором могут быть любые оптимизации, в том числе и ваш код). И только если это окажется медленно, надо брать ваш вариант и сравнивать производительность.

Вот это — объективно.

tyrotoxin Jan 15 2013 at 01:22

Нет, я утверждаю, что два разных массива байт могут представлять одни и те же xml-данные.

Хорошо, значит, два идентичных массива байт представляют один и тот же XML. Почему тогда нельзя сравнивать два массива байт? Объясните?
Ну а если массивы разные — то будет сравниваться структура XML — об этом написано в статье. Вы думаете о чём пишете?

хотя любому грамотному программисту известно, что использовать надо вариант со своим компарером

Да будет известно грамотному программисту, что перечисление StringComparison содержит 6 значений, и у каждого есть своё применение. А то что вы пишете «использовать надо вариант» — за это надо наказывать программистов, если они лепят это везде. И если вы ознакомитесь со стандартом Unicode, сравнением строк (string collation algorithm), то тогда вы поймёте о чём всё же я писал…

-1

lair Jan 15 2013 at 11:14

Ну а если массивы разные — то будет сравниваться структура XML — об этом написано в статье. Вы думаете о чём пишете?

Да, думаю. Во-первых, я не уверен, что это предложение изначально было в статье. Но даже если было — вы тем самым делаете два сравнения вместо одного, что очень выгодно на xml в пару десятков мегабайт.

Да будет известно грамотному программисту, что перечисление StringComparison содержит 6 значений

А при чем тут вообще StringComparison, если я говорю о компарерах? Я ведь не зря привел сигнатуру конструктора (new HashSet<T>(IEqualityComparer<T>)). Что характерно, там есть и сам алгоритм сравнения объектов (где можно ничего нового не создавать и использовать произвольную математику), и алгоритм расчета хэш-кодов. И именно так реализуются «нестандартные» хэшсеты, а не написанием своего внешнего метода — программист продолжать видеть, что он работает с привычным ему хэшсетом, но логика сравнения внутри оптимизируется.

Это как раз пример типичного велосипедостроения без желания внимательно прочитать документацию (даже в исходники лезть не надо).

VladVR Jan 15 2013 at 15:13

Два сравнения вместо одного, это да, несомненно. Также, как и при поиске объектов в хэшсете, сначала сравнивается хэш, потом сам объект, сравнения тоже два.
Побайтовое сравнение этак в десяток раз быстрее, чем полное(навскидку).
Если есть 1000 пар xml-ек, из которых сотня была изменена со времени последней синхронизации, то вместо 1000 единиц времени, мы получим, что 900, оставшись неизменными, ускорились в 10 раз, то есть 90 условных единиц времени, а 100 оставшихся замедлились на 10%, то есть итого 200 единиц времени вместо 1000.
Плюс к этому, в изменившихся xml файлах вероятность того, что изменился и размер тоже — почти 100%, то есть побайтовая проверка займет околонулевое время, и перейдет сразу к полной проверке.
Итого худший случай — замедление на 10%, лучший случай — ускорение в 10 раз. Как мне кажется все же такая оптимизация имеет смысл. Правда, конечно же, надо сделать замеры на средневзятой xml-ке, чтобы вместо 10ки получить реальный коэффициент.

lair Jan 15 2013 at 15:17

мы получим, что 900, оставшись неизменными, ускорились в 10 раз

Кто вам это сказал? Вы исходите из того, что бинарное представление, в котором xml передается от сервера в IDataReader одинаково для одинакового xml — а с чего вы это взяли?

VladVR Jan 15 2013 at 16:39

Предположение тут такое, что если взять xml из одной базы(1) и положить в другую, и потом извлечь ее(2), то (1) и (2), будут до байта cовпадать.
Автор конечно обманывает себя и других, говоря что оптимизирует что то «зная как это работает». Так и в данном случае это чисто практическая оптимизация без доли теории. Но мне кажется, что это работает. Проверять, если честно, уже лень.

lair Jan 15 2013 at 16:46

Что будет до байта совпадать, транспортное представление xml внутри SqlDataReader? А почему?

ivanov Jan 15 2013 at 18:06

Предположу, что потому что версии SQL Server одинаковые, они одинаково обрабатывают входящие данные.

Генератор случайных чисел, который выдаёт неслучайные числа, это не ошибка реализации, это так задумано было, чтобы можно было повторить.

Я тоже полагаю, что сравнение двух массивов байтов перед сравнением XML даст огромный прирост производительности. Если не даст, надо делать какие-то трюки и всё равно приходить к тому, чтобы сравнивать не XML, а что-то попроще.

Эта статья про то, как одни безрукие программисты тягались с другими безрукими программистами, тем не менее, я считаю, что спор про сравнение массивов вы проиграли =)

lair Jan 15 2013 at 18:12

Предположу, что потому что версии SQL Server одинаковые, они одинаково обрабатывают входящие данные.

А почему версии одинаковые? А ничего, что это для них не входящие, а исходящие данные, а обрабатывает их клиентский код?

Я тоже полагаю, что сравнение двух массивов байтов перед сравнением XML даст огромный прирост производительности.

С этим никто не спорит. Но только надо понимать, в каких граничных условиях этим можно пользоваться. Если бы речь шла о файлах на диске, я бы вопросов не задавал.

ivanov Jan 15 2013 at 18:36

Одинаковые, потому что уверен, что они не ставили разные версии для тестирования =) Замеры на базе в 200 метров, а в предисловии про терабайтные базы — думаю, что разные версии серверов не такой забавный челлендж будет, как проблема локальности, когда продукт конкурентов перестанет отставать =)

Про сравнение массивов — они просто в начале пути, я полагаю =) Про понимать — это нужно обычно везде ;)

lair Jan 15 2013 at 18:38

Одинаковые, потому что уверен, что они не ставили разные версии для тестирования

Это означает, что результаты в тестовой среде и в продуктивной могут приятно удивить.

думаю, что разные версии серверов не такой забавный челлендж будет, как проблема локальности, когда продукт конкурентов перестанет отставать

Я тоже так думаю.

tyrotoxin Jan 15 2013 at 22:42

уверен, что они не ставили разные версии для тестирования

Воспринимаю как плохой отзыв обо мне и моих коллегах — вы сильно наc недооцениваете. Мы занимаемся минрацией баз данных с различными версиями серверов.

А на самом деле, достаточно заглянуть в код SqlDataReader — там есть метод, который десериализует массив байт в XML, и он одинаков для всех версий SQL Server.

И сразу в этом комменте допишу, что при сравнении баз обычно отношение изменишевся данных к идентичным составляет маленький процент, поэтому побайтовое сравнение даёт существенный прирост производительности.

ivanov Jan 16 2013 at 08:41

Да нормально я вас оцениваю =) Вы выложили тесты на базе 200 мегабайтов, это не очень разумно, слишком мало данных.

Одинаковые версии серверов это не самое страшное, я бы для первичного тестирования сделал то же самое.

Со сравнения массивов я и начал переписку с вашим оппонентом, считаю, что в этом споре он неправ.

tyrotoxin Jan 17 2013 at 14:50

Со сравнения массивов я и начал переписку с вашим оппонентом, считаю, что в этом споре он неправ.

Спасибо, я заметил. Я просто решил все мысли в одном коментарии написать, это был не упрёк в вашу сторону =)

VladVR Jan 15 2013 at 07:55

Но эта «оптимизация» действительно ересь. Во первых при сравнении строк, начиная с фреймворка 3.5 строки побайтово не сравниваются. Сравнение строк эквивалентно сравнению ссылок, и по времени оно занимает столько же, сколько и сравнение хэш кодов. То есть сравнение строк все равно присутствует, но на тот момент, когда мы пишем a==b или mySet.Contains CLR это сравнение уже сделал. Кроме этого, я не понял, зачем вообще приводить к верхнему регистру? SQL код же генерится своим же приложением, почему бы сразу в нем все ключевые слова не сделать в верхнем регистре? Лишнее действие оптимизировать можно в зародыше. И последнее, собственно почему это ересь — допустим между SELECT и INSERT совпадений хэша не будет, но как можно довериться тому, что совпадений не будет в произвольном тексте, извлеченном из бд? Рано или поздно лексер подсветит какое нибудь левое слово, да еще с опечаткой(чтоб ваш тест со словарем обойти), как будто оно ключевое.

tyrotoxin Jan 15 2013 at 13:22

Вас нужно тыкнуть носом?

код из mscorlib

class String {
    public bool Equals(string value)
    {
    	if (this == null)
	{
		throw new NullReferenceException();
	}
	return value != null && (object.ReferenceEquals(this, value) || (this.Length == value.Length && string.EqualsHelper(this, value)));
    }
}

private unsafe static bool EqualsHelper(string strA, string strB)
{
	int i = strA.Length;
	if (i != strB.Length)
	{
		return false;
	}
	char* ptr = &strA.m_firstChar;
	char* ptr2 = &strB.m_firstChar;
	bool result;
	while (i >= 12)
	{
		if (*(long*)ptr != *(long*)ptr2)
		{
			result = false;
		}
		else
		{
			if (*(long*)(ptr + (IntPtr)8 / 2) != *(long*)(ptr2 + (IntPtr)8 / 2))
			{
				result = false;
			}
			else
			{
				if (*(long*)(ptr + (IntPtr)16 / 2) == *(long*)(ptr2 + (IntPtr)16 / 2))
				{
					ptr += (IntPtr)24 / 2;
					ptr2 += (IntPtr)24 / 2;
					i -= 12;
					continue;
				}
				result = false;
			}
		}
		return result;
	}
	while (i > 0 && *(int*)ptr == *(int*)ptr2)
	{
		ptr += (IntPtr)4 / 2;
		ptr2 += (IntPtr)4 / 2;
		i -= 2;
	}
	result = (i <= 0);
	return result;
}

-1

lair Jan 15 2013 at 13:49

Осталось сказать, в каких именно случаях (а) вызывается Equals (в частности, вызывается ли он внутри HashSet) и (б) неверно условие object.ReferenceEquals(this, value).

VladVR Jan 15 2013 at 14:48

Вместо тысячи слов

static void Main(string[] args)
        {
            string[] z = 
            new string[] { "abc"//воткнуть любой набор строк  };
            Stopwatch watch1 = new Stopwatch();
            Stopwatch watch2 = new Stopwatch();

            HashSet<String> str = new HashSet<String>();
            HashSet<int> dig = new HashSet<int>();
            foreach (var s in z)
            {
                str.Add(s);
                dig.Add(s.GetHashCode());
            }
            int a = 7;
            watch2.Start();
            for (int n = 0; n < 10000000; n++)
                if (dig.Contains(z[0].GetHashCode()))
                    a--;
            watch2.Stop();
            watch1.Start();            
            for(int n =0;n<10000000;n++)
                if (str.Contains(z[0]))                
                    a++;
            watch1.Stop();
 

            Console.Write(string.Format("str {0} int {1} a {2}",watch1.Elapsed,watch2.Elapsed,a));
            Console.ReadKey();
        }

Профайлер это еще полбеды, но замеры «до» и «после» все же надо делать?

tyrotoxin Jan 15 2013 at 22:56

Только ваш код не решает никакой задачи. Вы не верно понимаете условия реального test case: при разборе текста лексер возвращает новые объекты String, поэтому Object.ReferenceEquals никогда не вернёт true.

VladVR Jan 15 2013 at 23:09

Я предлагаю вписать нужный набор строк, в т.ч. в .Contains() и убедиться, что это не так.

Подсказать что вернет этот код?

ReferenceEquals("abcd","ab"+"cd");

VladVR Jan 15 2013 at 23:16

Разверну ответ немного. Вписать предполагается «SELECT», «INSERT» ну и еще что то до кучи

tyrotoxin Jan 15 2013 at 23:20

Подсказать что вернет этот код?
ReferenceEquals(«abcd»,«ab»+«cd»);

Подсказать почему?

lair Jan 15 2013 at 23:21

Этот пример некорректен, потому что он опирается на string interning, который работает на этапе компиляции.

Другое дело, что в лексерах как раз надо делать интернинг, просто вручную, благо это просто.

tyrotoxin Jan 15 2013 at 23:23

да вас бы убили за такой код :)
представьте скрипт с данными размер несколько сотен MiB. Вы будете для каждого токена делать Intern, чтобы просто сработал Object.ReferenceEquals?

lair Jan 15 2013 at 23:29

Не, для того, чтобы уменьшить бессмысленную нагрузку на память.

Новообще, конечно, я бы сначала написал в лоб, а потом уже смотрел.

xXxVano Jan 17 2013 at 10:29

Тоже сперва так подумал, но потом запустил код и увидел немного другой результат :)
Проблема в том что при поиске по числу (хешкоду от строки) Вам придется сначала его рассчитать, а потом уже искать по нему. В случае же поиска по строке точно тоже самое за вас сделает HashSet. По-этому оба варианта почти одинаковы.

lair Jan 17 2013 at 10:33

Вы точно не ошиблись с тем, куда написали свой комментарий?

xXxVano Jan 17 2013 at 10:49

Этот пример некорректен, потому что он опирается на string interning, который работает на этапе компиляции.

Вроде нет.

Интернирование он конечно использует но не в этом дело.

lair Jan 17 2013 at 10:52

Теперь посмотрите на код примера:

ReferenceEquals("abcd","ab"+"cd");

Где здесь хэшсет?

xXxVano Jan 17 2013 at 11:20

Да, пожалуй я все таки потерял мысль треда. Мне почему то показалось что ваш комментарий относится к этому.

tyrotoxin Jan 18 2013 at 16:07

Если искать по строке, то верно что будет расчитан hash code, однако при совпадении этого кода переданная строка будет сравниваться побайтого с той, которая лежит в HashSet (потому что Object.ReferenceEquals вернёт false).
Если искать сразу по hash code, то HashSet для расчёта hash code ключа типа int будет использовать само значени ключа типа int, и сравнивать строки не нужно — будут сравниваться значения типа int. Т.е. что-то типа такого:

int key = 12345; // pre-computed hash code for a string

bool Contains<T>(T key) { // where "T" is "int"
  int hashCode = key; // get hash code for "T" type, when it's "int"
  int bucketIndex = hashCode % bucketCount;
  int itemIndex = buckets[bucketIndex];
@loop:
  Item item = itemArray[itemIndex];
  if (item.Key == key) // Call operator '==' for 'T' type.
    return true;
  itemIndex = item.NextItemIndex;
  if (itemIndex >= 0)
    goto loop;
  return false;
}

lair Jan 18 2013 at 18:37

Не побайтно (сравниваться), а так, как задано в компарере.

tyrotoxin Jan 19 2013 at 07:22

Имелось в виду при использовании HashSet<T> без своего IEqualityComparer. А в GenericEqualityComparer как раз и вызываются стандартные методы Equals и GetHashCode.

Вы — самый настоящий тролль. В вашем коментарии я вижу всего один умысел — поумничать. Придраться можно абсолютно бесконечно к любой мелочи, чем собственно вы и занимаетесь. Вы бы ещё добавили, что Object.ReferenceEquals может вернуть true; что хэш коды на самом деле не сравниваются, что остатки от их деления являются индексами в массиве; что пример кода неправильный, там «if» не в том месте, и что bucketIndex может быть отрицательным; и т.д. и пр.

Прочитайте раздел «Специальное дополнение», которое я добавил в конец статьи. Может тогда вы станете добрее… :)

lair Jan 19 2013 at 12:41

Имелось в виду при использовании HashSet без своего IEqualityComparer.
А зачем использовать решение, заведомо не подходящее к задаче?

Прочитайте раздел «Специальное дополнение», которое я добавил в конец статьи.

habrahabr.ru/post/165729/#comment_5742425

shai_hulud Jan 17 2013 at 11:44

Выражение:
ReferenceEquals(«abcd»,«ab»+«cd»); // true

Компилируется в:
L_0001: ldstr «abcd»
L_0006: ldstr «abcd»
L_000b: call bool [mscorlib]System.Object::ReferenceEquals(object, object)

Так что правильнее:
ReferenceEquals(«abcd», string.Concat(«ab», «cd»)); // false

noldo32 Jan 19 2013 at 18:01

Просто преступно создавать подобный код, в то время как даже у 8086 уже была хардверная команда CMPS для сравнения строк! (потом появились команды CMPSD и CMPSQ для сравнения 32-битными и 64-битными блоками соответственно, что ускорит сравнение мегабайтных строк).
Подобный код — ответ на вопрос, почему процессоры становятся мощнее, а толку — нет.

tyrotoxin Jan 15 2013 at 13:28

что совпадений не будет в произвольном тексте

Здесь согласен, в статье приведён код, который специально написан для неё. К тому же, он вырван из контекста, поэтому логично сделать такое предположение. Эта проблема решена очень просто. Я не хотел писать лишний код в статье, чтобы он не мешал чтение основного. Тем не менее, это не отменяет саму суть оптимизации.

FuriCuri Jan 14 2013 at 15:32

Превентивная оптимизация да ещё и без профайлинга? Выводы об эффективности «оптимизации» на базе black-box замеров двух разных систем? Да вы шутите. Вот не дай бог начинающие программисты начитаются подобных «советов».

+34

tyrotoxin Jan 14 2013 at 16:08

> black-box замеров двух разных систем
Откуда такие сведения? Я точно знаю по какому алгоритму работает конкурентная сисетма. У меня было достаточно времени чтоб ознакомится с исходным кодом с помощью .NET Reflector.

> Да вы шутите
Out-of-box thinking ;)

-15

Illivion Jan 14 2013 at 15:49

13. Асинхронная запись.
А как же BeginRead и BeginWrite в FileStream или Socket? Эти операции выполняются асинхронно на уровне ОС.

tyrotoxin Jan 14 2013 at 16:05

Опять же, вы можете рассуждать сколь угодно. На практике проверяли? Думаете я просто так об этом всё писал, чисто из-за незнания .NET Framework?

-8

Illivion Jan 14 2013 at 16:16

Я не рассуждаю. А сообщаю информацию, почерпнутую из достоверных источников, коим я считаю и Рихтера, который рекомендует пользоваться асинхронными операциями для FileStream, NetworkStream и Ко. В статье же, на мой взгляд, предлагается создать свой велосипед и бороться с ветряными мельницами. Вы, наверное, очень много и долго писали ранее на С++ =)

tyrotoxin Jan 14 2013 at 17:10

На самом деле многие серъёзные компании изобретают велосипеды, даже если есть уже что-то готовое и отлично спавляющееся с задачами, и тут скрывается много причин. Они готовы переходить с .NET или Java на С/С++ ради достижения наивысшего качества продукта.
Я, конечно же, не собираюсь учить программированию на C#, просто хочу показать как можно писать на С++ используя C# :) Если бы была возможность, я бы написал программу на С++.

-3

Illivion Jan 14 2013 at 17:41

Не спорю. Но прежде чем приступать к разработке продукта, необходимо выбрать инструмент, соответствующий задаче. Если стоит задача обрабатывать гигабайты данных в реальном времени, то имеет смысл продумать путь каждого байта. Выбрать минимально необходимые размеры структур, избежать копирования, внедрить быстрые алгоритмы и озаботиться вопросами оптимизации при компиляции. Да что тут говорить — иногда внедрение asm кода, значительно увеличивает производительность приложения. А что из этого следует? Что в качестве инструмента нужно сразу выбирать С++, и не пытаться ставить профессиональные трековые покрышки на любительский велосипед.

«Далее, если вы знаете, что диапазон значений занимает всего 20 бит (от 0 до 1048575) и вам нужен «int» (32 бита), то вы можете использовать оставшиеся 12 бит для других целей, например для неких флагов.» — уместно в контексте программирования микроконтроллеров, но для шарпа, это просто аморально, на мой взгляд :). На шарпе можно оперативно писать код, который достаточно быстро работает в 99% случаев. И, главное то, что язык и платформа толкают к написанию кода для людей. «Не стоит стачивать лопату до маникюрной пилки.» =)

+10

ivanov Jan 15 2013 at 18:46

Когда у вас много параллельных чтений, нагрузка распределяется сама собой и никакого выигрыша от предложенной в статье «асинхронности» не будет. А когда читаете в один поток, разница будет зависеть от времени обработки — чем больше время обработки, тем больше разница, но не более, чем в два раза. Если вы читаете и пишете одновременно, разница будет до 4 раз.

lair Jan 14 2013 at 16:21

В ту же копилку:

И никогда, никогда не пишите в таком стиле
for (int i = 0; i < a.Count; i++) {
    int a = a[i];
    int b = a[i];
    int c = a[i];
}

Цитируем ту же статью, на которую ссылается сам автор поста (выделение мое):

In the method:
    static void Test_SimpleRedundant(int[] a, int i) {
        k = a[i];
        k = k + a[i];
    }
bounds-check code is generated for the first instance of “a[i]”, but not the second. In fact, the x86 JIT treats it as a common subexpression, and the first result is re-used.

Не надо пытаться быть умнее компилятора.

+10

tyrotoxin Jan 14 2013 at 17:12

Вы не поняли пункт. Я говорил об обращении к памяти.

также избежите лишних проверок границ массива (если таковые имеют место)

-5

lair Jan 14 2013 at 17:15

А что обращения к памяти? Вы (специально для вас выделенную) фразу про использование одного и того же первого результата не заметили?

tyrotoxin Jan 14 2013 at 17:21

Вы говорите про частный случай с типом int[]
Я нигде не указывал в своём коде, что переменная «а» — именно этого типа. Если это будет IList, или что угодно ещё, правило «the first result is re-used» уже может не работать.

-4

lair Jan 14 2013 at 17:26

Если это будет IList, или что угодно ещё, правило «the first result is re-used» уже может не работать.

А вы не задумывались о том, что в случае «что угодно еще» там и результат может быть разный, и поведение кода

int a = a[i];
int b = a[i];
int c = a[i];

может отличаться от

int t = a[i]
int a = t;
int b = t;
int c = t;

Так что для общего случая ваше решение некорректно. А для двух частных: когда нужно гарантированно одинаковое значение и когда нужно гарантированно текущее значение — код должен быть написан так, чтобы отображать это намерение.

Пламенный привет МакКоннелу и intention-revealing code.

lair Jan 14 2013 at 16:24

И там же:

Arrays implement the IEnumerable interface, which raises a reasonable question: if you enumerate over the elements of an array using C#’s foreach construct, do you get bounds checks? For example:
static int Test_Foreach(int[] ia) {
        int sum = 0;
        foreach (int i in ia) {
            sum += i;
        }
        return sum;
    }
Happily, we do eliminate the bounds checks in this case.

Привет «единственному способу избежать проверок».

leventov Jan 14 2013 at 16:29

На эту тему вспонинается история одной «оптимизации».

leventov Jan 14 2013 at 16:26

Скорее всего 95% прироста производительности вашей программы обеспечены 1-2 оптимизациями. Кроме того, зачем вообще упираться с оптимизацией этапов, которые заведомо работают пару секунд (что можно было понять по программе конкурента еще до начала разработки), если другие занимают пару минут.

tyrotoxin Jan 14 2013 at 16:45

Это ж на примере демобазы. В реальных базах конкурент справлялся с задачей где-то за 40 часов, а мы за 1 час 40 мин! Теперь разницу чувствуете?

-1

leventov Jan 14 2013 at 16:51

Что это меняет? Было бы интересно, если бы вы подробнее рассказали про самое горячее место в программе, которое сделало эту разницу, с сравнением реализаций конкурента и вашей.

tyrotoxin Jan 14 2013 at 16:58

Для конечных пользователей это много чего меняет :) Собственно, я для этого и написал основных 30 пунктов. Каждый из них привнёс в производительность свою долю. Я упоминал, что разработка велась сразу с учётом оптимизации, поэтому сложно говорить о самых горячих местах. Да, после первой реализации программа была уже быстрее конкурентов, а дальнейшая оптимизация была что-то вроде «надо выжать по максимуму».

-1

alan008 Jan 15 2013 at 09:42

Да возьмите же уже профайлер наконец и посмотрите. Тормоза, как правила, оказываются совсем не в том месте и по совсем не очевидной причине.

tyrotoxin Jan 15 2013 at 12:25

Зачем? Какие тормоза? Вы читали статью? Программа «летает» по сравнению со всеми конкурентами.

-2

lair Jan 15 2013 at 12:30

Сейчас уже незачем. А вот если бы вы это (профилирование) сделали в начале разработки, то, возможно, разработка и поддержка обошлись бы вам дешевле.

tyrotoxin Jan 15 2013 at 12:38

Вы советуете мне как распоряжаться средствами компании?
Вы знаете требования к приложению?
В начале разработки профилировать ничего не было — ведь кода ещё не было :)

-3

lair Jan 15 2013 at 13:50

Вы советуете мне как распоряжаться средствами компании?

Я советую вам (да и всем читающим) вести разработку в «правильном» порядке.

В начале разработки профилировать ничего не было — ведь кода ещё не было

Окей, я был неправ. Не «в начале разработки», а «на первом этапе разработки», т.е. после построения вертикального прототипа, проверяющего работоспособность алгоритма.

lexx2real May 20 2013 at 10:32

Зачем вы сводите до абсурда обсуждение, если прекрасно понимаете, о чем идет речь? Это как не тру. Кроме того вы имеете тенденцию задавать вопросы «о знании требований к приложению» даже когда это никак не влияет на суть темы. Если в требованиях была «скорость работы», то туда вы были тем более обязаны посмотреть.

alan008 Jan 15 2013 at 13:20

Просто статья получилась в духе «да здравствует premature optimization!!!»
Скорее всего применительно к (тормозному по умолчанию) .NET ваши советы действительно имеют смысл, но не дай бог вам сказать такое применительно к C++ или Delphi, вас просто освистают, т.к. все эти действия ничтожны по сравнению с полезными действиями, которые производит программа (читает/пишет данные на диск, передает данные по сети, общается с SQL-сервером (даже если MS SQL стоит на той же машине, что и программа, межпроцессное взаимодействие на порядок тормознее любых операций со строками в памяти вашей программы)).

Вы даже не представляете, сколько действий выполняется, чтобы найти в вашей строке “{0}” и подставить значение в указанном формате.

А вы представляете, сколько действий выполняется, когда вы отправляете один единственный (неподготовленный) SQL-запрос SQL-серверу? От количества этих действий просто с ума сойти можно (парсинг, построение и выбор оптимального плана выполнения, само выполнение, связанное, возможно, с обращением к диску), а ведь SQL-сервер выполняет сотни и тысячи запросов в секунду и ничего, как-то справляется.

-3

KvanTTT Jan 15 2013 at 16:17

Скорее всего применительно к (тормозному по умолчанию) .NET

Не надо, .NET не такой уж и тормознутый :)

ivanov Jan 15 2013 at 17:54

Вот-вот. Всего лишь сотни и тысячи запросов.
Вместо десятков тысяч на MongoDB, например.

Конкатенация раз в 50-100 примерно быстрее форматной строки для записи в журнал.
А если писать в журнал сразу байтики, без конкатенации, то будет быстрее в 1000 раз, чем с конкатенацией =)

Чтобы не писать бреда, который вы написали, надо получить опыт, а не прочитать где-то про плохую раннюю оптимизацию. С опытом приходит тайное знание, где оптимизация нужна, а где можно отложить на потом и доработать профайлером.

tyrotoxin Jan 14 2013 at 17:02

> Скорее всего 95% прироста производительности вашей программы обеспечены 1-2 оптимизациями
Это не так. Мы много смотрели в код конкурентов, и знаем что мы используем практически идентичные алгоритмы, просто для задачи сравнения данных в базе других особо нет. Насчёт асинхронности — да, тут есть хороший выигрыш, но даже без неё программа всё-равно в разы быстрее, благодаря остальным оптимизациям.

ToSHiC Jan 14 2013 at 16:31

Пункт 9 — менеджер задач уже встроен в ядро ОС. Если у вас много IO операций — либо делайте больше потоков, чем ядер, либо используйте асинхронное IO (что, суть, одно и то же). Писать свой менеджер задач в большинстве случаев не стоит.

Вторая половина пункта 11 тоже спорная, современные ОС умеют распределять процессы с учётом множества факторов.

Пункты 12-14 — опять же, в современных ОС есть readahead, writeback, pagecache… Не стоит советовать переписывать их. Лучше поставить в сервер побольше памяти :)

tyrotoxin Jan 14 2013 at 16:49

Не спорю. Я тоже говорю, что стоит вначале определится с требованиями к приложению, а только в самых необходимых случаях прибегать к хардкорным оптимизациям :)

ivanov Jan 15 2013 at 17:44

Самый быстрый способ работы с файлами это memory mapping.

Readahead, например, из вашего рассказа, это магия, недоступная простым смертным. Эту прекрасную неотключаемую «фичу» в ядре Линукса мы обычно закручиваем до минимума, потому что она упарывает производительность БД на ровном месте.
Когда поработаете с десятками гигабайтов данных, почувствуете «эффективность» и остальных перечисленных «фич». Статья про максимальную производительность, а не про лабораторные работы в школе.

ToSHiC Jan 15 2013 at 17:57

Readahead — это магия, которую уже сделали, просто пользуйтесь fadvise для указания профиля работы с данными. Мы юзаем и работает это хорошо. Если какая-то БД умеет работать с диском лучше, то пусть флашки указывает, или в документации пишут, как закрутить readahead. Если она только считает, что может работать лучше — то тут ещё непонятно, кто виноват в смерти диска по io.

Про десятки гигабайт данных — это вы мне написали, или автору статьи?

ivanov Jan 15 2013 at 20:19

Вызов fadvise завершается успешно, но ядро на это не обращает внимания.
MongoDB ничего не считает, просто использует memory mapping с соответствующим вызовом madvise. Виновата магия readahead, которую я не могу понять с давнишних времён первой встречи на рейд-контроллерах.

Писал вам, естественно =) Последний абзац указывает на то, что вы верите в магию. Что поможет readahead или там больше памяти. Это верно очень недолго, или на десктопных приложениях, когда постоянной нагрузки нет.
Суть затеи в том, если много писать просто так, в Windows заканчивается оперативная память. Гигабайты в час имелись в виду, а не вообще.

Написал и понял, что мы в разных мирах живём. В обсуждении статьи про ПО, тестируемое на 200 метрах данных вполне нормально давать советы поставить больше оперативки. Извините, что влез со своим представлением о высокой нагрузке.

ToSHiC Jan 15 2013 at 20:53

Наверное, в разных, да. И у нас почему-то readahead в линуксе работает хорошо. Может, потому, что мы не монгу используем? Надо только хорошо понимать, когда он хорош, а когда плох, когда надо как можно агрессивнее забивать pagecache данными, а что лучше не помещать туда, как расположить данные на диске, чтобы они быстрее считывались. Под заканчивающейся памятью вы что имеете в виду? А под гигабайтами в час — это запись на диск, или чтение? Какой размер каждой записи? Как именно они располагаются на диске?

Вы точно хотите меряться представлениями о высокой нагрузке?

ivanov Jan 15 2013 at 21:08

Они RA отключают, не помогает, только если его на всю систему закрутить до минимума, жить можно.

Под заканчивающейся памятью имею в виду именно заканчивающуюся доступную память, а что ещё можно иметь в виду? ;) Гигабайты записи просто файлов. В Windows. Как расположены, по барабану, это просто такая «оптимизация» для SMB, фиг отключишь. Writeback, который «решает все проблемы» =)

«Меряться представлениями» это прекрасно =)

ToSHiC Jan 15 2013 at 23:17

Идея readahead проста:
— прочитать с диска (обычного крутящегося, не SSD) несколько секторов занимает практически столько же времени, сколько и прочитать 1 сектор
— чаще всего данные читают последовательно

Конечно, нельзя придумать универсальные цифры подходящие под все условия, поэтому он адаптируется, отталкиваясь от базового значения, которое вы и меняете.

Если какое-то приложение плохо работает с readahead — то это означает либо то, что оно плохо работает с диском, либо оптимизировано для работы с SSD.

А зачем вам на машине свободная память? Они же не обязательно все грязные, большинство сразу сбрасывается на диск. Когда память понадобится — быстренько освободится. Во всяком случае, в линуксе так. Free памяти на сервере быть совсем немного, на десктопе можно побольше, но тоже нечего ей простаивать.

Вот, правдоподобные хорошие цифры (не мои, из интернетов):

$ free -m
             total       used       free     shared    buffers     cached
Mem:         96730      96418        311          0         71      93120
-/+ buffers/cache:       3227      93502
Swap:        21000         51      20949

Вы правда считаете, что это плохо?

ivanov Jan 16 2013 at 09:07

Про RA — диски шпиндельные, с секторами по 4к. В теории наверное да, несколько секторов прочитать времени занимает столько же, в реальности нет.

На практике, знаете ли, в здравом уме не читают последовательно блоками по 1 сектору, читают мегабайтами обычно. И пишут тоже. Есть нормальные понятные технологии, типа NCQ, чтобы ускорять доступ к диску. RA это магия.

Если какое-то приложение хорошо работает с RA, оно обычно работу с диском имеет третьестепенной важности — конфиг там прочитать или раз в час скинуть в журнал что-нибудь. То есть, ситуации, когда огромный относительный рост производительности выливается с смехотворные абсолютные значения.

Когда память понадобится — быстренько освободится.

В теории так, да =) Пока не столкнулся с этим, тоже так думал. В Linux свои «оптимизации», про доступную память при активной записи я говорил в Windows. В Task manager есть счётчик доступной памяти (Available), это чистые страницы или готовые в любой момент к возврату пользователю, грубо говоря, кэш чтения. Кэш записи просто так на диск не сбросить, особенно в контексте «поставить больше оперативки», когда скинуть на диск надо 90 гигабайтов. Free без разницы, какое значение имеет.

Конечно, я считаю, что это очень плохо, когда система всю свою оперативку использует под «грязные» страницы. Это плохо во всех отношениях, и пропадание питания чревато потерей очень большого количества данных, и доступной оперативки для приложений нет, и кэша чтения тоже нет.

ToSHiC Jan 16 2013 at 14:13

Начнём с того, что магия — это технология, которую вы не понимаете.

Итак, практика: 100 IOPS random read дадут вам 3 мб/с, 100 IOPS последовательных чтений дадут 30 мб/с при сравнимой latency. Что это говорит? Что время чтения 1 сектора сильно меньше времени позиционирования головки. У вас другая реальность? NCQ, кстати, замедляет доступ к диску, зато даёт возможность сделать больше IO операций в секунду. Latency при включении NCQ растёт, т.к. появляется ещё одна очередь запросов.

Читают и пишут обычно так, как удобно. Единственное, если читать по 100 байт — то количество сисколов будет слишком большим, и тормозить будет уже из-за этого. Но читать с диска сразу мегабайты/гигабайты, как-то кешировать внутри своей системы, следить за этим — это переписывать pagecache операционной системы. Особенно когда у вас индексы для данных перестают помещаться в память, ну очень нетривиальный код будет. Попахивает велосипедизмом.

Кстати, я разве где-то писал, что pagecache = writeback cache? Если какая-то из подсистем windows держит огроменный writeback cache — это, конечно, не всегда хорошо. Но обычно в pagecache мало грязных страниц, даже если вы интенсивно пишете на диск. Вот вам пример с реальной машинки:

$ free -m
             total       used       free     shared    buffers     cached
Mem:         64557      64232        324          0        227      57165
-/+ buffers/cache:       6838      57718
Swap:         4093          6       4087

sync делается каждые 30 секунд, так что там практически нету грязных страниц.

На другой машинке похожая картина:

$ free -m
             total       used       free     shared    buffers     cached
Mem:        193831     193037        794          0       1783      97128
-/+ buffers/cache:      94125      99706
Swap:         4102          0       4102

На неё постоянно сыпется нагрузка в несколько сотен запросов в секунду на чтение и запись, каждая по несколько килобайт.

Мне кажется, что очень даже хорошо — память используется, данные кешируются, и всё это делает ОС для меня. Коллега, linux kernel hacker, тоже считает, что надо по-максимуму использовать то, что даёт сама операционная система, и что её писали далеко не глупые люди. Но тем не менее регулярно находятся господа, которые пишут свой «TCP» поверх UDP, и в некоторых тестах их реализация работает действительно лучше TCP. Правда в других — сильно сливает, и именно поэтому стоит использовать TCP вместо своих велосипедов.

Кстати, на счёт вашего выпада в первом посте про десятки гигабайт… У меня обычно по полсотни терабайт данных на сервер. И по несколько сотен тебарайт на кластер.

ivanov Jan 17 2013 at 11:00

Магия это технология, которая не работает, как анонсируется. Конечно же, я знаю, как readahead работает. Последовательное чтение на серверах читают мегабайтами, а не как удобно. «Как удобно» делают только когда скорость не имеет значения.

Итак, практика: 100 IOPS random read дадут вам 3 мб/с, 100 IOPS последовательных чтений дадут 30 мб/с при сравнимой latency. Что это говорит? Что время чтения 1 сектора сильно меньше времени позиционирования головки. У вас другая реальность?

Это практика чего? Синтетического теста? У меня реальность другая, да. Чтения никогда не бывают без записей, такие нюансы придают бодрости на первой встрече с реальностью. Вы написали очевидный факт, непонятно зачем. Я утверждал исключительно о том, что readahead на сервере только вредит. В следующий раз, когда захотите блеснуть эрудицией, упомяните ещё промахи позиционирования головки, на современных дисках с ростом плотности актуальность всё больше.

NCQ, кстати, замедляет доступ к диску, зато даёт возможность сделать больше IO операций в секунду. Latency при включении NCQ растёт, т.к. появляется ещё одна очередь запросов.

Велик и могуч русский язык =) Увеличение задержки чтения и уменьшение количества прочитанных байтов есть замедление. Просто зависит от ситуации, что важнее.

Но читать с диска сразу мегабайты/гигабайты, как-то кешировать внутри своей системы, следить за этим — это переписывать pagecache операционной системы.

Последовательное чтение мегабайтами используется для последовательной обработки данных. Не надо ничего переписывать. Вы рассуждаете про общие теории ни о чём. Я утверждаю, что когда может помочь readahead, он не имеет смысла. И утверждаю, что вы агитируете за использование магии, потому что нет опыта её применения. Ни один из ваших «советов» нельзя применить к опыту, описанному в статье, потому что опыт на Windows и говорить «а вот у меня в Линуксе много пишется и с памятью всё хорошо» демагогия.

Особенно когда у вас индексы для данных перестают помещаться в память, ну очень нетривиальный код будет.

Когда у нас индексы перестанут помещаться в память, всё встанет колом =) Тем не менее, ручным кэшированием обычно заниматься, ясное дело, неразумно.

На неё постоянно сыпется нагрузка в несколько сотен запросов в секунду на чтение и запись, каждая по несколько килобайт.

Без деталей это данные ни о чём. Запросы к БД должны измеряться тысячами в секунду, обращения к просто файлам измеряться десятками килобайтов хотя бы (иначе зачем файлы?). Описанная вами ситуация ни рыба, ни мясо.

Коллега, linux kernel hacker, тоже считает, что надо по-максимуму использовать то, что даёт сама операционная система, и что её писали далеко не глупые люди.

Невероятное знание! =)
IO-шедулер в серверной Убунте по умолчанию стоит десктопный, для единообразия. Дураков хватает везде. Тем не менее, я уважаю авторов Линукса, потому что в целом достойный результат.

Кстати, на счёт вашего выпада в первом посте про десятки гигабайт… У меня обычно по полсотни терабайт данных на сервер. И по несколько сотен тебарайт на кластер.

Там был нюанс «в час». Либо вы в юношеском задоре пропустили этот нюанс, либо я сильно устарел и не в курсе, что уже можно писать по 15 гигабайтов в секунду на один сервер. Напомню ещё, что это было про Windows, который используется в обсуждаемом материале.

ToSHiC Jan 17 2013 at 14:22

Ну раз вы начали рассуждать про записи и чтения — то давайте начнём с того, как именно у вас хранятся данные на диске, без этого рассуждать о том, что readahead всегда вредит как-то странно. А вот про описанную ситуацию — это вы зря, она более чем реальна. Надо хранить много (по 2 млрд на машину) объектов размером в несколько килобайт (средний размер пусть будет 3кб). Ваши варианты, как это положить на диск?

Далее у вас началась последовательная обработка данных. Как часто она случается в MongoDB? Можно ли в принципе так положить данные, к которым производится произвольный более-менее равномерный доступ, на диск так, чтобы их можно было последовательно считывать большими кусками? Кстати, про шедулер: какой шедулер стоит при этом применять и почему, какой при этом будет профит?

Про нюанс «в час» — можете сами посчитать, а могу сразу сказать: на систему, которая была второй в предыдущем посте, постоянно льётся 3-5гб/ч, в пиках — больше. Но там маленькие записи, дискам сложно переваривать бОльшие объёмы из-за IO. В других местах, где записи по несколько мегабайт — конечно гигабайты в час легко получаются, когда начинают контент заливать.

А в Windows то вы с заканчивающейся памятью на диск писали или в сеть? В оригинальной статье всё же шёл разговор о работе с диском. В то, что в Windows хреново написан file cache, простите, не верю. Вот если кто-то накрутил настройки lazy write — тогда вполне возможны проблемы с большим количеством грязных страниц. В любом случае, настраивать надо периодичность flush, а не отключать writeback. А диски — они одинаковые, проблемы при работе с ними слабо зависят от операционной системы.

ivanov Jan 17 2013 at 15:50

Как хранит данные MongoDB, можно почитать в интернетах.
О том, что RA вредит случайному доступу, очевидно и ребёнку, о том, что RA не помогает, я вам написал несколько раз — при линейном чтении от RA никакого толка, потому что линейно всегда читается большими блоками.

Файловая система не предназначена для хранения большого количества мелких экземпляров. Во-первых, оверхеад, во-вторых, скорость низкая, в-третьих, репликация это ужас. Есть несколько ФС, решающих часть проблем (btrfs, например, или gfs), но они нестабильны просто или в плане скорости.
Мы храним в MongoDB файлы даже по 500кб. Есть нюансы, конечно, но как решение в целом на данный момент эффективность максимальная.

Последовательное чтение используется для парсера лога, например. Естественно, писать надо так, чтобы потом быстро читать. В MongoDB последовательная обработка тоже возможна, но есть нюансы.

Кстати, про шедулер: какой шедулер стоит при этом применять и почему, какой при этом будет профит?

Я не справочное бюро =) А так для линейного чтения в один поток по фигу, что за шедулер.

Про нюанс «в час» — можете сами посчитать

Не могу! Вы написали конечный объём в 50 терабайтов, за день это или за год, у меня данных нет. Но это всё равно про Линукс, написал уже два или три раза, что проблемы записи в Windows, используемом автором статьи.

А в Windows то вы с заканчивающейся памятью на диск писали или в сеть?

Диск.

В то, что в Windows хреново написан file cache, простите, не верю.

Об этом я написал в самом начале, вера опыт не заменяет. Скопируйте образ BR диска, например, и посмотрите, что будет с системой происходить. Чтобы два раза не вставать, советую смотреть счётчик Available для памяти в Task manager.

Про отключение writeback занятная теория (отключение WB, сюрприз!, не помогает), есть способ лучше =) O_DIRECT.

ToSHiC Jan 17 2013 at 19:17

Как хранит данные MongoDB, можно почитать в интернетах.

Это переводится как «я не знаю»?

О том, что RA вредит случайному доступу, очевидно и ребёнку, о том, что RA не помогает, я вам написал несколько раз — при линейном чтении от RA никакого толка, потому что линейно всегда читается большими блоками.

You can always use POSIX_FADVISE_RANDOM to disable it, but it's seldom
something that people do. And there are real loads that have random
components to them without being _entirely_ random, so in an optimal world
we should just have heuristics that work well.

©Linux Torvalds

sendfile, кстати, через readahead работает. Примеры, когда readahead будет хорошо работать: вычитывание b-tree индекса, подгрузка какой нибудь игрой ресурсов из большого ресурсного файла. В обоих случаях доступ рандомный, да не совсем.

Файловая система не предназначена для хранения большого количества мелких экземпляров. Во-первых, оверхеад, во-вторых, скорость низкая, в-третьих, репликация это ужас. Есть несколько ФС, решающих часть проблем (btrfs, например, или gfs), но они нестабильны просто или в плане скорости.

Кто вам сказал, что я храню 2 млрд файлов на файловой системе?

Мы храним в MongoDB файлы даже по 500кб. Есть нюансы, конечно, но как решение в целом на данный момент эффективность максимальная.

Вы в монгу сможете положить 2млрд записей по 3 кб?

Последовательное чтение используется для парсера лога, например. Естественно, писать надо так, чтобы потом быстро читать. В MongoDB последовательная обработка тоже возможна, но есть нюансы.

Чаще всего если данные надо хранить в большом объёме — то доступ к ним будет случайный. А если чтения всё равно не получится оптимизировать — то надо оптимизировать хотя бы запись, делая её линейной.

Не могу! Вы написали конечный объём в 50 терабайтов, за день это или за год, у меня данных нет. Но это всё равно про Линукс, написал уже два или три раза, что проблемы записи в Windows, используемом автором статьи.

Монгу вы под линуксом запускаете или под виндой?

Об этом я написал в самом начале, вера опыт не заменяет. Скопируйте образ BR диска, например, и посмотрите, что будет с системой происходить. Чтобы два раза не вставать, советую смотреть счётчик Available для памяти в Task manager.

Про отключение writeback занятная теория (отключение WB, сюрприз!, не помогает), есть способ лучше =) O_DIRECT.

Вы отключаете writeback и у вас всё равно остаётся много грязных страниц? Видимо, как-то не так отключаете. Вы случаем не во временный файл писали? Если проблема действительно есть — то дайте ссылку, мне сходу ни одной не попалось.

ivanov Jan 18 2013 at 14:36

Это переводится как «я не знаю»?

Нам бессмысленно продолжать дискуссию. Спорить с детьми я могу и без интернетов, дома. Хинт — не надо общаться вопросами, надо общаться утверждениями, вероятность ошибки значительно выше, это отличный показатель ответственности за свои слова.

Спасибо за новую шутку. Раньше мне нравилась «Стив Джобс сказал, что вам это не надо», теперь к ней будет «Линукс Торвальдс сказал, что это работает» =) Кроме самой прекрасной фразы вы ещё подсказали, что и имя можно написать с ошибкой для пущего эффекта ;)

Не смог удержаться =) Вместо поиска информации про MongoDB (и расширения кругозора) вы стали искать информацию про простой и понятный для повторения пример. Не получилось.

social.technet.microsoft.com/Forums/ru/sqlru/thread/7721af71-6eaa-48a0-85c1-b231ef23b85e
social.technet.microsoft.com/Forums/ru/ws2008r2ru/thread/1bef70b4-932e-4104-996e-1fadb1fda9d2
social.technet.microsoft.com/Forums/ru-RU/ws2008r2ru/thread/cd60a4a5-4bb4-4ad9-b498-457bdf141c89
social.technet.microsoft.com/Forums/ru-RU/ws2008r2ru/thread/3fc0a8be-8d32-4ab5-be93-de51dc82128b
social.technet.microsoft.com/Forums/ru/sqlru/thread/7721af71-6eaa-48a0-85c1-b231ef23b85e
Часть примеров про SQL Server, так как он отличный индикатор описанной проблемы.

MongoDB, к слову, на Windows работает для галочки, как только начинается серьёзная запись, сервер умирает.

Ответов больше не будет, не обессудьте.

ToSHiC Jan 18 2013 at 15:44

Да, вы уже сделали пару необоснованных заявлений, типа «readahead плохо, потому что MongoDB с ним работает плохо» и «Windows не скидывает страницы на диск, в итоге Allocated стремится к нулю после записи больших файлов».

Специально сейчас на Win7 скопировал с сетевой шары на локальный диск 400мб файл, ближе к концу копирования действительно было мало Allocated памяти, но через минуту после копирования Allocated = Cached + Free, то есть грязных страниц не осталось. Все ссылки, что вы привели — про то, что File Cache занимает весь доступный объём ОЗУ и приложениям, которые предварительно резервировали себе память, ничего не достаётся и они даже в файл подкачки вытесняются. Ну так это же нормально, оно так и должно работать! Файловый кэш выедает всю свободную память, чтобы она не простаивала, для ускорения операции записи. Если не нравится — уменьшайте объём памяти, который готовы выделять под буферы, делайте синк на диск чаще, инструменты то есть для этого.

Вы готовы привести другие ссылки, где будет написано про большое количество грязных страниц в памяти после окончания процесса копирования? Или, может быть, готовы показать ссылку, где будет описано, что страницы не сбрасываются на диск, когда вызывается sync? Мне такие не попадались.

По вашим ответам складывается ощущение, что вы считаете себя большим специалистом в области программирования, но при этом плохо понимаете, как работает файловых кэш. Вы много раз повторили про случайный доступ к диску, про монго, но ни разу не описали структуры данных, к которым тот самый случайный доступ производится. Вы опять же голосновно объявили cfq «десктопным» шедулером, хотя только он, в текущий момент, поддерживает io приоритеты.

Можете не отвечать, но советую всё же разобраться с «магией», которую применяют во всех современных операционных системах много лет, и с которой успешно работают миллионы программистов по всему миру. Расширьте кругозор. И не стоит учиться этому у разработчиков MongoDB, это далеко не самая лучшая база данных.

ivanov Jan 18 2013 at 16:33

ближе к концу копирования действительно было мало Allocated памяти, но через минуту после копирования Allocated = Cached + Free, то есть грязных страниц не осталось

На сервере не бывает «через минуту», пишется непрерывно.

ToSHiC Jan 18 2013 at 16:36

Так делайте sync чтобы страницы на диск сбросить, в чём проблема то?

ivanov Jan 18 2013 at 16:53

Уже несколько раз написал — в том, что не работает =)
Точнее, лишь позволяет отсрочить смерть, а помогает от захламления памяти только O_DIRECT.

tyrotoxin Jan 15 2013 at 23:07

Кстати, мы тестировали сравнение реальных баз размером около 100 GiB, и получили такую картину:
конкурент — 40 часов
мы — 1 час 40 мин
Так что пример с демобазой на 200 MiB наверно не самый удачный :)

ivanov Jan 16 2013 at 08:47

Дык, и приводили бы этот пример. С какими-нибудь нюансами, типа количества таблиц, максимального количества строк в таблицах или ещё чего-нибудь интересного на абзац текста.
Выглядело бы значительно ближе к реальности.

retran Jan 14 2013 at 17:38

«1. Хороший алгоритм.»

В большинстве случаев не алгоритм, а в первую очередь хорошая структура данных. Классика же (Кнут, кажется).

И вопрос — а собственно в каких задачах из дотнетовского скоупа могут понадобиться такие оптимизации? Собственно, если следовать большей части этих советов, то мы радостно получим неподдерживаемый код.

UPD Сорри, не увидел.

tyrotoxin Jan 14 2013 at 17:46

Сколько людей — столько и мнений. Если вы, например, скажете на собеседовании в Microsoft, что алгоритм — не главное, то скорее всего вы его не пройдёте. Там алгоритмам уделяется особое внимание, и слова «Хороший алгоритм» я брал не с потолка :) Если один алгоритм решает задачу за O(N*logN), а второй за O(logN), то выбор очевиден.

в каких задачах из дотнетовского скоупа могут понадобиться такие оптимизации?

Это уже вам решать, надо вам это или не надо. Задачи всегда найдутся, поверьте :)

-1

lair Jan 14 2013 at 17:54

Если один алгоритм решает задачу за O(N*logN), а второй за O(logN), то выбор очевиден.

Нет, не очевиден. Потому что если первый требует n памяти, а второй — n³ памяти, то мы имеем балансировку между одним и другим.

VenomBlood Jan 14 2013 at 19:02

Поддержу. Более того, благодаря скрытым константам даже и требование по памяти не нужно. Да и вообще куча причин есть, по которой первый алгоритм может быть предпочтительнее.

retran Jan 14 2013 at 18:44

Алгоритм прямо вытекает из структур данных. Поиск по линейному списку, по бинарному дереву и по хэш-таблице — дадут вам как раз таки разную вычислительную сложность. Ну и как написал lair, есть еще требования к памяти.

Прекрасно описано вот в этой книжке, например — www.ozon.ru/context/detail/id/4788523/ и в аналогичной книжке от Вирта.

UPD И да, крайне часто, буст по производительности как раз таки дает именно схема хранения данных, а не «байтодрочерство».

UnknownGosu Jan 15 2013 at 00:05

Вы с каждым новым комментарием все больше разуверяете в собственной компетентности по теме топика, либо прекращайте вести двойную игру, либо одно из двух =).

UFO just landed and posted this here

tyrotoxin Jan 14 2013 at 17:57

спасибо, я от английского «edge» написал так.

UnknownGosu Jan 15 2013 at 00:10

<зануда>У графа грани таки есть, это число связных областей при какой-либо конкретной его укладке</зануда>

UnknownGosu Jan 15 2013 at 04:57

Но в тексте топика, конечно, речь о ребрах =).

ramntry Jan 14 2013 at 19:58

Я надеюсь, автор очень хорошо понимает, что фразой «Никаких профайлеров» во втором абзаце (особенно после весьма пафосно и, я бы сказал, дёшево звучащего первого) статьи, посвященной оптимизации, он отбивает желание знакомиться с материалом у большей части здравомыслящих посетителей хабра.
Предложение же возводить целое число в 4-ую степень так:

int power4(int v)
{
    int r = 1;
    r *= v;
    r *= v;
    r *= v;
    r *= v;
    return r;
}

может вызвать только смех. Я уж не говорю о том, что добиться результата можно и двумя умножениями… Можно. Но нужно так: Math.Pow(youVarible, 4); (алгоритм возведения в целую степень за логарифмическое время). Этот кусок кода бросается в глаза почти сразу — плохая реклама.

KvanTTT Jan 14 2013 at 23:01

Я уж не говорю о том, что добиться результата можно и двумя умножениями…

И не говорите. Я тоже хотел сказать, но потом вспомнил, что результаты будут различными в общем случае.

Но нужно так: Math.Pow(youVarible, 4);

Вот так вот для четвертой степени уж точно ни в коем случае не нужно, если конечно вам не пофиг на производительность! .NET для такого будет использовать Exp и Ln, ну или что-нибудь, что заведомо медленнее перемножения. Изучили бы лучше сначала как работает Math.Pow, а потом критиковали.

ramntry Jan 14 2013 at 23:40

И не говорите. Я тоже хотел сказать, но потом вспомнил, что результаты будут различными в общем случае.

Назовите, пожалуйста, этот случай. Интересно.

.NET для такого будет использовать Exp и Ln, ну или что-нибудь, что заведомо медленнее перемножения. Изучили бы лучше сначала как работает Math.Pow, а потом критиковали.

Пускай использует на здоровье, что считает нужным. Я вижу, что это одна строчка против десятка — и с совершенно недвусмысленной семантикой, позволяющая, к тому же, число 4 заменить именованной разумным образом контантой, если такое имя возможно придумать. И до тех пор, пока:
1) пользователем приложения не востребовано повышение его производительности и
2) профилированием не доказано, что значимая часть времени затрачивается на возведение некоторого значения в четвертую степень именно в этом месте кода в наиболее распространенных сценариях использования и
3) не удалось найти устранимых ошибок проектирования на архитектурном, а затем и на алгоритмическом уровнях системы, приводящих к чрезмерно частому исполнению блока, в котором это несчастное возведение расположено и
4) повторным профилированием не было доказано, что умножение действительно быстрее в случае использования актуальных версий .NET, JVM, компилятора / интерпретатора
- я по-прежнему буду считать, что Math.Pow, std::pow или любой другой стандартный power лучше этого смеха.

tyrotoxin Jan 15 2013 at 00:18

Math.Pow, std::pow или любой другой стандартный power лучше этого смеха.

1) Я вижу, Вы так и не поняли, что суть в разворачивании циклов, а не оптимизации функции возведения в степень. И упорно продолжаете выражать мысли не в том контексте.

2) Вы заблуждаетесь.

Пример кода

        static double power4(double v, double N)
        {
            double r = 1;
            r *= v;
            r *= v;
            r *= v;
            r *= v;
            return r;
        }

        delegate double PowDelegate(double v, double n);

        unsafe static void Main(string[] args)
        {
            PowDelegate method = Math.Pow;

            int timestamp = Environment.TickCount;
            for (int i = 1000000; i > 0; i--)
                method(10, 4);
            int time = Environment.TickCount - timestamp;
            Console.WriteLine("Math.Pow: " + time);

            method = power4;

            timestamp = Environment.TickCount;
            for (int i = 1000000; i > 0; i--)
                method(10, 4);
            time = Environment.TickCount - timestamp;
            Console.WriteLine("Custom: " + time);
        }

Запускайте, и смейтесь дальше, что Math.Pow всегда будет работать за константное время (в моём грубом тесте на моей машине) — за 63 мс, а power4 — за 0 мс.

Не выставляете себя глупцом, утверждая то, что сами не проверяли, а только «считаете» и «насмехаетесь».

-2

leventov Jan 15 2013 at 00:30

И часто вы в своей программе прогоняли тысячи одинаковых возведений в 4-ю степень? :) Если бы компилятор не выкинул 2-й цикл, результаты были бы сопоставимыми.

tyrotoxin Jan 15 2013 at 00:39

Вы издеваетесь?

компилятор не выкинул 2-й цикл

Вы уже смотрели какие инструкции генерируется? Без компиляции? Не заявляете того, чего наверняка не знаете. Это смешно. Проверьте — и вы убедитесь что инструкции для цикла там есть ;)

И часто вы в своей программе прогоняли тысячи одинаковых возведений в 4-ю степень? :)

Ещё один..(face palm) Пункт о «разматывании циклов» :) Не увиливайте от темы. Скорость выполнения предоставлена специально для верующих в силу Math.Pow.

-1

leventov Jan 15 2013 at 01:40

0 мс это максимум 999 нс, за 1 нс = максимум 5 тактов для домашнего проца x 4 потока = 20 микроопераций на целочисленном модуле. Т. е. если бы цикл содержал возведение в степень, то она бы вычислялась в самом худшем случае за 1/50 микрооперации. Правдоподобно?

tyrotoxin Jan 15 2013 at 01:48

На мой вопрос «смотрели какие инструкции генерируется?» вы продолжаете рассуждать. Это не профессионально.

-1

Mrrl Jan 15 2013 at 07:03

А чем вы смотрите, какие там инструкции?

leventov Jan 15 2013 at 16:26

Ошибся в 1000 раз. Поэтому если второй цикл действительно занимает близко к 1 мс, то tyrotoxin возможно прав.

ramntry Jan 15 2013 at 01:03

1) Простите, но приведенная вами цитата — часть ответа на комментарий KvanTTT, ни вас, ни разворачивания циклов уже особенно не касающегося.
2) В чём именно я заблуждаюсь?

KvanTTT Jan 15 2013 at 00:41

Назовите, пожалуйста, этот случай. Интересно.

Вообще-то умножение вещественных чисел не является ассоциативной операцией. Развернутая дискуссия есть в вопросе на SO: Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?

Что касается второго замечания, то в целом согласен. Однако считаю, что например для подсчета расстояния между точками использовать Math.Pow(x, 2) плохо. И такое я видел в нескольких Open Source проектах.

lair Jan 15 2013 at 00:52

Вообще-то умножение вещественных чисел не является ассоциативной операцией.

Так там целые числа:

Предложение же возводить целое число в 4-ую степень так:
int power4(int v)
{
    int r = 1;
    r *= v;
    r *= v;
    r *= v;
    r *= v;
    return r;
}

KvanTTT Jan 15 2013 at 01:02

Извиняюсь, не заметил, что про целые.

ramntry Jan 15 2013 at 01:14

1. В примере, приведенном в статье, используется целочисленное умножение.
2. Потери точности в арифметике с плавающей точкой значительны редко, и практически всегда это — сложение / вычитание чисел с сильно различающимися экспонентами — при неизбежном приведении к общей экспоненте часть (или даже все) знаков мантиссы одного из чисел может быть потеряна. В случае умножения практически всегда достаточно предполагать, что чем меньше умножений — тем выше точность.

Mrrl Jan 15 2013 at 01:01

Проверил 4 варианта (сумма 4-х степеней элементов массива длиной 160 млн). Вызов Math.Pow(x,4) в среднем составил 84 нс, вычисление 4-й степени прямо в цикле за 3 умножения — 6 нс, вычисление за 2 умножения — 1.7 нс, вызов функции, вычисляющей его за 2 умножения — 5 нс.
Если я могу оценить число возведений в 4-ю степень в своём коде, и сравнить их время (получив его умножением) со временем работы всей программы — то зачем профайлер? Увидев выигрыш в 20% (13 секунд из 60, например), я, скорее всего, исправлю код в тех местах, которые дают хотя бы 90% от общего числа возведений в степень. На что исправлю? На самодельную функцию, хоть она и втрое медленнее inline кода. Если удастся набрать пять раз по 20%, то программа будет работать втрое быстрее, что вполне заслуживает проделанной работы.
Часто ли приходится 160 миллионов раз вычислять 4-ю степень? Редко. Чаще это 300 миллионов вычислений арктангенса на одну обработку. И его замена на самодельную функцию в своё время дала очень хороший прирост в скорости…

Mrrl Jan 15 2013 at 01:07

Да, я тоже забыл про целые. В моих опытах были double.

Mrrl Jan 15 2013 at 00:16

.NET для такого будет использовать Exp и Ln, ну или что-нибудь, что заведомо медленнее перемножения.

Не похоже. Math.Pow(-2.5,4) сработало уверенно, а Math.Pow(-2.5,3.5) выдало ошибку. Так что, они, по меньшей мере, проверяют, целый ли показатель.

KvanTTT Jan 15 2013 at 00:58

В любом случае Math.Pow работает за O(1), обычное перемножение за O(N), а быстрое возведение в степень — за Log_2(N). Это можно увидеть в моем тестовом проекте (C# + MVS 2010).

Может показатель и проверяется. Но в подавляющем большинстве случаем быстрое возведение всегда будет быстрее Math.Pow.

Я на stackoverflow еще вроде читал, что используется интеловская реализация возведения в степень.

Mrrl Jan 15 2013 at 01:03

Что используется — непонятно. В исходниках просто ссылка на какую-то внешнюю функцию.

KvanTTT Jan 15 2013 at 01:13

Ничего внешнего там не используется. Есть три функции в MathPowVsMultTest.Gui: MathPow (вызывает стандартную Math.Pow), IntPow и FastPow, они все в начале.

Mrrl Jan 15 2013 at 01:17

А, я не так понял. Имелось в виду, что код Math.Pow написан не на C#, а где-то еще.

tyrotoxin Jan 14 2013 at 20:08

1) Я показываю другой путь подхода к разработке. Если вы умеете пользоваться только профайлером — пожалуйста, никто вам не запрещает. Делайте как вам проще и удобней, и вы считаете со «здравым смыслом».
2) Вы, как и другие, докапываетесь к мелочам, не желая понять основную суть. Вы думаете что пример с возведением в степень — это самый оптимальный способ? Пункт о разматывании циклов, а не о самой лучшей функции power.

-3

ramntry Jan 14 2013 at 21:20

1) Вашим другим способом разработки разрабатывает не меньшинство, а подавляющее большинство. И об этот способ было копий сломано неисчислимо. Если вы хотите, чтобы вас услышали коллеги по оружию, напишите хоть целую статью про одно только разматывание циклов — но основанную на множестве, пусть и не очень большом, осмысленных и всестороенне протестированных примеров из вашей практики. Чтобы бы была хотя бы какая-то надежда на воспроизводимость результатов. Иначе тот, кто не знал ранее про разматывание циклов, компиляторные оптимизации и некоторые заветы в промышленной разработке, начнет радостно писать «китайский код» где ни попадя, а более подготовленный читатель — лишь посмеётся и пожалеет потраченного времени.
2) Нет, не думаю. Скорее думаю, что это глупый и вредный пример.

micbsv Jan 14 2013 at 21:28

> «High Performance Computing и платформа .NET как минимум вызывает улыбку»

… только у тех, кто не в теме :)

NeoNN Jan 14 2013 at 22:39

Я ведь прав, что при частом использовании структур, как в совете 16, с передачей их по ссылке, затраты на boxing-unboxing могут перекрыть многие микрооптимизации?

tyrotoxin Jan 14 2013 at 22:42

нет, при передаче по ссылке (ref или out) передаётся указатель на область памяти (целочисленное число; 4 или 8 байт), и при этом boxing / unboxing не происходит.

NeoNN Jan 14 2013 at 23:02

Да, и точно, спасибо, что-то я затупил. Даже на stackoverflow есть исчерпывающий ответ stackoverflow.com/questions/4807659/boxing-vs-valuetype-by-reference-whats-the-difference
Но все равно с value типами надо быть внимательным.

alex_shabalin Jan 14 2013 at 22:46

++i выполняется быстрее i++. В нем на одну операцию меньше. Очень полезно для циклов.

lair Jan 14 2013 at 22:58

Вы, конечно же, можете доказать это утверждение (для .net и для целочисленных i)?

(с учетом вот этого ответа Липперта)

KvanTTT Jan 14 2013 at 23:04

Мне кажется это был просто сарказм :)

tyrotoxin Jan 14 2013 at 23:16

Даже если так, я не вижу разумных причин. Например, в работе с американцами мне нравится то, что они говорят и хорошие и плохие отзывы. Хорошие — подбадривают человека, и толкают на новые подвиги. А в таких странах, как Россия и Украина многие любят жаловаться, только критиковать, насмеиваться, и показывать насколько они умнее других. Думаю, кто переехал жить в те же США, поймёт меня :) Но это уже другая тема.

23derevo Jan 14 2013 at 23:13

а Вы думаете, что JIT-компилятор не поправит за Вас этот момент?

KvanTTT Jan 14 2013 at 23:09

Да, совет про foreach как минимум странный, а то и вредный.

UFO just landed and posted this here

KvanTTT Jan 15 2013 at 01:07

А знаете, можно не только решетку сточить, но и саму букву, начав писать на ассемблере под C# :)

UFO just landed and posted this here

Mrrl Jan 15 2013 at 01:13

Жаль, что оно плохо переносится между платформами. А есть ли хороший способ использовать в проекте код на ILASM?

UFO just landed and posted this here

ramntry Jan 15 2013 at 01:23

en.wikipedia.org/wiki/ILAsm

UFO just landed and posted this here

Mrrl Jan 15 2013 at 07:00

Смысл есть. У ассемблеров синтаксис может меняться от компилятора к компилятору, и в этом случае в фразе «программа на чем» часто называют компилятор. «Программа на TASM/MASM», «программа на Дельфи», «программа на BCC/на GNU-C»… Было всё это.

Mrrl Jan 15 2013 at 01:26

Действительно, имелся в виду CIL.

    IL_0000:  ldc.i4.0
    IL_0001:  stloc.0
    IL_0002:  ldc.i4.1
    IL_0003:  stloc.1
    IL_0004:  ldarg.0
    IL_0005:  stloc.s    CS$519$0000
    IL_0007:  ldloc.s    CS$519$0000
    IL_0009:  conv.i
    IL_000a:  dup
    IL_000b:  brfalse.s  IL_0013

и так далее. Ассемблер внутреннего кода .NET

UFO just landed and posted this here

Mrrl Jan 15 2013 at 07:02

В идеале — написать на CIL один или несколько методов класса. Если не получится — написать на нём целый класс. Возможно, в качестве затычки пришлось бы дисассембрировать всю сборку, постпроцессором менять в ней нужные методы, а потом ассемблером собирать обратно, но этот способ я считаю плохим.

UFO just landed and posted this here

Mrrl Jan 15 2013 at 10:23

Если я увижу, что код, созданный С#, оптимален, я его, конечно, трогать не буду. Но если видно, что в узком месте можно выиграть 10-15% за счет более эффективного использования стека и локальных переменных, то почему бы и нет?

KvanTTT Jan 15 2013 at 17:05

На самом деле то, что C# может генерировать не самый оптимальный IL — правда.
У меня сейчас C# компилятор даже не использует стек для уже вычисленных функций, используемых больше одного раза, не говоря о дополнительных локальных переменных.

Например для выражения (x + 3) * (x + 3) промежуточная переменная x + 3 будет вычислена два раза, хотя она будет вычислена два раза. (Странно, раньше мне казалось, что для таких простых выражений она вычисляется один раз). Но это простой пример, а если взять пример посложнее и в коде не использовать промежуточные переменные для результатов более сложных функций, то производительность может сильно упасть, по сравнению с оптимизированной версией. JIT компилятором такое тоже не будет оптимизироваться, я проверял.

На самом деле я почти дописал статью про компиляцию математических выражений в .NET (скорее в академических целях), поэтому знаю о таких нюансах.

Mrrl Jan 15 2013 at 17:29

Очень грустно, что у них нет команды «скопировать переменную из локального стека» (или я её не нашел). Не работает стандартная схема: вычислили выражение, его результат оказался на стеке, теперь будем пользоваться этой ячейкой в качестве локальной переменной, пока она нам не надоест — а потом забудем.

KvanTTT Jan 15 2013 at 17:39

Ну можно же просто локальные переменные для этого создавать, чем хуже? Скорее всего они хранятся там же, где и стек после этапа JIT компиляции. Это подкрепляется еще и тем фактом, что в IL коде для всех методов указывается параметр .maxstack и сразу объявляются все локальные переменные, даже если они объявляются после условия, т.е. размер стека заранее определен.

А такая инструкция не введена (я тоже не знаю) скорее всего из-за излишнего усложнения и безопасности.

VenomBlood Jan 20 2013 at 21:09

Ну зачем же ты обманываешь. (x+3)*(x+3) замечательно оптимизируется Jit'тером, выдавая код:

lea ecx,[rax+3]
imul ecx,ecx

KvanTTT Jan 20 2013 at 22:26

Я говорил странно про то, что это не оптимизируется на уровне компиляции.
А оптимизирует ли Jit'тер выражение Math.Sin(x) * Math.Sin(x)? Если да, то более сложные выражения, например Math.Sin(x) *… * Math.Sin(x * 1), т.е. чтобы одинаковые выражения стояли не сразу друг за другом. Такие более сложные выражения я и тестил (правда просто делал замер скорости, а не ассемблерный код смотрел).

VenomBlood Jan 20 2013 at 22:34

Я исходил из твоей цитаты

JIT компилятором такое тоже не будет оптимизироваться, я проверял.

Которая шла в конце абзаца про (x+3)(x+3).

В данный момент компилятор не имеет права оптимизировать таким образом Math.Sin(x), потому что на уровне компиляции, насколько мне известно, нет понятия Pure методов. А т.к. все Sin, Pow и т.д. — мапятся на реализации соответствующих функций в стандартной библиотеке C, с которой компилится CLR — то оптимизация невозможна даже при инлайне (в принципе в других языках и средах тоже самое).

Но в любом случае — лучше писать Math.Pow, чем просто умножать (можно, конечно, поспорить для возведения в квадрат, потому что тут x*x даже короче и нагляднее чем Math.Pow(x, 2)). Наглядность, особенно в математических вычислениях в коде, важна в первую очередь. А дальше если профайлер не покажет что это самая горячая точка, и если программа не будет испытывать реальных проблем с производительностью — то и не надо оптимизировать этот код.

Я говорил странно про то, что это не оптимизируется на уровне компиляции.

Да, на уровне компиляции в IL код практически ничего не оптимизируется, да и не нужно там это. JIT'тер вполне справляется с этой задачей.

KvanTTT Jan 20 2013 at 22:46

Но это простой пример, а если взять пример посложнее…
JIT компилятором такое тоже не будет оптимизироваться, я проверял.

Тут еще можно поспорить про что это я так сказал :)

Да, на уровне компиляции в IL код практически ничего не оптимизируется, да и не нужно там это. JIT'тер вполне справляется с этой задачей.

Это конечно да, но видимо поэтому не все все агрессивные оптимизации применяются на этапе JIT компиляции (которые применяются например в C++) из-за потенциально большого время запуска.

UFO just landed and posted this here

KvanTTT Jan 15 2013 at 20:13

Ну Mrrl вроде имел ввиду использование произвольной ячейки памяти в IL стеке, а не только самой верхней.

UFO just landed and posted this here

Mrrl Jan 15 2013 at 20:59

Разумеется. Если использование «чистого» стека мешает эффективности, тем хуже для стека… придётся добавить ему методы Stack[N]=value и x=Stack[N]… Насколько я помню, в FORTH что-то подобное есть. А в CIL их нет… и приходится выполнять лишние stloc/ldloc даже тогда, когда это не нужно. А JIT их честно раскрывает, и оптимизировать не очень может.

UFO just landed and posted this here

Mrrl Jan 15 2013 at 22:40

Я подумаю над этой идеей. Хотя лучше, наверное, заняться перестраиваемой архитектурой процессора. Жаль, что я в этом ничего не понимаю :)

Mrrl Jan 17 2013 at 18:18

Засада. Код, который генерируется JIT в рабочем режиме, не имеет вообще ничего общего с тем, что показывает отладчик. Все локальные переменные размещаются (при возможности) в регистрах, так что stloc/ldloc может вообще не занимать времени.
Что же, будем это учитывать.

UFO just landed and posted this here

Mrrl Jan 20 2013 at 10:15

Хм. После выбора алгоритма есть реализация на C#. После неё — C#-компилятор. После него — джиттер, дающий ассемблерный код, и различающийся для разных платформ. После него — микрокоды и конвееры процессора, опять же, различающиеся для разных производителей и версий процессора.
В некоторых случаях мы можем подменить какой-то этап (компилятор, джиттер, взять другой процессор...). Иногда это невозможно, и приходится влиять на результаты с помощью входных данных. Через две ступеньки (джиттер-микрокоды) это сложно, через три (добавив C#) еще сложнее. Ну и что? Конечно, в 97% программ (даже не кода!) достаточно ограничиться выбором правильного алгоритма (даже не обязательно эффективного, важнее, чтоб понятного), и написанием правильного кода на C#. Но это не интересные (для данной темы) случаи, они разбраются в темах по правильному программированию. Но здесь-то речь идёт про 3% кода, содержащегося в оставшихся 3% программ! (это получается больше, чем 0.09% от общего кода в мире, поскольку сами эти программы достаточно большие). Почему мы там должны себя ограничивать? И вообще, что это за «быть умнее… не получится»? Вы сомневаетесь в безграничности своих способностей?

lair Jan 20 2013 at 11:00

Почему мы там должны себя ограничивать?

Потому что экономически нецелесообразно. Намного проще взять managed c++ (или даже просто c++) и написать отдельный кусок кода, который потом использовать из c#.

Mrrl Jan 20 2013 at 11:09

Managed c++ даст тот же IL-код. Который точно так же будет скормлен джиттеру. И будет ли этот код эффективнее, чем из C#, всё равно надо будет смотреть.
Просто c++ не будет кроссплатформенным, да и на вызов потратится значительно больше времени, чем мы выиграем на микрооптимизации. Но все эти варианты тоже нужно рассматривать.
А насчет «экономически нецелесообразно» — тут уж зависит от задачи. И от имеющихся ресурсов и их распределения.

lair Jan 20 2013 at 11:13

Managed c++ даст тот же IL-код. Который точно так же будет скормлен джиттеру. И будет ли этот код эффективнее, чем из C#, всё равно надо будет смотреть.

Как минимум, он даст IL не хуже, чем описанный в статье, однако при этом не будет насилием над C#.

Просто c++ не будет кроссплатформенным

В случае с .net это не великая проблема.

на вызов потратится значительно больше времени, чем мы выиграем на микрооптимизации

Это еще нужно измерить и доказать. Очевидно, что надо не один метод выносить.

А насчет «экономически нецелесообразно» — тут уж зависит от задачи. И от имеющихся ресурсов и их распределения.

Вот именно. И я пока ни разу не видел задачи и матрицы ресурсов, при которых подход статьи был бы оправдан.

Mrrl Jan 20 2013 at 11:36

Как минимум, он даст IL не хуже, чем описанный в статье, однако при этом не будет насилием над C#.

Это еще надо проанализировать и доказать ;) Может оказаться хуже, если компилятору managed c++ уделяется меньше внимания, чем C#.

В случае с .net это не великая проблема.

Не великая, но проблема. После полного отказа от unmanaged кода в проекте разрабатывать и поддерживать его стало гораздо легче.

Вот именно. И я пока ни разу не видел задачи и матрицы ресурсов, при которых подход статьи был бы оправдан.

Как насчет embedded .net кода на устройстве, на котором нужно экономить потребляемые процессором ватты, но при этом не терять производительности? Переписывать всю программу на unmanged код будет дольше, чем потихоньку оптимизировать кусок за куском и продавать новые улучшенные версии устройства :)

lair Jan 20 2013 at 11:39

Может оказаться хуже, если компилятору managed c++ уделяется меньше внимания, чем C#.

Ну так в статье уже все оптимизации руками сделаны, компилятору ничего не оставили.

После полного отказа от unmanaged кода в проекте разрабатывать и поддерживать его стало гораздо легче.

Как это связано с кросс-платформенностью?

Как насчет embedded .net кода на устройстве, на котором нужно экономить потребляемые процессором ватты, но при этом не терять производительности?

Интересно, под управлением чего это устройство, и почему для него до сих пор не сделали свой собственный jit-компилятор.

Переписывать всю программу на unmanged код будет дольше, чем потихоньку оптимизировать кусок за куском и продавать новые улучшенные версии устройства

Не понятно, почему здесь нет пункта «переписывать куски программы на unmanaged-код».

Mrrl Jan 20 2013 at 11:57

Интересно, под управлением чего это устройство, и почему для него до сих пор не сделали свой собственный jit-компилятор.

Переносом управления на борт занялись совсем недавно, до сих пор работали по USB из-под Windows. Поскольку хочется быстро, в первой версии будет какая-нибудь Windows с .NET на не слишком мощном процессоре. А там посмотрим.

Не понятно, почему здесь нет пункта «переписывать куски программы на unmanaged-код».

Почитаю про mixed assemblies, тогда подумаю над этим пунктом. Но, кстати, один из последних вариантов кода самого узкого места на C# дал такое же быстродействие, как тот же кусок на unmanaged C++ (и то и дугое в stand-alone программах). И сейчас я знаю, почему — оказывается, JIT гораздо лучше, чем я о нем думал.
Одна из альтернатив — перенос фрагментов кода на DSP.

lair Jan 20 2013 at 11:23

Ну и да.

msdn.microsoft.com/en-us/library/x0w2664k.aspx

Mrrl Jan 20 2013 at 11:39

Спасибо, погляжу.

UFO just landed and posted this here

Mrrl Jan 20 2013 at 11:44

Вот спасибо! Особенно за это:
«Intel® 64 and IA-32 Architectures Optimization Reference Manual».

Почему-то часто утверждают, что это закрытая информация, известная только разработчикам Intel — так что мне и в голову не пришло её искать.
А по AMD такое есть?

UFO just landed and posted this here

KvanTTT Jan 15 2013 at 01:29

Я видел такое расширение для Visual Stuido: IL Support, но подробно его не изучал. А также не уверен, что переписывание C# кода на IL целесообразно, учитывая время написание IL кода. Ведь основные оптимизации происходят на уровне JIT компиляции, даже методы встраиваются там.

Mrrl Jan 15 2013 at 01:36

Тот результат JIT, который показывает окно дисассемблера, выглядит просто плачевно. Конечно, это может быть следствием того, что он знает, что на него будут смотреть в отладчике… Я тоже не уверен в целесообразности. Этим можно заниматься, только когда основные задачи проекта решены, и изучаются пути его улучшения, включая самые экзотические.

Mrrl Jan 16 2013 at 17:45

Попробовал IL_Support. Пока неудачно. Такое впечатление, что компилятор вставляет в код контрольные точки (границы строк?), через которые JIT не может оптимизировать. В IL-коде строк больше, и возможностей для оптимизации гораздо меньше.
Есть ли такой механизм на самом деле? И как его выключить?

Mrrl Jan 15 2013 at 01:11

Зато библиотеки остались. Которые местами удобнее, чем у C.

Weageoo Jan 15 2013 at 01:22

Я не хочу писать на С++, я хочу писать на C#, где строгой ОО-подход, сборка мусора, своя BCL, а потом бороться с этим ООП, глупым сборщиком мусора и неоптимальными для высокопроизводительных приложений стандартными инструментами.

Но за статью все же плюс — есть много интересного.

onikiychuka Jan 15 2013 at 10:19

Может вам стоило смотреть в сторону Managed C++. Просто ваш код на шарпе не читаем вообще и смысла писать на шарпе вот так нет. Ну и конечно писать свою асинхронность вместо системной это полный ахтунг.
Вообще от статью осталось впечатление что опытный С/С++ разработчик пришел на .NET и не посмотрев что уже написано до него, а сразу кинулся все оптимизировать таким образом как он привык в С/С++.

+11

UFO just landed and posted this here

shai_hulud Jan 15 2013 at 11:32

Весьма интересно узнать эти «некоторые реализации .NET».

UFO just landed and posted this here

shai_hulud Jan 15 2013 at 11:54

судя то тому что опкод jmp(http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.jmp.aspx) существует с версии 1.1. у меня есть сомнения, что закрытый делегат исполнялся медленнее обычного статичного вызова.

UFO just landed and posted this here

shai_hulud Jan 15 2013 at 23:34

сомнений больше нет, спасибо за ссылку.

lair Jan 15 2013 at 11:37

Пункт 4 окажется неверным для таблицы из одной строчки и 800 колонок. Даже никаких альтернативных реализаций .net не надо.

lair Jan 15 2013 at 13:53

(только сейчас заметил)

Все тесты я проводил на своём рабочем компьютере с вот такой конфигурацией:[...] Microsoft SQL Server 2008 R2 Developer Edition 64-bit

То есть сетевое взаимодействие исключено полностью, а память распределяется между приложением и SQL-сервером случайным образом. Учитывая размеры БД, я не удивлюсь, если MS SQL ее всю съел в память.

Это все прекрасно, только это не рабочие условия (для типового приложения по сравнению двух БД).

tyrotoxin Jan 15 2013 at 23:18

Предположим SQL Server съел всю базу в память. Чем это плохо? Это наоборот хорошо для тестирования, т.к. времени чтения данных с диска нет, и можно более объективно сравнивать быстродействие двух продуктов.
Ранее в коментариях, я упоминал, что на некой реальной базе конкурент показал время 40 часов, а мы — 1 час 40 мин.

lair Jan 15 2013 at 23:23

Это плохо тем, что вы меряете производительность не в тех условиях, в которых будет работать реальное приложение. Так что это хоть и «объективно», но бессмысленно.

tyrotoxin Jan 15 2013 at 23:29

Если вы предоставите статистику, что все базы в миире крупные, а не мелкие (как Adventure Works), тогда можете заявлять о «реальных условиях». Рынок разнообразный, вы не можете этого просто так знать. А мы можем строить хоть какую-то картину по нашим клиентам.

lair Jan 15 2013 at 23:30

Вы не понимаете. Дело даже не в размере БД, а в том, что обычно она на другом сервере, так что привет (неконтролируемому вами) сетевому взаимодействию.

tyrotoxin Jan 15 2013 at 23:45

Я как раз понимаю. В статье не написано, но приложение работает чуть быстрее если сервер не на локальной машине (при 1 gbit). Опять же какой сервер, где стоит, виртуальная машина или нет, пропускная способность… Поэтому ещё раз повторюсь, что в реальных условиях (даже 100 Mbit сеть), на реальном примере, мы справляемся чуть менее чем за 2 часа, когда конкурент это делает за 40.
Возвращаемся к вопросу «хоть и объективно, но бессмысленно». Статья про то, как можно сделать простые вещи сложными, но очень эффективными, а не про конкретный продукт и «реальных» условиях тестирования. Результаты оптимизации лучше показывать с минимумов воздействия внешних факторов.

lair Jan 16 2013 at 00:11

Результаты оптимизации лучше показывать с минимумов воздействия внешних факторов.

Вот только вы не показали конкретных результатов ни одной своей оптимизации, если мне память не изменяет. Что как раз и делает вашу статью набором трюков, а не реальными полезными советами.

dmOx Jan 15 2013 at 18:36

Вы смотрите на C# с уровня ассемблера. Половину из этих оптимизаций сделает за вас компилятор ещё в стадии генерации IL-кодов, неиспользуемый и недостижимый код будет удален, если на этом этапе будет известно что он недостижим, дальше ещё интереснее — JIT компилятор который может позаботиться и о развертывании циклов, не увеличивая размер сборки и вызовах ненужных if, переписывании String.Format в StringBbuilder (если, конечно, строка форматирования не генерируется каждый раз новая).

lair Jan 16 2013 at 11:35

Сегодняшний пост Липперта исключительно по теме:

Donald Knuth, author of the classic four-volume series The Art of Computer Programming, famously said “premature optimization is the root of all evil.“. I think however that it is more instructive to read that quotation with more context:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.

Which is of course what I have echoed in my numerous performance rants over the years: don’t waste your valuable time making risky changes to the 97% of the code that isn’t the slowest thing and that no customer will ever notice. Use a profiler, find the slowest 3%, and spend your optimization budget on that.

Andrey_Kuprikov Jan 17 2013 at 11:00

Добрая половина приемов — это эдакий привет из 90-х. И главное — совершенно неверный подход к вопросу. Есть несколько простых правил:
1. Преждевременная оптимизация — зло! Сначала сделай, чтобы работало качественно и правильно, а потом оптимизируй.
2. Не оптимизируй без профайлера! Сначала собери статистику по скорости работы, а потом оптимизируй то, что действительно тормозит. Пункт 2 делается в цикле до того момента, как скорость работы станет достаточной.
3. Помни, что на дворе 21 век и компилятор / операционная система / железо умеют оптимизировать выполнение команд. Всякие там кеши жестких дисков, NCQ, оптимизаторы компиляторов и многое многое другое позволяют не делать лишней работы и оставить приложение в понятном виде.
4. Иногда надо добавить ресурсов на сервер. Например, если докинуть памяти, чтобы ее было с избытком, операционка начнет сама кешировать ввод-вывод.

Для справки, обычное .NET MVC приложение (RESTful api), работающее с БД при использовании указанных трех правил удалось оптимизировать на 2 порядлка. И при этом никакие foreach, if и прочая муть не трогалась вообще. Достаточно было прекомпилировать запросы, кешировать некоторые данные в Hashtable и отказаться от Newtonsoft JSON сериализатора в сторону стригбилдеров (что, кстати, дало проирост процентов 15, но было самым геморойным). Итого с двух ядер ноутбука приложение стало выдавать около 1000 запросов в секунду вместо 20-35 до оптимизации.

tyrotoxin Jan 17 2013 at 12:27

Есть различные классы задач, поэтому я всех неоднократно предупреждаю об использовании «здравого смысла» перед применением. Я уверен, что больше чем 85% приложений не требуют таких оптимизаций, но есть другие 15%, причём некоторые могут занимать очень существенную долю рынка. Взгляните на тот же Microsoft SQL Server, там всё есть: страницы базы по 8KiB, использование SIMD (таких как AVX), оптимизация со знанием про кэш-линии процессора, свой менеджер памяти и потоков, и пр. Не стоит сравнивать молоток с дрелью — эти вещи решают разные задачи, но каждую из них тоже можно улучшить по-своему.

Andrey_Kuprikov Jan 17 2013 at 15:04

Вообще глобально любая оптимизация — это повышение скорости работы приложения в ущерб затратам на его дальнейшую поддержку. Чем больше тюнинга, тем хуже код.
Проблема статьи в том, что автор начал оптимизировать приложение слишком рано и начал использовать приемы низкоуровневой оптимизации, которые на сегодняшний день дают небольшой прирост производительности при больших трудозатратах.

tyrotoxin Jan 17 2013 at 15:49

Вообще глобально любая оптимизация — это повышение скорости работы приложения в ущерб затратам на его дальнейшую поддержку. Чем больше тюнинга, тем хуже код.

Я об этом написал не один раз.

Проблема статьи в том, что автор начал оптимизировать приложение слишком рано

Я для сравнения результатов привёл лучшего конкурента на рынке, который существует более десятка лет. Результаты превосходят в разы — это провал?
Вы когда-нибудь читали про микроплатежи и истории самых богатых людей в мире? Можно провести параллель со статьёй ;)

низкоуровневой оптимизации, которые на сегодняшний день дают небольшой прирост производительности

Неверно. Всё зависит от задачи. Вы думаете люди зря придумывают SIMD (MMX, SSE, 3DNow!, AVX и пр.)? nVidia CUDA? Их используют для той же декодировки MPEG видео. И это — низкоуровневая оптимизация.

lair Jan 19 2013 at 12:36

… и о специальном дополнении.

1) HashSet + ToUpperInvariant
2) HashSet + StringComparer.OrdinalIgnoreCase в качесте IEqualityComparer
3) Оптимизированный код — рабочий, а не демонстрационный как в статье.

Спрашивается, где же вариант «HashSet + специально написанный компарер»? Ведь там можно было бы реализовать все ваши оптимизации, при этом для программиста это продолжало бы выглядеть стандартным образом.

C ToUpperInvariant я действительно погорячился, представляя его в статье — метод действительно оказался очень отвратным, но это можно было проверить только опытным путём.

Почему только опытным? Здравый смысл и документация вам не помогают?

И это в очередной раз подтверждает вредность создания новых объектов и неиспользования слияния алгоритмов, которое с большой вероятностью есть в недрах .NET Framework (или Windows).

Это подтверждает вредность нечтения документации. Потому что, как мы видим из вашего же примера, использование документированного (и рекомендуемого) подхода дает прирост в 3.5 раза.

Думайте глобальнее — если функция экономит 400мс в час, то это будет экономия одного часа в год.

Это только в том случае, если эта функция вызывается постоянно.

насколько часто прийдётся менять функцию проверки токена на ключевое слово?

Важно не то, сколько раз придется ее менять, а то, сколько раз придется ее читать.

lair Jan 19 2013 at 15:07

BTW, вот результаты выполнения на моей рабочей машине на массиве реальных данных (4041 скрипт суммарным объемом 58 мегабайт):

ToUpper: 769 мс
StringComparer: 512 мс
Optimized: 267 мс

И вот как-то кажется мне, что цена, которую заплатили за 0,06 мс среднего выигрыша на файле (при том, что читается массив существенно дольше, чем обрабатывается), — 150 строчек неподдерживаемого кода — великовата. И это при том, что из документированных возможностей еще выжато не всё.

tyrotoxin Jan 19 2013 at 18:02

Дорогой lair, я вам всё уже объяснил. Это всего лишь одна функция из сотен, которые используются для синтаксического разбора. Если весь парсер хорошенько оптимизировать, то разница может измерятся в десятках секунд.
Что выпытаетесь доказать?
— Что оптимизация не работает? Она работает, вы согласитесь.
— Что так писать нельзя? Можно — нет сборника законов или «библии», которая говорит как можно писать код а как нельзя.
— Что так писать неразумно? Об этом никто и не спорит, я постоянно в статье твержу что применять такую оптимизацию использовать по необходимости, и что она может привести к «вонючему» сильно связанному коду, который сложно поддерживать, развивать.

lair Jan 19 2013 at 19:15

Что выпытаетесь доказать?

Что надо сначала полностью оптимизировать штатными средствами, а потом уже лезть в unsafe-код. Вы же, как видно из вашего текста, вообще не пробовали работать с этими самими штатными средствами, а сразу полезли писать свою оптимизированную версию.

tyrotoxin Jan 20 2013 at 02:57

Вы так говорите, как будто я пропагандирую такой способ разработки. Я нигде в статье не даю советы как нужно разрабатывать приложения, а вы мне пытаетесь рассказать инное.
Вы понимаете что проект, на котором был поставлен эксперимент такой разработки, просто демонстрирует чего можно добиться? И как это отличается от стандартного подхода «сделать, найти bottleneck, оптимизировать», который представлен конкурентным решением? Почему вы отвергаете такого рода эксперименты и рассказваете мне как «надо» делать?
Вы хотели бы увидеть очередную статью «Как я воспользовался профайлером..»? Я предлагаю другой взгляд на вещи.

lair Jan 20 2013 at 10:58

Вы так говорите, как будто я пропагандирую такой способ разработки.

А так оно и есть.

Я нигде в статье не даю советы как нужно разрабатывать приложения, а вы мне пытаетесь рассказать инное.

«Никаких «foreach»» — это не совет, как нужно разрабатывать приложения?

Вы понимаете что проект, на котором был поставлен эксперимент такой разработки, просто демонстрирует чего можно добиться?

К сожалению, он не показывает, какой ценой.

И как это отличается от стандартного подхода «сделать, найти bottleneck, оптимизировать», который представлен конкурентным решением?

Нет, не понимаю. Я правда не понимаю, почему подход «сделать — определить — оптимизировать» не может привести к такой же производительности, что и ваш.

Почему вы отвергаете такого рода эксперименты и рассказваете мне как «надо» делать?

Не вам — читателям статьи. Почему — потому же, почему и вы считаете нужным рассказывать, как надо делать — потому что я считаю, что понимаю, как надо делать.

tyrotoxin Jan 20 2013 at 15:17

Пожалуйста, прочтите внимательно. Я пишу вначале статьи:

для достижения максимальной производительности приложений, которые этого требуют

Разбор:
• «для производительности приложений» — статья на эту тему
• «достижения » — будет описано как это сделать
• «максимальной» — это значит «предел», дальше некуда
• «которые этого требуют» — слово «которые» относится к слову «приложений» и уточняет подмножество всего множества приложений; «этого» относится к «максимальной производительности»
Т.е. я даю советы только для тех приложений, которые требуют достижение предела в возможной прозводительности. Статья так и называется «Предельная производительность», и не претендует на звание «Guideline для оптимизации всех приложений».
Поэтому в рамках такого подмножества я считаю правомерным давать свои советы. Читатели, которые невнимательно прочли, или не поняли в чём-то суть — это уже не моя ответственность. Любой человек может что-то невнимательно прочитать в том же MSDN и пойти писать «китайский» код (ничего не имею против китайцев, просто такое выражение).

lair Jan 20 2013 at 16:15

для достижения максимальной производительности приложений, которые этого требуют

Дело за малым — определить, какие приложения этого требуют.

Впрочем, даже это не оправдывает фактических ошибок в статье.

tyrotoxin Jan 20 2013 at 16:40

А ошибок ли? Лучше разобраться на реальных примерах, прежде чем утверждать. Ваше право поставить под сомнение — это нормально, но сразу заявлять о некорректности я бы не стал.
Я привёл пример в «Специальном дополнении», но не намерен этого делать по каждому пункту — статья итак слишком большая получилась, да и книгу мне писать не хочется :)

lair Jan 20 2013 at 16:42

А ошибок ли?

Ошибок. Я вам привел конкретный пример с IEnumerable, но вы так и не потрудились исправить.

Что же касается вашего «специального дополнения» — по его поводу я уже тоже написал, и там вы тоже проверять не стали.

tyrotoxin Jan 20 2013 at 15:27

И поймите меня правильно, что я нигде не спорю и не утверждаю что подход «сделать, найти bottleneck, оптимизировать» чем-то плох и нигде не спорю о разумности отимизаций штатными средствами. Статья ориентирована совершенно на другую тематику, и я честно предупреждаю во что может превратится код после таких оптимизаций.

lair Jan 20 2013 at 16:17

Просто вы нигде не сравниваете эффективность вашего кода с эффективностью кода после стандартных оптимизаций. И нигде не указываете стоимость разработки.

tyrotoxin Jan 20 2013 at 17:16

Здесь согласен, этот момент не освещён. Такие замечания действительно полезны, поэтому я их обязательно учту. На самом деле я пишу историю про вторую версию приложения. Первая версия со штатными оптимизациями была на уровне конкурентного решения, где-то чуточку выигрывая. Это был предел, которые мы могли позволить стандартными средствами.

А вот вторая версия была начата с чистого листа, где умение построить понятную программисту архитектуру и совместить её с суровыми оптимизациями — это исскуство. Поэтому не стоит думать, что цена такого подхода слишком большая. Код там — не «манная каша», а хорошо продуманное до мелочей архитектурное решение, которое даже лучше первого (просто код некоторых методов сложнее).

Стоимость разработки — около 1700 человеко-часов. Поверьте, это совсем ничего для такого серъёзного продукта. Всё зависит от мастерства разработчиков, кто-то может потратить в 10 раз больше времени и близко не достичь такого же результата.

lair Jan 20 2013 at 17:21

Стоимость разработки — около 1700 человеко-часов

Осталось сравнить со стоимостью разработки без оптимизаций и задуматься.

tyrotoxin Jan 20 2013 at 17:28

Я уже не помню, но первая версия заняла у команды где-то 15000-17000 человеко-часов — тогда нам приходилось проходить долгий путь изучая много деталей (сколько из них ушло на оптимизацию — тут никто не скажет).
Мы потратили в почти 10 раз меньше времени чтобы это всё переделать с чистого листа и довести до предела. Как вы оцените такие цифры? Неужели всё так плохо и стоит задуматься?

lair Jan 20 2013 at 17:31

Мы потратили в почти 10 раз меньше времени чтобы это всё переделать с чистого листа и довести до предела. Как вы оцените такие цифры?

Не «в десять раз меньше», а «плюс десять процентов» на производительность. Потому что основные бизнес-алгоритмы, насколько я понимаю, уже были разработаны.

Вопрос в том, получили ли вы соответствующий прирост прибыли, и не выгоднее ли было вложить эти ресурсы в разработку новой функциональности.

tyrotoxin Jan 20 2013 at 17:37

Потому что основные бизнес-алгоритмы, насколько я понимаю, уже были разработаны.

мы именно всё переделали с чистого листа, используя накопленный опыт.

Вопрос в том, получили ли вы соответствующий прирост прибыли, и не выгоднее ли было вложить эти ресурсы в разработку новой функциональности.

Это действительно очень интересно, но не по теме статьи :)

lair Jan 20 2013 at 17:38

мы именно всё переделали с чистого листа, используя накопленный опыт.

Предметную область тоже с нуля изучали?

dobriykot Jan 20 2013 at 17:34

Я слежу за вашей беседой с момента написания топика и мне кажется, что вы никак не можете успокоиться и перестать, образно выражаясь, считать чужие деньги. Ваша позиция давно ясна и понятна, ошибки автора обсосаны в комментариях, вы к каждому предложению уже придрались. Решение, которое работает на бою в результате всех махинаций, пусть даже и идеологически неверно написанное, разве это плохо?
Может уже пора остановиться?

lair Jan 20 2013 at 17:36

Решение, которое работает на бою в результате всех махинаций, пусть даже и идеологически неверно написанное, разве это плохо?

Плохо. Это я говорю как человек, которому досталось такое приложение поддерживать и развивать.

dobriykot Jan 20 2013 at 17:41

Конкретно это приложение развивать не вам и от того что вы тут пишете «плохо» написанный код не перепишется. Люди на собеседовании будут уведомлены о предстоящей работе, кому не нравится, тот уйдет. Лично я был бы заинтересован в таком опыте, потому что программируя простую логику и рисуя формы многому не научишься. Самую большую пользу, как мне кажется, приносит работа с такими проектами, которые на границе разумного. Как разработчик на .Net я поставил плюс статье и морально поддерживаю автора. Это интересно.

lair Jan 20 2013 at 17:42

Конкретно это приложение развивать не вам и от того что вы тут пишете «плохо» написанный код не перепишется.

Зато есть надежда, что кто-то подумает, прежде чем порождать еще одно такое же.

Люди на собеседовании будут уведомлены о предстоящей работе, кому не нравится, тот уйдет.

К сожалению, на собеседованиях обычно говорят «поддержка крупной информационной системы, частично унаследованной».

Самую большую пользу, как мне кажется, приносит работа с такими проектами, которые на границе разумного.

Пользу кому? Вам или заказчику?

dobriykot Jan 20 2013 at 17:59

Зато есть надежда, что кто-то подумает, прежде чем порождать еще одно такое же.

Я же сказал, что все давно в комментариях есть. Почитают, подумают, что же вы не успокоитесь?

Пользу кому? Вам или заказчику?

Мне. Заказчику-то какое дело, как там все внутри? Работает быстро и качественно, значит задача решена.

lair Jan 20 2013 at 18:04

Заказчику-то какое дело, как там все внутри? Работает быстро и качественно

Пока работает — действительно, никакого. Но как только начинаются проблемы и/или доработки — заказчику не все равно, что доработка стоит в десять-пятнадцать раз дороже, чем могла бы.

dobriykot Jan 20 2013 at 18:08

Мне кажется, что заказчику нельзя сказать «у нас тут все сложно, поэтому вы платите больше». Есть договора и все такое. Это же не биллинг какой-нибудь, а утилита, можно просто уйти к конкурентам в конце концов.

Я вообще подумал, вижу у вас много доводов против такого подхода. Напишите статью, всем будет полезно почитать другую точку зрения. Вы в этом топике уже столько времени потратили, кучу материала написали, а простыню комментариев мало кто будет читать всю.

lair Jan 20 2013 at 18:10

Мне кажется, что заказчику нельзя сказать «у нас тут все сложно, поэтому вы платите больше». Есть договора и все такое.

Bingo!

Именно поэтому написать код, поддержка которого обойдется компании на порядок дороже — это, по сути, подставить компанию на деньги. Есть такой хороший термин — «технический долг».

dobriykot Jan 20 2013 at 18:25

Ну тут можно долго считать, что лучше — много заказчиков из-за быстрого продукта или дешевая поддержка. Статью будете писать или продолжите длинные споры в комментариях? :)

lair Jan 20 2013 at 18:28

Ну тут можно долго считать, что лучше — много заказчиков из-за быстрого продукта или дешевая поддержка

Ну, известный мне тренд (по крайней мере, в корпоративных информационных системых) — это предпочтение дешевой поддержки.

Статью будете писать или продолжите длинные споры в комментариях?

Да не о чем писать-то.

tyrotoxin Jan 20 2013 at 17:44

Забавно, что кто-то следит за нитью :)
Здесь я с вами согласен — я останавливаюсь комментировать, я не вижу смысла дальнейшего обсуждения, т.к. трачу своё время непонятно на что, когда его можно вложить в изучение новой предметной области :D
Спасибо за сигнал!

Mrrl Jan 20 2013 at 17:56

Несколько новых (или незамеченных старых) предметных областей из комментариев почерпнуть можно. И возникли они как раз в результате обсуждений. И по всему видно, что ещё есть куда стремиться и на низком, и на высоком уровнях оптимизации.

dobriykot Jan 20 2013 at 18:02

Комментарии часто полезные, разные взгляды на одну проблему, новые решения, хитрые ходы. :) Вам спасибо за статью!

tyrotoxin Jan 20 2013 at 17:50

Я бы вам плюс поставил, но карма у меня маленькая — не взлюбила меня публика :)

Mrrl Jan 20 2013 at 18:07

Ничего, я поставлю…
Карма в плюсе — значит, публике, скорее, понравилось, чем нет :)

noldo32 Jan 19 2013 at 17:02

Автору большущий респект за внимание к оптимизации на низком уровне при программировании на высоком. При таких интересах я бы программировал на чем-то более приличном — дающем на выходе полноценные исполняемые файлы с машинным кодом, а не с CLR. Даже если оно и компилируется потом в машинный код ngen-ом и т.д. и т.п., дотнет в общем и целом — зло. Идеологически и архитектурно (я про .net framework).

-8

mezastel Jan 19 2013 at 18:56

Вообще, главное зло — это невежество. А дотнет с точки зрения юзабельности как языка так и библиотек рвет с++ как тузик грелку, даже со всеми новомодными `auto`, лямбдами и пр. И опять же, никто не мешает для использования «плюсов» или например cuda c для оптимизации наиболее критичных участков.

UFO just landed and posted this here

noldo32 Jan 20 2013 at 13:00

Идеологически — это про любой интерпретируемый/управляемый код во всех его вариациях, архитектурно — framework из over 9000 файлов, лишние сервисы Microsoft .NET Framework NGEN и ASP.NET State Service. Даже ругаемый ранее VB за ненастоящий машинный код и тормоза — архитектурно всего 1 DLL (напрмер msvbvm60.dll), вот и весь «framework». Был бы таким дотнет — вопросов к нему бы не было.
А еще версионность: поставил 4.0 для одного софта, а другой софт требует 3.5, что из себя представляет безумный сплав из 2.0, 3.0 и 3.5. В итоге в системе образуется свалка из 4х версий .net framework, каждая из которых поставлена полностью.

-1

lair Jan 20 2013 at 13:13

Идеологически — это про любой интерпретируемый/управляемый код во всех его вариациях

.net не является интерпретируемым кодом. Что же до управляемого кода — вы еще докажите, что идеологически это неверно.

лишние сервисы Microsoft .NET Framework NGEN и ASP.NET State Service

… которые не являются необходимыми для работы .net.

Был бы таким дотнет — вопросов к нему бы не было.

И как вы себе это технологически представляете?

В итоге в системе образуется свалка из 4х версий .net framework, каждая из которых поставлена полностью.

Никакой свалки, четыре независимых версии.

Нет, я понимаю, что вам .net не нравится. Имеете полное право. Только не надо свое личное мнение выдавать за объективное суждение.

tyrotoxin Jan 19 2013 at 17:35

Спасбо вам — хоть один человек сказал вразумительные слова :)
Опять же, это не guidline, а просто пример как можно выжать помаксимуму из .NET. Я сам почти никогда так не пишу, пока это действительно не востребованно.
" дотнет в общем и целом — зло" — тут я предвижу много гнилых помидоров, летящих в вашу сторону :) Эти споры — как религия, никогда ничем хорошим не заканчиваются :)

noldo32 Jan 19 2013 at 18:23

Не только из .NET — я вижу, что перечисленные идеи оптимизации м.б. полезны при программировании на других языках. Предполагаю, что даже больше полезны (из-за большей определенности, в какие машинные команды превратится твой код)

Что касается споров — один вид структуры папок (и общего размера) установленного .net framework, лишние сервисы (которые, если их не отключать, время от времени грузят процессор), долгое «фырчание» жесткого диска при запуске .net приложения (при мгновенном запуске нормального того же функционала) — всё это может быть слишком эстетические, но всё же объективные доводы против использования .NET там, где его можно не использовать

P.S. Предвижу совет использовать SSD или наушники :)

tyrotoxin Jan 19 2013 at 18:36

Предвижу совет использовать SSD или наушники :)

Троллей хватает, так что предвидение вполне реально :)

Я знаю одну ISV компанию, самую крупную в Европе в определенной сфере, которая отказалась от Java, и переписали весь код на С++. Более того они реализовали свой движок распределённой базы данных, которая заточена под конкретную цель. И много чего ещё сделали, чтобы их система могла стоять на самых дешёвых серверах под Linux. Итог — один из самых лучших и известных продуктов, которым пользуются сотни миллионов пользователей по всему миру.
Это на тему советов «серверу добавить памяти, поставить SSD, добавить узлы в датацентр» :)

VSOP_juDGe Jan 19 2013 at 18:55

Мне тоже хочется спросить у автора, а зачем ему C#? :)

tyrotoxin Jan 20 2013 at 14:54

Я очень люблю C# и .NET (особенно WPF по сравнению с WinForms) — классные штуки, которые позволяют быстро и эффективно создавать приложения с минимумом затрат.
После многолетней работы с высокопроизводительными приложениями на C++, assembler + SIMD, CUDA и пр. мне интересно было «А что если применить накопленный опыт в .NET и выжать из него по-максимуму?». Причём проект как раз попался требующий производительности. Эксперимент удался, и принёс отличные плоды, поэтому захотелось написать статью и поделится таким необычным опытом :)

Mrrl Jan 20 2013 at 18:11

Вот только неизвестно, насколько этот опыт необычный. Не так давно в одном из комментариев промелькнуло, что «большинство так пишет» (имелась в виду как раз оптимизация), но я не могу его найти. Может быть, это в самом деле так, просто у тех, кто занят микрооптимизацией, нет времени ходить на Хабр?

tyrotoxin Jan 20 2013 at 18:21

Вот началось с этого коментария. Из всего моего комерческого опыта, на C# как раз так почти никто не пишет :)

Mrrl Jan 20 2013 at 19:04

Да кто же в таком признается :)

tyrotoxin Jan 20 2013 at 19:31

Да вот же:

Начните с … 1. Хороший алгоритм.

Нет, начинать надо с того, что определить, где именно у вас боттлнек (и есть ли он вообще).

В моём понимании это значит: «Давайте сделаем в лоб не задумываясь, а потом найдём проблему и придумаем для неё алгоритм решения» :D

Mrrl Jan 20 2013 at 20:11

«Давайте сделаем в лоб не задумываясь, а потом найдём проблему и придумаем для неё алгоритм решения»

Между прочим, совершенно правильный подход. Только проблему искать не надо, она включает в себя всю программу. Зато теперь можно спокойно искать и реализовывать правильные алгоритмы для всех участков и видеть результат своих действий. Написать сразу-правильную программу на несколько тысяч человеко-часов с нуля, все-таки, довольно рискованное мероприятие.

tyrotoxin Jan 20 2013 at 20:38

проблему искать не надо, она включает в себя всю программу

Вот собственно почему и существует Закон Вирта :)

Написать сразу-правильную программу довольно рискованное мероприятие

Обычно это не проблема для людей с богатым опытом не только в программировании, а в проектировании. Люди, которые знают, например, в чём разница между heapsort и mergesort, не смотря что оба алгоритма работают за O(N*logN), просто не позволят себе плохо написать код изначально ;)

Mrrl Jan 20 2013 at 21:36

Не уверен. Изначально я напишу Array.Sort(). И меня не очень будет беспокоить, что там за алгоритм. Но я сделаю пометку, что можно слегка преобразовать или дополнить сортируемые данные так, что функция сравнения будет гораздо эффективнее, что при определенных усилиях в этом месте можно будет воспользоваться даже radix-сортировкой, но что при ожидаемых масштабах данных массив в память не уместится, поэтому придётся готовиться к тому, чтобы воспользоваться здесь внешней сортировкой. И если сортировка — часть какой-то более сложной обработки (у меня в голове модель — построение k-дерева из большого числа 3D точек, очень скоро предстоит этим заниматься), то когда-нибудь потом придётся делать выбор — выполнять частичную обработку и потом объединять результаты, или выполнять полную внешнюю сортировку и обрабатывать то, что получилось. Или взять промежуточный вариант. И думать об эффективности отдельных этапов. Но всё это потом, а пока — Array.Sort() :)

tyrotoxin Jan 20 2013 at 23:15

Да, согласен, это зависит от многих факторов. В моём случае это была вторая версия, где после первой было накопленно огромное кол-во знаний. И в таком случае, если заранее всё известно, то почему бы не сделать сразу хорошо, чтоб по 100500 раз не переделывать? Опять же, у приложения может не быть требования «быть хорошим или самым лучшим», лень и недобросовестность разработчиков, или просто незнание технической области.
Однозначного ответа здесь нет — всё зависит от конкретной ситуации. Но ваше высказывание правдиво в большей части случаев, т.к. невозможно знать всё наперёд. Я тоже не спешу делать того, что не требуется (YAGNI).

Mrrl Jan 21 2013 at 08:39

Вообще, YAGNI получается как прямое следствие оптимизации: то, что не нужно, отъедает ресурсы, а значит, должно быть вычищено. После чего происходит атака на принцип «Single responsibility»: если одним действием или в одном месте мы можем решить две совершенно разные задачи, то так и будем делать. И когда приходит пора развивать код, то оказывается, что расплетать полученный клубок совсем не просто :(
В проекте у меня идёт активная работа с углами. Чтобы быстрее работать по модулю 360 градусов, я их представляю как целые 32-битные числа (в единицах измерения 360гр/2^32), и вся модулярная арифметика идёт за счет переполнений. Сейчас принято решение расширить диапазон углов до нескольких оборотов, чтобы -1, 359 и 1079 градусов различались. Целыми-то я их оставлю (уменьшив точность в 16 раз, для проекта этого хватит). Но найти все места, где неявно используются переполнения… Страшно.

tyrotoxin Jan 21 2013 at 14:32

Насчёт первого — думаю не совсем так. Я познакомился с YAGNI занимаясь TDD: вначале думали где разместить желаемый код, потом писали тест на несуществующий код, потом писали код чтобы прошёл тест и ничего лишнего. Мы не писали ни лишние тесты, ни лишной код — только удовлетворяли потребности из спецификации — это и есть YAGNI. Если где-то понадобится тот код, который уже есть, то следуя стратегии Red-Green-Refactor, single responsibility (и прочее) сохраняется. Но опять же, есть куча факторов, где это может не работать или быть неразумной тратой времени.
Насчёт второго, если я не ошибаюсь, можно было решить введя константу, значение которой 360гр/2^32. Тогда проблема решилась бы изменением этой константы. Вам виднее, проекта я не видел :)

Mrrl Jan 21 2013 at 15:32

Не решилась бы. Чтобы «повернуться» из точки a на угол b, я пишу просто a+b, зная, что переход через 360 гр отработается правильно. Там придется каждый такой случай отлавливать, и либо оставлять без изменений, либо заменять на (a+b)&ANGLE_MASK…
А константа 2^32/360 уже есть, надеюсь, что вставлена везде, где надо…

KvanTTT Jan 21 2013 at 14:41

17. Освобождение памяти.
…
Здесь можно вывести для себя очень простое правило – как только объект перестаёт быть нужным, обнулите ссылку на него.

Кстати, это тоже довольно странный совет. Судя по stackoverflow, обнулять ссылку на объект почти никогда не нужно, это только портит код. Да и в CLR via C#, насколько я помню, обнулять ссылку нужно в редких случаях, например в условном блоке.

tyrotoxin Jan 21 2013 at 15:15

Как ни странно, .NET и Java призваны избавить рабработчика от слежки за памятью, но «утечки» всё-равно происходят по той причине, что разработчики просто забывают о принципе работы GC. Когда проект разростается до громадных размеров, то визуально представить все связи между всеми классами практически невозможно (нужно учесть не только свои написанные классы, а и frameworks которые используете). Так вы можете пропустить всего одну ссылку при «удалении», а она тянет засобой ещё пару сотен объектов. В итоге, они могут вечно остаться в памяти приложения, и рано или поздно оно упадёт с OutOfMemoryException.
Конечно, если вы на 100% уверены, что некий класс создаёт для внутренних нужд другие объекты, то при «удалении» такого класса действительно нет смысла обнулять ссылки на эти другие объекты. Если вы в этом не уверены, то лишнее присвоение в null не помешает :)

-1

lair Jan 21 2013 at 15:21

Это признак плохой архитектуры (очередной раз).

tyrotoxin Jan 21 2013 at 15:44

Мистер «самый умный» или «переведу стрелки на другого»,
если вы где-то в коде подписались на событие, и забыли отписаться, причём weak reference не используется, то ваш объект (который есть в делегате), останется висеть в памяти, пока тот, у которого объявлено событие (event), не будет «удалён». И это пример не плохой архитектуры, а пример, что нужно за собой чистить ссылки.
Была бы карма у меня побольше, то заминусовал вас за вашу неадекватность! Изучайте мат часть, до того как писать глупости.

lair Jan 21 2013 at 15:48

Так вот, надо не забыть отписаться, а не null проставлять.

tyrotoxin Jan 21 2013 at 15:55

1) отписаться — не архитектурная пролема
2) отписаться — это не магия. Это косвенно ведёт к установке в NULL. В статье говорится в первую очередь про граф, а если ваше воображение заканчивается конструкцией «var = null», то это ваша проблема.
3) перестаньте умничать, это уже не смешно. Это печально.

lair Jan 21 2013 at 15:58

отписаться — не архитектурная пролема

Архитектурная проблема — это то, что вы теряетесь в графе зависимостей между классами.

Это косвенно ведёт к установке в NULL

Вообще-то, нет. Это ведет к убиранию делегата из списка.

tyrotoxin Jan 21 2013 at 16:24

Архитектурная проблема — это то, что вы теряетесь в графе зависимостей между классами.

Вы представляете себе весь .NET Framework? Даже если вы его разработчик? Вы можете рассказать что от чего зависит? Бред! Если вы только не человек с феноменальной памятьи, и если не разрабатывали каждую его часть. Похоже вы никогда не работали над действительно большими проектами, тогда да, в сотне классов сложно заблудиться, конечно.
Причём вы даже неправильно понимаете суть. Архитектура может быть замечательной и понятной, но это только на диаграмме, а вот когда смотришь в код, то видишь офигенное кол-во классов, и связи нужно проставлять не между компонентами архитектуры, а между классами, которые её реализуют, потому что .NET оперирует имеенно объектами для сборки мусора, а не какой-то там диаграммой архитектуры.

Вообще-то, нет. Это ведет к убиранию делегата из списка.

А что такое убрать делегат из списка? Встроенные MulticastDelegate хранят делегаты в обычном массиве []. А Delegate, это какой класс? Immutable. При отписке, создаётся новый MulticastDelegate с новый массивом, где уже нет вашего подписанного делегата. А что происходит со старым массивом? Он висит в памяти до сборки мусора. А при сборке мусора массив будет «удалён», при этом все объекты, на которые он ссыллася станут отвязанными от него, что можно считать установкой в NULL на уровне CLR.

Вы только продолжаете смешить тапочки, всё больше и больше уверяя в вашей неадекватности.

lair Jan 21 2013 at 16:31

Архитектура может быть замечательной и понятной, но это только на диаграмме, а вот когда смотришь в код, то видишь офигенное кол-во классов, и связи нужно проставлять не между компонентами архитектуры, а между классами, которые её реализуют, потому что .NET оперирует имеенно объектами для сборки мусора, а не какой-то там диаграммой архитектуры.

Не пробовали уменьшать количество связей между классами? И в особенности — двунаправленных? После этого проблемы с GC уменьшаются.

А при сборке мусора массив будет «удалён», при этом все объекты, на которые он ссыллася станут отвязанными от него, что можно считать установкой в NULL на уровне CLR.

Вот это ваше «можно считать» — и есть допущение, из которого вы развиваете все свое логическое построение. Можно считать. А можно — не считать.

Mrrl Jan 21 2013 at 16:35

Количество связей надо уменьшать именно между классами? Или между объектами?

lair Jan 21 2013 at 16:36

Между классами.

(между объектами — тоже, но это на моей памяти всегда было следствием неправильных зависимостей между классами)

tyrotoxin Jan 21 2013 at 16:44

Не пробовали уменьшать количество связей между классами?

Идите учите проектированию разработчиков .NET framework.

Можно считать. А можно — не считать.

Считайте как вам угодно, фактов это не изменит.

Разговор окончен.

-1

lair Jan 21 2013 at 16:53

Идите учите проектированию разработчиков .NET framework.

А вы считаете, что BCL везде хорошо спроектирован?

VMAtm Apr 13 2015 at 13:13

Только сейчас наткнулся на пост, спасибо за обзор техник. Обсуждения в комментариях получились ещё более познавательными.
PS: вот откуда у моего вопроса на SO про StructLayout такое количество просмотров :)

mmortall Feb 8 2018 at 23:51

Думаю, про вредность Boxing / Unboxing в этом примере не стоит рассказывать, и надеюсь, вы догадываетесь как это исправить.

Я понятия не имею как переписать этот пример без использования типа object. Можете прояснить этот момент?

Show the best of all time