Учимся оптимизировать с помощью Assembly [закрыто]

21

Я студент второго курса технологии компьютерных игр. Я недавно закончил свой первый прототип моего «вида» собственного поискового указателя (который не использует A * вместо геометрического подхода / распознавания образов, так как для принятия решений следопыт просто нуждается в знаниях о местности, которая, по его мнению) хотел ИИ, который мог бы на самом деле исследовать, если местность уже известна, тогда он будет идти кратчайшим путем, потому что у следопыта есть память узлов).

В любом случае, мой вопрос более общий: как мне начать оптимизировать алгоритмы / циклы / for_each / и т.д. используя сборку, хотя общие советы приветствуются. Я специально ищу хорошие книги, потому что действительно трудно найти хорошие книги на эту тему. Есть несколько небольших статей, подобных этой , но все еще недостаточно знаний для оптимизации алгоритма / игры ...

Я надеюсь, что есть современная хорошая книга, которую я просто не мог найти ...

niktehpui
источник
1
Это не дает прямого ответа на ваш вопрос, но исследовательское (так называемое адаптивное) A * было исследовано и имеет действительно хорошую производительность (то есть вам не нужно оптимизировать его с помощью ASM). Посмотрите на D * Lite .
Джонатан Дикинсон

Ответы:

21

Здесь я буду против, и скажу, что никогда не рано узнавать об оптимизации, особенно об сборочных оптимизациях и, что более важно, об отладке в сборке. Я верю, что вы получите максимальную выгоду от этого, если будете студентом (потому что тогда вам будет очень мало терять (т. Е. Время / деньги)) и все, что можно получить.

Если вы работаете в отрасли и вам не нужно возиться с сборкой, то не делайте этого. В противном случае, если вы студент или у вас есть время в целом, я бы нашел время, чтобы научиться разбирать программы и посмотреть, смогу ли я найти лучшее решение, чем компилятор. Если я не могу, кого это волнует! Я только что научился писать так же хорошо, как и компилятор, и это ОГРОМНЫЙ плюс, когда вы столкнулись с ошибкой в ​​коде релиза (без символов отладки) и смотрели на разборку, потому что это единственное, на что вы можете посмотреть.

Ответ

Это один из лучших ресурсов, которые я нашел для изучения оптимизации.

http://www.agner.org/optimize/

Напыщенная речь

Если вы читаете некоторые статьи крупных разработчиков (например, рассуждения о создании EASTL и более внимательный анализ кода приведут вас к комментариям, подобным тому, как это сделано, потому что GCC ужасно указывает на это утверждение if, которое скажет вам, что большинство люди говорят, что вы доверяете компилятору, который не всегда прав, особенно в разработке игр), а затем вступаете в индустрию, вы обнаружите, что оптимизация - это повседневное дело, и знание того, что означает вывод сборки, является большим плюсом. Кроме того, люди, кажется, не осознают (особенно в стеке потока), что профилирование игр очень сложно и не всегда точно.

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

То, что сейчас занимает SO - это, на мой взгляд, религиозная позиция в отношении этого утверждения , не оптимизируйте, пока вы не профилируете и не волнуйтесь, компилятор знает лучше вас . Это мешает обучению. Я знаю экспертов в отрасли, которым платят очень хорошие деньги (и я имею в виду ОЧЕНЬ хорошие деньги), чтобы возиться в сборке, чтобы оптимизировать игру и отлаживать ее, потому что компилятор в этом плох или просто не может вам помочь, потому что, ну, это не может (сбои, связанные с графическим процессором, сбои, в которых невозможно прочитать данные в отладчике и т. д. и т. д.)!

Что, если кто-то, кто любит это делать, еще не полностью осознал это, задает вопрос здесь и отвергается / выключается компилятором многих ответов, который знает лучше вас! и никогда не станет одним из тех высокооплачиваемых программистов?

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

  1. Преинкремент, если вы действительно не хотите постинкремент
  2. Написание циклов для контейнеров с использованием постоянной локальной переменной размера, а не вызова size () для контейнера внутри цикла.

РЕДАКТИРОВАТЬ: Обновление после еще 8 лет в отрасли. Изучите сборку. Узнайте, как работают оптимизаторы и какие сборки они генерируют (CompilerExplorer - отличный инструмент для этого). Я сталкивался с бесчисленными сбоями в тестовых сборках (оптимизированных сборках для внутреннего тестирования), где вы не можете полагаться на отладчик даже с символами отладки. Компилятор оптимизировал слишком много вещей, и сборка - ваш единственный источник ценной информации, чтобы найти ошибку из аварийного дампа. Каждая сборка занимает 30-40 минут, если вам повезет, и сначала в очереди на сборку - поэтому вы не можете полагаться на некоторые традиционные методы, чтобы изолировать ошибку. Мультиплеер делает вещи хуже. Знание сборки и умение читать оптимизированную сборку просто сделает вас лучше и, в конечном счете, более ценным для команды.

