Скорость чистого перебора — как такое может быть?

Преамбула.
Есть программка, делает полный перебор с возвратом и отсечением тупиков. Грубо говоря, решает задачу о рюкзаке в крупном масштабе.
Программа написана на С++ с использованием STL. В процессе перебора память не выделяется, переиспользуется заготовленная, данные невелики и должны попадать в кэш процессора.
Под Linux программа собрана GCC, под Windows - VS2010.

Амбула.
Один и тот же кейс, полный перебор всех вариантов, на Windows занимает 40 - 60 секунд.
На Linux - 11 минут!

Полная амбула.
Та же самая Windows-версия под Wine тормозит ровно так же, как Linux-версия. Соответственно, нюансы компилирования можем свернуть трубочкой.
Если кто-то считает, что разбирается - накиньте идей, в какую сторону вообще думать, поскольку использование именно этой программы именно под Linux предпочтительнее.
Профилирование перебора, очевидно, покажет, что все время жрет перебор, это я и так понимаю...

UPD: профилировка вручную показала довольно забавную штуку, на которой сегодня приходится закончить рабочий день:
// Вот эти строчки кушают под Окошками и под Линем практически одинаково
std::vector< short > update;
std::vector< short >::const_iterator v1 = nextVar.begin(), v2 = already.begin();
std::vector< short >::const_iterator e1 = nextVar.end(), e2 = already.end();
update.reserve(std::min(nextVar.size(), already.size())));

// А вот эти - 11% всего времени перебора под Окошками и 62% - под Линем!
// При том, что тот update УЖЕ имеет достаточный размер и НИКАК не может его превысить
while((v1 != e1) && (v2 != e2)) {
	if(*v1 < *v2) {
		++v1;
	} else if(*v1 > *v2) {
		++v2;
	} else {
		update.push_back(*v1);
		++v1;
		++v2;
	}
}

Код просто делает из двух отсортированных векторов третий, содержащий исключительно совпадающие значения.
  • Вопрос задан
  • 1032 просмотра
Решения вопроса 1
Adamos
@Adamos Автор вопроса
— Это просто, как блин, — сказал он. — Это тривиально. Это плоско и банально. Это даже неинтересно рассказывать

QtCreator при сборке Release-версии, оказывается, почему-то забывает сообщить своему qmake, что собирается именно Release-версия.
Прописанное в проекте QMAKE_CXXFLAGS_RELEASE += -Ofast - просто игнорируется.
Достаточно заменить его на QMAKE_CXXFLAGS += -Ofast или добавить в вызов qmake CONFIG += release - и собранная программа в Лине на реальном железе, разумеется, сразу кроет виртуальные Винды, как то положено природой.
Достаточно было внимательно заглянуть в вывод сборки, который, внезапно, от переключения между Debug и Release практически не менялся.
А дырочка
И щелочка
И странное отверстьице
Здесь вовсе ни при чем!
Ответ написан
Пригласить эксперта
Ответы на вопрос 6
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
В вопросе НЕТ НИКАКИХ СОБРАННЫХ ДАННЫХ, чтобы грамотно и чётко ответить на этот вопрос!
Ни собранных метрик, ни архитектуры, ни используемых технологий, ни тип приложения, ни инструменты компиляции кода, ни репозитория (или структуры), и т.д. - НИЧЕГО этого НЕТ.

Профилирование?! Нет, не слышали. :)
Ок. Сделайте вручную сами: возьмите и добавьте в инкапсулирующие (вызовы объектов) и итерационные вызовы (циклы, рекурсии) тайминги и ID-потоков (и другие метрики, для используемого функционального окружения).
После замера - сами всё увидите.

Профилирование перебора, очевидно, покажет, что все время жрет перебор, это я и так понимаю...
Странно, что только Вы это понимаете! ;)

я постараюсь рассказать, в чем дело, когда (и если) докопаюсь до истины.
...И покажу, что вы все тут нихрена не знаете, а я - д'Артаньян и могу ДАЖЕ! сам ответить на своё жалкое подобие "вопроса"!

UPD:
Код просто делает из двух отсортированных векторов третий, содержащий исключительно совпадающие значения.
тут
Ответ написан
profesor08
@profesor08
Придется признать победу windows.

Я бы замерил количество итерраций, сколько делает цикл, может он много лишнего делает, раз так в 100.
Ответ написан
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
Принты. Или наблюдения.
1. Цикл где идет merge двух векторов - тривиален. Слабым местом может быть функция резерва памяти, которая по разному реализована в win/Linux. Я не утверждаю что в linux она плохая. Возможно просто звёзды сошлись так что page или другие свойства ос по отношению к аллокаций стали неблагоприятны.

2. Что там с разрядностью 32/64? Надо проверить. Что с железом? Не пытается ли автор нас обхитрить, запуская все это на разном железе. Даже ничтожные различия в размере кешей L1 могли тут сработать.

3. Версии STL. Автор использует не сырые указатели а итераторы. Причем хитрые. Какая там логика на инкремент и на разыменование под капотом.

Чтоб отбросить мои предположения полностью - предлагаю этот цикл (предположительно самый горячий код со слов автора) переписать на указатели без STL.

4. Опции GCC надо посмотреть. Оптимизацию подвигать. O1, O2.
Ответ написан
@MechanID
Админ хостинг провайдера
я не настоящий сварщик но... посмотрите в gcc -v есть ли опция "-march=native" ? если нет задайте ее явно при компиляции.
Ответ написан
@Karpion
Ну, я бы посмотрел, сколько потоков порождает программа, и сколько ядер они занимают. Если у Вас на компьютере ядер примерно столько же, во сколько раз различие скорости работы - то имеет смысл смотреть именно сюда (я предполагаю, что WINE может задействовать только одно ядро).

Программа выполняется пакетно, как консольная утилита? Или она графическая?
Может, запустить её через команду time - посмотреть, что та скажет?
Ответ написан
@asd111
Если программе реально 15 лет то скорее всего проблема в wxWidget. Деды пишут что в те времена wxWidget тормозила на gtk2 и потребляла 10% CPU в редактировании текста.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы