Почему так долго происходит инициализация нулями?

lujant

Есть глобальный массив float [10000][10000][2], пишу на c++, компилирую в msvs 2008. Программа решает уравнение Лапласа, вычисляя каждый элемент этого массива. В самом начале программы есть двойной цикл, который заполняет всю область массива, кроме границ, нулями: u[k][l][0]=0;. А потом есть ещё второй двойной цикл, который присваивает элементу значение, согласно поставленной задачи: uglobal[k][l][1-cL]=uglobal[k-1][l][cL]+uglobal[k+1][l][cL] + otn*(uglobal[k][l+1][cL]+uglobal[k][l-1][cL]);
И казалось бы, самым долгим и ресурсоемким должен быть второй цикл, поскольку там всякие умножения, никак не оптимизировать, но на деле оба цикла вместе выполняются 50 секунд, а если закомментить инициализацию программа работает 10 секунд.
В чем дело?

Helga87

код в студию
и да — почему не использовать memset вместо цикла?

Serab

Надеюсь, не отладочную версию собираешь?

lujant

Вот код: http://slil.ru/28976096
Там для снятия замеров используется сторонняя библиотека, которая вряд ли у вас есть, так что скомпилировать, видимо, не получится.
Мемсет не использую, потому что нет привычки. Собираю релиз-версию.

Devid

float [10000][10000][2]

Может лучше std::vector использовать?

lujant

Использовал три вложенных std::vector'а - они вообще не позволяют столько памяти выделить, вылетают ещё до самой первой команды.

Devid

Попробуй дебаг собрать. У меня на float f[10000][10000][2]; в дебаге выдается overflow, что неудивительно.

Helga87

Я провел замеры.
1. Инициализации нет:

krasin:~/Downloads$ time ./a.out

1.Simple, serial calculation let's start!



real    0m2.277s

user    0m1.668s

sys     0m0.516s

2. Инициализация циклом



for(int k = 1; k < Nx; k++)

{

  for(int l = 1; l < Ny; l++)

  {

    u[k][l][0]=0;

    u[k][l][1]=0;

  }

}

krasin:~/Downloads$ time ./a.out

1.Simple, serial calculation let's start!



real    0m3.321s

user    0m2.548s

sys     0m0.480s

3. Инициализация memset-ом