Samaursa
источник
1
Хорошая мысль об оптимизации компиляторов. Их приятно иметь, но они далеки от совершенства, и в отличие от того, что, по мнению некоторых людей, обычно нетрудно найти простую оптимизацию, которую не выполнял компилятор.
аааааааааааа
3
Следует отметить, что существует разница между «обучением чтению сборки» и «обучением оптимизации со сборкой». Это не одно и то же, и ваш ответ на самом деле не касается использования сборки для реализации оптимизаций. Чтение ассемблера - полезный навык, так как он может помочь в отладке и определении мест, где компилятор не делает что-то правильно. Но это сильно отличается от фактического использования ассемблера для написания оптимизированных подпрограмм, что требует глубоких знаний планирования команд для конкретного процессора. И это также то, что вы не освещали.
Никол Болас
1
Кроме того, «Я только что научился писать так же хорошо, как и компилятор» Нет, вы этого не сделали. Вы смотрели, как одна конкретная процедура была скомпилирована для одного конкретного процессора. Изучение того, как реализовать оптимизированные подпрограммы сборки, требует больше, чем просто посмотреть, как компилятор скомпилировал одну подпрограмму. Вы должны понять, почему компилятор выбрал эти коды операций для того, чтобы воспроизвести этот конкретный код C ++. И это требует глубоких знаний о процессоре, планировании команд и так далее. Обобщение этого требует многолетнего опыта; вы не получите его, просто расшифровав пару подпрограмм.
Николь Болас
7
Итак, -1 для A: фактически не отвечает на вопрос о том, как писать подпрограммы, оптимизированные для ассемблера. B: искажая представление о том, как легко научиться побеждать компилятор при написании процедур, оптимизированных для сборки. И C: поощрение программиста взглянуть на оптимизацию на уровне сборки перед оптимизацией на уровне алгоритма. Даже те высокооплачиваемые "эксперты в отрасли" скажут вам, что это ставит телегу перед лошадью.
Николь Болас
2
@Samaursa: Никто не говорил, что люди не должны «разбираться в разборке и как оптимизировать код». Это не религиозная дискуссия; это простой факт. Люди потратили несколько столетий на ручную оптимизацию какой-то рутины, только чтобы понять, что это ничего не значит для общей производительности. Научиться оптимизировать алгоритмы - это очень ценный набор навыков. Научиться читать ассемблер - это полуценный набор навыков. Обучение написанию процедур сборки - это набор навыков, который используется редко. И в наши дни лучшая оптимизация достигается за счет лучшего использования кэша, а не ручной сборки.
Николь Болас
22

Первый совет, который вы получите, это - не надо.

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

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

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

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

Максимус Минимус
источник
15

Обычно надежная оптимизация не зависит от использования ассемблера или микрооптимизаций с кодом на языках более высокого уровня. Если вы прочитаете много исследовательских работ (как я - или попытаюсь!), Вы увидите, что часто улучшения, вносимые в алгоритмы, находятся на более широком концептуальном, «качественном» уровне, а не на более «количественном» уровень микрооптимизации. Я хотел бы подчеркнуть, что выигрыши в порядке увеличения вероятности можно найти, если взглянуть на алгоритмы с этой точки зрения или на векторизацию / распараллеливание существующих решений.

Сказав это, я недавно натолкнулся на это , что может стать хорошим путем к изучению ASM для x86 специально для разработчиков игр.


ДОПОЛНЕНИЕ

Два источника с моей головы:

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

  • Сокращение использования самых дорогостоящих операций (в первую очередь div, SQRT, триггеров и условных операций);
  • Повышение производительности кэша за счет использования более эффективных структур данных, выравнивания памяти и сокращения условных выражений;
  • Снижение качества продукции в приемлемых зонах для улучшения производительности;
  • Векторизация (SIMD);
  • Распараллеливание (многопоточность, включает перенос задач на графический процессор);
  • И конечно (все реже) ручная сборка. Сначала, конечно, осмотрите сборки C / C ++, чтобы увидеть, где компилятор делает неоптимальный выбор. Вы найдете больше об этом в старых статьях 80-х и 90-х годов, IME.

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

инженер
источник
Вы говорите об оптимизации алгоритма, но не даете никакой информации об этом, если бы мы следовали вашим советам и смотрели на это, могли бы вы дать какое-то руководство?
Скейт
На самом деле, я упоминаю об этом; вам нужно изучить алгоритмы, понимая, что делают компьютерные специалисты для качественного улучшения производительности. Погрузитесь в это достаточно, и со временем вы начнете мыслить похожими словами. Дополнительные усилия здесь окупаются большим временем, в отличие от того, чтобы тратить годы (и я недавно видел это упомянутое на форуме ASM), овладевая плюсами и минусами (просто) например. архитектура x86. Охотьтесь за крупной игрой: учитесь сводить проблемы до самого основания, а затем решайте, что излишне, для оптимизации. Смотрите справочные книги выше.
Инженер
@NickWiggill Какой у тебя обычный источник исследовательских работ?
kizzx2
3

Я думаю, что это может быть слишком рано.

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

Для начала хотя бы сконцентрируйтесь на оптимизации без сборки. У Игоря Островского есть несколько хороших статей, которые демонстрируют некоторые из основ: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

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

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

AAAAAAAAAAAA
источник
2

Эта книга исключительно хороша для учебника. Но это не специально для оптимизации. Ассемблер для процессоров x86, 6-е издание

Это больше о обучении основам сборки с использованием MASM. Затем, ближе к концу книги, рассказывается о том, как встроить ассемблер в c ++ и интегрировать его в большие программы.

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

Мне нравится эта книга, потому что Ирвин учит вас, как использовать инструменты, необходимые для написания магистерских программ. Он специально разбирается в том, как использовать IDE (Visual Studio C ++) и отладчик. В каждой главе есть несколько видеороликов, посвященных решению проблем. Часть этой информации свободно доступна на веб-сайте в списке.

NadtheVlad
источник
1
«имеет смысл изучить основы сборки, прежде чем вы научитесь оптимизировать программы с ее помощью» - хороший совет.
Максимус Минимус