Перегрузка new/delete, хранение "метки" для выделенного учас
От: SeninAndrew Россия  
Дата: 17.09.06 17:35
Оценка:
Перегрузил глобальные операторы new/delete для оптимизации многопоточного приложения на многопроцессорном компьютере. Суть оптимизации: выделение памяти каждым потоком из отдельной кучи (все под ОС Windows). Удаление участков памяти возможно не из того потока, который память создал. Следовательно, нужно хранить для каждого выделенного участка метку: номер кучи, из которой память была выделена.

Прошу критически оценить предлагаемый способ хранения метки. В new с помощью HeapAlloc выделяется на 8 байт больше требуемого объема. В начале выделенного массива записывается номер кучи. Возвращается указатель ((char*)pPointer) + 8. В delete по адресу ((char*)pPointer) — 8 читается номер кучи и из нее удаляется память.

8 байт (хотя достаточно 1) резервируется для того, чтобы не нарушалось выравнивание данных. Законен ли такой подход.

Буду рад также други идеям хранения требуемых "меток".
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re: Перегрузка new/delete, хранение "метки" для выделенного
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 17.09.06 17:49
Оценка: 2 (1)
Здравствуйте, SeninAndrew

SA>Перегрузил глобальные операторы new/delete для оптимизации многопоточного приложения на многопроцессорном компьютере. Суть оптимизации: выделение памяти каждым потоком из отдельной кучи (все под ОС Windows). Удаление участков памяти возможно не из того потока, который память создал. Следовательно, нужно хранить для каждого выделенного участка метку: номер кучи, из которой память была выделена.


JFYI: Fast memory allocation library for multithreaded applications by Konstantine Knizhnik.


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[2]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 17.09.06 18:23
Оценка:
Здравствуйте, eao197, Вы писали:

E>JFYI: Fast memory allocation library for multithreaded applications by Konstantine Knizhnik.


Спасибо. Ссылка очень интересная.
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re: Перегрузка new/delete, хранение "метки" для выделенного
От: MaximE Великобритания  
Дата: 17.09.06 19:28
Оценка: 2 (1)
SeninAndrew wrote:

> Перегрузил глобальные операторы new/delete для оптимизации

> многопоточного приложения на многопроцессорном компьютере. Суть
> оптимизации: выделение памяти каждым потоком из отдельной кучи (все под
> ОС Windows). Удаление участков памяти возможно *не* из того потока,
> который память создал. Следовательно, нужно хранить для каждого
> выделенного участка метку: номер кучи, из которой память была выделена.
>
> Прошу критически оценить предлагаемый способ хранения метки. В new с
> помощью HeapAlloc выделяется на 8 байт больше требуемого объема. В
> начале выделенного массива записывается номер кучи. Возвращается
> указатель ((char*)pPointer) + 8. В delete по адресу ((char*)pPointer) —
> 8 читается номер кучи и из нее удаляется память.
>
> 8 байт (хотя достаточно 1) резервируется для того, чтобы не нарушалось
> выравнивание данных. Законен ли такой подход.
>
> Буду рад также други идеям хранения требуемых "меток".

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

Еще можно посмотреть на http://www.cs.umass.edu/~emery/hoard/

The Hoard memory allocator is a fast, scalable, and memory-efficient memory
allocator. It runs on a variety of platforms, including Linux, Solaris, and
Windows. Hoard is a drop-in replacement for malloc() that can dramatically
improve application performance, especially for multithreaded programs running
on multiprocessors. No change to your source is necessary. Just link it in or
set just one environment variable (see Using Hoard for more information).


--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re: Перегрузка new/delete, хранение "метки" для выделенного
От: Vain Россия google.ru
Дата: 17.09.06 19:47
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Перегрузил глобальные операторы new/delete для оптимизации многопоточного приложения на многопроцессорном компьютере. Суть оптимизации: выделение памяти каждым потоком из отдельной кучи (все под ОС Windows). Удаление участков памяти возможно не из того потока, который память создал. Следовательно, нужно хранить для каждого выделенного участка метку: номер кучи, из которой память была выделена.


SA>Прошу критически оценить предлагаемый способ хранения метки. В new с помощью HeapAlloc выделяется на 8 байт больше требуемого объема. В начале выделенного массива записывается номер кучи. Возвращается указатель ((char*)pPointer) + 8. В delete по адресу ((char*)pPointer) — 8 читается номер кучи и из нее удаляется память.


SA>8 байт (хотя достаточно 1) резервируется для того, чтобы не нарушалось выравнивание данных. Законен ли такой подход.


SA>Буду рад также други идеям хранения требуемых "меток".

А зачем тебе хранить "номер" кучи в памяти из этой кучи? Как ты собираешся обращаться к этой памяти без номера кучи?
Просто это похоже на задачу где единственный ключ (дескриптор кучи) от сейфа заперт в самом сейфе.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 17.09.06 20:02
Оценка:
Здравствуйте, Vain, Вы писали:

V>А зачем тебе хранить "номер" кучи в памяти из этой кучи? Как ты собираешся обращаться к этой памяти без номера кучи?

V>Просто это похоже на задачу где единственный ключ (дескриптор кучи) от сейфа заперт в самом сейфе.

Нет, ты немного не понял. Я выделяю память из кучи, соответствующей текущему потоку. То есть на момент, когда нужно выделить память (в перегруженном new), номер кучи я знаю (определяется по идентификатору потока). А когда память уже выделена, то у меня есть просто указатель, там никакой номер не нужен. Этот указатель я возвращаю из перегруженного оператора new, после чего он используется обычным образом. Проблема возникает, когда надо удалить память (перегруженный delete). Ведь удаление может происходить из другого потока. А в функцию HeapFree нужно передать описатель именно той кучи, из которой память выделена. Описатели у меня перенумерованы (массив в сегменте данных), поэтому мне в момент выделения надо запомнить индекс кучи в массиве, а при удалении передать описатель (полученный по сохраненному индексу) в HeapFree.

Вся проблема, как хранить этот идентификатор для каждого выделенного участка динамической памяти.
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[3]: Перегрузка new/delete, хранение "метки" для выделенно
От: Vain Россия google.ru
Дата: 17.09.06 20:15
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Нет, ты немного не понял. Я выделяю память из кучи, соответствующей текущему потоку. То есть на момент, когда нужно выделить память (в перегруженном new), номер кучи я знаю (определяется по идентификатору потока). А когда память уже выделена, то у меня есть просто указатель, там никакой номер не нужен. Этот указатель я возвращаю из перегруженного оператора new, после чего он используется обычным образом.

А как он у тебя используется?
К примеру, выделена куча1-память1, потом выделена куча2-память1 и сразу после надо обратиться к куча1-память1 — как ты это делаешь?
SA>Проблема возникает, когда надо удалить память (перегруженный delete). Ведь удаление может происходить из другого потока. А в функцию HeapFree нужно передать описатель именно той кучи, из которой память выделена.
Ну, ты пытаешься читать память из кучи идентификатора которого ты не знаешь, но при этом он храниться в массиве по индексу, который храниться в памяти, а чтобы обратиться к этой памяти нужен номер её кучи. Замкнутый круг выходит
SA>Описатели у меня перенумерованы (массив в сегменте данных), поэтому мне в момент выделения надо запомнить индекс кучи в массиве, а при удалении передать описатель (полученный по сохраненному индексу) в HeapFree.
Так где ты хранишь индекс, в памяти кучи или вместе с указателем как пару?

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

Получается что в памяти бессмысленно хранить, т.к. он тебе нужен для обращения к этой памяти
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 17.09.06 20:19
Оценка:
Здравствуйте, MaximE, Вы писали:

ME>Можно попробовать выделять непрерывные пулы для каждого потока, фиксированного,

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

ME>Еще можно посмотреть на http://www.cs.umass.edu/~emery/hoard/


Спасибо. Ссылка пригодится.

Что касается фиксированного пула, то спасибо за идею, но в моем случае это не получится. Программа требует очень много памяти, а потоков может быть до 256 (реально — до 32). Они могут приостанавливать свою работу, потом опять включаться. И фиксированные пулы здесь не сработают (слишком мало памяти на поток получится: 2 Гб / 32 = 65 Мб).
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[4]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 17.09.06 20:49
Оценка:
Здравствуйте, Vain, Вы писали:
SA>>Этот указатель я возвращаю из перегруженного оператора new, после чего он используется обычным образом.
V>А как он у тебя используется?
V>К примеру, выделена куча1-память1, потом выделена куча2-память1 и сразу после надо обратиться к куча1-память1 — как ты это делаешь?
V>Ну, ты пытаешься читать память из кучи идентификатора которого ты не знаешь, но при этом он храниться в массиве по индексу, который храниться в памяти, а чтобы обратиться к этой памяти нужен номер её кучи. Замкнутый круг выходит
Нет, там все проще. Вот когда ты используешь new:
    int *pA = new int;

ты же потом не будешь спрашивать индекс или описатель кучи, из которой память выделена. Вообще о существовании нескольких куч знают только перегруженные операторы new/delete. Пользоваться этой памятью можно совершенно обычно. Поэтому твой вопрос "обратиться к куча1-память1 — как ты это делаешь?" неуместен. Я просто беру указатель pA и использую. Для пользователя нет разницы в использовании.

Вся задача в выделении (new) и удалении (delete).

