Infinity World (Дневники разработчицы)

do
{
   do
   {
      // читаем из TLS текущего потока
      idx = Volatile.Read(ref TLS[threadIndex]);
   }while (idx == -3);
   if(idx < 0)
     // в TLS нашего потока больше нет ничего
}while (Interlocked.CompareExchange(ref TLS[threadIndex], -3, idx) != idx);
// записали следующий свободный в наш TLS
Interlocked.Exchange(ref TLS[threadIndex], nextPtrs[idx]);

Interlocked.Exchange(ref poolData->FirstFreeTLS[threadIndex], -2); // помечаем, что мы будем еще выделять

if (allocatedCount < capacity)
{
   idx = Interlocked.Add(ref allocatedCount, 16) - 16; // пытаемся отдать все 16 индексов
   if (idx < capacity - 1)
   {
       var count = math.min(16, capacity - idx);
       for (var i = 1; i < count; ++i)
       {
           // сразу их записываем в список свободных
           nextPtrs[idx + i] = idx + i + 1;
       }
       nextPtrs[idx + count - 1] = -1;
       nextPtrs[idx] = -1; // текущий мы отдаем, поэтому он не свободен
       // и в TLS тоже записываем следующий свободный
       Interlocked.Exchange(ref TLS[threadIndex], idx + 1);
       return idx;
   }

   if (idx == capacity - 1)
   {
       // это был последний доступный в пуле, значит помечаем как "больше элементов нет"
       Interlocked.Exchange(ref TLS[threadIndex], -1);
       return idx;
   }
}
// ничего не нашли, следующих свободных нет
Interlocked.Exchange(ref TLS[threadIndex], -1);

for(var threadIndex = 0; threadIndex != currentIndex; threadIndex < threadCount; threadIndex++)
{
   do
   {
      do
      {
         idx = Volatile.Read(ref TLS[threadIndex]);
      }while(idx == -3);
      
      if(idx < 0)
         break;
   }while (Interlocked.CompareExchange(ref TLS[threadIndex], -3, idx) != idx);
}

step = (верхняя граница диапазона - нижняя + 1) / 16

SLI = (size - base) / step

slBitmap[fli] |=  (1u << sli);   // ставим бит для SLI
flBitmap      |=  (1u << fli);
...
slBitmap[fli] &= ~(1u << sli);   // сбрасываем бит для SLI
if (slBitmap[fli] == 0)
    flBitmap &= ~(1u << fli);    // если весь FLI пуст, сбросить и его бит

uint mask = slBitmap[5] & (~0u << 7);

uint maskFL = flBitmap & (~0u << (5+1)); // находим другой свободный FLI
if (maskFL != 0) {
    int newFli = BitOperations.TrailingZeroCount(maskFL);
    int newSli = BitOperations.TrailingZeroCount(slBitmap[newFli]);
    ...
}

byte* memory = memalloc(1024*1024); // выделяем сразу большой кусок
byte* current = memory; // сохраняем указатель
...
byte* block = current;
current = current + blockSize; // сдвигаем указатель для следующей аллокации
return block;

byte* memory = memalloc(1024*1024); // выделяем сразу большой кусок
int* freeList; // список свободных элементов
int freeCount = 0;
int allocatedCount = 0;
...
if(freeCount > 0)
{
   int idx = freeList[--freeCount];
   return memory + idx * blockSize; // выдаем из пула
}
if(allocatedCount < capacity)
   return memory + (allocatedCount++) * blockSize; // выдаем следующий не аллоцированный

return null; // блоков больше нет

int idx = (ptr - memory) / blockSize; // вычисляем индекс блока по адресу памяти
freeList[freeCount++] = idx; // записываем индекс как свободный