Что быстрее c или c
Перейти к содержимому

Что быстрее c или c

  • автор:

Почему С++ быстрее многих языков программирования?

Достаточно интересно полностью понять, почему С++ настолько быстр по сравнению с условным Kotlin, Java или C#. Вопрос: Расскажите пожалуйста в деталях, почему именно так) Предполагаю, что это благодаря достаточно гибкой работой с памятью, но кажется, что сильно заблуждаюсь)

Отслеживать
задан 6 мая 2023 в 14:41
118 2 2 серебряных знака 17 17 бронзовых знаков

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

6 мая 2023 в 14:43
6 мая 2023 в 14:53
@aleksandrbarakin тут вопрос не про Python
6 мая 2023 в 14:53
@andreymal, какая разница? ответы там есть и они полностью покрывают смысл данного вопроса.
6 мая 2023 в 14:54

@aleksandrbarakin целых три принципиальных разницы: в питоне (подразумеваю CPython) есть GIL, нет статической типизации и нет JIT-компиляации — а в Java и C# всё ровно наоборот

6 мая 2023 в 14:56

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

Во, я наверное хорошо смогу ответить, так как являюсь специалистом в C# и .NET

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

И главная проблема плохого тормозящего кода в таких средах со сборщиком мусора, как .NET и Java, это отсутствие экспертизы в области поведения той самой машины управления памятью. Хочешь создать 200кк массивов для выполнения задачи — легко, код прост. Просто спавни объекты и ни о чем не думай, а сборщик мусора разберется.

В таких средах, где нет встроенного управления памятью, и надо его писать по большей части самому, приходится разбираться с этим до того как код дописать, потому что иначе будут утечки и прочие неприятности. Когда учишь С++, изначально познаешь базовые тонкости работы с памятью, а многие новички сразу начинают различать malloc и calloc , и осознавать, что выделение высвобождение памяти не бесплатно по времени и требует работы, переиспользуют память и т.д.

Чтобы научиться контролю аллокаций в средах типа .NET, требуется сначала написать много тормознутого кода, и наконец-то встретиться с проблемой низкой производительности или перерасхода памяти лицом к лицу. То есть вникание в управление памятью и суть работы сборщика происходит гораздо позднее. Поэтому при одинаковом объеме обучающих материалов, специалист по C++ узнает про нюансы производительности раньше, чем специалист по C#. И это нормально, это специфика среды, в которой работает код.

Поэтому вопрос «что быстрее, С++ или C#/Java» изначально не имеет смысла. Даже если столкнуть лбами двух супермегаэкспертов C++ и C# — неизвестно, чей код будет быстрее. Напишешь на C++ код, потом начнешь тестировать, на одном сервере победишь C#, на другом в другой архитектуре — проиграешь. Ну потому что JIT во время компиляции знает все тонкости процессора, выполняющего код, а компилятор C++ — не знает, он знает только архитектуру. Есть еще PGO (Profile-Guided Optimization) в CLR (Common Language Runtime/.NET) — великолепная шутка, которая может перекомпилировать с сильными оптимизациями код уже запущенного приложения в зависимости от интенсивности использования некоторых методов в коде (речь про последние версии .NET, но раньше ситуация была хуже). В C++ такого либо нет, либо оно достигается значительно тяжелее, чем в среде с JIT. И еще миллионы нюансов, которые никак не ответят на ваш вопрос однозначно.

И здесь можно повторить вывод, который написан жирным шрифтом выше, в самом начале. А утверждение «С++ быстрее многих языков программирования» по факту не соответствует действительности. Я могу на C# написать код, который будет например применять фильтр к Full HD картинке 2 секунды, а могу потом переписать его так, что станет потом 4мс, а качество машинного кода, который выдает JIT, будет не сильно хуже, чем генерит gcc/clang. Не забывайте, что компиляция байт-кода (или CIL) производится машиной в целом однократно, а затем уже работает только скомпилированная версия. Например вызываете какой-то метод 1000 раз, а компилироваться он будет только однажды. JIT — это не интерпритатор байт-кода, а компилятор.

Сравнение производительности С++ и C#

Существуют различные мнения относительно производительности С++ и C#.

Например, сложно поспорить с тем, что код C# может работать быстрее за счет оптимизации под платформу во время JIT компиляции. Или например с тем, что ядро .Net Framework само по себе очень хорошо оптимизировано.

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

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

Попадались и утверждения о том, что код на С++ примерно в десять раз быстрее кода на С#.

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

Тест, который выполнен в этой статье

Мне хотелось выполнить самый примитивный тест, который покажет разницу между языками на микро-уровне. В тесте пройдем полный цикл операций с данными, создание контейнера, заполнение, обработка и удаление, т.е. как обычно и бывает в приложениях.
Работать будем с данными типа int, дабы сделать их обработку максимально идентичной. Сравнивать будем только релизные билды дефолтной конфигурации используя Visual Studio 2010.

Код будет выполнять следующие действия:
1. Аллоцирование массива\контейнера
2. Заполнение массива\контейнера числами по возрастанию
3. Сортировка массива\контейнера методом пузырька по убыванию (метод выбран самый простой, по скольку мы не сравниваем методы сортировки, а средства реализации)
4. Удаление массива\контейнера

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

С++ HeapArray С# HeapArray fixed tmp

Как вы можете убедиться, код достаточно простой и почти идентичный. Поскольку в C# нельзя явно выполнить удаление, время выполнения которого мы хотим измерить, вместо удаления будем использовать items = null; GC.Collect(); при условии что ничего кроме контейнера мы (во всем нашем примере) не создавали, GC.Collect удалить должен бы тоже только контейнер, поэтому думаю это достаточно адекватная замена delete[] items.