Я хочу, чтобы динамическая память для разных потоков выделялась из разных куч. Уточню, что под кучей я понимаю heap object в смысле Windows (см. функции HeapCreate, HeapAlloc, HeapFree, HeapDestroy для работы с кучами). То есть мы можем создать несколько куч. Я их создаю фиксированное число (на самом деле, они создаются по мере надобности, но для описания сойдет и так). Описатели загоняю в глобальный массив. Массив фиксированной длины. То есть есть биекция: <индекс кучи> <-> <описатель кучи>. Кроме того, есть функция, которая по идентификатору потока дает индекс его кучи.

Еще раз. 2 задачи перед нами: выделение и удаление.

Выделение (operator new) size байт.
idthread = Получить идентификатор потока().
idheap = Получить идентификатор соответствующей кучи(idthread).
pPointer = Выделить память из кучи idheap размером size + 8.
По адресу pPointer записать idheap.
Вернуть адрес ((char*)pPointer) + 8


Удаление (operator delete)
(Требуется удалить память pPointer)
//Получаем идентификатор кучи, из которой была выделена память
idheap = *((int*)(((char*)pPointer) - 8))
Удаляем из кучи idheap (описатель берем из глобального массива <индекс кучи> <-> <описатель кучи>) память ((char*)pPointer) - 8)

Объяснил как мог подробно .

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

V>Так где ты хранишь индекс, в памяти кучи или вместе с указателем как пару?

Индекс кучи хранится для каждого участка дин. памяти, созданного оператором new (перед памятью, возвращаемой пользователю — см. "Выделение").
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[3]: Перегрузка new/delete, хранение "метки" для выделенно
От: MaximE Великобритания  
Дата: 17.09.06 20:50
Оценка:
SeninAndrew wrote:

> Здравствуйте, MaximE, Вы писали:

>
> ME>Можно попробовать выделять непрерывные пулы для каждого потока,
> фиксированного,
> ME>заведомо большого объема. В этом случае достаточно самого адреса, чтобы
> ME>определить к пулу какого потока этот адрес относится.
>
> ME>Еще можно посмотреть на http://www.cs.umass.edu/~emery/hoard/
>
> Спасибо. Ссылка пригодится.
>
> Что касается фиксированного пула, то спасибо за идею, но в моем случае
> это не получится. Программа требует очень много памяти, а потоков может
> быть до 256 (реально — до 32). Они могут приостанавливать свою работу,
> потом опять включаться. И фиксированные пулы здесь не сработают (слишком
> мало памяти на поток получится: 2 Гб / 32 = 65 Мб).

Согласен, возможно этот способ был бы более пригоден для архитектур с более чем
32-битным адрессным пространством.

Если взять не самый старый opteron c 48-битным адрессным пространством:
$ cat /cpu/procinfo
model name      : Dual Core AMD Opteron(tm) Processor 275
...
address sizes   : 40 bits physical, 48 bits virtual


Получается 262144 Гб / 32 = 8192 Гб

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

--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re: Перегрузка new/delete, хранение "метки" для выделенного
От: Risk Server  
Дата: 17.09.06 23:25
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Перегрузил глобальные операторы new/delete для оптимизации многопоточного приложения на многопроцессорном компьютере. Суть оптимизации: выделение памяти каждым потоком из отдельной кучи (все под ОС Windows). Удаление участков памяти возможно не из того потока, который память создал. Следовательно, нужно хранить для каждого выделенного участка метку: номер кучи, из которой память была выделена.


SA>Прошу критически оценить предлагаемый способ хранения метки. В new с помощью HeapAlloc выделяется на 8 байт больше требуемого объема. В начале выделенного массива записывается номер кучи. Возвращается указатель ((char*)pPointer) + 8. В delete по адресу ((char*)pPointer) — 8 читается номер кучи и из нее удаляется память.


SA>8 байт (хотя достаточно 1) резервируется для того, чтобы не нарушалось выравнивание данных. Законен ли такой подход.


SA>Буду рад также други идеям хранения требуемых "меток".


А в чём вообще смысл подобной оптимизации? Поскольку удаление возможно из произвольного потока всё равно прийдётся синхронизироваь _все_ операции с кучей.
Re[5]: Перегрузка new/delete, хранение "метки" для выделенно
От: Vain Россия google.ru
Дата: 17.09.06 23:55
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Вся задача в выделении (new) и удалении (delete).

Давай разберёмся как идёт доступ к памяти из разных куч, потому что мне стало интересно "а как это работает?".
Есть куча, я помню что в куче нельзя выделить больше определённого размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с "адресным пространством", которое както там мапиться менеджером памяти на физические страницы. Если каждый указатель из этого адресного пространства — уникален, то получаем просто диапазон от 0 до 0x7FFFFFFF (короче эти 2GB). Теперь мы создаём две кучи и выделяем память по куску в каждой, указатели на каждый кусок будут также уникальными между собой или у них адреса всётаки могут случайно совпадать (ну если там долго выделяли память из каждой кучи и адресное пространство каждой из куч начало подходить к концу)?
Так вот если адреса указателей на куски памяти из разных куч совпадают, то как менеджер определит какой указатель из какой кучи? Или даже проще, если адресные пространства двух кусков пересекаются, то при обращении по адресу попадающему в оба куска, как менеджер разберёт куда мы обращаемся?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 06:06
Оценка:
Здравствуйте, Risk Server, Вы писали:

RS>А в чём вообще смысл подобной оптимизации? Поскольку удаление возможно из произвольного потока всё равно прийдётся синхронизироваь _все_ операции с кучей.


Не совсем так. Можно просто завести столько критических секций сколько у нас потоков. И синхронизация нужна только в том случае, когда поток А удаляет память из кучи потока В. А это случается существенно реже, чем удаление собственной памяти (из своей кучи). В случае же использования одной кучи синхронизация происходит при каждом new и при каждом delete. То есть полностью от блокировки мы не избавились, но существенно ее сократили.

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

Что касается синхронизации между 2 разными кучами, то она, конечно, тоже как-то должна обеспечиваться системой. Однако, по результатам тестов, накладные расходы на это (обеспечение корректной работы приложения и системы в целом при одновременном использовании 1 процессом 2 разных куч) очень малы (почти нет).
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[6]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 06:19
Оценка:
Здравствуйте, Vain, Вы писали:

V>Давай разберёмся как идёт доступ к памяти из разных куч, потому что мне стало интересно "а как это работает?


Давай.

V>Есть куча, я помню что в куче нельзя выделить больше определённого размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с "адресным пространством", которое както там мапиться менеджером памяти на физические страницы.


Это касается только 32-битного адресного пространства (ограничение 2Гб). И больше 2Гб нельзя выделить не в куче, а во всем процессе, если не использовать либо ключ /3GB, либо механизм Address Windowsing Extensions (AWE). То есть если из каждой, положим, 2х куч процесса мы навыделяли по 1Гб, то дальнейшие попытки взять память приведут к ошибке.

V> Если каждый указатель из этого адресного пространства — уникален, то получаем просто диапазон от 0 до 0x7FFFFFFF (короче эти 2GB).


Именно так. Без использования AWE иначе быть не может (я имею ввиду, что диапазоны, возвращаемые кучами, уникальны).

V>Теперь мы создаём две кучи и выделяем память по куску в каждой, указатели на каждый кусок будут также уникальными между собой или у них адреса всётаки могут случайно совпадать (ну если там долго выделяли память из каждой кучи и адресное пространство каждой из куч начало подходить к концу)?


Нет, диапазоны совпадать не могут.

V>Так вот если адреса указателей на куски памяти из разных куч совпадают, то как менеджер определит какой указатель из какой кучи? Или даже проще, если адресные пространства двух кусков пересекаются, то при обращении по адресу попадающему в оба куска, как менеджер разберёт куда мы обращаемся?


Нет, такого не может быть.
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[7]: Перегрузка new/delete, хранение "метки" для выделенно
От: Vain Россия google.ru
Дата: 18.09.06 07:26
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

V>>Есть куча, я помню что в куче нельзя выделить больше определённого размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с "адресным пространством", которое както там мапиться менеджером памяти на физические страницы.

SA>Это касается только 32-битного адресного пространства (ограничение 2Гб). И больше 2Гб нельзя выделить не в куче, а во всем процессе, если не использовать либо ключ /3GB, либо механизм Address Windowsing Extensions (AWE). То есть если из каждой, положим, 2х куч процесса мы навыделяли по 1Гб, то дальнейшие попытки взять память приведут к ошибке.
Да, думаю ты прав, я почему то считал что можно.
Буду презнателен, если ты мне укажешь правильную статью, где объясняется почему в принципе нельзя выделить больше 2-3GB.
V>> Если каждый указатель из этого адресного пространства — уникален, то получаем просто диапазон от 0 до 0x7FFFFFFF (короче эти 2GB).
SA>Именно так. Без использования AWE иначе быть не может (я имею ввиду, что диапазоны, возвращаемые кучами, уникальны).
------------------------
Address Windowing Extensions (AWE) enables applications to address more than 4 GB. AWE enables an application to reserve physical memory as nonpaged memory, then dynamically map portions of the nonpaged memory to its working set. This enables memory-intensive programs to reserve large amounts of physical memory for data without swapping to disk. Instead, the data is swapped between the working set and reserved memory above the 4 GB range. The memory above 4 GB is exposed to the memory manager and the AWE functions by PAE. Without PAE, AWE is unable to reserve memory in excess of 4 GB.
------------------------
AWE я так понял это фича для расширения виртуального адресного пространства, но работающая токо под PAE, которое как указывается работает токо c non-paged physical RAM. То есть это для выделения и адресации токо физической памяти.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[8]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 07:55
Оценка:
Здравствуйте, Vain, Вы писали:

V>Буду презнателен, если ты мне укажешь правильную статью, где объясняется почему в принципе нельзя выделить больше 2-3GB.


Это в Рихтере
Автор(ы): Джеффри Рихтер
Это издание — практически новая книга, посвещенная программированию серьезных приложений на Microsoft Visual C++ в операционных системах Windows 2000 (32- и 64-разрядных версиях) и Windows 98 с использованием функций Windows API. Состоит из 27 глав, двух приложений и предметного указателя. Гораздо глубже, чем в предыдущих изданиях рассматриваются такие темы, как взаимодействие с операционной системой библиотеки C/C++, программирование DLL и оптимизация кода, описываются новые механизмы и функции, появившиеся в Windows 2000, и приводится информация, специфическая для 64-разрядной Windows 2000. В этом издании автор, перейдя с языка C на C++, переработал все программы-примеры и представил ряд новых приложений, например ProcessInfo и LISWatch. Также появились совершенно новые материалы: выравнивание данных, привязка потоков к процессорам, кэш-линии процессоров, архитектура NUMA, перехват API-вызовов и др. Книга предназначена профессиональным программистам, владеющим языком C/C++ и имеющим опыт разработки Windows-приложений. Прилагаемый компакт-диск содержит все программы из книги (исходный код и исполняемые файлы для процессоров x86, IA-64 и Alpha).
хорошо описано. 13 глава ("Архитектура памяти в Windows").

V>------------------------

V>Address Windowing Extensions (AWE) enables applications to address more than 4 GB. AWE enables an application to reserve physical memory as nonpaged memory, then dynamically map portions of the nonpaged memory to its working set. This enables memory-intensive programs to reserve large amounts of physical memory for data without swapping to disk. Instead, the data is swapped between the working set and reserved memory above the 4 GB range. The memory above 4 GB is exposed to the memory manager and the AWE functions by PAE. Without PAE, AWE is unable to reserve memory in excess of 4 GB.
V>------------------------
V>AWE я так понял это фича для расширения виртуального адресного пространства, но работающая токо под PAE, которое как указывается работает токо c non-paged physical RAM. То есть это для выделения и адресации токо физической памяти.

С использованием мезанизма AWE на компьютере с поддержкой PAE (кажется, PAE появилось с Pentium Pro) можно использовать до 15 Гб памяти. Но при этом для использования AWE программу придется модифицировать (необходимо будет переключать адресное окно на разные блоки оперативной памяти). Сам я никогда этой штукой не пользовался, но в Рихтере написано, что, в принципе, это несложно.
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re: Перегрузка new/delete, хранение "метки" для выделенного
От: deadSLAYER  
Дата: 18.09.06 08:28
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Перегрузил глобальные операторы new/delete для оптимизации многопоточного приложения на многопроцессорном компьютере. Суть оптимизации: выделение памяти каждым потоком из отдельной кучи (все под ОС Windows). Удаление участков памяти возможно не из того потока, который память создал. Следовательно, нужно хранить для каждого выделенного участка метку: номер кучи, из которой память была выделена.


SA>Прошу критически оценить предлагаемый способ хранения метки. В new с помощью HeapAlloc выделяется на 8 байт больше требуемого объема. В начале выделенного массива записывается номер кучи. Возвращается указатель ((char*)pPointer) + 8. В delete по адресу ((char*)pPointer) — 8 читается номер кучи и из нее удаляется память.


SA>8 байт (хотя достаточно 1) резервируется для того, чтобы не нарушалось выравнивание данных. Законен ли такой подход.


SA>Буду рад также други идеям хранения требуемых "меток".


Может конечно так не получится, но проверять самоу влом
Все кучи делят одно адресное пространство, если предположить, что адресные пространстав разных куч не пересекаются,
а идут последовательно, можно просто запоминать диапазон значения указателей а-ля:
куча-раз — 0x1324-
куча-два — 0x4657-

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

Если сморозил чушь — ногами не бить



--
regards,
SLAYER
Re[8]: Перегрузка new/delete, хранение "метки" для выделенно
От: MaximE Великобритания  
Дата: 18.09.06 08:35
Оценка: 1 (1)
Vain wrote:

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

> размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с
> "адресным пространством", которое както там мапиться менеджером памяти
> на физические страницы.

Несколько не так.

Если ты хочешь использовать больше памяти, чем размер адрессного пр-ва процесса,
тебе придется переключать проекции. Так делалось на zx spectrum 128k с 16-битным
адрессным пространством, где чтобы доступится к памяти больше 64k, приходилось
переключать две страницы, отображенные на 0x4000-0x7fff и 0xc000-0xffff. Т.е.
размер виртуального адрессного пространства ограничивает лишь объем памяти, к
которому ты можешь доступиться одновременно.

> SA>Это касается только 32-битного адресного пространства (ограничение

> 2Гб). И больше 2Гб нельзя выделить не в куче, а во всем процессе, если
> не использовать либо ключ /3GB, либо механизм Address Windowsing
> Extensions (AWE). То есть если из каждой, положим, 2х куч процесса мы
> навыделяли по 1Гб, то дальнейшие попытки взять память приведут к ошибке.

