Прийшов час осідлати справжнього Буцефала🏇🏻Приборкай норовливого коня разом з Newxel🏇🏻Умови на сайті
×Закрыть

C++ функция странно тормозит все программу

Ести функция которая комбинирует числа из переданного массива цифр. Например для массива [1,2,3] она составляет комбинации , 1,2,3,12,23,123 и передает их дальше для проверки является ли составленное число простым или нет. Если переданное число оказалось простым то в функцию возвращается 1 и мы увеличиваем счетчик простых чисел на 1. В конце возвращаем количество найденных простных чисел.
Наблюдается такая фигня — если я возвращаю в конце переменную primes_to_show, то обсчет 1000 массивов занимает 48 секунд, если я возвращаю просто число 5 или 10 или переменную primes_to_show_ret которая только что была инициализированна и ей присвоенно 10 то обсчет 1000 массивов занимает всего 5 секунд !!!!! Почему наблюдается такая большая разница ? И еще одна фигня, переменная к — это индекс цифры которая будет выбранна из массива, если я инициализирую ее как short (а не как int) то 5 секунд превращаются в 27 секунд, тоесть замедляестя все в 5 раз.

int get_all_simple(int *list_to_work,int dont_check_1_digit, int len_of_list){
//#    list_to_work=[1,2,3,4]
//#    print("list to work ",list_to_work)
	int primes_to_show = 0;
	int test_succ = 0;
	for(int i= 0; i<len_of_list; i++){
		for (int j=1;j<len_of_list-i+1-dont_check_1_digit;j++){
                int number_for_test=0;
		int k; /////////////////////must be int for speed!!!!!
		for (k=i;k<len_of_list-j+1;k++){
                    number_for_test = number_for_test*10 + list_to_work[k];
		}
		if (number_for_test%2){
	test_succ=prepare_and_check_simple(number_for_test,list_to_work[k]);
		primes_to_show = primes_to_show + test_succ;};
	        }
        }
//int primes_to_show_ret = 54;
//return (primes_to_show_ret);
//return (20);
return (primes_to_show);   //////////////////zasada tut
}
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Кстати, ради интереса прикиньте, сколько раз у вас одно и тоже число умножается на 10, 100, 1000.... Так как цифр всего 10, то может заранее подготовить таблицы. Может оказаться быстрее. Хотя умножение на 10 тоже быстро делается (по сути компилятор использует два сдвига и одно сложение). Да, скорость меряете в релизе или дебаге? В дебаге не мерьте.

А вот что стоит сделать — из трех вложенных циклов сделать 2. Третий лишний по определению.

в релизе, а как тут можна сделать два цикла если перебираются все возможные варианты для построения чисел ?

Я по Вашему коду смотрю, я ж говорил — у Вас в третьем цикле бОльшей частью делаются одни и те же операции для каждого j. Посмотрите внимательно — по сути хватит одного прогона k до < len_of_list и в течении него получить все значения для всех j, а не пускать по новой каждый раз цикл k. Чуть переделать, но можно.

Почему наблюдается такая большая разница ?
Посмотрите в отладке, что он там генерит в обоих случаях (при отладке открыть дизасемблер, уже не помню точное название в студии — давно слишком запускал %))). Скорее всего при возвращении фиксированного или заранее определенного значения компилятор выкидывает лишний код, который не влияет на формирование результата. Ну или профайлер запустите — тогда точно увидите, на что сколько тратится.
если я инициализирую ее как short
Как уже сказали ниже — компилятор максимально быстро работает в родном размере целого (обычно 32-бит, далее предположим, что компилируете в х86). Работа с 16, 8 битными переменными требует дополнительной конвертации в 32-бит целое. Хотя бы потому, что в цикле у вас кроме к все остальные 32-бит. Число 1 — это int, len_of_list-j+1 — тоже int. Делая к short Вы заставляете делать компилятор лишние телодвижения по конверсии. А так как предел цикла — выражение, которое заранее неизвестно, то телодвижения делаются много раз.

ну не в 5 раз же ? скорее всего это как то связанно с оптимизацией кода компилятором, потому что он этот кусок кода должен был вообще выбросить, но если записать как short то он видно кусок кода не может отбросить и проганяет его — как то так вообщем

Профайлер в руки, тем более в студии даже есть встроенный. Всё остальное — гадание на кофейной гуще и упражнение в догадливости и прозорливости.

Сдается мне, что у вас идет каждый раз пересчет в циклах.

for (int j=1;j<len_of_list-i+1-dont_check_1_digit;j++)

