Выделение свободной памяти в многопоточных приложениях

[Real16]

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

[Аэтерос]

Присутствует

[amk]

По крайней мере, если используется библиотека, собранная с поддержкой многопоточности.

[Real16]

А если в одном потоке будет неудача, как поведут себя другие?

[amk]

Зависит от библиотеки, но скорее всего дело будет обстоять так же как и при однопоточном.

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

[Real16]

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

[amk]

А смысл ее делить по потокам? Они в одном адресном пространстве выполняются.

[niXman]

Цитата Real16 @ 03.09.11, 06:22

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

угу.

[Real16]

Цитата amk @ 03.09.11, 08:30

А смысл ее делить по потокам? Они в одном адресном пространстве выполняются.

А если библиотека универсальна относительно кластеров и систем с общей памятью, то она в системе с общей памятью как-то разделяет.

(Из статической памяти же можно выделить приватную область - например, threadprivate в OpenMP или thread_local в С++11 - хотя при доступе к ней по адресу приватность, скорее всего не имеет значения)

[evlan]

Цитата Real16 @ 07.09.11, 08:34

А если библиотека универсальна относительно кластеров и систем с общей памятью

Есть такие?

[Real16]

Цитата evlan @ 07.09.11, 09:48

Цитата (Real16 @ Сегодня, 11:34)
А если библиотека универсальна относительно кластеров и систем с общей памятью
Есть такие?

Если применительно к С, то, по-видимому, такой должна быть UnifiedParallelC.
В других языках точно есть (Например, COARRAY-расширения стандартны для Фортрана).

[amk]

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

[Real16]

Т.е. в итоге можно сказать, что выделение памяти параллельно не имеет смысла, если только речь не идет о каких-то специальных средствах нестандартных библиотек или о применении нечто вроде _malloca?

[leo]

Дело не в адресном пространстве и доступности\недоступности памяти, а в том, что динамическая память (куча) имеет достаточно сложную организацию с множеством служебных структур, обновление которых и требует межпоточной блокировки при выделении\освобождении памяти. Соотв-но создавать отдельные кучи под разные потоки в общем случае накладно\нецелесообразно. Хотя, например, WinAPI позволяет это делать (HeapCreate + HeapDestroy). При этом ес-но все кучи создаются в одном адресном пространстве и выделенная в них память доступна всем потокам.
В связи со сложной организацией кучи логичнее не плодить их для разных потоков, а грубо говоря "еще более усложнить" организацию с целью сокращения времени межпоточных блокировок. Наглядный пример - это менеджер кучи FastMM, используемый в Дельфи и С-Билдере (с 2006г), который работает (как минимум) на порядок быстрее виндового = msvcrt-шного.

Добавлено 09.09.11, 07:13
PS: В FastMM как раз и используется идея кластеризации\распаралеливания в сочетании с interlocked спин-блокировками, т.е. вместо "тупого" прямого входа в крит.секцию, сначала предпринимаются попытки обратиться к другому кластеру и\или "чуток" подождать в спин-цикле, и только в сл.облома "на всех фронтах" приходится "подтягивать тяжелую артиллерию" (входить в крит.секцию)

[amk]

Вот как раз то, что память распределяется в одном адресном пространстве имеет определяющую роль.
Отбросим ситуации когда потоки имеют менеджеры памяти, ссылающиеся к общему, глобальному менеджеру. Так как это как раз ситуация общего менеджера.
Представьте, два потока, работающие в одном адресном пространстве, имеют каждый свой, независимый менеджер памяти. Первый распределяет блок памяти, передает ссылку второму, а тот должен ее освободить. Вопрос, менеджер памяти какого потока должен вернуть память в кучу?
Вторая проблема. Если каждый поток имеет свой менеджер памяти, значит какждый менеджер управляет своим участуом памяти. А это значит, что каждому менеджеру доступна не вся свободная память, а только половина. Если один из потоков кучей не пользуется - половина памяти не будет использоваться вообще.

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

[leo]

amk
Насколько я понимаю, таким образом ты поясняешь, почему new\malloc в разных потоках работают с одной кучей, а не каждый со своей.
Но для спец.задач ес-но можно и разные кучи использовать (те же виндовые HeapCreate), но разумеется не для передачи ссылок между разными потоками, а наоборот для максимально независимой их работы

[amk]

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

[Real16]

Цитата amk @ 10.09.11, 17:52

и распределить память статически.

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

[amk]

Цитата Real16 @ 11.09.11, 05:10

Статически (по умолчанию) много не распределишь. Динамически можно разместить в разы большие массивы, чем статически.

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

[Real16]

Цитата amk @ 11.09.11, 06:29

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

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

Цитата amk @ 11.09.11, 06:29

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

Какие преимущества в работе с большими кусками памяти в Linux?

[leo]

Цитата Real16 @ 11.09.11, 05:10

Итак, если выделять память параллельно при использовании стандартных средств не имеет смысла в силу неявной синхронизации, приводящей к сериализации (вырождению в последовательное выполнение).

Не имеет смысла в случае, если твои потоки ничем другим не занимаются кроме выделения\освобождения памяти. Если же поток бОльшую часть времени занимается обработкой данных, а выделение\освобождение памяти происходит "сравнительно редко", то и вероятность конфликта потоков на этих операциях выделения\освобождения памяти мала, и нечего над эти ломать голову
Сам подумай - чем больше массив, тем больше времени потребуется на его обработку, и соотв-но тем меньше будет относительный вклад затрат времени на выделение\освобождение массива

[amk]

Цитата Real16 @ 11.09.11, 06:36

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

Что ж, попробую проверить это утверждение

Цитата Real16 @ 11.09.11, 06:36

Какие преимущества в работе с большими кусками памяти в Linux?

Думаю никаких особых преимуществ нет (разве что может быть в винде искусственно ограничивается память), но вот 32-разрядная система может выделить больше памяти, чем 16-разрядная, а 64-разрядная больше, чем 32-разрядная.

[Real16]

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

[amk]

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

[trainer]

Цитата Real16 @ 27.09.11, 13:11

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

Есть такая удобная штука - называется "реентрантность (функций)"

[Real16]

Цитата trainer @ 27.09.11, 18:48

Есть такая удобная штука - называется "реентрантность (функций)"

Это обеспечения корректности рекурсивных вызовов?

Сообщение отредактировано: Real16 - 28.09.11, 03:50

[trainer]

Цитата Real16 @ 28.09.11, 03:50

Это обеспечения корректности рекурсивных вызовов?

В том числе. А также - корректный вызов из разных потоков.

[leo]

Цитата Real16 @ 27.09.11, 13:11

Хотя казалось бы, зачем массивам с константными размерами размещаться в автоматической памяти

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

[Real16]

Вопрос не странный. Особенно если его переформулировать так - зачем в стандартном С++ автоматические массивы должны иметь константные размеры? Например, в функциях автоматическими могли бы быть массивы с размерами, не являющимися константами (что, насколько помню, сделано в С99 и поддерживается в g++).

[shm]

Цитата Real16 @ 29.09.11, 15:28

Особенно если его переформулировать так - зачем в стандартном С++ автоматические массивы должны иметь константные размеры?

Вроде leo тебе нормально объяснил, ты вообще в курсе, что такое стековый кадр? или видел когда-нибудь ассемблерный листинг высокоуровневой процедуры?

Цитата Real16 @ 29.09.11, 15:28

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

А тебе лень написать "= new type[x]"? При использовании этого расширения выделяется память из кучи, а не из стека, т. е. почти ровно тоже самое, что malloc/new, только с автоматическим вызовом освобождения при выходе (хотя я вот лично сомневаюсь, что не будет утечки памяти в некоторых исключительных ситуациях).

Сообщение отредактировано: shm - 29.09.11, 16:16

[Qraizer]

C++ имеет иную философию, нежели C. Для C неинициализированный объект - обычное явление, и это проблема программиста озабачиваться его инициализацией. В C++ ты при желании можешь поступать так же, но в отличие от C, язык даёт возможность такого дизайна, что можно будет гарантировать невозможность существования неинициализрованных объектов. Т.е. если ты создал объект, то он есть, иначе до него добраться будет просто невозможно. Для классов есть конструкторы, которые бросят исключение, и объект просто уходит из области видимости, для хипа есть std::bad_alloc с аналогичным следствием. Для обычных автоматических C-массивов нет языковых механизмов, в ран-тайм обрабатывающих ситуацию нехватки памяти на стеке. Если же их ввести, то, во-первых, это будет требованием поддерживать их реализацию везде, даже на тех платформах, где это трудоёмко из-за отсутствия аппаратной проверки на переполнение, во-вторых, получится, что вызов любой функции потенциально способен бросить исключение переполнения стека. Стандарт на это никогда не шёл и не пойдёт.
Одно дело, когда вызывается new или определяется экземпляр класса, другое дело, когда просто вызывается функция или метод. С использованием автоматических C-массивов константного размера нет необходимости придумывать какие-либо новые языковые механизмы. Требуемые лимиты потенциально могут быть оценены и учтены в дизайне приложения, поэтому проблема переполнения стека перетекает из языковой в платформенную.

[leo]

Цитата Real16 @ 29.09.11, 15:28

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

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

[trainer]

Цитата Real16 @ 29.09.11, 15:28

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

Это не автоматические, а variable length array

P.S. А что такое вообще "автоматический массив" в твоем понимании? Массив, удаляемый автоматически по выходу из области видимости(т.е. имеющий automatic storage duration)?

[Real16]

Цитата trainer @ 30.09.11, 04:24

P.S. А что такое вообще "автоматический массив" в твоем понимании? Массив, удаляемый автоматически по выходу из области видимости(т.е. имеющий automatic storage duration)?

Вне контекста С++ - это массив, который может быть определен в некоторой функции fun (т.е. размещается в автоматической памяти), причем размеры не обязаны быть константами, т.е.,например, могут быть введены с клавиатуры в функции, вызывающей функцию fun, и переданы в качестве параметров fun. Что собственно возможно в gcc/g++, да и в других языках.

По-видимому, Qraiser дал близкое к истине обоснование.

Сообщение отредактировано: Real16 - 30.09.11, 08:32

[leo]

Раз не обязаны быть константами, то это не статика, а динамика, т.е. new\delete[] и т.п. В чем тогда суть вопроса? Типа не нравится new, хачу ReDim как в васике?!

[Real16]

Цитата leo @ 30.09.11, 08:34

хачу ReDim как в васике?!

Basic'а не знаю.

Сообщение отредактировано: Real16 - 30.09.11, 10:10

[Qraizer]

Вторая причина не философская, а сугубо практическая. Локальные массивы с автоматическим размещением удобны тем, что автоматически разрушаются при выходе из области видимости. В отличие от динамических массивов, которые следует явно освобождать free(). Тем самым в C99 работа с массивами переменной длины проще и безопаснее с точки зрения утечки ресурсов, нежели с динамическими. В C++ уже есть аналогичный функционал - std::vector. Так что к архитектурному обоснованию отсутствия таких массивов прибавляется бритва Оккама.

Добавлено 30.09.11, 10:40
Да, ещё следует заметить, что в младших C Стандартах, где таких массивов ещё не было, практически каждая C реализация имела функцию _alloca(). Она была аналогом malloc(), но память распределяла на стеке. Её не было в Стандарте языка, но в итоге её функционал был аналогичен тому, каковой предлагают массивы переменного размера. В новом C99, учитывая её распространённость и востребованность, видимо решили её стандартизировать, что и вылилось в новый вид массивов.

[trainer]

Цитата Qraizer @ 30.09.11, 10:35

Тем самым в C99 работа с массивами переменной длины

Это не массивы переменной длины. Это массивы, размерность которых задана не константным выражением.

Цитата

The size of each instance of a variable length array type does not change during its lifetime.

[Qraizer]

Та я просто перевёл variable length array.

[amk]

К сожалению, alloca (_alloca), будучи нестандартизованной, от реализации к реализации очень сильно отличались. В DECUS-С это было выделение памяти на стеке, привязанное к способу управления стеком принятому в DECUS-С потому решение непереносимое, хотя память освобождалась сразу при покидании выделившей ее функции.. В gcc alloca это выделение памяти в куче, но привязанное к стеку, благодаря чему при вызове alloca ранее выделенная, но более не использованная память обычно освобождается. К сожалению, можно придумать вполне реалистичные ситуации, когда память освобождаться не будет.