информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медГде водятся OGRыПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Хм. Интересно а в чем логика? Я то уж было ломанулся... 28.03.09 05:53  Число просмотров: 2000
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> UPD: Забыл сказать - доступ к элементу пула должет быть
> именно по индексу, а не по адресу обекта пула. Поэтому
> одного SLIST (когда бы Index_in_pool включал бы указатель
> на ptr = new Pool_entry_t() вместо индекса) без
> Pool_entry_t m_pool[pool_size] недостаточно. Это часть
> бизнес логики.

Хм. Интересно а в чем логика? Я то уж было ломанулся исправлять явно лишнее индексирование :-)

А вообще только что пришла идея: для каждого процессора выделить свой лист свободных индексов. Если выделение произошло на одном процессоре, а возврат на другом - это ожидаемо и нормально. Если пул у какого нибудь процессора закончится, то тогда уж и делать stop-the-world и балансировать пулы, предполагается, что если выделения/освобождения распределены более менее равномерно, то листы свободных индексов для каждого процессора будут примерно равными по длине.

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

Ну и после всех этих манипуляций придется проверять дают ли они хоть какой то выигрыш :-)
<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
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach