Преамбула.
Есть программка, делает полный перебор с возвратом и отсечением тупиков. Грубо говоря, решает задачу о рюкзаке в крупном масштабе.
Программа написана на С++ с использованием 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;
}
}
Код просто делает из двух отсортированных векторов третий, содержащий исключительно совпадающие значения.
Простой
