Ещё раз про latency
Сперва чтиво 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
-
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 <typename TT>
-
__forceinline void Attach ( TT * & pHead, TT * pPointer )
-
{
-
TT * pLink = pPointer;
-
if ( pHead )
-
pHead->prev = pLink;
-
pLink->next = pHead;
-
pLink->prev = NULL;
-
pHead = pLink;
-
}
-
-
-
template <typename TT>
-
__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 <bool isPrefetch>
-
class NaivePool
-
{
-
public:
-
NaivePool ( void )
-
{
-
work = NULL;
-
empty = particles;
-
for ( int i=0; i<TotalNumParticles; 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 <class POOL>
-
void Measure ( const char * name )
-
{
-
POOL testPool;
-
-
clock_t nt0 = clock();
-
-
for ( int f=0; f<TotalFrames; 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<false> >("naive");
-
Measure< NaivePool<true> >("naive with prefetch");
-
Measure< RingPool >("ring");
-
-
return 0;
-
}
lordmaze:
Ya vot dobavlu chto na bokse naprimer tozhe mozhno PRAVILNO usat prefetch. Te naprimer usat __xdcbt na vseh intermidiate results chtobi oni ne popadali nikogda v L2( kogda konechno usautsya vmx ). Nu a final results kotorie idut v GPU taki nado samomu flush iz L1. obichno __dcbi dostatochno… - uskorenie mozhno poluchit protsentov na 20…
nu potom uzhe mozhno nachat kreativit s __restrict :)
10 October 2007, 3:54 amlook4awhile:
на боксе и на PS3 PPU префетч можно расставлять с удивительными результатами.
надо префетчить, только, не на 1-2 линейки вперёд - а на пару килобайт вперёд.
кусками килобайта по два.
у меня банальный ADLER32 такими методами ускорился в 6.5 раз!!!
10 October 2007, 7:25 amlordmaze:
> надо префетчить, только, не на 1-2 линейки вперёд - а на пару килобайт вперёд.
> кусками килобайта по два.
ты какой то умный слишком. я просто делал - для всех intermidiate результатов - dcbt, для всех результатов которые идут на gpu - dcbi. И заебись - на тех же партиклах ускорение раз в пять.
А еще когда дураком был и shadow volumes любил - считал скиннинг на цпу. Там вообще заебись - vmx + L1 force cache + force flush - и супербыстро. И даже наверно без stalls.
Но если честно я не очень во все это верю :) - потому что “правильно” смоделеный домик может нафик убить любые твои джедайские оптимизации. Ну и да - к сожалению на бабло это никак не влияет. А бабло - оно рулт :)
10 October 2007, 9:29 amfinnan:
Класс, спасибо)
А что случилось с operator– в листинге?
13 November 2007, 4:08 pm