Объявление int tmp; за циклом в случае C# экономит время, поэтому рассмотрена именно такая вариация теста для случая C#.

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

В измерениях, для подсчета времени выполнения кода, был использован QueryPerformanceCounter, измерялось «время» создания, заполнения, сортировки и удаления на тестовых платформах формах получились следующие результаты:

Из таблиц видно что:
1. Cамая быстрая С# реализация работает медленнее самой быстрой C++ реализации на 30-60% (в зависимости от платформы)
2. Разброс между самой быстрой и самой медленной С++ реализацией 1-65% (в зависимости от платформы)
3. Самая медленная(из рассмотренных конечно) реализация на С#, медленнее самой медленной С++ реализации примерно в 4 раза
4. Больше всего времени занимает этап сортировки (по сему, в дальнейшем рассмотрим его более детально)

Еще стоит обратить внимание на то, что std::vector является медленным контейнером на старых платформах, однако вполне быстрым на современных. А также на то, что время «удаления» в случае первого .Net теста несколько выше, видимо из-за того что кроме тестовых данных удаляются еще какие-то сущности.

Причина разницы производительности С++ и С# кода

Давайте посмотрим на код, который выполняется процессором в каждом случае. Для этого возьмем код сортировки из самых быстрых примеров и посмотрим во что он компилируется, смотреть будем используя отладчик Visual Studio 2010 и режим disassembly, в результате для сортировки увидим следующий код:

С++ С#
for(int i=0;i<10000;i++)
00F71051 xor ebx,ebx
00F71053 mov esi,edi
for(int j=i;j<10000;j++)
00F71055 mov eax,ebx
00F71057 cmp ebx,2710h
00F7105D jge HeapArray+76h (0F71076h)
00F7105F nop
if(items[i] < items[j])
00F71060 mov ecx,dword ptr [edi+eax*4]
00F71063 mov edx,dword ptr [esi]
00F71065 cmp edx,ecx
00F71067 jge HeapArray+6Eh (0F7106Eh)
int tmp = items[j];
items[j] = items[i];

00F71069 mov dword ptr [edi+eax*4],edx
items[i] = tmp;
00F7106C mov dword ptr [esi],ecx
for(int j=i;j<10000;j++)
00F7106E inc eax
00F7106F cmp eax,2710h
00F71074 jl HeapArray+60h (0F71060h)
for(int i=0;i<10000;i++)
00F71076 inc ebx
00F71077 add esi,4
00F7107A cmp ebx,2710h
00F71080 jl HeapArray+55h (0F71055h)
>
>

Что мы тут можем увидеть?
19 инструкций C++ против 23 на С#, разница не большая, но в купе с прочей оптимизацией, думаю она может объяснить причину большего времени выполнения C# кода.

В C# реализации также некоторые вопросы вызывает
jae 000001C2, который выполняет переход
на 000001c2 call 731661B1
Который видимо также и влияет на разницу во времени выполнения, внося дополнительные задержки.

Другие сравнения производительности

Стоит отметить что есть и другие статьи, где измеряли производительность С++ и С#. Из тех, что попадались мне, самой содержательной показалась Head-to-head benchmark: C++ vs .NET

Автор этой статьи, в некоторых тестах «подыграл» C# запретив использовать SSE2 для С++, поэтому некоторые результаты С++ тестов с плавающей стали примерно в два раза медленнее чем были бы с включенным SSE2. В статье можно найти и другую критику методологии автора, среди которой очень субъективный выбор контейнера для теста в С++.

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

По результатам измерений можно сделать ряд интересных выводов:
1. Дебажный билд С++ заметно медленнее релизного, при том что разница дебажного и релизного билда С# менее существенна
2. Производительность C# под .Net Framework заметно(более 2х раз) выше чем производительность под Mono
3. Для С++ вполне можно найти контейнер который будет работать медленнее подобного контейнера для C#, и никакая оптимизация не поможет это побороть кроме как использование другого контейнера
4. Некоторые операции работы с файлом в С++ заметно медленнее аналогов в С#, однако их альтернативы столь же заметно быстрее аналогов С#.

Если подводить итоги и говорить о Windows, то статья приходит примерно к похожим результатам: код С# медленнее С++ кода, примерно на 10-80%

Много ли это -10..-80%?
Допустим при разработке на С# мы всегда будем использовать наиболее оптимальное решение, что потребует от нас очень неплохих навыков. И предположим мы будем укладываться в суммарные 10..80% потерь производительности производительности. Чем это нам грозит? Попробуем сравнить эти проценты с другими показателями характеризующими производительность.

image

Например, в 1990-2000 годах, одно-поточная производительность процессора росла за год примерно на 50%. А начиная с 2004 года темпы роста производительности процессоров упали, и составляли лишь 21% в год, по крайней мере до 2011 года.

A Look Back at Single-Threaded CPU Performance

Ожидаемые показатели роста производительности весьма туманны. Вряд ли в 2013 и 2014 годах был показан рост выше 21%, более того, вполне вероятно что в будущем рост ожидается еще ниже. По крайней мере, планы Intel по осваиванию новых технологий с каждым годом все скромнее…

Другое направление для оценки,- это энергоэффективность и дешевизна железа. Например тут можно увидеть, что говоря о топовом железе +50% одно-поточной производительности может в 2-3 раза удорожать стоимость процессора.

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

