Жирные программы — факторы скорости
Картинка из фильма «Размер имеет значение», 2009Данная статья была начата в апреле 2016 г в результате того, что компьютер опять стал работать медленнее, чем я щелкаю мышкой. Собственно, она является компиляцией многих тестов (некоторых еще с 2010 г) и обсуждений с моим участием. Ее нельзя назвать полностью законченной, поскольку это не окончательные выводы, а некие промежуточные точки, показывающие на что обратить внимание и куда копать дальше.
Название частично позаимствовано из статьи Никлауса Вирта «Долой «жирные» программы», которой в 2016 г было ровно 10 лет, и актуальности она не утратила —, а скорее вышла на новый уровень, кто не знаком — почитайте.
Рассмотрим разные аспекты, влияющие на производительность систем и программ.
Языковой аспект
Аспекты памяти
Аспекты реального мира
Неязыковые факторы
Аспект человеческого фактора
Языковой аспект
а) Влияние языка программирования и компилятора
Как я и говорил ранее в комментариях, использование «хорошего» языка дает приличную разницу в скорости.
За точку отсчета возьмем старый добрый С. Понятно, что применив достаточно усердия, на ассемблере можно сделать лучше, но пусть ассемблерный мир, и связанные с ними тонкие настройки высших порядков, останется слабодосягаемым идеалом.
Рассмотрим оценку аспекта в двух вариантах — бизнес приложение, мало зависящее от вычислений с плавающей точкой, и чисто вычислительную задачу.
Далее пройдемся по градации между ними.
Тест для целочисленных вычислений — это Dhrystone (я знаю, что он старый и плохой, но для оценки глубины норы вполне годится — в нем хороший набор фундаментальных операция языка).
Копии и модифицированные исходники я выложил здесь github.com/Siemargl/FatProgs
Крайними точками отрезка являются оптимизированная С-программа и интерпретируемая Python3.6 программа (не потому, что Питон мне не нравится, но потому что он на предыдущих подобных тестах всем проиграл и является точкой Б, да еще и нужные тесты для него есть уже готовые)
>gcc -O2 -DTIME -DHZ= dhry_1.c dhry_2.c -o gcc_dry2
D:\VSProjects\_pl_benchmark\Dhrystone>gcc --version
gcc.EXE (tdm-1) 4.9.2
>gcc_dry2 500000000
User time = 27 sec
Microseconds for one run through Dhrystone: 0.1
Dhrystones per Second: 18518518.0
DMIPS 10539.9
>python.exe pystone.py
Pystone (1.2) time for 5000000 passes = 46.4937
This machine benchmarks at 107542 pystones/second
Разница в скорости в 172 раза. Если посмотреть исходники, то пистоуны это и есть драйстоуны в оригинале.
Для исключения махинаций, возьмем еще TinyC — который не умеет оптимизировать в принципе
>cc_dry2.exe 500000000
User time = 55 sec
Microseconds for one run through Dhrystone: 0.1
Dhrystones per Second: 9090909.0
DMIPS 5174.1
«Всего» в 84 раза быстрее интерпретатора, и вдвое медленнее оптимизированной версии.
Тест вычислений с плавающей точкой, например Scimark2 (он тоже старый и до сих пор используется, например в пакете performance
D:\VSProjects\Python36\python.exe pyperformance run -o py3z.json -b=scimark
Python version: 3.6.0 (64-bit) revision 41df79263a11
Report on Windows-7–6.1.7601-SP1
Number of logical CPUs: 4
Start date: 2017–01–19 03:03:35.583496
End date: 2017–01–19 03:07:00.042133
### scimark_fft ###
Median ± std dev: 863 ms ± 4 ms
### scimark_lu ###
Median ± std dev: 462 ms ± 10 ms
### scimark_monte_carlo ###
Median ± std dev: 247 ms ± 2 ms
### scimark_sor ###
Median ± std dev: 577 ms ± 6 ms
### scimark_sparse_mat_mult ###
Median ± std dev: 10.3 ms ± 0.1 ms
Результаты для одинакового с Питоном по количеству итераций теста на С
>gcc -mfpmath=sse -march=native -O2
FFT ms*50: 2.06 (N=1024)
SOR ms*10: 0.59 (100×100)
MonteCarlo: ms*1e5: 1.51
Sparse matmult ms: 0.79 (N=1000, nz=50000)
LU ms: 0.32 (M=100, N=100)
Расшифровка — Питоновский тест показывает время на одно выполнение теста, но которое может содержать разное количество одинаковых итераций, например преобразование Фурье считается 50 раз, что отражено множителем в С-результатах.
Здесь разница на разных тестах может достигать 1500 раз (мне это не нравится, выглядит подозрительно большой — так что желающие найти ошибки в тестировании — приветствуются)
Отключение оптимизаций и SIMD на С дает в 3–4 раза более медленный результат
FFT ms*50: 8.80 (N=1024)
SOR ms*10: 0.66 (100×100)
MonteCarlo: ms*1e5: 4.04
Sparse matmult ms: 2.87 (N=1000, nz=50000)
LU ms: 1.11 (M=100, N=100)
Теперь о градации.
Если не брать в расчет чистые интерпретаторы вроде питона и старого PHP, все компиляторы и большинство JIT-машин укладываются в диапазон x2-x4, причем лучший JIT у Java и отстает в даже в наихудших случаях менее чем в 2 раза, а неправильными опциями компиляции С-программа расчета FFT, например замедляется впятеро.
С другой стороны, если посмотреть сюда, — в современном мире Javascript«а интерпретатор от вас гораздо ближе, чем вы думаете.
Способ измерения данного фактора приведен выше.
Оценка. Поскольку впереди еще много факторов, я бы оценил этот фактор скорости, как малозначимый, кроме узкого круга чисто вычислительных задач.
б) Влияние парадигмы программирования
На примере C++/D. Эти языки добавляют две основные парадигмы — ООП и шаблонное метапрограммирование. Дифирамбов им я петь не буду — посмотрим как это влияет на производительность.
Использование метапрограммирования. Шаблоны, макросы, частично дженерики (хотя объекты относятся к худшей карме). Шаблоны развернутся в код без потери в производительности или же даже с выгодой в скорости, поскольку функции inline«тся и исчезают потери на вызов. Всё, чем грозит их применение — это code bloating из-за генерации копий кода одних и тех же алгоритмов для разных типов данных.
Использование ООП. Здесь проблема в том, что как только вы взяли объектик из фреймворка, тот «позвал» присоединиться в вашу программу своего папу, маму, и всех родственников, даже если они в вашей программе не используются (линкеры и класс-загрузчики не такие умные, как хотелось бы). Они вместе съедят время на загрузку с диска, место в памяти и в кэше процессора. Это тоже к аспекту памяти.
Чуть не забыл — некоторые техники привнесенные дополнительно к ООП, например исключения, или другие продвинутые, тоже не совсем бесплатны.
Как измерить аспект — есть Тесты Степанова, показывающий ускорение до 2х раз при разворачивании вызовов и потери до 2% на виртуальные вызовы, но влияние code bloating оценить крайне трудно, см. ниже аспект памяти.
Оценка этого фактора скорости — от малозначимого до заметного.
в) Байт кодовые машины (BCVM)
Находятся посередине по производительности между компиляторами в машинный код и интерпретаторами, близко к первым.
Здесь существенна разница, будет ли промежуточный байт-код компилироваться JIT либо AOT, или же будет интерпретироваться. Также возможен смешанный вариант, когда BCVM проектировалась для другого языка и часть кода невозможно оттранслировать в Пи-код этой машины.
В любом случае, мы платим либо временем загрузки, либо памятью. Например, Java JIT обходится примерно в 100Мб памяти, что уже существенно, хотя результирующий код очень быстр и использует SIMD (проверено на днях в статье про ФФТ)
Как измерить — использовать тесты, зачастую достаточно посмотреть в Интернете, на что то вроде этого
Оценка этого фактора скорости — если JIT хорош, то малозначимый, но плюсом идет аспект памяти, а если же байт машина — интерпретатор или «чужая», то увы.
Аспекты памяти
а) Стековое размещение
— не стоит ничего, обращение же к менеджеру динамической памяти уже часто тянет системный вызов. Вкупе со сборщиком мусора и фрагментацией памяти может составлять проблему для систем 24/7.
Если ваш язык позволяет временные локальные объекты создавать без использования хипа, вы будете в выигрыше.
Измеряется тестами, само по себе стоит мало, но может тянуть за собой аспекты ниже.
б) Сборщик мусора (GC)
— непонятно, благословение для новичков или проклятие для «больших» —, но поскольку с ним иногда приходится бороться, негативный фактор.
Измерение тестами затруднительно, требуется сложная диагностика поведения GC служебными средствами BCVM.
Оценка фактора — для больших систем могут возникать существенные непрогнозируемые лаги.
в) Динамическая загрузка
Когда мы запускаем новый класс — например открываем в программе новое окошко, происходит две вещи — нужно загрузить кусок связанного кода в случае машинного кода или фреймворка в случае BCVM- (смотрим про ООП и мать их всех родственников) и запустить JIT на загруженном коде.
Проверка для BCVM в реальности — можно провести простой тест — запускаем файловую нагрузку и усиленно лазим по интерфейсу — и теперь ваша программа работает со скоростью своппинга.
Полноценное тестирование затруднено, легко измерить только время загрузки и посмотреть на максимальные потенциальные аппетиты программы — размер VSZ memory для Linux и счетчик «Выделенная виртуальная память» в Windows. Немного поможет еще изучение статистики hard page faults.
Вроде бы проблема должна решаться количеством дешевой памяти и предзагрузки, но если одна программа потребляет лишних пару-тройку-десяток Мб, то в типичной системе их десятки — и ой.
Оценка влияния — возможные непрогнозируемые лаги.
г) Кэш процессора
Чем больше кода исполняется и данных обрабатывается вашей и не только вашей программой, тем сильнее влияние размера кэша процессора. Причем кэш потребуется и для многочисленных шаблонов и дженериков, и для JIT.
Тестирование — нужно одну и ту же программу гонять на однотипных процессорах с разным размером кэша, что доступно далеко не всем.
Влияние — сложно оценить. В этой статье утверждается, что локализация данных в кэше дает ускорение в разы.
Аспекты реального мира
а) Системные вызовы
На разных платформах системный вызов может иметь разную стоимость, например, мьютексы или создание потоков. Потому отличие в скорости может быть в разы только из-за данного фактора. Один из примеров недавно на Хабре.
Измерение — тестирование на разных платформах. Оценка влияния — примерно как для выбора языка программирования, как малозначимая, кроме конкретных задач.
б) Насколько абстрактная производительность важна ?
В большинстве случаев реальное железо, с которым приходится работать, всегда медленнее. Либо скорости вполне достаточно для реакции пользователя. Либо же ваш сайт недостаточно посещаем для возникновения задержек.
в) Железо влияет
Возможно, у вас ARM-процессор и все плохо с плавающей точкой.
Возможно, у вас жесткие ограничения по памяти не позволяют вместить сложный алгоритм.
Возможно, медленная или нестабильная сеть.
Может быть, видеоускоритель весьма специфичен по функционалу.
Требуется предварительное тестирование на макете.
Влияние может быть очень сильным.
Оценка — например это ваша батарейка в телефоне, которой приходится кормить память и гигагерцы.
Неязыковые факторы
Алгоритмы решают всё. Например SQL проигрывает по языковым вычислительным характеристикам (это обычный интерпретатор), но из-за хорошего мат.аппарата и долгого времени доступа к данным, в целом выглядит хорошо. Тем не менее, в некоторых конкретных случаях слишком обобщенный подход SQL проигрывает прямой навигации типа M/Cache или NoSQL — решениям.
Хорошие вылизанные библиотеки нивелируют недостатки конкретного языка — они занимают основное времени выполнения задачи и позволяют об этом почти не думать — это и математические библиотеки и, что почти всегда — библиотеки времени выполнения.
Проверка и оценка — здесь поможет только качественное образование, чтобы разбираться в алгоритмах.
Аспект человеческого фактора
Незнание языка, лень сразу писать правильно, слишком высокий уровень абстракции приводит к плохим решениям по всем фронтам — например бывает проще перебрать стандартным итератором весь массив или БД, чем реорганизовывать структуру данных, бывает проще скопировать себе пару-тройку-десяток мегабайт для временного анализа…
Примеров привести можно бесконечно много.
И что предлагается с этим делать?
Ответ первый, —, а ничего. В том случае, если вы скованы рабочими ограничениями, унаследованным кодом, или просто нехваткой опыта.
Ответ второй — пишите на ассемблере, используйте только родные для системы инструменты и API.
Если же вам лень, слишком сложно, то у вас есть выбор — предложу следующий набор ступеней из программистского рая к грехопадению:
NULL. Использование Си. Чистый Си увеличит вашу программу только на размер run-time library (libc) в памяти, а современный оптимизатор не испортит исполняемый код.
На самом деле, не обязательно брать Си — годится любой компилируемый язык по вкусу — ADA, Modula, Oberon, даже Pascal/Delphi, желательно оптимизирующий
-1. Использование метапрограммирования. Шаблоны, макросы, частично дженерики (хотя ООП уже относятся к худшей карме). Шаблоны развернутся в код без потери в производительности. Все чем грозит их применение — это code bloating из-за генерации копий кода одних и тех же алгоритмов для разных типов данных.
-2. Использование компилируемых объектных языков C++, D, Rust, Go. Что в этом плохого? С одной стороны, мода на объекты везде уже прошла, и многие трезвомыслящие разработчики критикуют объектный подход, что он не дает решающего выигрыша в разработке. С другой стороны — массивные наработанные обкатанные и удобные фреймворки. Проблема в том, что объекты в большей части фреймворка будут влинкованы, даже если они в вашей программе не используются. Упс, и ваш исполняемый файл перевалил за десяток мегабайт. Эти мегабайты занимают ваш диск, вашу память, и кэш процессора. Хотя накладные расходы на вызовы функций и измеряются парой процентов, но влияние занятости кэша процессора измерить сложно.
-1024. Интерпретируемые языки. PHP, CPython, отчасти Javascript. Благодаря им, сессия браузера перевалила за сотню мегабайт, а потеря на скорости вычислений в 100 раз — само собой нормальное дело.
-Pi. Виртуальные машины. Это языки с промежуточным байт кодом, базирующиеся на .NET платформе, либо на Java-платформе, ну и сюда же можно отнести и PyPy, и V8. Вы всегда с собой носите байт машину — она с вами на диске, она с вами в памяти. Хотя, если верить тестам, то кажется, что все почти нормально — проигрыш на вычислениях десятки процентов, ну максимум до 100% в худших случаях. Только тесты, как правило, не учитывают скорость загрузки самой виртуальной машины. И это память, память и еще раз память, десятки и сотни мегабайт.
Разработчики сами знают эту проблему и движутся в направлении компиляции в нативный код. Это ART вместо Dalvika для Android, и .NET Native от Microsoft.
P.S. Ну и для финального примера — у меня перед глазами 3 пользовательские программы, сходные по функциональности:
Одна написана на С++/Qt/Webkit
Другая на C# .NET 4.5
Третья на Python3/wx
Вот самая отзывчивая из них — на питоне, а самая медленная на дотнете.
Выводы — аспектов много, и учитывать только один — бесполезно.
