tyrotoxin 14 янв 2013 в 14:03

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

56 мин

264K

Высокая производительность*Параллельное программирование*Программирование*

Из песочницы

+45

289

Комментарии 289

dixx 14 янв 2013 в 14:10

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

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

tyrotoxin 14 янв 2013 в 14:32

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

dixx 14 янв 2013 в 14:37

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

mejedi 20 янв 2013 в 11:08

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

Ringess 14 янв 2013 в 14:11

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

tyrotoxin 14 янв 2013 в 14:14

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

OpenMinded 14 янв 2013 в 15:29

Как насчет X?

tyrotoxin 14 янв 2013 в 15:49

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

ad1Dima 15 янв 2013 в 01:41

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

tyrotoxin 15 янв 2013 в 01:53

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

ad1Dima 15 янв 2013 в 02:02

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

shai_hulud 14 янв 2013 в 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 типов
б) разное выравнивание структур на разных архитектурах

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

tyrotoxin 14 янв 2013 в 15:48

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

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

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

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

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

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

shai_hulud 14 янв 2013 в 16:39

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

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

MoveNext и Current

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

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

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

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

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

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

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

centur 14 янв 2013 в 15:16

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

Jholinar 14 янв 2013 в 15:35

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

lair 14 янв 2013 в 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>) вы не в курсе?

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

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

tyrotoxin 14 янв 2013 в 16:04

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

lair 14 янв 2013 в 16:08

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

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

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

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

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

Да.

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

shai_hulud 14 янв 2013 в 17:36

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

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

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

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

VladVR 14 янв 2013 в 23:42

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

lair 15 янв 2013 в 00:17

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

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

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

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

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

tyrotoxin 15 янв 2013 в 00:33

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

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

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

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

lair 15 янв 2013 в 00:46

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

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

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

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

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

tyrotoxin 15 янв 2013 в 01:22

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

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

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

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

lair 15 янв 2013 в 11:14

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

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

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

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

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

VladVR 15 янв 2013 в 15:13

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

lair 15 янв 2013 в 15:17

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

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

VladVR 15 янв 2013 в 16:39

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

lair 15 янв 2013 в 16:46

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

ivanov 15 янв 2013 в 18:06

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

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

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

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

lair 15 янв 2013 в 18:12

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

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

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

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

ivanov 15 янв 2013 в 18:36

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

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

lair 15 янв 2013 в 18:38

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

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

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

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

tyrotoxin 15 янв 2013 в 22:42

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

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

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

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

ivanov 16 янв 2013 в 08:41

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

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

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

tyrotoxin 17 янв 2013 в 14:50

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

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

VladVR 15 янв 2013 в 07:55

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

tyrotoxin 15 янв 2013 в 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;
}

lair 15 янв 2013 в 13:49

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

VladVR 15 янв 2013 в 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 15 янв 2013 в 22:56

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

VladVR 15 янв 2013 в 23:09

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

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

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

VladVR 15 янв 2013 в 23:16

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

tyrotoxin 15 янв 2013 в 23:20

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

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

lair 15 янв 2013 в 23:21

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

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

tyrotoxin 15 янв 2013 в 23:23

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

lair 15 янв 2013 в 23:29

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

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

xXxVano 17 янв 2013 в 10:29

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

lair 17 янв 2013 в 10:33

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

xXxVano 17 янв 2013 в 10:49

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

Вроде нет.

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

lair 17 янв 2013 в 10:52

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

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

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

xXxVano 17 янв 2013 в 11:20

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

tyrotoxin 18 янв 2013 в 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 18 янв 2013 в 18:37

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

tyrotoxin 19 янв 2013 в 07:22

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

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

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

lair 19 янв 2013 в 12:41

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

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

habrahabr.ru/post/165729/#comment_5742425

shai_hulud 17 янв 2013 в 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 19 янв 2013 в 18:01

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

tyrotoxin 15 янв 2013 в 13:28

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

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

FuriCuri 14 янв 2013 в 15:32

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

tyrotoxin 14 янв 2013 в 16:08

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

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

Illivion 14 янв 2013 в 15:49

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

tyrotoxin 14 янв 2013 в 16:05

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