Виртуальное 32-битное адрессное простанство ограничено 4гб. 2-3гб — это
ограничение операционной системы. Linux, к примеру, позволяет процессам
использовать полное 32-битное виртуальное ад. пр-во.
http://lkml.org/lkml/2003/7/8/246

> Да, думаю ты прав, я почему то считал что можно.

> Буду презнателен, если ты мне укажешь правильную статью, где объясняется
> почему в принципе нельзя выделить больше 2-3GB.

Выделить можно, но придется жонглировать отображаениями. Т.е. указатели на
объекты в этих отображениях, должны помимо адреса также идентифицировать
конкретную проекцию. Иными словами эмулировать более "широкое" адрессное
пространство.

> V>> Если каждый указатель из этого адресного пространства — уникален, то

> получаем просто диапазон от 0 до 0x7FFFFFFF (короче эти 2GB).
> SA>Именно так. Без использования AWE иначе быть не может (я имею ввиду,
> что диапазоны, возвращаемые кучами, уникальны).
> ------------------------
> Address Windowing Extensions (AWE) enables applications to address more
> than 4 GB. AWE enables an application to reserve physical memory as
> nonpaged memory, then dynamically map portions of the nonpaged memory to
> its working set. This enables memory-intensive programs to reserve large
> amounts of physical memory for data without swapping to disk. Instead,
> the data is swapped between the working set and reserved memory above
> the 4 GB range. The memory above 4 GB is exposed to the memory manager
> and the AWE functions by PAE. Without PAE, AWE is unable to reserve
> memory in excess of 4 GB.
> ------------------------
> AWE я так понял это фича для расширения виртуального адресного
> пространства, но работающая токо под PAE, которое как указывается
> работает токо c non-paged physical RAM. То есть это для выделения и
> адресации токо физической памяти.

Физическая память, отображенная в адрессное про-во процесса, становится обычной
виртуальной памятью. non-paged здесь лишь означает, что под эти страницы не
будет выделятся место в swap-файле, т.е. они никогда не будут выгружаться на
диск, что с точки зрения производительности очень неплохо.

--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re[2]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 08:59
Оценка:
Здравствуйте, deadSLAYER, Вы писали:

SLA>Все кучи делят одно адресное пространство, если предположить, что адресные пространстав разных куч не пересекаются,

SLA>а идут последовательно, можно просто запоминать диапазон значения указателей а-ля:
SLA>куча-раз — 0x1324-
SLA>куча-два — 0x4657-
SLA>Потом когда делиту приходит указатель можно попробовать по значению понять из какой он кучи.
SLA>вот.

Интересная идея, только как вот узнать эти диапазоны ...
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[9]: Перегрузка new/delete, хранение "метки" для выделенно
От: Vain Россия google.ru
Дата: 18.09.06 09:12
Оценка:
Здравствуйте, MaximE, Вы писали:

ME>Vain wrote:


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

>> размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с
>> "адресным пространством", которое както там мапиться менеджером памяти
>> на физические страницы.

ME>Несколько не так.


ME>Если ты хочешь использовать больше памяти, чем размер адрессного пр-ва процесса,

ME>тебе придется переключать проекции. Так делалось на zx spectrum 128k с 16-битным
ME>адрессным пространством, где чтобы доступится к памяти больше 64k, приходилось
ME>переключать две страницы, отображенные на 0x4000-0x7fff и 0xc000-0xffff. Т.е.
ME>размер виртуального адрессного пространства ограничивает лишь объем памяти, к
ME>которому ты можешь доступиться одновременно.
Всё равно не понял, а как ты будешь переключать страницы, через что? Пример какойнить приведи этого.

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

ME>объекты в этих отображениях, должны помимо адреса также идентифицировать
ME>конкретную проекцию. Иными словами эмулировать более "широкое" адрессное
ME>пространство.
А это возможно в рамках одного процесса?

ME>Физическая память, отображенная в адрессное про-во процесса, становится обычной

ME>виртуальной памятью. non-paged здесь лишь означает, что под эти страницы не
ME>будет выделятся место в swap-файле, т.е. они никогда не будут выгружаться на
ME>диск, что с точки зрения производительности очень неплохо.
Да просто с точки зрения обычной программы в общем случае это не очень хорошо, т.е. это хорошо для конкретного приложения к примеру для мат рассчётов.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[3]: Перегрузка new/delete, хранение "метки" для выделенно
От: deadSLAYER  
Дата: 18.09.06 09:46
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Здравствуйте, deadSLAYER, Вы писали:


SLA>>Все кучи делят одно адресное пространство, если предположить, что адресные пространстав разных куч не пересекаются,

