Это действительно широкий вопрос, и поэтому я не думаю, что вам следует надеяться, что кто-нибудь зайдет сюда и даст вам один последний правильный ответ относительно того, как измерять производительность.При этом ...
Во-первых, вы должны разработать набор тестов.Для этого существуют два популярных метода: отслеживать реальную последовательность операций, выполняемых приложением (поэтому найдите какое-либо приложение с открытым исходным кодом, использующее дерево AVL или RB, и добавьте некоторый код, чтобы распечатать последовательность операций, которые оно выполняет) или создать такой поток операций аналитически (или синтетически) для нацеливания на любое количество случаев (среднее использование, конкретные виды ненормального или необычного использования, случайное использование и т. д.).Чем больше таких трасс вы получите для проверки, тем лучше.
После того, как у вас есть набор трасс для тестирования, вам нужно разработать драйвер для оценки.Драйвер должен быть простым, одинаковым как для деревьев AVL, так и для деревьев RB (я думаю, что в этом случае это не должно быть проблемой; оба представляют один и тот же интерфейс для пользователей, различаясь только с точки зрения внутренних деталей реализации).Драйвер должен иметь возможность эффективно воспроизводить использование, записанное в ваших наборах трассировок, и выполнять отслеживаемые операции над вашими структурами данных.Одна вещь, которую мне нравится делать, - это включить третьего «фиктивного» кандидата, который ничего не делает;Таким образом, я вижу, как сильно влияет обработка трассировок на общую производительность.
Каждая трассировка должна выполняться много, много раз.Вы можете несколько формализовать это (чтобы уменьшить статистическую неопределенность в пределах известных границ), но практическое правило заключается в том, что порядок вашей ошибки будет уменьшаться в соответствии с 1 / sqrt (n), где n - количество испытаний.Другими словами, запустив каждую трассу 10000 раз вместо 100 раз, вы получите в среднем ошибки, которые в 10 раз меньше.Запишите все значения;нужно искать среднее значение, медиану, режим (ы) и т. д. Для каждого запуска старайтесь поддерживать системные условия одинаковыми;другие программы не запускаются и т. д. Чтобы устранить ложные результаты из-за изменения внешних факторов, вы можете отбросить нижние и верхние 10% выбросов ...
Теперь просто сравните наборы данных.Возможно, вас больше всего волнует среднее время, которое занимает трассировка?Возможно худшее?Может быть, то, что вас действительно волнует, это последовательность;стандартное отклонение большое или маленькое?У вас должно быть достаточно данных для сравнения результатов для данной трассы, выполненной в обеих тестовых структурах;и для разных трасс может иметь смысл взглянуть на разные фигуры (например, если вы создали синтетический эталонный тест, который должен быть наихудшим для деревьев RB, вы можете спросить, насколько плохи были деревья RB и AVL, тогда как вы можете этого не делать.позаботьтесь об этом для другой трассировки, представляющей наилучший случай для деревьев AVL и т. д.)
Временная привязка к ЦП может быть проблемой сама по себе.Вам нужно убедиться, что разрешение вашего таймера достаточно для измерения ваших событий.Функции clock () и gettimeofday () - и другие - являются популярным выбором для записи времени событий.Если ваши трассы заканчиваются слишком быстро, вы можете получить совокупное время для нескольких испытаний (так что, если ваш таймер поддерживает синхронизацию микросекунд и ваши трассы заканчиваются за 10 микросекунд, вы можете измерить 100 выполнений трассы вместо 1, и получить значения времени на10 миллисекунд, что должно быть точным).
Еще одна потенциальная ловушка - каждый раз предоставлять одну и ту же среду выполнения.В промежутках между трассировками, по крайней мере, вы могли бы рассмотреть методы для обеспечения того, чтобы вы начали с чистого кэша.Либо так, либо не рассчитывайте время первого выполнения, либо понимайте, что этот результат может быть отбракован, когда вы устраните выбросы.Возможно, было бы безопаснее просто сбросить кэш (манипулируя каждым элементом некоторого большого массива, например, между выполнениями трассировок), поскольку для кода A может быть полезно иметь некоторые значения в кэше, в то время как код B может пострадать.
Это несколько вещей, которые вы могли бы учесть, выполняя собственную оценку производительности.Другие инструменты, например, такие как PAPI и другие профилировщики, могут измерять определенные события - попадания / пропуски в кеше, инструкции и т. Д. - и эта информация позволяет проводить гораздо более сложные сравнения, чем простые сравнения времени выполнения настенных часов.