Сравнительный анализ алгоритмов / реализаций с привязкой к процессору - PullRequest
Новая
       53

Сравнительный анализ алгоритмов / реализаций с привязкой к процессору

4 голосов
/ 25 декабря 2011

Допустим, я пишу свой собственный StringBuilder на скомпилированном языке (например, C ++).

Каков наилучший способ измерения производительности различных реализаций? Простая синхронизация нескольких сотен тысяч прогонов дает весьма противоречивые результаты: временные интервалы от одного пакета к другому могут отличаться на целых 15%, что делает невозможным точную оценку потенциальных улучшений производительности, которые дают выигрыш в производительности, меньший, чем этот.

Я сделал следующее:

  1. Отключить SpeedStep
  2. Использовать RDTSC для синхронизации
  3. Запустить процесс с приоритетом в реальном времени
  4. Установить привязку к одному ядру процессора

Это несколько стабилизировало результаты. Есть еще идеи?

Ответы [ 3 ]

7 голосов
/ 26 декабря 2011

Я достиг 100% последовательных результатов следующим образом:

  1. Настройка Bochs с MS-DOS.
  2. Настройте ваш набор инструментов для целевой MS-DOS
    & Mdash; или & mdash;
    1. Настройте ваш набор инструментов на 32-битную Windows
    2. Установите расширитель HX-DOS в Bochs.
    3. При необходимости взломайте стандартную библиотеку / среду выполнения вашего инструментария и отключите / удалите функции, для которых требуются API-интерфейсы Windows, не реализованные в HX-DOS. Расширитель напечатает список нереализованных API, когда вы попытаетесь запустить программу.
  3. Уменьшите количество циклов в своем тесте на несколько порядков.
  4. Оберните тестовый код инструкциями ассемблера cli / sti (обратите внимание, что двоичный файл не будет работать в современных ОС после этого изменения).
  5. Если вы еще этого не сделали, сделайте в своем тесте rdtsc дельты для определения времени. Образцы должны соответствовать инструкциям cli & hellip; sti.
  6. Запустите его в Бохах!

Bochs screenshot

Результат представляется полностью детерминированным, но не является точной оценкой общей эффективности (подробности см. В обсуждении под ответом Османа Турана).

В качестве бонуса, вот простой способ поделиться файлами с Bochs (так что вам не нужно каждый раз размонтировать / перестраивать / перемонтировать образ дискеты):

В Windows Bochs заблокирует файл образа дискеты, но файл все еще открывается в режиме общей записи. Это означает, что вы не можете перезаписать файл, но вы можете записать в него. (Я думаю, * операционные системы * nix могут вызывать перезапись для создания нового файла, если речь идет о файловых дескрипторах.) Хитрость заключается в использовании dd. У меня был настроен следующий пакетный скрипт: 

... benchmark build commands here ...
copy /Y C:\Path\To\Benchmark\Project\test2dos.exe floppy\test2.exe
bfi -t=288 -f=floppysrc.img floppy
dd if=floppysrc.img of=floppy.img

bfi - это Барт Создание образа дискеты .

Затем просто смонтируйте floppy.img в Bochs.

Бонусный совет №2. Чтобы не запускать тест каждый раз вручную в Bochs, поместите пустой файл go.txt в каталог дискет и запустите этот пакет в Bochs: 

@echo off
A:
:loop
choice /T:y,1 > nul
if not exist go.txt goto loop
del go.txt
echo ---------------------------------------------------
test2
goto loop

Он запускает тестовую программу каждый раз, когда обнаруживает свежее изображение с дискеты. Таким образом, вы можете автоматизировать запуск теста в одном скрипте.

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

1 голос
/ 25 декабря 2011

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

Также я рекомендую вам посмотреть PDF документ с сайта Агнера. Это действительно бесценный документ, позволяющий проводить такую ​​микрооптимизацию.

В качестве примечания, фактическая производительность не является функцией "тактов". Промахи кэша могут изменить все для каждого запуска в реальном приложении. Итак, я бы сначала оптимизировал ошибки кеша. Простой запуск фрагмента кода несколько раз для одной и той же части памяти значительно снижает пропускную способность кэша. Таким образом, это затрудняет точное измерение. Настройка всего приложения обычно является лучшей идеей IMO. Intel VTune и другие инструменты действительно хороши для такого использования.

1 голос
/ 25 декабря 2011

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

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

...