Проблема с многопоточностью в Windows

[Sket4]

Здравствуйте!
Написал программу для расчета числа пи методом Монте-карло. Чтобы получить достоверное значение, нужно выполнить некоторый алгоритм n-е число раз. Вкратце, алгоритм такой: генерируем случайное число заданном в диапазоне и проверяем его на вхождение в некоторую область, если число "входит", увеличиваем счетчик вхождений на 1. Эти операции в моей программе повторяются 250 млн. раз (чем больше, тем точнее результат). Решил "помочь" процессору, создав поток, выполняющий те же самые операции
Вот сам алгоритм:

Код:

// passes - кол-во просчетов алгоритма ( == 250 млн.)
// kv_count - число текущих просчетов
// kr_count - число "подходящих точек"
while(kv_count < passes)
	{
		// генерируем случайные координаты в пределах квадрата
		x = rand() % radius;
		y = rand() % radius;

		// увеличиваем число обработанных точек
		InterlockedExchangeAdd(&kv_count, 1);
		
		// проверяем точку на вхождение в круг
		if((x * x + y * y) <= radius * radius)
			// если точка подходит, увеличиваем число вхождений на 1.
			InterlockedExchangeAdd(&kr_count, 1);
			
	}

Расчет алгоритма 250 млн. раз на моем компьютере занимает примерно 35 сек.
Теперь сама проблема: после просчета я обьявляю переменную r2 и присваиваю ей значение r2 = radius * radius, но в самом цикле не использую. Запускаю - теперь расчет занимает 50 секунд. Пробую закомментировать строку r2 = radius * radius, получаю снова 30 сек. Не понимаю, в чем проблема  99 % процессорного времени занимает прогон цикла, в котором перменная r2 даже не используется...
Кто знает,прошу помощи 

[RXL]

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

[Вад]

Я бы, кстати, вообще избавился от синхронизации каких-то счётчиков в работе алгоритма. Просто разделил бы число тестов на нужное количество потоков, считал бы в каждом потоке отдельно, а по итогам всей работы суммировал бы счётчики от каждого потока.
Кстати, не уверен, что rand потоконезависимый. Потоки создаются как, beginthreadex_ или CreateThread?

[Sket4]

В Debug- версии в обоих случаях время расчета одно. В релиз - версии без этой строки расчет выполняется гораздо быстрее. Пусть компилятор и уберет ее, мне не понятно, каким образом она влияет на время расчета, будучи ни разу не задействованная в ней. Кстати, процессор двухядерный.
Потоки создаются через _beginthreadex. В настройках проекта используется Многопоточная DLL

[Вад]

Sket4, не совсем понял, где ты заводишь и как используешь r2. Можешь показать изменённый код?

[Sket4]

int r2;    // глобальная переменная, обьявляется до ф-ии main
В теле ф-ии main, до выполнения цикла пишу строку: r2 = radius * radius. Это все. Если недостаточно, вложил файл с проектом.
Есть такие мысли, может дело в выравнивании данных 

[Вад]

У меня 2008 студия, пришлось создать свой проект.
Твой код у меня работает в релизе за 21.0-21.5 секунду в обоих случаях (со строкой и без неё). Или это какой-то баг в компиляторе 2010, или что-то ещё. Ты запускаешь релиз отдельно от студии? (Ctrl+F5, например)

[Sket4]

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

[Dimka]

По-моему алгоритм некорректный. Идея Монте-Карло состоит в том, чтобы соотнести площади внутри фигуры и полной площади. Это значит, что с заданной точностью будет получен результат при покрытии тестами всей полной площади (обычное сканирование по строкам и столбцам). При этом всегда есть множество ещё не рассмотренных и уже рассмотренных точек. Чтобы ускорить получение результата, точки выбираются равномерно случайным образом из множества нерассмотренных - равномерное случайное распределение при этом гарантирует, что число попавших в фигуру точек соотносится с общим числом рассмотренных точек так же, как соотносятся полные множества точек внутри фигуры и всех точек (т.е. плотность распределения одинакова на всей площади).

В приведённом решении нет контроля повторных попаданий в одну и ту же точку, а распределение остатков от деления не является равномерным. Это значит, что возможно получение плохого случая, когда плотность точек внутри фигуры может быть не равной плотности вне фигуры. В пределе стабильно попадаем в центр круга 250 млн раз и "узнаём", что площать круга равна площади квадрата

[Sket4]

Про некорректность соглашусь, даже при расчетах в 250 млн. раз результат может быть равен 3.146 но меня это сейчас мало интересует, эту реализацию я наспех набросал проект был создан с целью протестировать выгоду многопоточности, столкнулся вот с полным непониманием принципаработы компилятора в 2010 студии

[Dimka]

Sket4, а причём тут компилятор?

Прежде чем браться за потоки, хорошо было бы выполнить профилирование и узнать, какие инструкции являются самыми "тяжёлыми".

Второй момент: выгода от многопоточности будет лишь при эффективном распараллеливании выполнения инструкций (например, по ядрам процессора). В противном случае будет лишь торможение на переключении контекстов в Windows (если много потоков).

Третий момент: торможение на синхронизации (все потоки выполняют критическую секцию один за другим - получается очередь, бутылочное горлышко).

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

Лучше бы о предложении Вада подумал.

[lapulya]

У него в коде (тот, что отражается в ветке, прикрепленный файл не смотрел) нет переключения контекстов (поскольку ни критических секций, ни тем более синхронизаций с использованием объектов ядра). Но замечание про понимание поддерживаю в общем смысле.

[Dimka]

У него в коде (тот, что отражается в ветке, прикрепленный файл не смотрел) нет переключения контекстов

Естественно, это делает диспетчер задач операционной системы, а не программист.

поскольку ни критических секций, ни тем более синхронизаций с использованием объектов ядра

У него есть:

InterlockedExchangeAdd(&kv_count, 1);

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

Эффективное использование многих ядер возможно лишь в таком решении, которое предложил Вад.

[lapulya]

Еще раз повторяю - нет у него переключений контекста. Interlocked вызовы не приводят к переключениям контекста.

Нет у него использований объектов ядра. Объект ядра это некоторый дескриптор, их в коде нет.

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

[Dimka]

Еще раз повторяю - нет у него переключений контекста. Interlocked вызовы не приводят к переключениям контекста.

Нет у него использований объектов ядра. Объект ядра это некоторый дескриптор, их в коде нет.

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

И? Спор ради спора?

[lapulya]

да я и не спорил, я просто уточнить хотел.

[Sket4]

Так, как предложил Вад, уже сделал, время вычисления сократилось в два раза, после того, как убрал из кода Interlocked функции. Не спорю, что компилятор правильно исполняет свои обязанности, интереснее то, что результаты разительно отличаются в разных версиях компилятора, причем в версии поновее - в отрицательную сторону. А сама программа, пускай и написана "сходу", послужила хорошим полигоном для изучения плюсов многопоточности (я только - только начал втыкать в них . Плюсы были, кстати. Если кому интересно, при использовании 2х потоков вместо одного время вычисления на одноядерном проце с HT сократилось на 20 %, на двухядерном на 55 %. При трех потоках - уже минус. Ну может на трехядерном процессоре был бы прирост... За советы огромное спасибо, ценю 

[lapulya]

там кстати какие-то статьи были про многопоточность... помоему...

[Sket4]

Там, это где?

[lapulya]

Где то тут
https://club.shelek.ru/view.php

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

ну тогда тут
https://club.shelek.ru/download.php?id=239

[Вад]

Кстати, если помнить про разные фреймворки (как раз только что на глаза попался примерчик про Intel TBB: http://habrahabr.ru/blogs/development/102670/), данную задачу вообще практически не надо параллелить. Точнее, надо лишь организовать так, чтобы тесты были независимые. Думаю, это тоже полезно иметь в виду: если сколько-то там лет назад ничего такого ещё не было, то теперь есть openMP и тот же TBB, и если задача успешно решается готовыми средствами, не стоит городить велосипедов.

А вот, кстати, интересно, что будет с rand() в случае, если я опишу алгоритм и засуну в TBB. Но, думаю, об этом позаботились

[Ochkarik]

можно мои пять копеек вставить? поскольку оптимизацию люблю...

1. ошибка использовать InterlockedExchangeAdd() если возвращаемое значение вам не нужно. вместо нее - необходима всего лишь InterlockedIncrement().

2. Interlocked-функции выполняются очень быстро(это единственная аппаратно реализуемая синхронизация) - однако завернуты в вызов call. чтобы избежать этого - по возможности использовать intrinsic-аналоги _InterlockedIncrement().

3. само-собой включить всю отпимизацию на максимум.

4. оценивать работу комплиятора по ассемблерным листингам - это довольно просто, даже не сильно разбираясь в ассемблере.

5. основные накладные места цикла - всего два:
    1. rand() - посмотреть реализацию, не уверен что она очень быстрая, и хорошо работает в нескольких нитях
    2. вызов InterlockedExchangeAdd. не сама функция а именно вызов!

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

PS kv_count и kr_count  должны быть объявлены как volatile. так правильнее)
PPS а профайлер в данном случае бесполезен... тут же совсем простой код - все видно невооруженным глазом. да и вообще, ИМХО, пользоваться профайлером - все равно что не понимать собственную программу)
PPPS а по собственно вопросу - надо асемблер смотреть. чего там компилятор наворотил в обоих случаях)
PPPPS а про общую память и interlocked - по-моему верно. при слишком интенсивном использовании interlocked,  фактически память будет заблокирована одним из процессов. точнее - будет заблокирована вся кэш-линейка L1 на 128 байт, или как ее там... кэш я плохо знаю... выход - разворачивать цикл, благо тут это вполне возможно.

[lapulya]

Оф топ.
Размер кеша L1 это килобайты, а не байты

[Ochkarik]

я говорил про размер кэш-линейки а не всего кеша) если не ошибкаюсь она была 128 байт....
PS или кэш-строка, если угодно...

PPS кстати вот имеет смысл почитать... http://rus-linux.net/lib.php?name=/MyLDP/hard/memory/memory-7-1(6.4).html мельком глянул - вроде по теме.

[resource]

Много потоков для прироста скорости подобных действий это действительно несуразно. Параллелить нечего абсолютно. В этом случае меет смысл задать более высокий приоритет для потока.

[Ochkarik]

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

[resource]

ну значит я чего-то не так понял. Исходил из этого

Решил "помочь" процессору, создав поток, выполняющий те же самые операции

Как это еще можно понять, не знаю.