Illivion 14 янв 2013 в 16:16

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

tyrotoxin 14 янв 2013 в 17:10

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

Illivion 14 янв 2013 в 17:41

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

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

ivanov 15 янв 2013 в 18:46

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

lair 14 янв 2013 в 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.

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

tyrotoxin 14 янв 2013 в 17:12

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

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

lair 14 янв 2013 в 17:15

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

tyrotoxin 14 янв 2013 в 17:21

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

lair 14 янв 2013 в 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 14 янв 2013 в 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 14 янв 2013 в 16:29

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

leventov 14 янв 2013 в 16:26

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

tyrotoxin 14 янв 2013 в 16:45

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

leventov 14 янв 2013 в 16:51

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

tyrotoxin 14 янв 2013 в 16:58

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

alan008 15 янв 2013 в 09:42

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

tyrotoxin 15 янв 2013 в 12:25

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

lair 15 янв 2013 в 12:30

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

tyrotoxin 15 янв 2013 в 12:38

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

lair 15 янв 2013 в 13:50

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

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

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

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

lexx2real 20 мая 2013 в 10:32

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

alan008 15 янв 2013 в 13:20

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

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

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

KvanTTT 15 янв 2013 в 16:17

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

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

ivanov 15 янв 2013 в 17:54

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

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

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

tyrotoxin 14 янв 2013 в 17:02

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

ToSHiC 14 янв 2013 в 16:31

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

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

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

tyrotoxin 14 янв 2013 в 16:49

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

ivanov 15 янв 2013 в 17:44

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

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

ToSHiC 15 янв 2013 в 17:57

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

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

ivanov 15 янв 2013 в 20:19

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

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

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

ToSHiC 15 янв 2013 в 20:53

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

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

ivanov 15 янв 2013 в 21:08

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

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

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

ToSHiC 15 янв 2013 в 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 16 янв 2013 в 09:07

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

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

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

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

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

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

ToSHiC 16 янв 2013 в 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 17 янв 2013 в 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 17 янв 2013 в 14:22

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

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

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

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

ivanov 17 янв 2013 в 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 17 янв 2013 в 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 18 янв 2013 в 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 18 янв 2013 в 15:44

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

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

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

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

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

ivanov 18 янв 2013 в 16:33

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

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

ToSHiC 18 янв 2013 в 16:36

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

ivanov 18 янв 2013 в 16:53

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

tyrotoxin 15 янв 2013 в 23:07

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

ivanov 16 янв 2013 в 08:47

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

retran 14 янв 2013 в 17:38

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

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

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

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

tyrotoxin 14 янв 2013 в 17:46

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

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

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

lair 14 янв 2013 в 17:54

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

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

VenomBlood 14 янв 2013 в 19:02

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

retran 14 янв 2013 в 18:44

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

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

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

UnknownGosu 15 янв 2013 в 00:05

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

НЛО прилетело и опубликовало эту надпись здесь

tyrotoxin 14 янв 2013 в 17:57

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

UnknownGosu 15 янв 2013 в 00:10

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

UnknownGosu 15 янв 2013 в 04:57

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

ramntry 14 янв 2013 в 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 14 янв 2013 в 23:01

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

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

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

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

ramntry 14 янв 2013 в 23:40

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

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

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

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

tyrotoxin 15 янв 2013 в 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 мс.

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

leventov 15 янв 2013 в 00:30

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

tyrotoxin 15 янв 2013 в 00:39

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

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

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

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

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

leventov 15 янв 2013 в 01:40

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

tyrotoxin 15 янв 2013 в 01:48

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

Mrrl 15 янв 2013 в 07:03

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

leventov 15 янв 2013 в 16:26

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

ramntry 15 янв 2013 в 01:03

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

KvanTTT 15 янв 2013 в 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 15 янв 2013 в 00:52

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

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

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

KvanTTT 15 янв 2013 в 01:02

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

ramntry 15 янв 2013 в 01:14

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

Mrrl 15 янв 2013 в 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 15 янв 2013 в 01:07

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

Mrrl 15 янв 2013 в 00:16

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

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

KvanTTT 15 янв 2013 в 00:58

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

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

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

Mrrl 15 янв 2013 в 01:03

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

