Отличный учебник-серия статей по оптимизации более-менее реального кода с итогом:
527 times faster than the original version.
Allocate 1350 times less memory.
1/3 of the working set.
Able to process 3.7 GB / sec.
… the first version took about 10 minutes to write, then another half an hour to fiddle with it to make it non obviously inefficient. The final version took several days of careful though, analysis of the data and careful optimizations.
Отличная — не только в плане "пошагово расписаны основные оптимизации", но и в количестве граблей, на которые наступил автор. Вплоть до незамеченных ошибок в последней статье цикла.
Мораль: перфоманс — это конечно хорошо, но для начала надо бы набросать тесты.
UPD, бонус №4 Раз уж в теме зашла речь о OutOfMemory в коллекциях — Understanding OutOfMemoryException, снова Szymon Warda. И таки да, снова баги в коде в теме про производительность. Традиция
Смешно! .NET и перфоманс.
Недавно у меня стояла задача — есть csv на 100ГБ, там логи одного сайта за неделю. Каждая строчка содержит идентификатор пользователя (long в 16-ричном) формате. Я задался вопросом посчитать сколько всего уникальных пользователей и как часто каждый из них встречается. Идея проста — создать Dictionary с ключом по long и value — счетчик. Так вот оно падает по OutOfMemory — стандартные коллекции не могут аллоцировать более 2ГБ памяти. Даже если у тебя всюду стоит 64 бит. Два словаря по 2 Гб можно создать, а вот один — нельзя. Оно доходит до 60000000 строчки и падает. Какой-то жалкий интерпретируемый питон версии 2.7 доходит в несколько раз дальше — до 300000000 строчки. Далее у меня на машине память кончается.
После поста Липперта на эту тему: Ответ Липперта как-то совсем грустно стало.
Re[2]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Gattaka, Вы писали:
G>Смешно! .NET и перфоманс.
Ну тут как: кому-то смешно, кто-то делает
G>Так вот оно падает по OutOfMemory — стандартные коллекции не могут аллоцировать более 2ГБ памяти.
Два варианта — или проблема в исчерпании адресного пространства / фрагментации LOH, или <gcAllowVeryLargeObjects> не указан.
Нехватка АП лечится снятой галочкой prefer 32-bit, фрагментация LOH — обновлением фреймворка и (в тяжёлых случаях) server gc.
G>После поста Липперта на эту тему: Ответ Липперта как-то совсем грустно стало.
А в чём проблема-то?
off-the-shelf parts like Dictionary were designed to solve more common business problems, like mapping zip codes to cities and that sort of thing.
Не подходят стандартные контейнеры — используем сторонние (c5 пойдёт) или пишем свою.
Ну, или как правильно подсказывают в ответах, используем решение, не утыкающееся в память.
Re[3]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, Gattaka, Вы писали:
G>>Смешно! .NET и перфоманс. S>Ну тут как: кому-то смешно, кто-то делает
G>>Так вот оно падает по OutOfMemory — стандартные коллекции не могут аллоцировать более 2ГБ памяти. S>Два варианта — или проблема в исчерпании адресного пространства / фрагментации LOH, или <gcAllowVeryLargeObjects> не указан.
S>Нехватка АП лечится снятой галочкой prefer 32-bit, фрагментация LOH — обновлением фреймворка и (в тяжёлых случаях) server gc.
Нет, это все не работает — проверял, а не просто фантазирую.
G>>После поста Липперта на эту тему: Ответ Липперта как-то совсем грустно стало. S>А в чём проблема-то? S>
S>off-the-shelf parts like Dictionary were designed to solve more common business problems, like mapping zip codes to cities and that sort of thing.
Иными словами над перфомансом особо не задумывались. Просто для решения бизнес-задач. Еще раз отмечу, что у питона таких проблем нет и все работает на ура.
S>Не подходят стандартные контейнеры — используем сторонние (c5 пойдёт) или пишем свою. S>Ну, или как правильно подсказывают в ответах, используем решение, не утыкающееся в память.
Пишем свое — это, конечно сильно. С5-проверим, но на stackoverflow встречал мнение, что ему кампец еще быстрее, чем стандартному Dictionary придет. Но надо проверить.
Re[4]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Gattaka, Вы писали: G>>>Так вот оно падает по OutOfMemory — стандартные коллекции не могут аллоцировать более 2ГБ памяти. G>Нет, это все не работает — проверял, а не просто фантазирую.
using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
namespace LargeArrays
{
public struct ComplexNumber
{
public double Re;
public double Im;
public ComplexNumber(double re, double im)
{
Re = re;
Im = im;
}
}
class Program
{
static void Main(string[] args)
{
var p = new ComplexNumber(1, 1);
int sizeByte = Marshal.SizeOf(typeof(ComplexNumber));
Console.WriteLine("The size of single ComplexNumber struct is={0}", sizeByte);
Console.WriteLine("");
int maxCount = 200 * 1024 * 1024;
var m1 = GC.GetTotalMemory(false);
var dict = new Dictionary<int, ComplexNumber>();
try
{
for (int i = 0; i < maxCount; i++)
{
dict[i] = new ComplexNumber();
}
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
var m2 = GC.GetTotalMemory(false);
Console.WriteLine("Total memory: {0:N2} GB", (m2 - m1) / 1024.0 / 1024);
Console.Read();
}
}
}
— работает, пока хватает памяти G>Иными словами над перфомансом особо не задумывались. Просто для решения бизнес-задач. Еще раз отмечу, что у питона таких проблем нет и все работает на ура.
Если нужны циферки, то в свой время код на .net написанный в лоб без какой-либо оптимизации оказался у нас примерно равен вылизанному варианту PyPy. Просто питон отставал на полтора порядка.
О, вот похожий бенчмарк кстати. Вариант на шарпе там тяп-ляп сделан, если что.
Re[5]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Sinix, Вы писали:
S>Ну вот берём первый попавшийся пример, меняем на словарь
Хм... Мой пример с csv заработал. Единственное что поменялось — я перезагружал компьютер. И да, у меня он падал не один день и не один раз я запускал. Как-то это все хрупко...
Причем на той же машине аналогичный пример на питоне заходил дальше. Сейчас проверю отработает ли он.
G>>Иными словами над перфомансом особо не задумывались. Просто для решения бизнес-задач. Еще раз отмечу, что у питона таких проблем нет и все работает на ура. S>Если нужны циферки, то в свой время код на .net написанный в лоб без какой-либо оптимизации оказался у нас примерно равен вылизанному варианту PyPy. Просто питон отставал на полтора порядка.
S>О, вот похожий бенчмарк кстати. Вариант на шарпе там тяп-ляп сделан, если что.
То что медленее это понятно, но на питоне код получается всяко более локаничный и лучше читаемый.
Re[6]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Gattaka, Вы писали:
G>И да, у меня он падал не один день и не один раз я запускал. Как-то это все хрупко...
Угу, работа с непрерывными объёмами памяти больших размеров — то ещё приключение. Оно, конечно, чинится, причём масштабно (в дотнете для этого вот-вот зарелизят ArrayPool<T> и затем — Memory<T> для коллекций структур поверх unmanaged- кусков памяти), но когда это всё ещё будет...
Re[7]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, Gattaka, Вы писали:
G>>И да, у меня он падал не один день и не один раз я запускал. Как-то это все хрупко... S>Угу, работа с непрерывными объёмами памяти больших размеров — то ещё приключение. Оно, конечно, чинится, причём масштабно (в дотнете для этого вот-вот зарелизят ArrayPool<T> и затем — Memory<T> для коллекций структур поверх unmanaged- кусков памяти), но когда это всё ещё будет...
Здравствуйте, Gattaka, Вы писали:
G>Здравствуйте, Sinix, Вы писали:
G>Смешно! .NET и перфоманс. G>Недавно у меня стояла задача — есть csv на 100ГБ, там логи одного сайта за неделю. Каждая строчка содержит идентификатор пользователя (long в 16-ричном) формате. Я задался вопросом посчитать сколько всего уникальных пользователей и как часто каждый из них встречается. Идея проста — создать Dictionary с ключом по long и value — счетчик. Так вот оно падает по OutOfMemory — стандартные коллекции не могут аллоцировать более 2ГБ памяти. Даже если у тебя всюду стоит 64 бит. Два словаря по 2 Гб можно создать, а вот один — нельзя. Оно доходит до 60000000 строчки и падает. Какой-то жалкий интерпретируемый питон версии 2.7 доходит в несколько раз дальше — до 300000000 строчки. Далее у меня на машине память кончается. G>После поста Липперта на эту тему: Ответ Липперта как-то совсем грустно стало.
Восстанавливаю пробелы в знаниях. Вопрос не конкретно по дотнет, а по работе ОС с устройствами ввода/вывода: здесь есть такой комментарий
To clarify, the main benefit of memory-mapping in this case (I think) is that it drastically reduces the number of syscalls and memory copies required to access the data.
Reading a typical stream:
1)OS reads from disk into a buffer.
2)Application library code requests data from OS, which involves copying from the OS buffer into the application's buffer (typically 4K for .NET buffered streams?). This also involves a syscall so it might cause a context switch.
3)Application copies from its buffer into smaller structures.
And that's assuming that the application is using a buffered stream. Otherwise, pretty much every tiny read could result in a syscall.
Reading a memmapped file effectively bypasses the second step, mapping the page read from disk directly into the application's memory space. By using unsafe code and dealing with the bytes in-place, we can skip the third step too.
Это получается, что на каждый чих взаимодействия с I/O мы данные дважды копируем -- сначала в адресное пр-во ядра (буфер), потом в адресное пр-во программы (буфер)? Во дела , это же дико не эффективно. Я на эту тему не задумывался, но мне казалось там без двойного копирования. И единственный способ этого избежать -- mmf, так?
Весьма интересная и познавательная серия, и комментарии крайне любопытны. Но люди там не зря советовали за рад микросекунд такие задачи на С/С++ делать.
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, Sinix, Вы писали:
S>Восстанавливаю пробелы в знаниях. Вопрос не конкретно по дотнет, а по работе ОС с устройствами ввода/вывода:
Смысл в чём: вместо чтения через StreamReader.ReadBlock() вот тут код был заменён на MemoryMappedFile и на прямую работу с блоками памяти из MMF.
StreamReader.ReadBlock() работает с массивом char, т.е. сразу добавляем расходы на преобразование utf-8=>utf-16. Ну, т.е. код незаметно подменяется более специализированной версией, есть такой момент.
По памяти, примерно то же самое можно было бы изобразить и на простых потоках, но код был бы сложнее за счёт кучи ручной работы с буферами. Ну, или чуть сложнее, чуть помедленнее, но зато без unsafe. На blittable-структурах и SafeBuffer<T>.
S>Но люди там не зря советовали за рад микросекунд такие задачи на С/С++ делать.
Или дождаться кучи исправлений для .net core vNext, включая Memory<T>. Там нет никакой магии, которая требует натива, на самом деле.
Здравствуйте, Sharov, Вы писали:
S>Весьма интересная и познавательная серия, и комментарии крайне любопытны. Но люди там не зря советовали за рад микросекунд такие задачи на С/С++ делать.
У Rico Mariani в блоге был цикл постов про то, как Raymond Chen на С++ оптимизировал парсер для Китайско-Английского словаря. Rico Mariani параллельно написал несколько версий на C#. C++ в конце победил, но как-то пиррово.
Здравствуйте, Sinix, Вы писали: S>Или дождаться кучи исправлений для .net core vNext, включая Memory<T>. Там нет никакой магии, которая требует натива, на самом деле.
Здравствуйте, Codechanger, Вы писали:
S>>Или дождаться кучи исправлений для .net core vNext, включая Memory<T>. Там нет никакой магии, которая требует натива, на самом деле.
C>Про Memory<T> есть где подробнее почитать?
Докинул в стартовый пост.
Re: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Sinix, Вы писали:
S>>Восстанавливаю пробелы в знаниях. Вопрос не конкретно по дотнет, а по работе ОС с устройствами ввода/вывода:
S>Смысл в чём: вместо чтения через StreamReader.ReadBlock() вот тут код был заменён на MemoryMappedFile и на прямую работу с блоками памяти из MMF.
S>StreamReader.ReadBlock() работает с массивом char, т.е. сразу добавляем расходы на преобразование utf-8=>utf-16. Ну, т.е. код незаметно подменяется более специализированной версией, есть такой момент.
S>По памяти, примерно то же самое можно было бы изобразить и на простых потоках, но код был бы сложнее за счёт кучи ручной работы с буферами. Ну, или чуть сложнее, чуть помедленнее, но зато без unsafe. На blittable-структурах и SafeBuffer<T>.
Это я все понял. Я спрашивал про принципы работы ОС с I/O устройствами -- т.е. мы сначала копируем в буфер ядра, потом копируем в буфер пользовательского процесса. Это так или не так? Этот вопрос можно вынести на более широкое обсуждение, если захотите. Это либо в ветку win api, либо аsm, либо в железо на худой конец.
Кодом людям нужно помогать!
Re[2]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Serginio1, Вы писали:
S>Кстати собираются они сделать A new stackalloc operator for reference types with CoreCLR and Roslyn
Пока неясно. В смысле, что-то точно будет, но что получится в итоге: auto-stackalloc, local memory heaps, explicit stackalloc или что-то ещё — .
Заметных с точки зрения GC проблем в принципе четыре:
* куча аллокаций в gc0 для IEnumerable<>, string.Format() etc. — это как раз stackalloc сотоварищи.
* долгоживущие объекты в огромных количествах — может быть решено через ArrayPool<T>, Memory<T>, explicit heaps etc.
* pinned objects в GC0 и большие короткоживущие массивы — пулинг ч/з ArrayPool<T> обычно.
* большие коллекции — chunked-коллекции поверх ArrayPool<T>
Здравствуйте, Sharov, Вы писали:
S>Это я все понял. Я спрашивал про принципы работы ОС с I/O устройствами -- т.е. мы сначала копируем в буфер ядра, потом копируем в буфер пользовательского процесса. Это так или не так?
Оффтоп слегка, поэтому отделаюсь ссылками: раз, два.
Re[2]: Минутка хардкора-4: Ayende Rahien: How much is the fish?
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, Sharov, Вы писали:
S>>Это я все понял. Я спрашивал про принципы работы ОС с I/O устройствами -- т.е. мы сначала копируем в буфер ядра, потом копируем в буфер пользовательского процесса. Это так или не так? S>Оффтоп слегка, поэтому отделаюсь ссылками: раз, два.
Благодарю, вторая ссылка то что надо Можно мне было не флеймить, а открыть книжку Соломона и Руссиновича
, это же дико не эффективно. Я на эту тему не задумывался, но мне казалось там без двойного копирования. И единственный способ этого избежать -- mmf, так?
Можно мне было не флеймить, а открыть книжку Соломона и Руссиновича 
