Загрузка...Оптимизация кода c
Оптимизация кода на С++
Иногда бывает сложно решить, какую конструкцию лучше использовать i++ или ++i, либо выбрать между конструкцией if-else и switch. В этой статье, написанной специально для сообщества iT works, представлены наиболее реальные средства оптимизации кода, которые должен знать каждый профессиональный программист.
Некоторые считают, что времена оптимизации на уровне кода прошли навсегда, однако это не так. Сейчас существует множество платформ в которых нет таких могущественных компиляторов как в Microsoft Visual Studio. Например шейдерные языки (hlsl, glsl) или код для CUDA, PlayStation3, SPU или мобильные платформы. В зависимости от организации кода, может в десятки раз отличаться его эффективность иногда из-за неэффективности компилятора, на чаще из-за доступа к памяти.
Программируя для разных платформ изучите возможности вашего компилятора и особенности архитектуры процессора (если вы пишите для конкретной консоли). Проведите тесты производительности разных вариантов оптимизации. Часто сложно предполагать, какие именно способы будут наиболее эффективными. А эта статья подскажет разные приемы, которые могут вам помочь. Однако не следует оптимизировать слепо, без предварительного анализа и профилирования. Помните, что преждевременная оптимизация — это зло.
Если вы являетесь программистом в VS под Windows, то скорее всего со многими описанными приемами оптимизации компилятор эффективно справится. Обратите внимание на пункты работы с памятью, а так же я рекомендую ознакомиться с техникой Data oriented design. Некоторые советы по ее использования ищите в статье Методы оптимизации памяти.
1. Используйте векторизацию данных и векторные команды их обработки (например SSE в CPU или упаковывайте данные если используете шейдеры или CUDA). Это позволит использовать SIMD (Single Instruction, Multiple Data) архитектуру, что значительно повысит скорость вычислений. Если вы решите использовать этот метод, то не забывайте про выравнивание данных в памяти.
2. Эффективнее складывать и умножать в перемешку, чем сначала все сложить, а потом все умножить. Это происходит от того, что сложение и умножение выполняются разными модулями процессора и могут выполняться одновременно.
3. Нет разницы по скорости в работе с float и double при сложении и умножении. Они выполняются за равное число тактов процессора и используют одни и те же регистры. При делении и извлечении корня, float работает быстрее. Однако если вы будете использовать большие объемы данных, то за счет кеша быстрее будет работать тот тип, который занимает меньше памяти (т.е. float), поэтому в общем случае именно его предпочтительно использовать. Выбирать double имеет смысл когда нужна большая точность.
4.
Почему это будет эффективнее? Операторы с равным приоритетом выполняются последовательно. Это значит, что будет выполнено сначала умножение, а затем деление. Если же обрамить операцию деления в скобки, то ее выполнит компилятор, а в реальном времени будет выполняться только операция умножения. Что качается отличий варианта 3 от варианта 2, то в 3-ем варианте не создается дополнительной переменной, нет нужны глядя на код думать о том, что это за переменная. А эффективность 2-го и 3-го варианты будет одинаковой.
5. На больших объемах данных и вычислений на них float выгоднее чем double (из за cache miss’ов, см. пункт 3).
8. Если есть большой массив структур, то нужно делать размер его элементов равным степени двойки. Тогда проход по такому массиву будет значительно быстрее (в 4 -6 раз), за счет выравнивания указателя на каждую структуру в массиве.
10.
По той же причине что и пункт 1. В первом случае будет осуществляться разыменование указателя и его инкремент параллельно, а во втором — последовательно.
11. Количество колонок двумерного массива желательно должно быть равно степени двойки. Это увеличит скорость работы с массивом. Это выравняет указатели на первые элементы каждой строки, что ускорит доступ к элементам.
13. Избегайте операции приведения типов.
14. Разумно используйте операции округления:
16. Если в switch используются последовательные значения параметров case ( case 0: case 1: case 2. ) то switch значительно эффективнее чем if-else. Это происходит за счет того, что при if-else будет вычисляться значение каждого условия, а в случае таких параметров в конструкции switch значение будет вычислено один раз, а затем будет переход сразу к нужному пункту.
17. Ветвления — это зло. Старайтесь сокращать их количество. Не делайте их внутри больших циклов. switch — это тоже ветвление. Процессор старается предсказывать результат условия (branch prediction) и если значение выражение почти всегда одно и то же, то ветвление не отразится на скорости выполнения кода. Однако в общем случае, предсказание ветвления будет не верно в 50% случаев, что будет замедлять выполнение алгоритма. Каждое ветвление — это переход к последовательности команд процессора. Такой переход ломает конвейер команд процессора и стоит достаточно дорого.
Это особенно актуально для шейдеров, SPU подпрограмм, CUDA подпрограмм и в алгоритмах, где идет обработка большого количества данных. Если вам нужно для ста тысяч частиц выполнить какой то код, то постарайтесь минимизировать количество ветвлений. Это может существенно ускорить выполнение кода.
18. Рассмотрим пример. Двумерный спрайт содержит массив вершин vertex[ 4 ]. Гораздо эффективнее было бы сделать одно хранилище вершин, а в спрайте индекс смещения относительно первого элемента.
Это по памяти сэкономит 16 байт на каждый спрайт, а по скорости будет процентов на 30 быстрее проход по вершинам. Это data orientad design. Для С# он так же справедлив.
Основные направления оптимизаций:
1. Уменьшение числа ветвлений
2. Группировка данных по одинаковым типам в памяти (в C# никто еще не отменял массивы структур)
3. Уменьшение размеров структур
19. inline функции:
+ дает выигрыш в скорости
— увелечивает код
— добавляет в код зависимости (*.h файлов) при компиляции. Это увеличивает время и объем компиляции при изменении кода в функции
Факты:
1. компилятор может не встроить функцию (даже _forceinlie — нет горантии встраивания)
2. VS компилятор при включенной оптимизацией по скорости встраивает любые функции по своему усмотрению, даже если они не объявлены как inline.
Вывод: нужно избегать использования inline функций. Сейчас это не необходимо. Исключением может быть только очень часто выполняемый низкоуровневый код (как например математические функции) или, если вы пишите программу используя компилятор без полной оптимизации кода (например для компилятора под PlayStation3 использование inline до сих пор актуально).
20. Рассмотрим результат смены порядка переменных в структуре.
21. От перестановки мест слогаемых для float value, сумма меняется:
22. Бинарный поиск не следует использовать на малом количестве элементов. Если количество элементов меньше чем 40-60 (это число может варьироваться от реализации алгоритмов, но имеет примерно такой порядок), бинарный поиск будет медленнее линейного.
26. Выше был пример, как можно switch превратить в static const array и обращаться по индексу. Это применимо например для rtti (run time type identification). Если таким образом определены switch указателей на функции, то замена его доступом к нужной функции за константное время — может быть крайне полезна. То же самое — если это машина состояний. Вместо того, чтобы добавлять новый элемент в свитч, его можно добавлять в массив выше. Но помните про пункт 16.
Дополнительно
Дополнительные рекомендации по написанию более эффективного кода, можно найти в статьях:
Эффективный код на С++
Методы оптимизации памяти
Генерация кода
Прием генерации кода часто используется фреймворками, выполняющими сериализацию, такими как механизмы объектно-реляционного отображения (Object/Relational Mappers, ORM) наподобие Entity Framework, динамические прокси-объекты и другими, которые вынуждены работать с объектами неизвестных типов. В .NET Framework поддерживается несколько способов динамической генерации кода, и еще больше способов поддерживается сторонними фреймворками, такими как LLBLGen и T4:
Легковесный генератор кода (Lightweight Code Generation, LCG), он же класс DynamicMethod. Этот API можно использовать для генерации метода без создания типа и сборки, содержащих его. Для коротких методов — это самый эффективный механизм генерации кода. Чтобы сгенерировать код с помощью механизма LCG, следует создать класс ILGenerator, который работает непосредственно с инструкциями на языке IL.
Пространство имен System.Reflection.Emit содержит методы, с помощью которых можно генерировать сборки, типы и методы на языке IL.
Деревья выражений (expression trees), имеющиеся в пространстве имен System.Linq.Expression можно использовать для создания легковесных выражений из последовательного представления.
Класс CSharpCodeProvider можно использовать для непосредственной компиляции исходного кода на C# (из строки или из файла) в сборку.
Генерация из исходного кода
Допустим, что вам требуется реализовать фреймворк, выполняющий сериализацию произвольных объектов и сохраняющий результаты в формате XML. Получение непустых, общедоступных полей с использованием Reflection API и их запись — весьма дорогостоящая операция, но ее вполне можно использовать для создания простейших реализаций:
Вместо этого можно было бы сгенерировать строго типизированный код, выполняющий сериализацию объектов конкретного типа, и вызывать этот код. Ниже представлена реализация, использующая CSharpCodeProvider:
Код, использующий Reflection API, выполняется только один раз при генерации строго типизированного кода — результат кешируется в статическом поле и повторно используется всякий раз, когда требуется сериализовать экземпляр данного конкретного типа. Обратите внимание, что пример, представленный выше, не прошел всестороннее тестирование; он лишь доказывает возможность реализации генератора кода. Простой хронометраж показывает, что подход на основе генерации кода более чем в два раза быстрее, чем первоначальный подход, основанный исключительно на применении Reflection API.
Генерация кода с использованием легковесного генератора кода
Рассмотрим еще один пример из области синтаксического анализа сетевого протокола. Допустим, что имеется объемный поток двоичных данных, например, состоящий из сетевых пакетов, и вам нужно выделить из пакетов заголовки и полезные данные. Например, взгляните на следующую структура заголовка пакета (это полностью искусственный пример — заголовки TCP-пакетов имеют совершенно иную структуру):
Реализация на C/C++ извлечения такой структуры из потока байтов — тривиальная задача, и для этого не требуется даже копировать данные, если использовать указатели. Фактически, извлечение любых структур из потока байтов, реализуется очень просто:
В C# все оказывается гораздо сложнее. Существует множество способов чтения произвольных двоичных данных из потока. Один из них — выделить поля с помощью Reflection API и читать их отдельно от потока байтов:
На одном из наших тестовых компьютеров мы выполнили анализ 1 000 000 20-байтных структур TcpHeader и выяснили, что в среднем метод выполняется примерно 170 миллисекунд. Скорость работы выглядит не так уж и плохо, но объем выделяемой при этом памяти операциями упаковки оказался внушительным. Кроме того, при вполне реальной скорости обмена по сети, равной 1 Гбит/сек, приложение будет получать десятки миллионов пакетов в секунду, что потребует значительных затрат вычислительных ресурсов только на чтение структур из входящих данных.
На этом фоне гораздо более удачным выглядит решение, основанное на использовании метода Marshal.PtrToStructure(), предназначенного для преобразования фрагментов неуправляемой памяти в управляемые структуры, этот подход требует закрепления исходных данных в памяти, чтобы получить возможность извлекать их по указателю:
Эта версия показывает гораздо более высокую производительность — в среднем 39 миллисекунд на 1 000 000 пакетов. Это существенное улучшение, но Marshal.PtrToStructure() все так же использует динамическую память, потому что возвращает ссылку на объект, и к тому же скорость работы явно недостаточна для обслуживания десятков миллионов пакетов в секунду.
Ранее исследовали использование указателей и небезопасного кода в C#, и похоже, что данный пример — отличная возможность использовать их. В конце концов, версия на C++ настолько проста именно потому, что использует указатели. Следующий код работает намного, намного быстрее, обрабатывая 1 000 000 пакетов за 0.45 миллисекунды — невероятное улучшение!
Почему этот способ оказался таким быстрым? Потому что для копирования данных больше не используются такие ресурсоемкие API, как Marshal.PtrToStructure — копирование выполняет сам JIT-компилятор. Машинный код, полученный в результате компиляции этого метода, может встраиваться (в действительности 64-разрядный JIT-компилятор так и поступает) и использовать для копирования областей памяти 3-4 инструкции (например, инструкцию MOVQ в 32-разрядных системах, копирующую сразу 64 бита). Единственная проблема в том, что получившийся метод ReadPointer не так универсален, как версия на C++.
Первая реакция на это замечание — реализовать универсальную версию:
которая даже не компилируется! В частности, T* — это недопустимая конструкция в C#, потому что нет никакого способа гарантировать, что указатель на T можно будет разыменовать (к тому же, закреплять объекты и получать указатели на них можно, только если они имеют двоично совместимые типы). Поскольку нет никаких обобщенных средств, чтобы выразить наши намерения, похоже, что мы должны будем написать отдельные версии ReadPointer для всех поддерживаемых типов, и в этом нам снова помогут генераторы кода.
Чтобы избежать необходимости писать отдельные копии метода ReadPointer для каждого типа, мы воспользуемся легковесным генератором кода (классом DynamicMethod). Прежде всего исследуем код на языке IL, сгенерированный для метода ReadPointer:
Теперь нам осталось сгенерировать код IL, заменив тип TcpHeader аргументом обобщенного типа. Фактически, благодаря превосходному расширению ReflectionEmitLanguage для утилиты .NET Reflector, которое преобразует методы в вызовы Reflection.Emit, необходимые для генерации кода методов, нам даже не придется писать код вручную — хотя нам придется внести несколько небольших изменений:
Эта версия обрабатывает 1 000 000 пакетов в среднем за 1.05 миллисекунды — более чем в два раза медленнее, чем ReadPointer, но все еще на два порядка быстрее оригинальной реализации на основе механизма рефлексии — еще одна победа генератора кода. (Потеря производительности в сравнении ReadPointer обусловлена необходимостью получения делегата из статического поля, проверки ссылки на пустое значение и вызов метода с применением делегата.)
Структура TypedReference и два недокументированных ключевых слова в языке C#
В отчаянных ситуациях требуются отчаянные меры, и такими отчаянными мерами являются два недокументированных ключевых слова в языке C#, __makeref и __refvalue (поддерживаемые такими же недокументированными кодами операций на языке IL). Вместе со структурой TypedReference эти ключевые слова используются в некоторых сценариях низкоуровневых взаимодействий с применением методов, имеющих переменное количество аргументов в стиле языка C (что требует применения еще одного недокументированного ключевого слова __arglist).
TypedReference — это небольшая структура с двумя полями типа IntPtr — Type и Value. Поле Value — это указатель на значение, которое может быть ссылочного типа или типа значения, а поле Type — указатель на таблицу методов типа. Создавая экземпляры TypedReference, указывающие на экземпляры типов значений, можно обеспечить интерпретацию содержимого памяти строго типизированным образом, как того требует ситуация, и использовать JIT-компилятор для копирования памяти, как это делается в реализации метода ReadPointer:
К сожалению, вся эта «магия» компилятора имеет свою цену. В частности, оператор __makeref компилируется JIT-компилятором в вызов call clr!JIT_GetRefAny, который несет дополнительные накладные расходы в сравнении с полностью встраиваемой версией ReadPointer. Результатом является почти 2-кратная потеря производительности — этот метод обрабатывает 1 000 000 пакетов в среднем за 0.83 миллисекунды. Но, как ни странно, он все еще остается самым быстрым универсальным решением из всех, что были показаны.
Оптимизация многопоточного кода C++
Уже много лет твой компьютер умеет выполнять код любимого ПО параллельно, на всех своих ядрах и процессорах. Да что там компьютер — скоро холодильники смогут обсчитывать гастрономические предпочтения хозяина в несколько потоков, недаром IoT движется по планете семимильными шагами. И казалось бы, уже весь софт давным-давно должен уметь максимально эффективно нагревать атмосферу вокруг тебя, нагружая транзисторы твоего ПК многопоточностью, но все не так замечательно, как хотелось бы.
В мире многопоточности существуют две основные проблемы: не все алгоритмы успешно распараллеливаются, а то, что все-таки удается запустить на нескольких ядрах, работает далеко не так быстро, как хотелось бы. Причина неэффективной работы мультипроцессорного кода (если не говорить про недостаточно прямые руки программистов) кроется в излишних затратах процессорного времени на синхронизацию данных между ядрами. Да-да. Это те самые мьютексы, семафоры и прочее, что мы так привыкли использовать в нашем нехитром ремесле.
Из этого следует простой вывод — если есть возможность избежать разделения данных между ядрами, то надо этой возможностью непременно воспользоваться. Но что делать, если такой возможности решительно нет?
Сферическая задача в вакууме
Допустим, нам нужно написать серверное приложение, которое принимает одно-единственное подключение по UDP-протоколу и как-то нехитро обрабатывает входящие датаграммы, например считает статистику по пришедшим данным. Основная проблема в том, что данные идут на очень больших скоростях, например 10 Гбит/c. Чтобы справиться с такой нагрузкой, нам надо проявить определенную сообразительность и не ударить в грязь лицом.
Хорошая новость состоит в том, что устройство, на котором наше ПО будет запущенно, принадлежит полностью нам, можно грузить процессор на 100%, и никто нас за это не поругает, главное — обсчитать как можно больше пакетов и максимально не допустить потерь. Размер данных в UDP-датаграмме не может превышать 512 байт (к примеру).
Архитектура приложения
Из описания задачи сразу становится понятно, что без всех ядер ПК нам тут не обойтись. Первое, что придет в голову более-менее опытному разработчику, — это выделить один поток на прием входящих датаграмм и создать пул потоков для их обработки. Размер пула обычно делают равным количеству доступных ядер у машины.
Так как по условиям задачи нам разрешено максимально использовать ресурсы системы, мы, чтобы упростить код (а следовательно, и снизить число потенциальных ошибок) и уменьшить задержку перед обработкой входящих данных, будем крутить бесконечный цикл, пытающийся вычитать данные из сокета на каждой итерации. Другими словами, ОС не будет усыплять наш поток, если входящих данных нет, и, соответственно, не будет тратить такты процессора на его пробуждение.
Для потоков из пула, которые обрабатывают UDP-пакеты, мы реализуем очередь из этих самых пакетов. Как только главный поток получает датаграмму, он сразу кладет ее в очередь и пытается прочитать следующую порцию данных из сокета. Потоки пула при этом придерживаются той же модели работы, что и main thread. В частности, они будут крутить цикл вычитки пакетов из очереди, не засыпая на ожидании, если очередь пуста.
Теперь надо немного напрячь мозг и подумать, что мы забыли учесть. Поскольку очередь — разделяемая структура данных, то работа с ней связанна с дополнительными расходами времени на синхронизацию. Как мы выяснили немного выше, нам надо максимально избегать разделяемых данных, поскольку это чревато потенциальными ошибками и возникновением «узких мест». К сожалению, полностью отказаться от очереди у нас не выйдет, но вот снизить затраты на синхронизацию вполне можно.
Вместо одной общей очереди для всех мы можем реализовать по отдельной очереди для каждого потока из пула обработки данных. В этом случае вероятность того, что thread, вычитывающий датаграммы, заснет, ожидая, пока завершится операция записи в очередь главным потоком, значительно уменьшается. Очередь для записи может выбираться по простейшему алгоритму, например round-robin.
Конечно, мы могли бы использовать readers-write lock, чтобы обеспечить одновременно чтение из очереди потокам пула, когда не ведется запись. Но проблема в том, что датаграммы будут сыпаться с большой частотой и основная конкуренция за разделяемый ресурс у обработчиков данных окажется не друг с другом, а с главным потоком.
Очередь
Итак, как мы уже поняли, сердце нашего мини-ПО — структура данных, предоставляющая безопасный доступ к пакетам в многопоточной среде. Поскольку софт может полностью утилизировать ресурсы машины, на которой он работает, мы можем сразу при запуске аллоцировать максимальный объем доступной нам памяти для очередей. В этом случае мы избежим затрат на выделение новых кусков памяти ядром ОС для нашего процесса.
Но нам придется решать, как работать дальше, если очередь заполнится. ПО не может просто так взять и упасть, когда доступная память закончится, поэтому у нас есть два варианта. Первый — при добавлении новых элементов в очередь затирать самые старые. В этом случае мы получим классический кольцевой буфер. Второй вариант — возвращать ошибку при попытке добавления элемента в полную очередь. Мы выберем последний вариант, так как в этом случае программа, а следовательно, и пользователь, сможет понять, что мы не справляемся с нагрузкой.
Таким образом, вырисовывается примерный интерфейс класса, который будет имплементировать нашу структуру данных. Назовем его RingQueue. Класс будет иметь как минимум два метода: push и pop. Причем метод push() будет возвращать булев результат, где true обозначает успешное добавление в очередь, а false — очередь полна.
Теперь, когда мы определились с общими принципами, по которым будет работать наш класс, давай подумаем о реализации.
Реализация на основе std::mutex
Первое, что приходит в голову для имплементации класса RingQueue, — это использовать STL vector в качестве хранилища для элементов очереди и STL mutex для защиты данных в многопоточной среде. Ниже представлен код класса RingQueue на основе vector и mutex.
Оптимизация кода c
Администратор 
Группа: Главные администраторы
Сообщений: 14349
Регистрация: 12.10.2007
Из: Twilight Zone
Пользователь №: 1
C++*
Хочется немного рассказать про оптимизацию С/C++ программ, ибо в интернете довольно мало информации. В посте будут объяснения некоторых оптимизаций на примере задачи, которую мне дали решить в институте (задача реализована на С++11, объяснение дается только для 64 битных систем).
В первую очередь статья писалась, чтобы больше узнать про оптимизацию, советы по которой, я надеюсь, вы оставите в комментариях.
Условие задачи и цель
Задача довольно тривиальна:
В городе M строятся N новых микрорайонов, между которыми запланировано M магистральных дорог. Каждая дорога имеет свою стоимость строительства Pij. В прошлом году из этих M дорог муниципалитет успел построить K штук. К сожалению, в этом году финансирование строительства решено было сократить, и теперь из запланированных, но непостроенных M-K дорог нужно оставить такие, чтобы из любого микрорайона в любой другой существовал хотя бы один путь, но при этом стоимость их строительства была минимальной (гарантируется, что такой набор существует).
Какова минимальная стоимость P завершения строительства дорожной сети по новому плану, и сколько новых дорог по нему предстоит построить?
Первая строка содержит через пробел два числа:
N (2 ≤ N ≤ 10^5) — число строящихся микрорайонов,
M (1 ≤ M ≤ min(N(N — 1), 2 * 10^6)) — число запланированных дорог.
Следующие M строк описывают запланированные дороги, отсортированные по паре номеров своих концов, и каждая содержит через пробел три целых числа:
i (1 ≤ i
#include
#include
/*
* Данная структура обусловлена форматом входных данных
*/
template
struct Triplet <
T first; // Город, в котором дорога начинается
T second; // Город, в котором дорога заканчивается
T third; // Цена строительства дороги
>;
/*
* Каждый элемент UnionFind это множество
*/
template
class UF_element <
public:
T parent; // представитель множества
T size; // размер множества
template
class UnionFind <
private:
std::vector > Elements;
public:
/*
* Сначала город состоит из микрорайонов не соединенных дорогами
*/
UnionFind(T n)
: Elements(n + 1)
<
for (register T i = 1; i (i);
>
>
/*
* При первом вызове поиска родителя, сокращаем путь до него.
* первый поиск за О(log n),
* последующие вызовы за O(1)
*/
T find(T id) <
UF_element & current = Elements[id];
while (current.parent != Elements[current.parent].parent) <
current.parent = Elements[current.parent].parent;
>
return current.parent;
>
void merge(T a, T <
UF_element & UF_elem_A = Elements[find(a)];
UF_element & UF_elem_B = Elements[find( ];
if(UF_elem_A.parent == UF_elem_B.parent)
return;
if(UF_elem_A.size
bool comp(const Triplet & a, const Triplet & <
return (a.third
void kruskal(std::vector
for (size_t i = 0; i );
kruskal(input, cost, count, n);
std::cout register — спецификатор автоматического класса памяти. Применяется к объектам, по умолчанию располагаемым в локальной памяти. Представляет из себя «просьбу»(необязателен к исполнению) к компилятору о размещении значений объектов, объявленных со спецификатором register в одном из доступных регистров, а не в локальной памяти.
В своем коде я использовал такую конструкцию:
for (register T i = 1; i (i);
>
Использовать этот спецификатор надо грамотно.
Если надо забить массив числами от 1 до n (почти как у меня в примере выше), то использование спецификатора даст прибавку в скорости, если тело цикла не такое тривиальное, то скорее всего register не только не изменит производительность, но может и уменьшить его, выделив под переменную регистр.
Работа с памятью
Очень коротко и хорошо написано тут. Вообще, когда начинаешь разбираться как программа использует память и, в особенности, ищешь утечки, вырабатываются некоторые правила. Для себя я уяснил одно: до тех пор, пока программист не в состоянии с ходу сказать когда и где освобождается память, выделенная с помощью оператора new и насколько удобно будет менеджеру памяти обращаться к освободившейся памяти после вызова delete, его надо бить ссаными тряпками за использование new/delete. Поэтому, чтобы не быть побитым, я избавился от использования этих операторов архитектурно:
UnionFind(T n)
: Elements(n + 1) // тут я выделяю нужный мне кусок памяти
<
for (register T i = 1; i (i); // тут его заполняю
>
>
Ввод и вывод данных
Руководствуясь этой статьей был значительно ускорен ввод. Так как в данной задаче выводятся только 2 числа, то использование putchar (putchar_unlocked) большого профита не приносит, но для тех кто не поверит, пока не проверит, привожу ниже реализацию вывода с использованием putchar_unlocked.
Функция вывода/*
* Подходит для всех неотрицательных целочисленных типов:
* первый параметр — это число, которое необходимо вывести
* второй параметр — это символ, который надо добавить после числа
*/
template
void write_unlocked(T inp, char last=’ ‘) <
if (!inp) <
putchar_unlocked(‘0’);
putchar_unlocked(last);
return;
>
T out = 0;
unsigned char sz_inp = 0;
// переворачиваем число
for (; inp; inp /= 10, ++sz_inp) <
out = (out << 3) + (out << 1) + inp % 10;
>
// печатаем число
for (; out; out /= 10, —sz_inp) <
putchar_unlocked(out % 10 + ‘0’);
>
// выводим нули, если они были в числе
for (;sz_inp; —sz_inp) <
putchar_unlocked(‘0’);
>
10 слов об оптимизации кода
Немного о грустном: вся наша жизнь – это борьба с тормозами. И вечно так продолжаться не может. Необходимо оптимизировать всё – начиная от своего рабочего места до времени. В этой статье я привёл примеры оптимизации кода на языке программирования Delphi, но поверь, эти советы могут пригодиться тебе и в реальной жизни, если подумать.
1. Оптимизировать можно практически всё. И даже там, где тебе кажется, что всё работает быстро, можно сделать ещё быстрее. Необходимо помнить, что любую задачу можно решить несколькими путями, и твоя задача выбрать из них наиболее рациональный.
2. Оптимизацию всегда надо начинать со слабых мест в коде программы. Обычно оптимизировать то, что и так быстро работает, необходимости не возникает. Да и эффект такой оптимизации будет минимален.
3. При оптимизации нужно разбирать все операции, каждый оператор, ничего не пропуская. Обычно оптимизацию начинают с тех мест в коде, где находятся регулярно повторяющиеся операции, циклы. То, что находится внутри цикла, будет повторена n количество раз, поэтому, чем меньше кода находится в цикле, тем быстрее процессор просчитает его. Если цикл получается слишком большой, его можно разложить на несколько более маленьких. В данном случае размер нашей программы повыситься, зато скорость увеличиться.
4. Старайтесь поменьше использовать вычисления с плавающей запятой. Любые операции с целыми числами выполняются на порядок быстрее. Операции умножения или деления также выполняются достаточно долго. Вместо умножения лучше использовать сложение, а деление можно заменить сдвигом. Сдвиг работает намного быстрее и умножения, и деления. Это связано с тем, что все числа хранятся в двоичной системе. Если перевести число из десятичной системы счисления в двоичную и сдвинуть число вправо на одну позицию, то можно заметить, что данная операция аналогична делению на 2. При сдвиге влево происходит деление числа на 2. Хоть эти операции и аналогичны, но сдвиг работает в несколько раз быстрее.
5. При создании процедур не надо обременять их большим количеством входных параметров. А всё потому, что при каждом вызове процедуры её параметры подымаются в специальную область памяти, стек, а после выхода изымаются оттуда. Также необходимо действовать аккуратно и с самими параметрами. Не надо пересылать процедурам переменные, содержащие данные большого объёма в чистом виде. Лучше передать адрес ячейки памяти, где хранятся данные, а внутри процедуры уже работать с этим адресом.
6. В самых критических моментах работы программы, например вывод на экран, можно воспользоваться языком Assembler. Даже встроенный в Delphi ассемблер намного быстрее родных функций языка. Код ассемблера можно вынести в отдельный модуль, откомпилировать и подключить к своей программе.
7. Лишних проверок не бывает. Не надо думать, что если у вас не возникла какая-то нестандартная ситуация, то она не возникнет и у пользователя. Всегда делайте проверку того, что вводит пользователь, не дожидаясь, когда эти данные понадобятся.
8. Если ты пишешь достаточно большую и громоздкую программу, добавляй в неё комментарии. Компилятор их всё равно игнорирует. И если вдруг тебе захочется продать исходные коды своих программ, комментарии повысят им цену, да и самому будет легче в них ориентироваться.
9. Для достижения хорошего эффекта ты должен знать IDE, интегрированную среду разработчика, языка, на котором ты программируешь, в нашем случае Delphi. Обычно в опциях IDE разрешается выбирать различные типы компиляторов, а по умолчанию стоит самый простой, быстро компилирующий, но создающий менее оптимизированный код. Поэтому всегда ставь самый оптимизирующий вид компилятора.
10. Старайся делать в программах стандартный интерфейс. Ну не надо делать треугольные кнопочки, нестандартные меню и прочие графические навороты. Всё это очень сильно тормозит программу, расходует большое количество ресурсов компьютера и требует дополнительного времени на разработку. К примеру, настоящий UNIX – это вообще обычный shell – строка для ввода команд.
Вот вроде и всё. Желаю, удачи в написании своих программ, просто следуй этим советам, и всё у тебя получиться.
