#c #c 11
#c #c 11
Вопрос:
В одном из наших университетских проектов мы работаем над проектом сравнительного анализа. По сути, мы генерируем случайное значение no. а затем вставьте его в std::set (RBTree), а затем удалите его. Мы делаем это в течение определенного интервала времени. По сути, так выглядит код
auto randomNo = std::random_device{}();
//Measure insertion
auto start = std::chrono::steady_clock::now();
myset.insert(randomNo ); //log(n)
auto end = std::chrono::steady_clock::now();
auto difference = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
//record the diff.
//Measure erasures
start = std::chrono::steady_clock::now();
myset.erase(randomNum); //log(n)
end = std::chrono::steady_clock::now();
difference = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
//record the diff.
Есть идеи, почему в некоторых новых запусках вставка и удаление занимают больше времени, чем обычно?
Комментарии:
1. Я предполагаю, что причина в том, что вы всегда начинаете с пустого набора. Если вы это сделаете, это может привести к нескольким последствиям, включая, но не ограничиваясь, поведение кэша, стоимость перебалансировки и т.д. Рассмотрим два этапа в вашем тесте: (i) загрузка данных, при которой вы инициализируете (фаза прогрева) набор с некоторыми случайными данными, (ii) фактический тест, при котором вы будете выполнять предопределенное количество операций вставки / стирания. Это хорошо известный метод выполнения бенчмарка для структур данных.
2. Часы
std::chronoизмеряют время работы, а не время процессора. Существует множество вещей на уровне операционной системы, которые могут отнимать процессорные циклы у вашей программы.3. Обратите внимание, что нет необходимости
std::set()использовать красно-черное дерево под капотом, это просто самый распространенный способ его реализации.4. Что такое «намного больше времени, чем обычно»? Обратите внимание, что эти часы C не имеют заданной точности. То, что вы приводите к наносекундам, не означает, что вы получаете измерения с точностью до наносекунды … это само по себе может объяснить большие различия от запуска к запуску. Вы могли бы предоставить нам несколько раз — возможно, небольшую гистограмму (таблицу), показывающую обнаруженное вами несоответствие.
5. Кроме того, почему ваша генерация случайных чисел находится внутри вашего временного блока? Вы понятия не имеете, сколько времени это займет, или если оно даже равномерное. О, подождите, это не тот код, который вы на самом деле рассчитываете… Кроме того, вы не знаете, находятся ли удаляемые элементы в дереве или нет (что, очевидно, дает разное время)! О, подождите, это не тот код, который вы на самом деле рассчитываете…
Ответ №1:
Здесь есть несколько вещей, которые идут не так:
- Вы измеряете только одну вставку или удаление. Вы должны попытаться измерить, сколько времени требуется для выполнения ста тысяч записей, и взять среднее значение.
- Вы не выполняете никакого прогрева. Операция set может работать с холодным кэшем процессора, следующее выделение памяти может быть невыполнимым без необходимости стандартной библиотеки запрашивать блок памяти у операционной системы и так далее. Попробуйте запустить цикл, который выполняет операцию на сто тысяч итераций, прежде чем начать фактическое измерение.
- Возможно, ваш процесс не работает непрерывно. На вашем компьютере запущено много процессов, возможно, операционная система решит приостановить ваш процесс на некоторое время, давая возможность запустить другой процесс. Если это произойдет между записью
startиstop, это будет выглядеть так, как будто ваша операция заняла много времени. - В настоящее время большинство процессоров постоянно меняют частоту, с которой они работают, чтобы быть энергоэффективными и оставаться прохладными. Возможно, в некоторых запусках частота процессора отличалась от других. Наличие фазы прогрева и усреднения многих операций поможет смягчить этот эффект.
Я предлагаю вам начать использовать существующую библиотеку сравнительного анализа для выполнения такого рода тестов производительности, например, Google Benchmark. Часто эти библиотеки уже решают некоторые из этих проблем за вас.
Комментарии:
1. Вы можете привязать процесс к определенному процессору, чтобы избежать влияния переключения.
2. OP следует рассмотреть возможность использования правильно разработанной библиотеки микро-тестов для проведения этих таймингов — после прочтения о том, как выполнять микро-тесты. Одна из нескольких библиотек, которая упоминалась в SO в прошлом, — это Google Benchmark .
3. Спасибо за комментарий. На самом деле мы выполняем прогрев и вставляем определенное количество элементов в набор.
4. YCSB-C — еще одна хорошая платформа для проведения такого сравнительного анализа.
5. @Rajeshwar — значит, опубликованный вами код на самом деле не тот код, который вы используете? Как вы знаете, это неоптимально для получения сфокусированных правильных ответов SO. Я понимаю необходимость здесь, на SO, размещать простой код… но это немного вводит в заблуждение и могло быть объяснено в вашем вопросе.