Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
В принципе достаточно много задач, где нужно клиенту... 28.03.09 06:25 Число просмотров: 2149
Автор: void <Grebnev Valery> Статус: Elderman Отредактировано 28.03.09 06:26 Количество правок: 1
|
> Хм. Интересно а в чем логика? Я то уж было ломанулся > исправлять явно лишнее индексирование :-)
В принципе достаточно много задач, где нужно клиенту отдавать индекс, а не адрес. В той задаче, для которой это сейчас делается - для храния имеетсятолько WORD. Получив новый объект из пула, клиент будет проводить типа CAS над этим индексом, чтобы удостовериться, что использует один и тот же shared буфер, который уже захвачен другим клиентом. Типа как общий объект, буфер, и т.д для нескольких клиентов. Другого рода задачи всплывают в IPC на shared memory, когда сервер отдаёт клиенту "номер" shared канала. Можно конечно, получив ::InterlockedPopEntrySList адрес затем мапить или хеш мапить его на индекс, но это может быть не бесплатно. Хотя конечно надо тестировать.
> А вообще только что пришла идея: для каждого процессора > выделить свой лист свободных индексов.
Идея хорошая и не только для данной задачи. Надо об этом подумать ;-)
> Кроме того, нужно > придумать способ лочить очередь без захвата шины (уже в > однопроцессорном окружении), но на мой взгляд это довольно > легко.
А как? ... Саттер не так давно написал нескольно статей по этому поводу. Но я признаться не смотрел.
|
<programming>
|
[C++] UPD: супер простой и супербыстрый pool 28.03.09 03:30
Автор: void <Grebnev Valery> Статус: Elderman Отредактировано 28.03.09 05:02 Количество правок: 1
|
UPD: Забыл сказать - доступ к элементу пула должет быть именно по индексу, а не по адресу обекта пула. Поэтому одного SLIST (когда бы Index_in_pool включал бы указатель на ptr = new Pool_entry_t() вместо индекса) без Pool_entry_t m_pool[pool_size] недостаточно. Это часть бизнес логики.
Ищется таковой. Чтобы было просто, и самое главное работало быстро (без высокого контеншн) для 5-10 thread-ов на multi-core box. Самое тривиальное, что приходит на ум - ниже. Сейчас очень модно lock-free решения. Может кто подскажет альтернативу тому, что ниже?
template <typename Pool_entry_t, size_t pool_size>
class Pool_t
{
public:
Pool_t()
{
::InitializeSListHead(&m_pool_index_head);
for(size_t i = 0; i < pool_size; i++)
{
Index_in_pool* pindex = new Index_in_pool(i);
::InterlockedPushEntrySList(&m_pool_index_head, pindex);
}
}
~Pool_t()
{
::InterlockedFlushSList(&m_pool_index_head);
}
typedef SLIST_HEADER DECLSPEC_ALIGN(MEMORY_ALLOCATION_ALIGNMENT) SLIST_HEADER_;
struct DECLSPEC_ALIGN(MEMORY_ALLOCATION_ALIGNMENT) Index_in_pool: SLIST_ENTRY
{
size_t m_index;
Index_in_pool(size_t index): m_index(index){}
void* operator new(size_t)
{
void*p = ::_aligned_malloc(sizeof(Index_in_pool),MEMORY_ALLOCATION_ALIGNMENT);
if (p == NULL)
{
::RaiseException( STATUS_NONCONTINUABLE_EXCEPTION, 0, 0, 0);
}
else
{
}
return p;
}
void operator delete (void *p)
{
::_aligned_free(p);
}
};
Index_in_pool* alloc_entry(void)
{
return (Index_in_pool*) ::InterlockedPopEntrySList(&m_pool_index_head);
}
void release_entry(Index_in_pool* pentry)
{
::InterlockedPushEntrySList(&m_pool_index_head, pentry);
}
Pool_entry_t* get_entry(size_t index)
{
return m_pool + index;
}
Pool_entry_t m_pool[pool_size];
SLIST_HEADER_ m_pool_index_head;
};
---
Использовать приблизительно так:
Pool_t<test_buffer, 5> g_buffer_pool;
bool simulate_pool_work(void)
{
Pool_t<test_buffer, 5>::Index_in_pool* pentry = g_buffer_pool.alloc_entry();
test_buffer* ptr_buffer = g_buffer_pool.get_entry(pentry->m_index);
for (int i = 0; i < 1; i++)
{
ptr_buffer->write();
if (!ptr_buffer->read())
{
return false;
}
else
{
}
}
g_buffer_pool.release_entry(pentry);
return true;
}
---
|
|
Хм. Интересно а в чем логика? Я то уж было ломанулся... 28.03.09 05:53
Автор: amirul <Serge> Статус: The Elderman
|
> UPD: Забыл сказать - доступ к элементу пула должет быть > именно по индексу, а не по адресу обекта пула. Поэтому > одного SLIST (когда бы Index_in_pool включал бы указатель > на ptr = new Pool_entry_t() вместо индекса) без > Pool_entry_t m_pool[pool_size] недостаточно. Это часть > бизнес логики.
Хм. Интересно а в чем логика? Я то уж было ломанулся исправлять явно лишнее индексирование :-)
А вообще только что пришла идея: для каждого процессора выделить свой лист свободных индексов. Если выделение произошло на одном процессоре, а возврат на другом - это ожидаемо и нормально. Если пул у какого нибудь процессора закончится, то тогда уж и делать stop-the-world и балансировать пулы, предполагается, что если выделения/освобождения распределены более менее равномерно, то листы свободных индексов для каждого процессора будут примерно равными по длине.
Осталось найти недорогой способ получения номера текущего процессора, но думаю это непривилегированная операция и может быть выполнена без ухода в ядро. Кроме того, нужно придумать способ лочить очередь без захвата шины (уже в однопроцессорном окружении), но на мой взгляд это довольно легко.
Ну и после всех этих манипуляций придется проверять дают ли они хоть какой то выигрыш :-)
|
| |
В принципе достаточно много задач, где нужно клиенту... 28.03.09 06:25
Автор: void <Grebnev Valery> Статус: Elderman Отредактировано 28.03.09 06:26 Количество правок: 1
|
> Хм. Интересно а в чем логика? Я то уж было ломанулся > исправлять явно лишнее индексирование :-)
В принципе достаточно много задач, где нужно клиенту отдавать индекс, а не адрес. В той задаче, для которой это сейчас делается - для храния имеетсятолько WORD. Получив новый объект из пула, клиент будет проводить типа CAS над этим индексом, чтобы удостовериться, что использует один и тот же shared буфер, который уже захвачен другим клиентом. Типа как общий объект, буфер, и т.д для нескольких клиентов. Другого рода задачи всплывают в IPC на shared memory, когда сервер отдаёт клиенту "номер" shared канала. Можно конечно, получив ::InterlockedPopEntrySList адрес затем мапить или хеш мапить его на индекс, но это может быть не бесплатно. Хотя конечно надо тестировать.
> А вообще только что пришла идея: для каждого процессора > выделить свой лист свободных индексов.
Идея хорошая и не только для данной задачи. Надо об этом подумать ;-)
> Кроме того, нужно > придумать способ лочить очередь без захвата шины (уже в > однопроцессорном окружении), но на мой взгляд это довольно > легко.
А как? ... Саттер не так давно написал нескольно статей по этому поводу. Но я признаться не смотрел.
|
| | |
Саттера не читал, но мнение имею [upd] 28.03.09 08:48
Автор: amirul <Serge> Статус: The Elderman Отредактировано 28.03.09 09:14 Количество правок: 1
|
> > Кроме того, нужно > > придумать способ лочить очередь без захвата шины (уже > в > > однопроцессорном окружении), но на мой взгляд это > довольно > > легко. > > А как? ... Саттер не так давно написал нескольно статей по > этому поводу. Но я признаться не смотрел.
Саттера не читал, но мнение имею
Вообще интуиция подсказывает, что обычный CMPXCHG (без префикса LOCK) - должен отлично сработать. Я могу ошибаться, но насколько я понимаю поток может быть вытеснен только между инструкциями, а не прямо посреди (если прерывание приходит посреди инструкции, то процессор дожидается окончания этой инструкции) - а для однопроцессорной среды этого достаточно для обеспечения атомарности. Соответственно, когда флаг, блокирующий очередь для процессора (одна очередь - один флаг) не получается "захватить" - отдаем квант чем то вроде sleep(0) или подобным и делаем спин. Огромная стоимость такой операции для ожидающего потока будет нивелироваться крайне низкой вероятностью рейса на участке из десятка инструкций (pop из односвязного списка и освобождение очереди).
-------------------
Кстати, о текущем процессоре. В Win2k3 появилась полезная функция GetCurrentProcessorNumber. Вот так выглядит версия из Win7 (в других скорее всего что то подобное):
ntdll!RtlGetCurrentProcessorNumberEx:
7787cab6 8bff mov edi,edi
7787cab8 55 push ebp
7787cab9 8bec mov ebp,esp
7787cabb 8b5508 mov edx,dword ptr [ebp+8]
7787cabe 33c0 xor eax,eax
7787cac0 668902 mov word ptr [edx],ax
7787cac3 b93b000000 mov ecx,3Bh
7787cac8 0f03c1 lsl eax,ecx
7787cacb c1e80e shr eax,0Eh
7787cace 884202 mov byte ptr [edx+2],al
7787cad1 c6420300 mov byte ptr [edx+3],0
7787cad5 5d pop ebp
7787cad6 c20400 ret 4
---
Передается туда указатель на структуру:
typedef struct _PROCESSOR_NUMBER {
WORD Group;
BYTE Number;
BYTE Reserved;
} PROCESSOR_NUMBER, *PPROCESSOR_NUMBER; ---
Так что болдом выделено конкретно получение номера процессора. Висты сейчас под рукой нет - проверить не могу, но как я уже сказал вряд ли она уходит в ядро, так что можно смело использовать эту функцию - оверхед на IPI и коллизии по идее должен быть больше. Так что можно сделать более продуктивную версию для 2k3+ с откатом к бейскейс реализации на interlocked-очереди для 2k/xp
|
|
|