Вынесите вычисления из цикла:

int limit = len_of_list-i+1-dont_check_1_digit; for (int j=1;j<limit;j++) { ... }

Ну и в других местах так же

могу попробовать, но насколько я помню нету выиграша если вычислять вне инициализации цикла или он очень маленький.

Ну как!?

А вообще в этом коде не сложно локализировать проблему. Используйте для этого метод сходий с «бинарным поиском»: закомментируйте половину кода и посмотрите есть ли «тормоза». В общем так вы сможете понять где именно узкие места.

Другой вариант использовать дебажный вывод сообщений с текущим временем (либо использовать системные тики). Опять же по выводу можно увидеть на каких местах именно «тупит».

пока не пробовал, во время пока я увлеченно лабал рекурсии на С++, накопилось других дел, поэтому пока ими занимаюсь. Я именно так и делал ставил счетчики времени на разные операции и смотрел где больше всего времени тереяется. Таким образом нашел что short k тормозит выполнение. Но в основном мест для оптимизации очень мало. Может завтра или послезавтра выложу код на гитхаб, пока что он очень грязный во многих местах и нуждается в переписке.

ну вообщем невидно прироста особого на 4×3

компилятор наооптимизировал. он увидел что там дурная работа которая ни на что не оказывает влияния в циклах выполняется, и что-то выкинул
попробуй отключить оптимизацию. если используеш gcc то дабавь флаги
-g -O0

С вероятностью 95% часть массивов дальше не используется (в отличии от возвращаемого prime_to_show) и компилятор просто выкидывает значительную часть вычислений.
Можно попробовать после этой функции распечатать все массивы (или посчитать сумму чисел и распечатать), чтоб компилятору думал, что они реально нужны. Если не поможет, в ассемблерный листинг надо глянуть, сравнить (это к вопросу, зачем нужно знать ассемблер).

что то не вижу связи массивов с возвращаемой переменной. Обе возвращаемые имеют тип int, одна из них сразу определенна а вторая чуть раньше. Почему скорость падает в 9 раз — непонятно.

Если у вас программа имеет вид:


int very_complex_function(int * array, size_t size)
{
int primes_to_show = 0;
...
// return 20; // Variant A
// return primes_to_show; // Variant B
}

int main()
{
...
printf("%d«, very_complex_function(array, size));
return 0;
}

То в случае варианта A компилятор просто выкинет все вычисления и оптимизирует программу чуть ли не до

int main()
{
...
write(STDOUT_FILENO, «20\n», 3);
return 0;
}
Вероятно, в вашем случае происходит что-то подобное.

так и есть, если определять тестовый ответ не перед отдачей а внутри циклов, то выполняется уже не 5сек а 15 сек, тоесть циклы не отброшены компилятором а выполняются. Спасибо за прояснение. А что может быть с типом к ?

Тип short у вас, вероятно, 16-битный, в то время как регистр процессора 32 или 64 битный. Операции с числами неродной длины всегда медленнее. В принципе, если размер массива — константа, то компилятор может забить на возможное перемолнение и соптимизировать, но лучше подсуетиться самому и использовать родные типы, тот же int. Я обычно size_t, ssize_t, ptrdiff_t использую для счетчиков, индексов, смещений и т. п.

Тип short у вас, вероятно, 16-битный, в то время как регистр процессора 32 или 64 битный. Операции с числами неродной длины всегда медленнее.

В C/C++ операции с числами короче int выполняются всегда в int (со знаком или без). Чтение такого числа из памяти/регистра в регистр в x86 делается через movsx/movzx, цена которым — копейки по сравнению даже с доступом в L2. Если значение лежит в регистре, то даже лишние movsx потратят ничтожное время. Если бы у него был MIPS/etc., я бы ещё понял Ваше замечание, но такая программа на них крайне маловероятна... ну, может, пару процентов потеряет, но не в 5 раз.

А вот то, что может тут влиять — это отказ компилятора производить оптимизации работы с индексом, если он непривычного типа. Например, в случае int производится внутренняя замена k на какое-нибудь _k2 = k*4, и k++ заменяется на _k2 += 4; если же он был short, то инкремент, копирование, умножение (если оптимизировал, то сдвиг и маскирование) заметно удлиняет цикл.

Я бы даже попытался этот цикл вручную развернуть — например, на 3 параллельных действия с промежуточным умножением на 1000.

меня тоже смутило замедление в 5 раз, и посетила такая же идея что компилятор что то там не отбрасывает и проходит по всему циклу если встретил разные типы.

Подписаться на комментарии