Как будет расти производительность процессоров точно не известно, однако по оценкам видно что в случае 21% роста производительности в год, приложение на С#, может отставать по производительности на 0.5-4 года относительно приложения на С++. В случае, например 10% роста, — отставание уже будет 1-8 лет. Однако, реальное приложение может отставать намного меньше, ниже рассмотрим почему.

Я пока не берусь оценивать рентабельность жертвы 10..80% производительности ради получения экономии на разработке. Очевидно, что эта рентабельность зависит от стоимости получения этих 10..80% другими способами (т.е. за счет железа). Однако наметившаяся тенденция показывает, что каждый следующий процент производительности железа будет дороже предыдущего, что, вполне вероятно, рано или поздно приведет к ситуации, когда дешевле будет получить дополнительную производительность оптимизируя код.

Какая же все-таки реальная оценка?

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

Но с другой стороны, что более важно: сколько runtime (времени выполнения) вашей программы будет занимать ваш код, а сколько код системы?

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

Но совсем другое дело когда около 100% времени выполнения приложения занимает выполнение вашего кода, а не кода ОС. В этом случае вы легко можете получить и -80% и большие потери производительности.

Выводы
Конечно из всего выше написанного не следует что нужно срочно переходить с С# на С++. Во первых разработка на C# дешевле, а во вторых для ряда задач производительность современных процессоров избыточна, и даже оптимизация в рамках C# не является нужной. Но мне кажется важным обратить внимание на накладные расходы т.е плату за использование managedсреды, и оценку этих расходов. Очевидно что в зависимости от рыночных условий и возникающих задач, эта плата может оказаться значимой. Другие аспекты сравнения С# и С++, можно найти в моей предыдущей статье Выбор между C++ и C#.

C++ или Си, на каком языке программы выполняются быстрее?

Если ты на C++ пишешь в стиле C, скорость будет идентична. Если используешь высокоуровневые возможности C++, код будет чуть медленнее. Но разница будет крайне незначительная.

Но надо понимать, что для компилируемых языков выбор оптимального алгоритма влияет на скорость работы программы несравнимо больше, чем выбор языка. И Go-код профессионального программиста будет работать куда быстрее, чем C-код новичка.

Lol NoLolУченик (185) 3 года назад

Есть что то что нельзя сделать на си, но можно на с++, с++ построен на си, но все же может быть?
Программы на си весят меньше программ на с++?

Андрей Высший разум (419041) Lol NoLol, Нет, не существует задач, которые можно решить на C++ и нельзя на C. C++ даёт только дополнительные удобства написания кода, но никак не увеличивает область использования языка. Что касается размера, то это неоднозначно. В целом, С++ обычно будет больше. Но в C нет очень многого из того что встроено в C++ -потому тебе придётся писать больше кода. В результате твой код может оказаться больше готового кода C++.

Остальные ответы
Быстрее C только Assembler в руках тру красноглазика.
Lol NoLolУченик (185) 3 года назад
Ага, но я спрашивал про с++ и си

Андрей Ситников Просветленный (21266) Lol NoLol, код джуна на C++ будет по скорости не очень быстрый. C++ хорошо только руках красноглазиков. C быстрее всех и вся, кроме ассемблера.

Сравнение производительности C и C++ на примере сжатия Хаффмана

Когда на IT-форумах задают вопрос «Быстрее ли язык программирования X языка Y», это обычно вызывает потоки эмоций и считается некорректным. Сродни вопросу про религию или предпочтение той или иной политической партии. Действительно, язык — это способ выражения мысли, идеи. В данном случае идеи программной системы. Он не быстр и не медлен. Он может быть более или менее лаконичным, более или менее точным. А скорость определяется не столько языком, сколько конечным кодом, который генерирует компилятор этого языка. Или скоростью интерпретатора в случае интерпретируемого языка.

Но это всё философия. А на практике обычно есть практическая задача разработки ПО. И, действительно, реализовать это ПО можно на десятке разных языков программирования. Поэтому, хоть это и «религиозный вопрос» в случае публичного обсуждения, вопрос этот часто возникает в голове IT-специалиста, стоящего перед конкретной задачей. «Сколько времени мне потребуется для реализации задачи на языке X и какие у полученного ПО будут характеристики, в том числе скоростные, по сравнению с реализацией этой задачи на языке Y». Понятное дело, точного ответа на этот вопрос нет, специалист опирается на свой личный опыт и отвечает как-то типа «с вероятностью 95%, написанная на ассемблере, эта задача будет работать быстрее, чем на php». Но, положа руку на сердце, опыт этот редко базируется на точных цифрах реальных задач, которые сам этот специалист реализовал. Нет, ну кто в здравом уме будет писать сложное ПО сначала на php, а потом его же переписывать на ассемблере, только чтобы измерить характеристики? В основном ограничиваются синтетическими тестами типа сортировки массива, построения и обхода бинарного дерева и тому подобных.

Я, как специалист, пишущий 90% на C++, часто натыкаюсь на «холливарные» темы сравнения этого языка с другими. И один из них — это прародитель — язык C. На том же quora.com часто поднимают этот вопрос «А быстрее ли язык C языка C++» (что некорректно, как я объяснил выше), или «А почему ядро Linux или тонна GNU утилит пишется на C а не на C++» (что является вполне корректным вопросом). На второй вопрос я для себя ответил так:

  • Освоение языка C требует на порядок меньших усилий, значит, больше людей могут поучаствовать в разработке этого ПО.
  • Сложные действия, потенциально затратные по памяти или скорости на языке C займут, вероятно, больше строчек кода и потребуют усилия от автора. А значит, неоптимальность в программе легче будет заметить по ходу написания или ревью. Программа на языке C++ может быть куда более лаконична и, с виду, проста в понимании. Но заметить, что за перегрузкой оператора «+», к примеру, скрывается запуск космического корабля к луне, заметить будет сложнее.