SLA>>а идут последовательно, можно просто запоминать диапазон значения указателей а-ля:
SLA>>куча-раз — 0x1324-
SLA>>куча-два — 0x4657-
SLA>>Потом когда делиту приходит указатель можно попробовать по значению понять из какой он кучи.
SLA>>вот.

SA>Интересная идея, только как вот узнать эти диапазоны ...


После создания кучи выделить 8 байт памяти
После создания другой еще 8 байт,
проверить опытным путем все ли указатели получаемые из первой кучи лежат между этими тестовыми указателями,
если все — считай что решение готово — при создании кучи делает "тестовый" аллокейт,
и сохраняешь эти значения, потом смотришь бинарным поиском между какими двумя находится поинтер и получаешь номер кучи.
Re[10]: Перегрузка new/delete, хранение "метки" для выделенн
От: MaximE Великобритания  
Дата: 18.09.06 10:07
Оценка:
Vain wrote:

> ME>Vain wrote:

>
>> > V>>Есть куча, я помню что в куче нельзя выделить больше определённого
>> > размера, вроде 2GB, а так как она виртуальная, то мы имеем дело просто с
>> > "адресным пространством", которое както там мапиться менеджером памяти
>> > на физические страницы.
>
> ME>Несколько не так.
>
> ME>Если ты хочешь использовать больше памяти, чем размер адрессного
> пр-ва процесса,
> ME>тебе придется переключать проекции. Так делалось на zx spectrum 128k
> с 16-битным
> ME>адрессным пространством, где чтобы доступится к памяти больше 64k,
> приходилось
> ME>переключать две страницы, отображенные на 0x4000-0x7fff и
> 0xc000-0xffff. Т.е.
> ME>размер виртуального адрессного пространства ограничивает лишь объем
> памяти, к
> ME>которому ты можешь доступиться одновременно.

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

> Пример какойнить приведи этого.

Создай несколько проекций (CreateFileMapping/shm_open). Отображай их
(MapViewOfVileEx/mmap) поочередно на один и тот же виртуальный адрес. С PAE не
работал, но там похожие вызовы.

(на spectrum это делалось выводом байта в непомню какой порт)

> ME>Выделить можно, но придется жонглировать отображаениями. Т.е.

> указатели на
> ME>объекты в этих отображениях, должны помимо адреса также идентифицировать
> ME>конкретную проекцию. Иными словами эмулировать более "широкое" адрессное
> ME>пространство.

> А это возможно в рамках одного процесса?


Про один процесс и речь.

--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re[11]: Перегрузка new/delete, хранение "метки" для выделенн
От: Vain Россия google.ru
Дата: 18.09.06 12:23
Оценка:
Здравствуйте, MaximE, Вы писали:

ME>Создай несколько проекций (CreateFileMapping/shm_open). Отображай их

ME>(MapViewOfVileEx/mmap) поочередно на один и тот же виртуальный адрес. С PAE не
ME>работал, но там похожие вызовы.
А, так ты имеешь ввиду свой менеджер написать? Я так понял что этот кусок пямяти должен обязательно быть Locked в на физическую память иначе будет двойной свап (сначала винды, а потом через мой менеджер)?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[3]: Перегрузка new/delete, хранение "метки" для выделенно
От: Risk Server  
Дата: 18.09.06 15:09
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Здравствуйте, Risk Server, Вы писали:


RS>>А в чём вообще смысл подобной оптимизации? Поскольку удаление возможно из произвольного потока всё равно прийдётся синхронизироваь _все_ операции с кучей.


SA> И синхронизация нужна только в том случае, когда поток А удаляет память из кучи потока В. А это случается существенно реже, чем удаление собственной памяти (из своей кучи).


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

SA>Более того. Если быть совсем точным, то собственные секции можно и не заводить, так как на уровне каждой кучи синхронизация обеспечена системой.


Ну это опционально, как попросите. Мой поинт в том, что синхронизация нужна. Лучше конечно использовать ту, что система сама предоставляет.
Re[4]: Перегрузка new/delete, хранение "метки" для выделенно
От: Risk Server  
Дата: 18.09.06 15:11
Оценка:
Здравствуйте, deadSLAYER, Вы писали:

SLA>Здравствуйте, SeninAndrew, Вы писали:


SA>>Здравствуйте, deadSLAYER, Вы писали:


SLA>>>Все кучи делят одно адресное пространство, если предположить, что адресные пространстав разных куч не пересекаются,

SLA>>>а идут последовательно, можно просто запоминать диапазон значения указателей а-ля:
SLA>>>куча-раз — 0x1324-
SLA>>>куча-два — 0x4657-
SLA>>>Потом когда делиту приходит указатель можно попробовать по значению понять из какой он кучи.
SLA>>>вот.

SA>>Интересная идея, только как вот узнать эти диапазоны ...


SLA>После создания кучи выделить 8 байт памяти

