Распараллеливание программы (ядра/потоки)

[Andrey_Kireew]

С другой стороны, если все эти массивы помещаются в chache, то их размещение хоть в куче хоть в стеке, вообще влиять ни на что не должно.

[Dmitriy40]

Andrey_Kireew в сообщении #1435520 писал(а):

С другой стороны, если все эти массивы помещаются в chache, то их размещение хоть в куче хоть в стеке, вообще влиять ни на что не должно.

Я повторю: если хватает ассоциативности кэшей (и TLB). Иначе они будут читаться из памяти, даже если объём меньше объёма кэша. Например достаточно читать 13 байтов/слов с адресами $i \cdot 2^{24}$ и вуаля, все они будут читаться из памяти, хотя 13 слов на порядки меньше объёма даже кэша L1. Пример на переполнение TLB придумать сложнее, не помню конкретных цифр, да ещё это и от ОС зависит.

[Andrey_Kireew]

Dmitriy40 в сообщении #1435527 писал(а):

Я повторю: если хватает ассоциативности кэшей (и TLB). Иначе они будут читаться из памяти, даже если объём меньше объёма кэша. Например достаточно читать 13 байтов/слов с адресами $i \cdot 2^{24}$ и вуаля

Из Вашего сообщения напрашивается вывод: если я все промежуточные данные объединю в единый массив, то проблема должна исчезнуть. По идее new может располагать массивы как рядом, так и далеко друг от друга. В принципе, от этого может и возникать наблюдаемая нестабильность. Верно ли я понимаю?

-- 17.01.2020, 00:14 --

Ещё один вопрос, правильно ли я Dmitriy40 понимаю, что на основании полученной информации можно с высокой уверенностью предположить, что данные у меня в chache на долго не задерживаются и чтение данных идёт в основном из памяти?

[Dmitriy40]

Andrey_Kireew в сообщении #1435532 писал(а):

Из Вашего сообщения напрашивается вывод: если я все промежуточные данные объединю в единый массив, то проблема должна исчезнуть. По идее new может располагать массивы как рядом, так и далеко друг от друга. В принципе, от этого может и возникать наблюдаемая нестабильность. Верно ли я понимаю?

Не совсем: не так важно как далеко данные, важно какие у их адресов младшие биты. Они могут быть в разных концах 2ГБ пространства, но иметь одинаковые младшие 13 битов (для вашего процессора) — и будет беда с кэшем L1. Одинаковые 15 младших битов — и беда с кэшем L2. Беда в том случае, если по таким вот адресам расположены более 8-ми адресуемых объектов (включая и стек и все переменные, вообще все данные). 17 объектов (про 13 был не прав) с одинаковыми 19 младшими битами надо для "переполнения" кэша L3 объёмом 8МБ.
И при этом самые младшие 6 битов адреса наоборот не влияют, они в одной кэшлинии, потому одинаковыми выше я подразумевал лишь биты 12..6 или 14..6 или 18..6 (нумерация с 0).

Andrey_Kireew в сообщении #1435532 писал(а):

на основании полученной информации можно с высокой уверенностью предположить, что данные у меня в chache на долго не задерживаются и чтение данных идёт в основном из памяти?

Я не видел к этому веских оснований, пока это лишь предположение, подтверждают ли Ваши опыты его или нет — мне непонятно.

[mihaild]

Andrey_Kireew в сообщении #1435532 писал(а):

на основании полученной информации можно с высокой уверенностью предположить, что данные у меня в chache на долго не задерживаются и чтение данных идёт в основном из памяти?

Под винду есть что-нибудь, умеющее считать промахи кеша? Если да, то кажется именно этим стоит воспользоваться для определения ответа.

[Andrey_Kireew]

Dmitriy40 в сообщении #1435538 писал(а):

Я не видел к этому веских оснований, пока это лишь предположение, подтверждают ли Ваши опыты его или нет — мне непонятно

как тогда объеснить что с кучей программа работает неустойчиво, а со стёком - нормально?

[Dmitriy40]

mihaild
Так ведь есть стандартный perfmon. Правда что конкретно там за счётчики и как его натравить на выделенный поток/процесс не знаю, изучать надо.

[Andrey_Kireew]

В общем, резюмируя вышеизложенное, можно сказать следующее:
1. многопоточное приложение неустойчиво работает с памятью, выделенной в куче с помощью new,
2. при работе с памятью, выделенной в стёке, всё работает отлично (проверял и с Hyperthread - это даёт дополнительное ускорение около 10%);
3. внятного объяснения всему этому нет, кроме сомнительных догадок
4. однако есть решение - выделять память через _malloca(); и освобождать через _freea(); (нужно #include <malloc.h>),
я так и сделал - пока всё работает чётко

[Dmitriy40]

Andrey_Kireew в сообщении #1435548 писал(а):

1. многопоточное приложение неустойчиво работает с памятью, выделенной в куче с помощью new,

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

[SergeCpp]

Andrey_Kireew в сообщении #1435548 писал(а):

Многопоточное приложение неустойчиво работает с памятью, выделенной в куче с помощью new.

Потому что new использует межпоточную синхронизацию (так как куча оператора new одна на процесс). Пройдите отладчиком, увидите.

MS всё поудаляли из msdn online, сложно вам ссылку найти... Вот SO.

Цитата:

When a multithreaded heap is used calls to memory allocation and deallocation are thread-safe at expense of additional overhead.

stackoverflow.com/questions/7991490/new-and-delete-handles-multithreading-issues

[Andrey_Kireew]

Dmitriy40 в сообщении #1435553 писал(а):

неустойчиво работает лишь конкретно ваше приложение

Это само собой разумеется, про другие я речи и не веду.
И тем не менее, думаю этот опыт может кому то и пригодится. Согласитесь, сразу в голову такое решение не придёт

[SergeCpp]

Рихтера почему не читаете?..

Цитата:

Многопоточная версия библиотеки С/С++, кроме того, "обертывает" некоторые функции синхронизирующими примитивами Всдь если бы два потока одновремен но вызывали функцию malloc, куча могла бы быть повреждена. Поэтому в многопо точной версии библиотеки потоки не могут одновременно выделять память из кучи. Второй поток она заставляет ждать до тех пор, пока первый не выйдет из функции malloc, и лишь тогда второй поток получает доступ к malloc. (Подробнее о синхрони зации потоков мы поговорим в главах 8, 9 и 10.)

Некоторые соображения по библиотеке С/С++

[Andrey_Kireew]

SergeCpp в сообщении #1435555 писал(а):

Потому что new использует межпоточную синхронизацию (так как куча оператора new одна на процесс). Пройдите отладчиком, увидите

т.е. Вы считаете, что запись массивов в стёк это правильное решение, а не какое то там "шаманство"?

[Dmitriy40]

SergeCpp
Может заодно объясните тогда и почему при выделении всей памяти в основном потоке и лишь её использовании (readonly) в вычислительных потоках скорость ещё хуже чем при выделении в вычислительных? Тут ведь нет задержек между потоками при выделении/освобождении памяти, а проблема ещё сильнее.

Да и выделение и освобождение происходит лишь единожды за 90с — ну какая к чёрту тут задержка синхронизации то?! На десятки мкс за сотню секунд?!

К тому же это было бы видно по функции GetThreadTimes, плавать ведь должно не user_time, а kernel_time. (Тут пожалуй не прав, наверняка new выполняется с правами юзера.)

[Andrey_Kireew]

SergeCpp в сообщении #1435557 писал(а):

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

но это не объяснение, там задержки по 30 секунд, а выделение памяти длится миллисекунды и оно у меня выполняется однократно

SergeCpp в сообщении #1435557 писал(а):

Рихтера почему не читаете?..

ещё как читаю, именно благодаря ему я привязал потоки к ядрам и установил максимальный приоритет потоков,
кстати спасибо! за эту книжку SergeCpp, мне понравилась, надо как нибудь её распечатать