Задачка

Для того, чтобы чуть более основательно ответить себе на этот вопрос, я решил написать ещё один (да-да, тоже немного синтетический) тест — кодирование данных методом Хаффмана. Навела на мысль статья «Алгоритм Хаффмана на пальцах» (https://habrahabr.ru/post/144200/).

Сначала я реализовал кодирование на чистом C. Если помните, для его реализации требуется очередь с приоритетом, потому как там для построения дерева кодирования нужно быстро находить символы, упорядоченные по числу их повторений. Алгоритмические подробности я опущу, отсылая читателя по ссылке выше (пардон за тавтологию). Собственно, на этом всё бы и закончилось, и не было бы никакой статьи, потому что кодирование я реализовывал только в качестве тренировки в алгоритмике. Но по ходу работы я заметил, как же быстро компилируется программа на C по сравнению с подобного размера исходниками на C++. И упомянул об этом коллеге по работе. Высказав предположение, что компиляция на C++ включает, наверное, ещё множество способов оптимизации. Так что подобно написанный код на C++, наверное, должен быть быстрее — там же будет работать магия самых-самых гуру в области написания оптимизирующих компиляторов. Ухмыльнувшись, коллега ответил: «Проверь».

И тогда я переписал кодирование Хаффмана на C++. Для чистоты эксперимента я не менял основополагающих принципов, к примеру, не вставлял пользовательский распределитель памяти. Это можно сделать и в C (более «кастомно») и в C++ (более «нативно»). В чём же тут тогда «C++-ность»?

Очередь с приоритетом

Первое, что логично выразить через шаблоны в C++, это очередь с приоритетом. На C она представлена в виде структуры, главный элемент которой — указатель на массив указателей на узлы с данными:

struct priority_queue < // A number of active (carrying data) nodes currently in the queue unsigned int size; // A total number of nodes in "nodes" array unsigned int capacity; // An array of pointers to nodes struct priority_queue_node** nodes; >; 

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

struct priority_queue_node < unsigned int weight; >; 

Так как очередь не занимается управлением памятью под сами узлы, ей незачем знать, из чего реально состоит узел. Всё, что требуется для работы, это получить его вес: ((struct priority_queue_node*) node_ptr)→weight. Добавление узла в очередь с учётом возможного перевыделения памяти выглядит несколько громоздко:

int priority_queue_push(struct priority_queue* queue, struct priority_queue_node* node) < if (queue->size >= queue->capacity) < int new_capacity = queue->capacity * 2; if (new_capacity == 0) new_capacity = 1; struct priority_queue_node** new_nodes = (struct priority_queue_node**) malloc(sizeof(struct priority_queue_node*) * new_capacity); if (! new_nodes) < return 0; >memcpy(new_nodes, queue->nodes, sizeof(struct priority_queue_node*) * queue->size); if (queue->capacity) free(queue->nodes); queue->nodes = new_nodes; queue->capacity = new_capacity; > queue->nodes[queue->size++] = node; heapify(queue); return 1; > 

Создание очереди и её удаление с обработкой всех ошибок — тоже много строчек кода по сравнению с C++ версией, что ожидаемо. Собственно, версия очереди на C++ выглядит так (внимание — на представление данных):

template class priority_queue < struct node < unsigned int m_weight; T m_data; >; using node_ptr = std::unique_ptr; std::size_t m_capacity; std::size_t m_size; std::unique_ptr m_nodes; void heapify() noexcept; void increase_capacity(); public: explicit priority_queue(std::size_t capacity = 16) ; // … >; 

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

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

template push(unsigned int weight, U&& obj) < if (m_size >= m_capacity) increase_capacity(); m_nodes[m_size++].reset(new node((obj)>)); heapify(); > void increase_capacity() < const auto new_capacity = m_capacity ? m_capacity * 2 : 1; std::unique_ptrnew_nodes(new node_ptr[new_capacity]); for (auto src = m_nodes.get(), dest = new_nodes.get(); src != m_nodes.get() + m_size; ++src, ++dest) *dest = std::move(*src); m_nodes = std::move(new_nodes); m_capacity = new_capacity; > 

Дерево символов (дерево кодирования)

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

#define NODE_TYPE_TERM 1 #define NODE_TYPE_NODE 2 struct char_node_base < int type; >; struct char_node_terminal < struct char_node_base base; char c; >; struct char_node < struct char_node_base base; struct char_node_base* left; struct char_node_base* right; >; 

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

struct char_node_root < struct priority_queue_node pq_node; int height; struct char_node_base* node; >; 

На C++ всё это выражается несколько элегантнее:

struct char_node_base < virtual ~char_node_base() = default; >; using char_node_ptr = std::unique_ptr; struct char_node_terminal : char_node_base < const unsigned char m_c; char_node_terminal(char c) noexcept : m_c(c) <>>; struct char_node : char_node_base < char_node_ptr m_left; char_node_ptr m_right; >; struct nodes_root < int m_height; char_node_ptr m_node; >; 

Здесь видно ключевое преимущество C++ — для корректного удаления этого дерева не нужно делать ничего. Просто удалить корень, авто указатели всё сделают сами. В C же для этой задачи написано изрядное количество кода.

Заполнение очереди и построение дерева

Этот шаг вообще не отличается для C и C++ реализации. Сначала просчитывается число повторений каждого символа во входном блоке данных, и заполняется табличка из 256 байт. Потом в очередь с приоритетом кладутся микро-деревья, состоящие только из одного терминального узла. Далее узлы объединяются путём последовательного извлечения из очереди пары, ближайшей к её вершине, и вставкой туда промежуточного узла, содержащего извлечённые прежде.

На C (здесь — без проверки на ошибки) это выглядит следующим образом:

static struct priority_queue* build_priority_queue( char* buffer, unsigned int size) < unsigned char table[256]; memset(table, 0, sizeof(table)); for (unsigned int i = 0; i < size; ++i) if (table[(unsigned char)buffer[i]] != 255) ++table[(unsigned char)buffer[i]]; struct priority_queue* queue = priority_queue_create(16); for (unsigned short i = 0; i < 256; ++i) < if (table[i]) < struct char_node_root* node = (struct char_node_root*) malloc(sizeof(struct char_node_root)); struct char_node_terminal* term = (struct char_node_terminal*) malloc(sizeof(struct char_node_terminal)); term->base.type = NODE_TYPE_TERM; term->c = (char)i; node->node = (struct char_node_base*) term; node->height = 0; node->pq_node.weight = table[i]; priority_queue_push(queue, (struct priority_queue_node*) node); > > return queue; > static struct char_node_root* queue_to_tree(struct priority_queue* queue) < while (priority_queue_size(queue) >1) < struct char_node_root* node1 = (struct char_node_root*) priority_queue_pop(queue); struct char_node_root* node2 = (struct char_node_root*) priority_queue_pop(queue); struct char_node_base* int_node1 = node1->node; struct char_node_base* int_node2 = node2->node; struct char_node* join_node = (struct char_node*) malloc(sizeof(struct char_node)); join_node->base.type = NODE_TYPE_NODE; join_node->left = int_node1; join_node->right = int_node2; int new_weight = node1->pq_node.weight; if (new_weight + node2->pq_node.weight pq_node.weight; else new_weight = 65535; node1->pq_node.weight = new_weight; if (node1->height > node2->height) ++node1->height; else node1->height = node2->height + 1; free(node2); node1->node = (struct char_node_base*) join_node; priority_queue_push(queue, (struct priority_queue_node*) node1); > return (struct char_node_root*) priority_queue_pop(queue); > 

На C++ — ещё короче и красивее при том, что любые ошибки выделения памяти будут обработаны корректно благодаря исключениям и применению авто указателей:

void fill_priority_queue( const unsigned char* buffer, std::size_t buffer_size, queue_t& queue) < unsigned char counts_table[256]<>; for (auto ptr = buffer; ptr != buffer + buffer_size; ++ptr) if (counts_table[*ptr] != 255) ++counts_table[*ptr]; for (unsigned short i = 0; i != 256; ++i) if (counts_table[i]) queue.push(counts_table[i], nodes_root ); > void queue_to_tree(queue_t& queue) < while (queue.size() >1) < auto old_root1_node = std::move(queue.top()); const auto old_root1_weight = queue.top_weight(); queue.pop(); auto old_root2_node = std::move(queue.top()); const auto old_root2_weight = queue.top_weight(); queue.pop(); auto joined_node = std::unique_ptr(new char_node); joined_node->m_left = std::move(old_root1_node.m_node); joined_node->m_right = std::move(old_root2_node.m_node); const auto new_weight = std::min(old_root1_weight + old_root2_weight, 65535U); const auto new_height = std::max(old_root1_node.m_height, old_root2_node.m_height) + 1; queue.push(new_weight, nodes_root ); > > 

Таблица кодирования

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

В C версии последовательность бит представляется тривиальной структурой, состоящей из указателя на массив байт и счётчика реально заполненных бит. Каких-то специальных операций для работы с ней нет. На этапе построения таблицы кодирования для каждого символа заводится такая структурка, куда копируется, найденная для текущего символа, последовательность бит. Таким образом, таблица кодирования — это просто массив этих структур для каждого символа.

struct bits_line < unsigned char bits_count; unsigned char* bits; >; static int build_encoding_map_node(struct char_node_base* node, struct bits_line* bits_table, unsigned char* bits_pattern, int bits_count) < if (node->type == NODE_TYPE_TERM) < unsigned char index = (unsigned char)((struct char_node_terminal*)node)->c; bits_table[index].bits_count = bits_count; bits_table[index].bits = (unsigned char*) malloc(bytes_count_from_bits(bits_count + 1)); if (! bits_table[index].bits) return 0; memcpy(bits_table[index].bits, bits_pattern, bytes_count_from_bits(bits_count)); return 1; > static const unsigned char bit_mask[] = ; bits_pattern[bits_count >> 3] &= ~bit_mask[bits_count & 7]; if (! build_encoding_map_node(((struct char_node*)node)->left, bits_table, bits_pattern, bits_count + 1)) return 0; bits_pattern[bits_count >> 3] |= bit_mask[bits_count & 7]; if (! build_encoding_map_node(((struct char_node*)node)->right, bits_table, bits_pattern, bits_count + 1)) return 0; return 1; > 

В C++ версии битовый массив удобнее представить полноценным классом, который будет не просто управлять ресурсами, но и поддерживать, нужную далее, операцию добавления другой битовой последовательности.

using unique_bytes_ptr = std::unique_ptr; class bit_ostream < std::size_t m_capacity; unsigned long m_bits_count = 0; unique_bytes_ptr m_data; public: explicit bit_ostream(std::size_t initial_capacity = 0) noexcept : m_capacity(initial_capacity) < >bit_ostream& push(const unsigned char* bits, unsigned long const bits_count) < if (bits_count == 0) return *this; const auto new_bits_count = m_bits_count + bits_count; if (covered_bytes(new_bits_count) + 1 >m_capacity || m_bits_count == 0) < decltype(m_capacity) new_capacity = m_capacity * 2; const auto cov_bytes = static_cast(covered_bytes(new_bits_count) + 1); if (new_capacity < cov_bytes) new_capacity = cov_bytes; unique_bytes_ptr new_data(new unsigned char[new_capacity]); std::memcpy(new_data.get(), m_data.get(), covered_bytes(m_bits_count)); m_capacity = new_capacity; m_data = std::move(new_data); >unsigned char* curr = m_data.get() + (m_bits_count >> 3); if ((m_bits_count & 7) == 0) < // All it's simple when current output data size is integer number of bytes std::memcpy(curr, bits, covered_bytes(bits_count)); >else < const unsigned char shift = m_bits_count & 7; for (auto bytes_count = covered_bytes(bits_count); bytes_count >0; ++curr, ++bits, --bytes_count) < unsigned short val = static_cast(*bits) << shift; val |= static_cast(*curr & g_bits_fill_mask[shift]); *curr = static_cast(val & 0xff); *(curr + 1) = static_cast(val >> 8); > > m_bits_count += bits_count; assert(covered_bytes(m_bits_count) bit_ostream& push(const bit_ostream& other) < return push(other.data(), other.bits_count()); >bit_ostream& clear_tail() noexcept < if (m_bits_count & 7) m_data.get()[m_bits_count >> 3] &= g_bits_fill_mask[m_bits_count & 7]; return *this; > unsigned long bits_count() const noexcept < return m_bits_count; >bool empty() const noexcept < return ! m_bits_count; >unsigned char* data() noexcept < return m_data.get(); >const unsigned char* data() const noexcept < return m_data.get(); >>; template constexpr inline std::size_t covered_bytes(T bits_count) noexcept < return (bits_count >> 3) + (bits_count & 7 ? 1 : 0); > 

Соберём всё воедино

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

  1. Запомнить точку во времени ts1 с помощью rdtsc.
  2. Заполнить очередь с приоритетом символами по числу их повторений.
  3. Построить дерево символов с помощью этой очереди. Удалить саму очередь.
  4. Вычислить число циклов t1, прошедшее с момента ts1, и запомнить следующую точку ts2.
  5. Построить таблицу кодирования, обходя дерево кодирования. Уничтожить дерево кодирования.
  6. Вычислить число циклов t2, прошедшее с момента ts2, и запомнить следующую точку ts3.
  7. Осуществить собственно кодирование входного потока, заменяя каждый входной символ последовательностью бит из таблицы кодирования.
  8. Вычислить число циклов t3, прошедшее с момента ts3.

Замеры и оптимизация

Нетерпеливый читатель, проглядевший столько кода выше, уже ёрзает на стуле, задаваясь вопросом: «Ну так что там получилось?». Попробуем запустить обе версии, скомпилированного компилятором gcc-5.4.0 с уровнем оптимизации «O3», упаковщика на файле размером около 31 Мб. Нужно отметить, что для кодирования можно выбирать разные размеры блока данных из входного файла. По умолчанию это 64 Кб. То есть, осуществляется кодирование 31 Мб / 64 Кб блоков, а все показатели времени суммируются.

> build-c/pack-c -m3 ../sample-1.dat data-c.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1053432 (0.754 seconds), t1 = 209957, t2 = 31023, t3 = 811377. > build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1182005 (0.846 seconds), t1 = 228527, t2 = 52680, t3 = 894081 

На опцию «-m3» можно не обращать внимание, это просто переключатель, означающий тестовый режим.

Ну что-ж, как-то не очень весело. То есть, C++ не дался бесплатно, провал по производительности порядка 12%. Все три этапа выполняются дольше, чем в C версии. А если размер блока выбрать поменьше, скажем, 1 Кб?

> build-c/pack-c -m3 -b1024 ../sample-1.dat data-c.dat File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 9397894 (6.731 seconds), t1 = 5320910, t2 = 1943422, t3 = 2094688. > build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11586220 (8.3 seconds), t1 = 6399593, t2 = 3125111, t3 = 1663035 

Понятное дело, просело всё, потому что теперь нужно гораздо чаще перестраивать дерево кодирования. Но C опять вырвался вперёд — аж на 23%!

Оптимизация «на глазок»

Что не так с C++ реализацией? Вроде один компилятор, один и тот же оптимизатор там. По счётчикам циклов выше видно, что самый большой вклад дают шаги, где начинается манипуляция с битами. Класс bit_ostream получился хороший. Но при наполнении таблицы кодирования так ли хорош его, чрезмерно нагруженный для составления таблицы, метод push? Ведь положить массив бит в изначально пустой объект должно быть куда проще, чем весь код в том методе. Да и таблица кодирования, составленная из 256 сущностей этого класса, занимает гораздо больше места, чем 256 структур bits_line из C версии. Попробуем сделать вариант этого класса для таблицы кодирования.

class small_bit_ostream < unique_bytes_ptr m_data; unsigned short m_bits_count = 0; public: small_bit_ostream& push(const unsigned char* bits, const unsigned short bits_count) < const auto cov_bytes ; m_data.reset(new unsigned char[cov_bytes]); std::memcpy(m_data.get(), bits, cov_bytes); m_bits_count = bits_count; return *this; > unsigned long bits_count() const noexcept < return m_bits_count; >bool empty() const noexcept < return ! m_bits_count; >unsigned char* data() noexcept < return m_data.get(); >const unsigned char* data() const noexcept < return m_data.get(); >>; 

Просто. Красиво. Ничего лишнего. Даёт ли это хоть что-то? (Не тронутую C версию не привожу тут.)

> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1173692 (0.84 seconds), t1 = 229942, t2 = 46677, t3 = 890323 > build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11198578 (8.02 seconds), t1 = 6404650, t2 = 2752852, t3 = 1641317 

Ну что, для большого блока улучшение — на уровне погрешности. Для маленького блока улучшение чуть заметнее — теперь C++ хуже всего на 19%. Видно по показателю t2, что заполнение таблицы стало лучше работать.

Профилирование

Начнём с проверки, как поживают кэши CPU. Запустим обе версии ПО под valgrind’ом с инструментарием «cachegrind». Вот краткий вывод для C версии.

==2794== I refs: 2,313,382,347 ==2794== I1 misses: 14,482 ==2794== LLi misses: 1,492 ==2794== I1 miss rate: 0.00% ==2794== LLi miss rate: 0.00% ==2794== ==2794== D refs: 601,604,444 (472,330,278 rd + 129,274,166 wr) ==2794== D1 misses: 3,966,884 ( 2,279,553 rd + 1,687,331 wr) ==2794== LLd misses: 7,030 ( 3,034 rd + 3,996 wr) ==2794== D1 miss rate: 0.7% ( 0.5% + 1.3% ) ==2794== LLd miss rate: 0.0% ( 0.0% + 0.0% ) ==2794== ==2794== LL refs: 3,981,366 ( 2,294,035 rd + 1,687,331 wr) ==2794== LL misses: 8,522 ( 4,526 rd + 3,996 wr) ==2794== LL miss rate: 0.0% ( 0.0% + 0.0% ) ==2794== ==2794== Branches: 299,244,261 (298,085,895 cond + 1,158,366 ind) ==2794== Mispredicts: 8,779,093 ( 8,778,920 cond + 173 ind) ==2794== Mispred rate: 2.9% ( 2.9% + 0.0% ) 

А вот и вывод для C++ версии с теми же параметрами:

==2994== I refs: 2,464,681,889 ==2994== I1 misses: 2,032 ==2994== LLi misses: 1,888 ==2994== I1 miss rate: 0.00% ==2994== LLi miss rate: 0.00% ==2994== ==2994== D refs: 633,267,329 (491,590,332 rd + 141,676,997 wr) ==2994== D1 misses: 3,992,071 ( 2,298,593 rd + 1,693,478 wr) ==2994== LLd misses: 8,292 ( 3,173 rd + 5,119 wr) ==2994== D1 miss rate: 0.6% ( 0.5% + 1.2% ) ==2994== LLd miss rate: 0.0% ( 0.0% + 0.0% ) ==2994== ==2994== LL refs: 3,994,103 ( 2,300,625 rd + 1,693,478 wr) ==2994== LL misses: 10,180 ( 5,061 rd + 5,119 wr) ==2994== LL miss rate: 0.0% ( 0.0% + 0.0% ) ==2994== ==2994== Branches: 348,146,710 (346,241,481 cond + 1,905,229 ind) ==2994== Mispredicts: 6,977,260 ( 6,792,066 cond + 185,194 ind) ==2994== Mispred rate: 2.0% ( 2.0% + 9.7% ) 

Можно заметить, что по попаданию в кэш и по данным и по инструкциям C++ не хуже, а иногда даже и лучше, чем C код. Предсказание переходов вообще лучше работает. А почему же он проваливается слегка? Очевидно, что в нём просто выполняется больше инструкцкий — 2 464 млн. против 2 313. Что и даёт примерно ту разницу в производительности, что была заметна при использовании больших блоков.

При анализе инструментарием «callgrind» видно, что много инструкций тратится на работу с кучей — malloc и free. Но помимо этого в C++ версии встречаются ещё и значительные, с точки зрения инструкций, упоминания операторов new и delete. А всегда ли они нужны? Те самые операции с битовыми массивами, что отдельно упоминались выше, реализованы с использованием авто указателя unique_ptr, для которого память выделяется с помощью new[]. Вспомним, что данный оператор внутри обращается к C-шному malloc, а затем инициализирует каждый объект в созданном массиве. То есть в нашем случае заполняет массив нулями. А зачем это программе? Класс bit_ostream сразу после получения массива заполняет его битами, дописывая их в конец. И хранит счётчик записанных бит. Ему вовсе не нужно, чтобы массив байт был предварительно очищен. Попробуем написать простейший адаптер для управления памятью через malloc / free, но с использованием unique_ptr, чтобы так же удобно не думать о её очистке.

struct free_deleter < void operator()(void* p) const noexcept < std::free(p); >>; template inline T* allocate_with_malloc(std::size_t size) < T* res = static_cast(std::malloc(sizeof(T) * size)); if (! res) throw std::bad_alloc(); return res; > template using unique_malloc_array_ptr = std::unique_ptr; template inline unique_malloc_array_ptr unique_allocate_with_malloc(std::size_t size) < return unique_malloc_array_ptr(allocate_with_malloc(size)); > // Typedefs for byte arrays using unique_bytes_ptr = unique_malloc_array_ptr; inline unique_bytes_ptr allocate_bytes(std::size_t size) < return unique_bytes_ptr(unique_allocate_with_malloc(size)); > 

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

> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1042665 (0.746 seconds), t1 = 250480, t2 = 45393, t3 = 740163 > build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11068384 (7.93 seconds), t1 = 6488100, t2 = 2694562, t3 = 1501027 

Ну что-ж, на больших блоках C++ реализация обогнала C! На малых всё пока что хуже, хотя лучше, чем в предыдущем эксперименте. Количество инструкций на всю программу — 2 430 млн. вместо 2 464. Количество обращений к данным тоже сократилось с 633 млн. до 536. Понятно, что на малых блоках новая реализация практически осталась как была — там же в основном играет роль построение дерева кодирования, а его код не менялся.

Ещё пару капелек

Обратим внимание на очередь с приоритетом, которую так красиво и лаконично удалось реализовать на C++. Она, как и всё остальное, использует авто указатели для управления памятью. Есть один главный указатель m_nodes, который указывает на массив указателей на узлы. В ходе выполнения любой изменяющей операции содержимое конечных указателей переставляется, как правило, выражением ptr1 = std::move(ptr2). Что тут «зарыто»? Указатель ptr1 должен проверить, что он ни на что не указывает, в противном случае удалить ресурс. Указатель ptr2 должен обнулиться после того, как ресурс у него заберут. Да, это малое количество инструкций, тут почти не о чем разговаривать. Но! Во всех операциях с очередью строго известно, когда и что на что указывает. Поэтому таких проверок и обнулений делать не надо. А копирование сырых указателей занимает одну (!) инструкцию. Давайте заменим конечные указатели в очереди с приоритетом на сырые и прогоним тесты ещё раз.

> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1008990 (0.722 seconds), t1 = 221001, t2 = 44870, t3 = 736557 > build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 10683068 (7.65 seconds), t1 = 6101534, t2 = 2689178, t3 = 1505929 

Ну что-ж, на больших блоках C++ быстрее на 4,3%, на малых — медленнее всего на 13,6%. Инструкций теперь 2 413 млн., обращений к данным — 531 млн.

Заключение

К каким мыслям я пришёл по ходу такого сравнительного анализа на примере задачки по кодированию Хаффмана?

  1. Сначала обе версии программы я реализовал «в лоб», не особенно задумываясь о каких-то специфических оптимизациях. Но так получилось, что C версия сразу получилась быстрее, а C++ я «дотягивал» до неё, изучал, профилировал и т. п. В результате я получил в среднем такое же быстрое решение. (Я думаю, что и этап построения дерева кодирования можно «допилить», чтобы он не «провисал» по скорости.) Но я хотел отметить то, что сам процесс написания программы на C «вёл меня» по пути создания быстрого кода, а в случае C++ пришлось заниматься дальнейшим анализом.
  2. Тем, кто хорошо знает C++, писать на нём гораздо удобнее, чем на C. Программы получаются лаконичнее и они лишены множества потенциальных ошибок, которые можно сделать на C. По ходу написания и отладки C программы я столкнулся с множеством (сравнивая с C++) случаев некорректного использования указателей, обращения к очищенной памяти, неверного преобразования типов. В хорошо типизированной C++ программе по максимуму действует правило — компилируется, значит корректна. Удаление сложных структур вместе с механизмом исключений — вообще сила, потому что здесь не нужно ни строчки пользовательского кода (разве что вывести сообщение об ошибке), а программа корректно обрабатывает такие ситуации «из коробки».
  3. Заметить, что что-то работает медленно в ходе профилирования очень сложно, потому что это субъективная оценка. У меня было две реализации, и я мог сравнить эквивалентные шаги. Но в реальности будет только одна реализация, потому что в начале выбрали для неё язык «XYZ». Как понять, быстро она работает, или медленно? Сравнить то не с чем. Если бы я написал только C++ реализацию и в конце замерил, что она обрабатывает 31 Мб за 0.85 секунды, я бы сразу считал, что это эталон скорости!
  4. Что же касается лично моих предпочтений при написании программ в будущем, то здесь подход следующий. Если мне нужно написать «молотилку», действия которой в основном будут состоять из миллионов похожих действий, то лучше писать её в C стиле, чтобы увидеть/реализовать самостоятельно все, пусть даже самые незначительные, шаги. Ведь каждая лишняя инструкция тут на миллионах повторений даст просадку. Если же я пишу сложную управляющую логику с очень разнообразными действиями, не сводящимися к «повторить вычисления A, B, C миллион раз», то лучше взять на вооружение всю мощь типизированного C++. Потому что конечное время работы такой программы уже не будет сводиться к вопросу «а за сколько времени она обработает терабайт данных», управляющая логика будет зависеть от множества внешних факторов и сценариев использования. И говорить о точных скоростных характеристиках не придётся. А вот корректность такой логики «из коробки» будет в сто крат ценнее, потому что никому не захочется вычищать из неё баги в C версии до скончания веков. И иметь в конце концов «жёсткую» версию кода, которую невозможно изменить, адаптировать под новые нужды, потому что, где бы ни тронул, всё посыпется. И начинай отладку сначала.

Update 1. По просьбам в комментариях я проверил работу упаковщиков, собранных компилятором clang-3.8.0. Результаты таковы.

> build-c/pack-c -m3 ../sample-1.dat data-c.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1139373 (0.816 seconds), t1 = 206305, t2 = 29559, t3 = 902493. 

Неоптимизированная C++ версия:

> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1417576 (1.01 seconds), t1 = 223441, t2 = 53057, t3 = 1134400 

Оптимизированная C++ версия:

> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1174028 (0.84 seconds), t1 = 215059, t2 = 59738, t3 = 892821 

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

Добавить комментарий

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