KvanTTT 15 янв 2013 в 01:13

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

Mrrl 15 янв 2013 в 01:17

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

tyrotoxin 14 янв 2013 в 20:08

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

ramntry 14 янв 2013 в 21:20

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

micbsv 14 янв 2013 в 21:28

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

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

NeoNN 14 янв 2013 в 22:39

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

tyrotoxin 14 янв 2013 в 22:42

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

NeoNN 14 янв 2013 в 23:02

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

alex_shabalin 14 янв 2013 в 22:46

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

lair 14 янв 2013 в 22:58

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

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

KvanTTT 14 янв 2013 в 23:04

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

tyrotoxin 14 янв 2013 в 23:16

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

23derevo 14 янв 2013 в 23:13

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

KvanTTT 14 янв 2013 в 23:09

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

НЛО прилетело и опубликовало эту надпись здесь

KvanTTT 15 янв 2013 в 01:07

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 01:13

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

НЛО прилетело и опубликовало эту надпись здесь

ramntry 15 янв 2013 в 01:23

en.wikipedia.org/wiki/ILAsm

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 07:00

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

Mrrl 15 янв 2013 в 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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 07:02

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 10:23

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

KvanTTT 15 янв 2013 в 17:05

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

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

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

Mrrl 15 янв 2013 в 17:29

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

KvanTTT 15 янв 2013 в 17:39

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

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

VenomBlood 20 янв 2013 в 21:09

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

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

KvanTTT 20 янв 2013 в 22:26

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

VenomBlood 20 янв 2013 в 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 20 янв 2013 в 22:46

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

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

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

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

НЛО прилетело и опубликовало эту надпись здесь

KvanTTT 15 янв 2013 в 20:13

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 20:59

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 15 янв 2013 в 22:40

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

Mrrl 17 янв 2013 в 18:18

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 20 янв 2013 в 10:15

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

lair 20 янв 2013 в 11:00

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

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

Mrrl 20 янв 2013 в 11:09

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

lair 20 янв 2013 в 11:13

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

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

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

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

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

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

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

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

Mrrl 20 янв 2013 в 11:36

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

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

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

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

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

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

lair 20 янв 2013 в 11:39

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

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

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

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

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

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

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

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

Mrrl 20 янв 2013 в 11:57

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

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

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

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

lair 20 янв 2013 в 11:23

Ну и да.

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

Mrrl 20 янв 2013 в 11:39

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

НЛО прилетело и опубликовало эту надпись здесь

Mrrl 20 янв 2013 в 11:44

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

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

НЛО прилетело и опубликовало эту надпись здесь

KvanTTT 15 янв 2013 в 01:29

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

Mrrl 15 янв 2013 в 01:36

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

Mrrl 16 янв 2013 в 17:45

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

Mrrl 15 янв 2013 в 01:11

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

Weageoo 15 янв 2013 в 01:22

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

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

onikiychuka 15 янв 2013 в 10:19

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

НЛО прилетело и опубликовало эту надпись здесь

shai_hulud 15 янв 2013 в 11:32

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

НЛО прилетело и опубликовало эту надпись здесь

shai_hulud 15 янв 2013 в 11:54

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

НЛО прилетело и опубликовало эту надпись здесь

shai_hulud 15 янв 2013 в 23:34

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

lair 15 янв 2013 в 11:37

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

lair 15 янв 2013 в 13:53

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

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

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

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

tyrotoxin 15 янв 2013 в 23:18

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

lair 15 янв 2013 в 23:23

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

tyrotoxin 15 янв 2013 в 23:29

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

lair 15 янв 2013 в 23:30

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

tyrotoxin 15 янв 2013 в 23:45

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

lair 16 янв 2013 в 00:11

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

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

dmOx 15 янв 2013 в 18:36

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

lair 16 янв 2013 в 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 17 янв 2013 в 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 17 янв 2013 в 12:27

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

Andrey_Kuprikov 17 янв 2013 в 15:04

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

tyrotoxin 17 янв 2013 в 15:49

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

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

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

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

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

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

lair 19 янв 2013 в 12:36

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

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

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

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

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

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

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

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

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

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

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

lair 19 янв 2013 в 15:07

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

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

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

