highly professional scums

Сперва чтиво http://lwn.net/Articles/250967/

Продолжая начатую тему замечу, что на PC latency тоже можно и нужно бороть. Prefetch есть, и он тоже реально работает. Правильная (линейная) организация данных работает ещё лучше, потому что процессор умеет предсказывать и префетчить сам. В статье, впрочем, всё гораздо подробнее.

Предложеный пример всё как-то иллюстрирует. Замечу, что в реальности эффект будет значительно большим потому, что L2 будет сбрасываться между итерациями. На внятных платформах ещё и рисовать можно прямо из того-же буфера. Накодить тоже можно значительно аккуратнее, развернуть циклы итп; мой lame excuse это банальный цейтнот.

Измеряем, как всегда, попугаев. В первый раз тупо, двусвязный список. Добавили-удалили. Во второй раз – всё тоже самое, только с префетчем. В третий – циклический буфер.

Циклический буфер вообщем-то реализует идею о том, что почти весь партикл изменяется. Т-е если писать линейно, то всё равно куда писать – latency спрячется. Аналогично latency спрячется если линейно читать. На PPU (и эквиваленте) prefetch понадобится и на циклическом буфере.

Результаты

naive 11905 msec
naive with prefetch 10918 msec
ring 10107 msec

[code lang="cpp"]

const int TotalFrames = 1024*64;
const int TotalNumParticles = 16384;
const int TotalNumParticlesMask = TotalNumParticles - 1;

//////////////////////////////////////////////////////////////////////////

__forceinline float frand ( void )
{
return float(double(rand())/double(RAND_MAX));
}

__m128 frandv ( void )
{
return _mm_set_ps ( frand(), frand(), frand(), frand() );
}

//////////////////////////////////////////////////////////////////////////

template
__forceinline void Attach ( TT * & pHead, TT * pPointer )
{
TT * pLink = pPointer;
if ( pHead )
pHead->prev = pLink;
pLink->next = pHead;
pLink->prev = NULL;
pHead = pLink;
}

template
__forceinline void Detach ( TT * & pHead, TT * pPointer )
{
TT * pLink = pPointer;
if ( pLink->prev )
pLink->prev->next = pLink->next;
else
pHead = pLink->next;
if ( pLink->next )
pLink->next->prev = pLink->prev;
pLink->prev = NULL;
pLink->next = NULL;
}

//////////////////////////////////////////////////////////////////////////

struct NaiveParticle
{
__m128 position;
__m128 velocity;
__m128 color;
NaiveParticle * next, * prev;
int lifetime;
int foobar;
};

NaiveParticle particles[TotalNumParticles];

//////////////////////////////////////////////////////////////////////////

template
class NaivePool
{
public:
NaivePool ( void )
{
work = NULL;
empty = particles;
for ( int i=0; i {
particles[i].next = particles + i + 1;
particles[i].prev = particles + i - 1;
}
particles[0].prev = NULL;
particles[TotalNumParticles-1].next = NULL;
}

void Seed ( int numParticles, int lifetime )
{
while ( numParticles && empty )
{
numParticles --;
NaiveParticle * pp = empty;
Detach ( empty, pp );
Attach ( work, pp );
pp->position = frandv();
pp->velocity = frandv();
pp->color = frandv();
pp->lifetime = (rand() % lifetime) + 1;
nParticles ++;
}
}

void Update ( __m128 acceleration, __m128 colorVelocity )
{
NaiveParticle * pp = work;
while ( pp )
{
NaiveParticle * np = pp->next;
if ( isPrefetch )
_mm_prefetch ( (const char *) np, _MM_HINT_T0 );

pp->position = _mm_add_ps ( pp->position, pp->velocity );
pp->velocity = _mm_add_ps ( pp->velocity, acceleration );
pp->color = _mm_add_ps ( pp->color, colorVelocity );
pp->lifetime --;
if ( pp->lifetime==0 )
{
Detach ( work, pp );
Attach ( empty, pp );
nParticles --;
}
pp = np;
}
}

public:
int nParticles;

protected:
NaiveParticle * work;
NaiveParticle * empty;
};

//////////////////////////////////////////////////////////////////////////

class RingPool
{

public:
RingPool ( void )
{
i0 = i1 = 0;
nParticles = 0;
}

void Seed ( int numParticles, int lifetime )
{
while ( numParticles && nParticles<(TotalNumParticles-1) )
{
numParticles --;
NaiveParticle * pp = particles + i1;
i1 = (i1 + 1) & TotalNumParticlesMask;
pp->position = frandv();
pp->velocity = frandv();
pp->color = frandv();
pp->lifetime = (rand() % lifetime) + 1;
nParticles ++;
}
}

void Update ( __m128 acceleration, __m128 colorVelocity )
{
for ( int nUpdate = nParticles; nUpdate; nUpdate-- )
{
NaiveParticle * pfr = particles + i0;
NaiveParticle * pto = particles + i1;
i0 = (i0 + 1) & TotalNumParticlesMask;
int lifetime = pfr->lifetime - 1;
if ( lifetime )
{
pto->position = _mm_add_ps ( pfr->position, pfr->velocity );
pto->velocity = _mm_add_ps ( pfr->velocity, acceleration );
pto->color = _mm_add_ps ( pfr->color, colorVelocity );
pto->lifetime = lifetime;
i1 = (i1 + 1) & TotalNumParticlesMask;
}
else
nParticles --;
}
}

public:
int nParticles;
int i0, i1;
};

//////////////////////////////////////////////////////////////////////////

static char blah_buffer[65536];

template
void Measure ( const char * name )
{
POOL testPool;

clock_t nt0 = clock();

for ( int f=0; f {
testPool.Seed(32,1024);
testPool.Update(frandv(),frandv());
}

clock_t nt1 = clock();

printf ( "%s %i msec\n", name, int(nt1-nt0) );
}

int main(int argc, char* argv[])
{
Measure< NaivePool >("naive");
Measure< NaivePool
>("naive with prefetch");
Measure< RingPool >("ring");

return 0;
}

[/code]