memset(u, 0, Nx * Ny * 2 * sizeof(float;



krasin:~/Downloads$ time ./a.out

1.Simple, serial calculation let's start!



real    0m2.580s

user    0m2.040s

sys     0m0.368s

Вывод: пользуйся memset
upd. Я временно стирал пост, поскольку выяснил, что неправильно вызывал memset (по памяти писал). Ща все правильно.

lujant

В дебаге же куча отладочной инфы, которая и замедлять должна, и куча вспомогательных структур, обилие которых, видимо, и вызвало overflow. Какой смысл, если релиз нормально работает?

Serab

Вывод: инициализировать статические переменные не особо-то и надо

Serab

Да не, дебаг-то может и не надо собирать, но вот 800Мб массивчик — это сила.

Devid

Короче, ты уверен, что у тебя в релизе корректно выделяется память, которой между прочим 800мб?
Просто float [10000][10000][2] должен выделять непрерывный кусок памяти и при этом он не расчисщает память, если такого куска нет и происходит какая-нибудь фигня, которую можно не сразу заметить.
А std::vector тоже выделяет непрерывный кусок, но при этом может расчищать себе место.

Helga87

float [10000][10000][2] должен выделять непрерывный кусок памяти

На 64 битной системе — это не проблема

Devid

Какой смысл, если релиз нормально работает?

Смысл в том, что релиз может делать вид, что он нормально работает, а работать неправильно. Затем и нужен дебаг. Например:

int main(int argc, char* argv[])

{

	float f[10000][10000][2];

	for(int i = 0; i < 10000; ++i)

		for(int j = 0; j < 10000; ++j)

			for(int k = 0; k < 2; ++k)

				f[i][j][k] = 0;



	return 0;

}

у меня в релизе работает, а

int main(int argc, char* argv[])

{

	float f[10000][10000][2];

	for(int i = 0; i < 10000; ++i)

		for(int j = 0; j < 10000; ++j)

			for(int k = 0; k < 2; ++k)

				f[i][j][k] = 0;



	std::cout << f[3434][343][1];

	system("pause");



	return 0;

}

уже нет.

Helga87

под "не работает" ты что понимаешь? coredump?
А! Так ты еще и на стеке выделяешь. Это ж наркоманство!

Devid

На 64 битной системе — это не проблема

Да, похоже у топикстартера такая.

Devid

stack overflow

lujant

Вывод: инициализировать статические переменные не особо-то и надо

Собственно, я так и заметил разницу во времени исполнения - понял, что инициализировать не надо, закомментил и обнаружил жуткую задержку. Вот и интересно стало - откуда она?
krasin, ты не мог бы объяснить время, которое выводит утилита time?
, ну, как бы, выделило-не выделило - работающие циклы (и при этом нормально завершающиеся, кстати) ведь от этого меньше или больше не становятся? Они абсолютно же одинаковые.

lujant

Нет, у меня 32-битная. , так а что - про выделение на стеке ведь сущая правда. Попробуй на глобале.
upd.: минуснул не я.

Helga87

krasin, ты не мог бы объяснить время, которое выводит утилита time?

Смотри на real. user и system тебя мало трогают (это детализация и она ваще тебя не парит)

Devid

Да пофиг. Глобал и правда инициализируется нормально.

lujant

А, я не обратил внимание на целую часть секунд. Блин, в любом случае, у тебя, похоже, очень быстрая тачка, так что замеры не показательны. Секундой больше - секундой меньше... Причем, даже инициализация циклом не намного дольше безинициализации работает - не видно, то ли у меня такой глюк на компе, то ли ещё чего.
В любом случае, вопрос не в том, как оптимизировать инициализацию, хотя за совет с мемсетом спасибо - в дальнейшейм буду использовать.

Helga87

~~У тебя сколько времени работает?~~50 секунд, это написано в первом сообщении
Может, тормозит твой профайлер? Еще я билдил g++, а не VS 2008. Тоже возможны варианты.
Тачка вроде не самая крутая, разве что памяти заведомо хватает (мб у тебя со swap борьба идет?)

lujant

Работает 50 и 10 секунд. Профайлеру я весьма доверяю.

Devid

Еще я билдил g++, а не VS 2008.

У меня VS 2008 за пару секунд заполняет. Профайлера нет.

lujant

Дело в том, что у меня бюджетнейшая тачка-неттоп с интел-атомом, поэтому, видимо, так долго. Что до памяти, то её тоже маловато, но причин для того, чтобы банальная инициализация нулями исполнялась в 40 раз дольше, чем заполнение массива вместе с громоздкими вычислениями - всё равно не видно, даже если там и правда постоянно со свопом идет работа.

Serab

Не, это ржака. Вот я раскомментил вывод на всякий случай (только в функции main, чтобы на времени не сказывалось так оно в дебаге работает 1784, а в Release — 3485. Это 9я студия, без явной инициализации.
С инициализацией соотношение сил примерно такое же, но ненамного больше (Release — 3843).
На gcc примерно как и у тебя, только там тачка послабее, там 10 и 12 секунд.

Helga87

Замени умножение сложением (т.е. приведи к одномерному массиву и индекс вычисляй как сумму предыдущего индекса + смещение)

vall

инициализировать в порядке размещения в памяти.
перепутанные индексы могут основательно замедлить всё дело.

Helga87

тачка-неттоп с интел-атомом

а! я, кстати, скорее всего понял
Atom — это in-order processor, да еще и кеша мало. Поэтому как тебе правильно сказал Blind, проблема в перепутанных индексах.

Serab

Ну там все так и делается. Я даже пробовал индексы [2] на начало вынести, это слабо сказалось.

lujant

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

Helga87

в чем разница между вычисляющим циклом и инициализирующим

а ты можешь посмотреть на количество cache miss-ов?

lujant

Если объяснишь, как это сделать - я как бы с профилировщиками вообще-то не работал, у меня простейшая функция, возвращающая время и всё.

Helga87

MSDN что-то рассказывает про это. Тебя интересует L2 Cache Read Misses

Helga87

Еще на ум пришло, что мб у атома настолько плохой branch predictor, что он никогда не угадывает. И в случае, когда тело цикла мало, все тупо.
Хотя это ща не самая главная гипотеза.

Serab

http://forums.bit-tech.net/showthread.php?t=166969 :crazy:

lujant

Кажется, там для этих цпу-счетчиков нужно использовать Profile Explorer, который есть только в Team Suite, а у меня Professional. Может быть какой-нибудь сторонний профилировщик посоветуешь?

apl13

Дело в том, что у меня бюджетнейшая тачка-неттоп с интел-атомом, поэтому, видимо, так долго. Что до памяти, то её тоже маловато

Однако массив на 800 миллионов байт помещается? :ooo:

Serab

Ничего, кроме AQTime под винду не знаю, к сожалению.

Helga87

http://stackoverflow.com/questions/1266183/how-can-i-access-...

procenkotanya

И казалось бы, самым долгим и ресурсоемким должен быть второй цикл, поскольку там всякие умножения, никак не оптимизировать, но на деле оба цикла вместе выполняются 50 секунд, а если закомментить инициализацию программа работает 10 секунд.
В чем дело?

Не видя код, который генерирует MSVC, можно только строить предположения. Можешь запостить сгенерированный ассемблер?
Ну и на будущее, в данном случае компилятор мог бы вообще выкинуть все циклы, потому что u нигде не используется. Лучше, как уже замечали в треде, печатать хотя бы один элемент из него.
edit: ну и замерить, сколько работает программа с инициализацией, но без вычислений, тоже было бы неплохо. Т.е. верно ли, что инициализация работает 40 секунд?

Andbar

Не видя код, который генерирует MSVC, можно только строить предположения. Можешь запостить сгенерированный ассемблер?

С включённой оптимизацией, превращается в

	mov	ecx, 200000000				; 0bebc200H

	xor	eax, eax

	mov	edi, OFFSET _f

	rep stosd

+сохранение edi в стеке

Serab

Ну это не тот исходник, у автора заполняется не весь массивчик, а только внутренность за исключением границы.

procenkotanya

Тогда неудивительно, что инициализация занимает 40 секунд, rep * у интела уже давно безнадёжно тормозят. У студии горе от ума

GCC отучили использовать rep, но пока не везде. А именно, strcmp и memcmp GCC до сих пор делает через rep cmpsb, что медленнее вызова библиотечной функции.

procenkotanya

Вопрос топикстартера относился именно к заполнению нулями всего двумерного массива, смотри внимательнее

Serab

Не понимаю. В первом сообщении написано "кроме границы", в коде написано кроме границы.

procenkotanya

А, да, я ступил (перепутал границу и внутренность). Сорри. Но это не сильно влияет, у студии будет rep stosd в цикле.

lujant

А как смотреть сгенерированный мсвс код? Пока что просто выдрал из иды нужные куски
http://slil.ru/28977459
Там четыре комментария от меня, надеюсь, понятные.

lujant

Сейчас сам смотрю код - какие-то там косяки с индексами мутные... Даже ида подсвечивает красным.

procenkotanya

это точно release версия? что за call'ы во внутренних циклах?

Serab

Мне кажется, это не полный asm-листинг. Причем там где комментарий говорит, что это заполнение нулями, мне кажется, что это вывод на экран (там же cout :ooo:

).
Еще мне кажется, что это асм уже другого исходника, где как минимум переименованы функции, так что сложновато будет понять

В общем это только код main, тут только вызовы calc и trueCalc.
Удивляет странная sub_401450. Такое ощущение, что она вызывает функцию с заданными параметрами, потому что перед ней пушится адрес функции. Что-то я такого раньше не видел :crazy:

lujant

я вставил cout'ы и только их, чтобы легче найти нужные места. Также, забыл написать, что в инициализирующим цикле, на самом деле, запись происходит дважды u[x][y][0] и для u[x][y][1] - вторую запись я закомментил. Ещё в коде по другому определены дефайны Nx = 10000, Ny = 7000, n = 100. Но как бы на код особо влиять не должно же.

lujant

Во-первых, idb к IDA:
http://slil.ru/28977795

lujant

А вот та загадочная функция:
http://slil.ru/28977823
Это релиз сборка, лично мой явный вызов этой функции в коде отсутствует. Зачем она нужна - не знаю.

lujant

По-поводу моих cout'ов
Я просто вставил строки вида cout << "lol1";
Ааа, ну да! Адрес cout'а пушится для загадочной функции, а она и выводит текст, в свою очередь. Ну да, всё ок по этой части.

Serab

Не, ну cout'ы внутри "вложенности" могли поломать оптимизацию.

lujant

http://slil.ru/28978034
В архиве idb + новый асм-код тех циклов. Убрал вложенные cout'ы, вернул 10000х10000.
И ещё, большое спасибо всем, кто участвовал и участвует в разборе этой геморройной странности и помогал советами!

Serab

Ну он по-честному ебашит и заполняет все нулями. Количество элементов в строке считает штуками (магическое число 270Fh = 9999 во всем массиве — адресами (магические числа 13888h = 1001 * 8, вот 8 — это как раз из-за "дырок", ты похоже [0] заполняешь, а [1] — нет, либо наоборот. И 2FF2AB58h - 43A360h примерно равно 8 * 10001 * 10001) Странно, рабочий код внешне отличается только проверкой этого условия на завершение цикла, причем внешнего, там просто два счетчика уменьшается, т.е. все считают штуками. Но там же куча вещественной арифметики.
Слушай, ты точно пробовал запустить без отладчика и всяких измерений времени? Все-таки 10 секунд от 50ти можно отличить и так, по ощущениям

Ответить по вопросу треда мне нечего =)
Кстати прикольно, что переносить "дырки" в начало массива как раз не надо, потому что новые значения слоя зависят от близких ячеек в предыдущий момент времени.

Helga87

http://slil.ru/28978034

есть такой сервис, pastebin.com. Намного удобнее для задач выложить кусок кода, нежели slil.ru

Serab

Интересно, кстати, что Intel Complier скажет. Ни у кого нету под рукой?

lujant

про [1] - так и есть, я отключил запись туда, чтобы соревнование по записям было равным. К сожалению, ситуация не стала ни на грамм лучше. По собственным же ощущениям (и часам виндавс) все подтверждается - с инициализацией все происходит гораздо дольше.
, спасибо! Добавил в ссылки!
И ещё один вброс: если закомментить вычисления и оставить только инициализацию, то длится она 19 секунд. То есть реально дольше вычислений.

lujant

кстати, буквально вчера пробовал ставить. Скачал редистрибьютивс библиотека, установил, но что-то нужная кнопочка в мсвс не появилась. Так что на время пока забил.

Serab

И ещё один вброс: если закомментить вычисления и оставить только инициализацию, то длится она 19 секунд. То есть реально дольше вычислений.

НО заметно меньше, чем <Вычисления + инициализация> - <Вычисления>?

Andbar

А как смотреть сгенерированный мсвс код? Пока что просто выдрал из иды нужные куски

Неплохо изучать бинарники с помощью IDA, но прежде чем это делать, следовало посмотреть на список параметров компилятора cl.exe и заметить там ключик /Fa

lujant

Ну как заметно... В 0.66 раза меньше, чем разница, но всё равно в два раза дольше, чем вычисления...
Ок, в следующий раз буду замечать - никогда просто эти опции не читал.

Serab

Если что в интерфейсе это Project Properties-> C/C++ -> Output Files -> Assembler Output (вторая строчка справа). Там можно выбрать, чего хочется. И cout'ы писать не придется, там есть варианты с отображением участков кода.
Спасибо за подсказку, кстати!

Оставить комментарий