tyrotoxin 19 янв 2013 в 18:02

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

lair 19 янв 2013 в 19:15

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

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

tyrotoxin 20 янв 2013 в 02:57

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

lair 20 янв 2013 в 10:58

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

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

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

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

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

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

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

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

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

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

tyrotoxin 20 янв 2013 в 15:17

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

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

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

lair 20 янв 2013 в 16:15

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

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

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

tyrotoxin 20 янв 2013 в 16:40

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

lair 20 янв 2013 в 16:42

А ошибок ли?

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

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

tyrotoxin 20 янв 2013 в 15:27

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

lair 20 янв 2013 в 16:17

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

tyrotoxin 20 янв 2013 в 17:16

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

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

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

lair 20 янв 2013 в 17:21

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

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

tyrotoxin 20 янв 2013 в 17:28

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

lair 20 янв 2013 в 17:31

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

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

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

tyrotoxin 20 янв 2013 в 17:37

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

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

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

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

lair 20 янв 2013 в 17:38

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

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

dobriykot 20 янв 2013 в 17:34

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

lair 20 янв 2013 в 17:36

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

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

dobriykot 20 янв 2013 в 17:41

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

lair 20 янв 2013 в 17:42

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

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

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

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

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

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

dobriykot 20 янв 2013 в 17:59

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

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

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

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

lair 20 янв 2013 в 18:04

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

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

dobriykot 20 янв 2013 в 18:08

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

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

lair 20 янв 2013 в 18:10

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

Bingo!

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

dobriykot 20 янв 2013 в 18:25

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

lair 20 янв 2013 в 18:28

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

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

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

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

tyrotoxin 20 янв 2013 в 17:44

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

Mrrl 20 янв 2013 в 17:56

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

dobriykot 20 янв 2013 в 18:02

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

tyrotoxin 20 янв 2013 в 17:50

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

Mrrl 20 янв 2013 в 18:07

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

noldo32 19 янв 2013 в 17:02

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

mezastel 19 янв 2013 в 18:56

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

НЛО прилетело и опубликовало эту надпись здесь

noldo32 20 янв 2013 в 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, каждая из которых поставлена полностью.

lair 20 янв 2013 в 13:13

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

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

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

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

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

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

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

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

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

tyrotoxin 19 янв 2013 в 17:35

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

noldo32 19 янв 2013 в 18:23

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

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

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

tyrotoxin 19 янв 2013 в 18:36

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

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

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

VSOP_juDGe 19 янв 2013 в 18:55

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

tyrotoxin 20 янв 2013 в 14:54

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

Mrrl 20 янв 2013 в 18:11

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

tyrotoxin 20 янв 2013 в 18:21

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

Mrrl 20 янв 2013 в 19:04

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

tyrotoxin 20 янв 2013 в 19:31

Да вот же:

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

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

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

Mrrl 20 янв 2013 в 20:11

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

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

tyrotoxin 20 янв 2013 в 20:38

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

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

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

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

Mrrl 20 янв 2013 в 21:36

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

tyrotoxin 20 янв 2013 в 23:15

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

Mrrl 21 янв 2013 в 08:39

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

tyrotoxin 21 янв 2013 в 14:32

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

Mrrl 21 янв 2013 в 15:32

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

KvanTTT 21 янв 2013 в 14:41

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

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

tyrotoxin 21 янв 2013 в 15:15

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

lair 21 янв 2013 в 15:21

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

tyrotoxin 21 янв 2013 в 15:44

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

lair 21 янв 2013 в 15:48

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

tyrotoxin 21 янв 2013 в 15:55

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

lair 21 янв 2013 в 15:58

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

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

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

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

tyrotoxin 21 янв 2013 в 16:24

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

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

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

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

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

lair 21 янв 2013 в 16:31

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

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

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

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

Mrrl 21 янв 2013 в 16:35

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

lair 21 янв 2013 в 16:36

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

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

tyrotoxin 21 янв 2013 в 16:44

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

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

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

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

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

lair 21 янв 2013 в 16:53

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

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

VMAtm 13 апр 2015 в 13:13

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

mmortall 8 фев 2018 в 23:51

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

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

Комментарии 289

Публикации

Истории