SLA>После создания другой еще 8 байт,
SLA>проверить опытным путем все ли указатели получаемые из первой кучи лежат между этими тестовыми указателями,
SLA>если все — считай что решение готово — при создании кучи делает "тестовый" аллокейт,
SLA>и сохраняешь эти значения, потом смотришь бинарным поиском между какими двумя находится поинтер и получаешь номер кучи.

почти уверен что куча виндоуз не гарантирует непрерывного диапазона адресов для всех блоков памяти, выделенных из кучи. Пока размер кучи мал — это будет работать, но со временем куча начнёт расти за счёт выделения новых регионов памяти и данные метод работать перестанет.
Re[4]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 15:48
Оценка:
Здравствуйте, Risk Server, Вы писали:

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

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

Ну да. Я согласен, что вход в критическую секцию (при их использовании) будет происходить при каждой операции. И действительно, знать, какому потоку какая куча принадлежит на момент удаления не обязательно (при выделении памяти это знать нужно, чтобы определить, откуда память взять). Поэтому, я в Вашем всказывании не вижу никаких противоречий моим утверждениям...
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[12]: Перегрузка new/delete, хранение "метки" для выделенн
От: MaximE Великобритания  
Дата: 18.09.06 17:15
Оценка:
Vain wrote:

> ME>Создай несколько проекций (CreateFileMapping/shm_open). Отображай их

> ME>(MapViewOfVileEx/mmap) поочередно на один и тот же виртуальный адрес.
> С PAE не
> ME>работал, но там похожие вызовы.
> А, так ты имеешь ввиду свой менеджер написать?

Не совсем понимаю, что ты имееешь ввиду под менеджер. Речь шла об аллокаторе для
многопоточного приложения, или я что-то упускаю?

> Я так понял что этот

> кусок пямяти должен обязательно быть Locked в на физическую память иначе
> будет двойной свап (сначала винды, а потом через мой менеджер)?

Память, которую аллокатор распределяет для приложению, аллокатор получает от ОС
стандартными средствами (sbrk/mmap/CreateFileMapping/whatever-your-os-provides).

--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re[13]: Перегрузка new/delete, хранение "метки" для выделенн
От: SeninAndrew Россия  
Дата: 18.09.06 17:59
Оценка:
Здравствуйте, MaximE, Вы писали:

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

ME>многопоточного приложения, или я что-то упускаю?

Ну менеджер и аллокатор — синонимы в данном контексе (поправьте кто-нибудь, если я неправ).
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[5]: Перегрузка new/delete, хранение "метки" для выделенно
От: Risk Server  
Дата: 18.09.06 19:00
Оценка:
Здравствуйте, SeninAndrew, Вы писали:

SA>Здравствуйте, Risk Server, Вы писали:


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


Вы же сами писали, что при выделении и так понятно из какой кучи бать (по идентификатору потока кучу найти можно). Зачем тогда в самом блоке памяти хранить метку какой куче он принадлежит? При удалении эта метка не нужна. При выделении, ясное дело, тоже
Re[6]: Перегрузка new/delete, хранение "метки" для выделенно
От: SeninAndrew Россия  
Дата: 18.09.06 19:55
Оценка:
Здравствуйте, Risk Server, Вы писали:

SA>>знать, какому потоку какая куча принадлежит на момент удаления не обязательно (при выделении памяти это знать нужно, чтобы определить, откуда память взять).

RS>Вы же сами писали, что при выделении и так понятно из какой кучи бать (по идентификатору потока кучу найти можно). Зачем тогда в самом блоке памяти хранить метку какой куче он принадлежит? При удалении эта метка не нужна. При выделении, ясное дело, тоже

Нет, Вы неправильно поняли мое прошлое сообщение. Я имел ввиду, что при удалении необязательно по индексу кучи, который хранится перед выделенной памятью, восстанавливать идентификатор потока, который память выделил. Однако сам индекс кучи необходим, потому что в функцию HeapFree необходимо передать описатель кучи, из которой память была выделена.

Если мы не знаем индекс кучи (а значит и описатель), то нам нечего передать первым параметром в HeapFree:
BOOL HeapFree(
  HANDLE hHeap,  // handle to the heap
  DWORD dwFlags, // heap freeing flags
  LPVOID lpMem   // pointer to the memory to free
);
... << RSDN@Home 1.2.0 alpha rev. 651>>
Re[7]: Перегрузка new/delete, хранение "метки" для выделенно
От: Risk Server  
Дата: 18.09.06 22:51
Оценка: :)
Здравствуйте, SeninAndrew, Вы писали:

SA>Здравствуйте, Risk Server, Вы писали:



SA>Если мы не знаем индекс кучи (а значит и описатель), то нам нечего передать первым параметром в HeapFree:


Да я уже и сам понял, что ерунду написал. Забыл что нэндл кучи нужен для удаления. А ведь HeapFree мог бы и сам догадаться...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.