[MSVC x64] Assembly routine linken met YASM

[Verwijderd]

Ik heb een programma onder x64 gecompileerd waar het bekende '1% van de code, 99% van de tijd' paradigma op invloed is. Als ik zo de assembly bekijk zijn er een aantal verbeteringen mogelijk (in het bijzonder, in de loop gebruikt msvc een aantal vmovaps welke totaal onnodig zijn, alles past in de registers).

Ik gebruik msvc11 (2012) x64. Deze ondersteunt geen inline assembly. Volgens deze http://www.sciencezero.or...nctions_in_Visual_C%2B%2B tutorial kan je met yasm een functie in asm definiëren welke je vervolgens kan aanroepen met een C call. Een probleem is dat deze tutorial (en elke andere die ik kan vinden) er van uit gaat dat je Microsoft IDE's gebruikt.


C++ code:

C++:

extern "C" {
        int calc (int a, int b, int c, char d, char* e, float fa, float fb);
}

int main()
{

    char q = 'q';
    calc( 1, 2, 3, 'a', &q, 1.0, -1.0 );

    return 0;
}

Assembly:

code:

PROC_FRAME      calc
    db          0x48            ; emit a REX prefix to enable hot-patching

    push        rbp             ; save prospective frame pointer
    [pushreg    rbp]            ; create unwind data for this rbp register push
    sub         rsp,0x40        ; allocate stack space
    [allocstack 0x40]           ; create unwind data for this stack allocation
    lea         rbp,[rsp+0x20]  ; assign the frame pointer with a bias of 32
    [setframe   rbp,0x20]       ; create unwind data for a frame register in rbp
    movdqa      [rbp],xmm7      ; save a non-volatile XMM register
    [savexmm128 xmm7, 0x20]     ; create unwind data for an XMM register save
    mov         [rbp+0x18],rsi  ; save rsi
    [savereg    rsi,0x38]       ; create unwind data for a save of rsi
    mov         [rsp+0x10],rdi  ; save rdi
    [savereg    rdi, 0x10]      ; create unwind data for a save of rdi
    [endprolog]


movdqa      xmm7,[rbp]      ; restore the registers that weren't saved
mov         rsi,[rbp+0x18]  ; with a push; this is not part of the
mov         rdi,[rbp-0x10]  ; official epilog

lea         rsp,[rbp-0x20]  ; This is the official epilog
pop         rbp
ret

ENDPROC_FRAME

.. wat gewoon een ctrl-c ctrl-v stuk code is.


Met YASM heb ik deze assembly gecompilered met deze command line:

code:

-Xvc -f x64 %{sourceDir}/calc.asm -o calc.obj

Probleem: mijn compilers willen deze .obj file niet linken. MVSC geeft:

code:

main.obj:-1: error: LNK2019: unresolved external symbol calc referenced in function main

MinGW (4.4 en 4.8.1 x64) geeft:

code:

C:\blaah blah\calc.obj:-1: error: file not recognized: File format not recognized

Het vreemde is dat wanneer ik MSVC compileer met de /VERBOSE switch, calc.obj niet voorkomt in de lijst met assembly's die hij doorzoekt. Het lijkt erop dat msvc mijn .obj negeert. Als ik de .obj dubbel in de command line gooi geeft hij wel netjes een warning dat het object meer dan eens is gespecificeerd.

Wie weet de oplossing?

[PrisonerOfPain]

Moet je `calc` niet ook GLOBAL maken? Wat zeggen objdump of dumpbin over de gexporteerde symbols?

[Verwijderd]

Wat bedoel je met 'global maken'?


dumpbin /SYMBOLS geeft dit als output:

code:

Dump of file calc.obj

File Type: COFF OBJECT

COFF SYMBOL TABLE
000 00000000 DEBUG  notype       Filename     | .file

002 00000000 SECT1  notype       Static       | .text
    Section length   2C, #relocs    0, #linenums    0, checksum        0
004 00000000 SECT1  notype       Static       | calc
005 00000000 SECT2  notype       Static       | .xdata
    Section length   18, #relocs    0, #linenums    0, checksum        0
007 00000000 SECT3  notype       Static       | .pdata
    Section length    C, #relocs    3, #linenums    0, checksum        0

String Table Size = 0x3C bytes

  Summary

           C .pdata
          2C .text
          18 .xdata

Op regel 10 zie je mijn geëxporteerde symbol calc.

[PrisonerOfPain]

Dat er een "GLOBAL calc" mist op de regel na je PROC_FRAME calc. Zo te zien word er geen namemangling toegepast op je symbol terwijl dat wel door de compiler verwacht word.

[Verwijderd]

als ik er

code:

PROC_FRAME  calc
global calc

van maakt werkt hij.

Dat vind ik vreemd. Er zit ook geen enkel verschil tussen de dumpbin output met en zonder die label.

Hij geeft wel een access violation bij het draaien van mijn code. Maar de debugger laat zien dat hij wel in mijn method komt. Dat zal wel aan mijn code liggen.

---

Edit: ik ben overgestapt naar MASM met intel syntax. Om 3 redenen:
Ik krijg het niet voor elkaar een float constante te loaden...
De GAS syntax is lelijk.
De intel syntax sluit veel beter aan bij Z80 assembly, welke ik tot in de puntjes beheers.

De code van deze tutorial compileert direct: http://software.intel.com...roduction-to-x64-assembly

[ Voor 36% gewijzigd door Verwijderd op 30-08-2013 22:45 ]

[Verwijderd]

Ik heb inmiddels een werkende implementatie. Ik ben nog wat vreemde dingen tegengekomen qua performance:

Ik heb een dubbele loop waarin telkens een x, y en mass wordt opgehaald ( 3 floats ). De volgende memory layout

C++:

float x[4096]
float y[4096]
float mass[4096]

is significant ( als in, 15%, iets minder met prefetch instructies) sneller dan:

C++:

struct Data {
  float x[8];
  float y[8];
  float mass[8];
};

Data data[512];

Ik gebruik AVX instructies, vandaar de packing van 8 floats. Het enige verschil in de code is het
[RCX + 4000] vs [RCX + 4 * 8]. Kort door de bocht levert het eerste voorbeeld reads op van 3 verschillende arrays, terwijl het 2e code snipper zuiver sequentiële access oplevert.

Dit is in totaal 48k cache, mijn CPU heeft er 32k per core. Wanneer ik het dataset verklein zodat alles in cache past zijn de rollen omgekeerd (met 15% performanceverschil).

Blijkbaar zorgt het gebruik van losse arrays ervoor dat de data beter in cache blijft staan.. ofzo. Ik kan me voorstellen dat hij met één grote array sneller geneigd is om data uit de cache te knikkeren.


Mijn huidige loopje is vanwege de prefetch instructies enkele procenten sneller dan de compiler intrinsic implementatie. Zoals ik had vermeld spillt de compiler wat registers als ik de loop een paar keer dupliceer. Daar moet ik nog aan beginnen. In elk geval heb ik nu een goede basis om mee te beginnen.

[Soultaker]

Komt dit niet gewoon doordat 3 arrays niet allemaal in een 2-way associative cache passen?

[Verwijderd]

Maar dat probleem heb je ook met één lange array. Het is immers dezelfde hoeveelheid data. Het enige verschil is het access patroon. (sequentieel met 1 read pointer, of sequentieel met 3 read pointers).

[Soultaker]

Ik bedoel: als je dezelfde index gebruikt in drie verschillende arrays die toevallig allemaal op een veelvoud van de cache size gealigned zijn (en dat zijn ze met 4096 bytes waarschijnlijk wel) dan worden drie verschillende adressen op dezelfde cache set gemapt; als die cache maar 2 entries per set support (dat is wel gebruikelijk, toch?) dan verdringen die elkaar natuurlijk steeds.

[Zoijar]

http://valgrind.org/docs/manual/cg-manual.html

[Verwijderd]

Soultaker schreef op zondag 01 september 2013 @ 15:10:
Ik bedoel: als je dezelfde index gebruikt in drie verschillende arrays die toevallig allemaal op een veelvoud van de cache size gealigned zijn (en dat zijn ze met 4096 bytes waarschijnlijk wel) dan worden drie verschillende adressen op dezelfde cache set gemapt; als die cache maar 2 entries per set support (dat is wel gebruikelijk, toch?) dan verdringen die elkaar natuurlijk steeds.

De arrays zijn 16k bytes, 4096 floats.

Maar: je hebt wel gelijk. Ik ben er nu achter waarom mijn assembly tragere code opleverde dan de C++ variant ondanks dat de main loop exact hetzelfde was. Bij de assembly versie zaten de 3 arrays direct achter elkaar, terwijl ik bij de C++ versie een padding van 96 bytes had toegevoegd.

Een snelle test wijst uit dan een padding van 100 bytes nog (meetbaar) sneller is dan 96 bytes padding. Hamvraag: hoeveel bytes Padding moet ik gebruiken?

Zoijar schreef op zondag 01 september 2013 @ 15:33:
http://valgrind.org/docs/manual/cg-manual.html

Ik zit al een hele tijd te twijfelen of ik voor development nu wil overstappen naar linux of niet, ondanks dat ik geen window management naar mijn smaak kan vinden. Het voornaamste argument daarvoor is dat valgrind zo verschrikkelijk veel beter is dan de Windows tools.

Ik zal even kijken of ik ergens een vm of linux bak vandaan kan toveren.

[Soultaker]

Waarom stop je niet gewoon 3 floats in een struct, en maak je een array van structs, als dat het probleem oplost?

[ Voor 18% gewijzigd door Soultaker op 01-09-2013 17:03 ]

[Verwijderd]

Ik gebruik AVX (SSE) instructies. Dat houd in dat je met één instructie 8 floats tegelijk bewerkt (add/sub/mul/sqrt/rcpt/whatever). Daarvoor dienen er 8 floats achter elkaar in het memory te staan. Dat kan je op 2 manieren doen: door 3 losse arrays te maken van 4096 lang, of door een hele lang array te maken van structs bestaande uit 3 * 8 floats.

Maar met losse arrays is het dus iets sneller als de data niets volledig in cache past.

Ik heb even een linux install ergens vandaan getoverd. Nu moet ik mijn assembly (masm syntax) nog werkend krijgen..

[Zoijar]

Verwijderd schreef op zondag 01 september 2013 @ 15:52:
Ik zit al een hele tijd te twijfelen of ik voor development nu wil overstappen naar linux of niet, ondanks dat ik geen window management naar mijn smaak kan vinden. Het voornaamste argument daarvoor is dat valgrind zo verschrikkelijk veel beter is dan de Windows tools.

Ik zal even kijken of ik ergens een vm of linux bak vandaan kan toveren.

MinGW-w64 met qtcreator Alleen is het wel een gedoe om alle tools/libs altijd te laten compilen in die omgeving.

[Verwijderd]

Met jwasm heb ik mijn assembly werkend gekregen in linux. For future reference:

code:

-10 -zcw -mf -elf64 %{sourceDir}/avx.asm

Ik moest wel de calling convention aanpassen voor linux.

Verder werd ik op het verkeerde been gezet door cachegrind te gebruiken. Dat faalt, g++ geeft de debug info niet door (of jwasm bouwt geen debug info, whatever). Met callgrind --dump-instr=yes --cache-sim=yes wordt het gewenste resultaat bereikt. Je kan daardoor gewoon de assembly bekijken.

Ik wordt op zich wijzer van de resultaten. Volgens de cycle estimation van callgrind wordt ongeveer de helft van de tijd besteed aan data L1 cache misses. Terwijl ik dacht dat de instructions de voorname bottleneck waren. Valgrind is natuurlijk niet perfect, maar het geeft wel perspectief. Een mooie tool. Zonde dat iets met deze gebruiksvriendelijkheid niet op windows beschikbaar is. Intel vtune geeft meer informatie, maar er is een halve studie nodig om de output te interprenteren en is niet gratis.

Valgrind mist nog wel wat dingetjes. Zo kan mijn architectuur een add en een multiply per clock uitvoeren, maar in valgrind is dat gewoon allebei 1 instruction retired. De latency van een add en divide zijn ook gelijk volgens valgrind. Bestaan er misschien tools die daar wel onderscheid in maken?

Vooralsnog valt het best tegen welke snelheidswinst er te boeken is met assembly, zelfs wanneer de compiler bewezen brak om gaat met registers. De impact van vreemd ge alignde arrays of het reorderen van 2 instructies maakt vaak meer verschil dan een register spill.

Edit: Ik denk dat ik het mysterie van de afwijkende offsets ontrafeld heb.. De compiler zorgt niet voor een goede alignment. Als de alignment één byte afwijkt heb ik direct lagere performance. De beste alignment is 64 bytes (dat is de cache line size).

Alignment aan de cacheline size (64) is iets sneller dan alignment aan een 16-byte boundry. Alles daarbuiten performt bagger. (10% trager direct). Ik zal deze avond nog even een automatische test laten draaien. Ik denk niet dat het iets te maken heeft met het 4096 bytes waar soultaker het over had.

[ Voor 15% gewijzigd door Verwijderd op 02-09-2013 02:38 ]

[MLM]

16 byte alignment heeft voor SSE ook andere voordelen, gezien je dan "aligned load" vector-instructies kan gebruiken (MOVAPS) die sneller zijn.

Een generieke load (MOVUPS) moet checken of je adres aligned is, en zo ja, doet dan MOVAPS, anders moet ie 2 cache lines laden, en dan met shifts combineren (dat is dus duidelijk langzamer, en ook het effect wat bij jou die 10% oplevert).

Als ik zo even kijk in de "Intel 64 and IA-32 Software Developer's Manual" (die kan je gratis downloaden als PDF van Intel, best handig als referentie materiaal), geld hetzelfde voor AVX.

VMOVAPS ymm1, ymm2/m256 -> Move aligned packed single-precision floating-point values from ymm2/mem to ymm1.
VMOVUPS ymm1, ymm2/m256 -> Move unaligned packed single-precision floating-point from ymm2/mem to ymm1.

Als jij dus in je programma kan garanderen dat je arrays aligned zijn (in MSVC kan je bijvoorbeeld kijken onder __declspec(align(16)) op je global arrays), dan kan je aligned loads/stores gebruiken.

Alignment heeft verder niets te doen met padding, behalve dan dat sommige compilers alignment regelen door padding te reserveren en dan de aligned pointer to berekenen (semi-code):

code:

ALIGNED_16 float x[64]; //64 floats, reserveerd 64 * 4 + 15 bytes op de stack
float *aligned = x; //doet eigenlijk: (float *)(((size_t)x + 15) & ~15);

Datzelfde kan jij ook doen als je geen aligned heap allocator hebt (of wilt gebruiken) om aligned geheugen te krijgen. (Voor AVX wil je 32 byte alignment hebben, trouwens, niet 16)

Hogere alignment dan 16 (voor SSE) of 32 (voor AVX) is vrij zinloos, tenzij je datasets klein genoeg zijn om daadwerkelijk een extra cacheline load te kunnen merken aan het begin/eind van de array.

Technisch zou ik verwachten dat je struct met 3x float[8] het beste zou performen uitgaande van 1 iteratie over de dataset omdat je access-patroon meer predictable is.

[ Voor 12% gewijzigd door MLM op 02-09-2013 12:28 ]

[Verwijderd]

Maar ik gebruik geen aligned load. Ik gebruik wel

code:

vsubps  ymm4,   ymm0,   [RCX + XBASE + 4 * 8 * 0]

een paar keer. Ik de instruction reference staat niets over alignment bij deze instructies. Meer het ligt voor de hand dat misaligns trager zijn.

---

Ik heb deze avond wat getest met alignment. Daar is dit uitgekomen:


Test is in de vorm van:

C++:

float langeAray[10000] // 64 byte aligned
float *x = langeArray;
float *y = langeArray + 4096 + offset1
float *mass = langeArray + 4096 * 2 + offset2

Ik weet niet of dit een meetfout is of niet, maar het lijkt zo te zijn dat de boel sneller wordt naarmate de offset2 groter wordt (zolang hij 16-byte aligned is). Bij de test heb ik de CPU snelheid gefixeerd. Het varieren van offset1 laat niet zo'n dalende lijn zien.

Moraal van het verhaal: altijd je alignment controleren.

[PrisonerOfPain]

Op welke CPU ben je dit aan het testen trouwens? De i7-2820QM uit je signature?

[Verwijderd]

Yup.

---

Oke, dat was dus een massive waste of time. Ik heb de loop binnenstebuiten gekeerd zodat hij 4096/16 maal over de data loopt in plaats van 4096 keer. Dat is iets sneller: 9.6 flops*/clock. Het maximum is 16 flops/clock, maar dat is alleen haalbaar als je een add en een multiply per clock kan uitvoeren. Vanwege een lange dependancy chain is dat met mijn code niet echt mogelijk.

*6 add's : 6 mul's : 1 rsqrt : 1 rcpt verhouding. Add is 3 clocks, mul is 5, rsqrt en rcpt 7 op mijn architectuur.

Nu heb ik ook geen register spills, dus kan de compiler netjes zijn gang gaan met lelijke instruction reordering. Dat is echt niet te doen in assembly als je de code onderhoudbaar wilt houden.

[ Voor 98% gewijzigd door Verwijderd op 02-09-2013 16:46 ]

[MSalters]

Houd er rekening mee dat multi-channel geheugenarchitecturen beter kunnen presteren als je parallele data access hebt. Het is goed mogelijk dat de sequentiele access van

C++:

2
3
4
5
6
7
struct Data { 
  float x[8]; 
  float y[8]; 
  float mass[8]; 
}; 

Data data[512];

betekent dat alle geheugenaccess via 1 channel moet.

[Verwijderd]

Dat wist ik nog niet. Zijn er ergens goede resources voor dat soort dingen? Behalve het overbekende maar ietswat gedateerde http://cs.smith.edu/~thiebaut/ArtOfAssembly/artofasm.html?

[PrisonerOfPain]

De Intel 64 and IA-32 Software Developer's Manual die MLM quote is aardig goed.

[PrisonerOfPain]

Verwijderd schreef op maandag 02 september 2013 @ 14:12:
*6 add's : 6 mul's : 1 rsqrt : 1 rcpt verhouding. Add is 3 clocks, mul is 5, rsqrt en rcpt 7 op mijn architectuur.

Ben je nog memory bound? Als je dat niet meer bent kun je je instructies handmatig pipelinen.

Je hebt een aantal dingen waar je rekening mee moet houden. Je execution port, de latency en de thoughput van je instructies (en de snelheid van je L1). Cijfers hier.

VADDPS heeft een latency van 3 cycles voor je het resultaat krijgt en een thoughput van 1 instructie per cycle om uit te voeren. In die 3 cycles kun je wel nuttig werk doen maar niet met het resultaat van de instructie - daar moet je 3 cy op wachten.

Het pipelinen houd in dat je meerdere iteraties van je loop gaat samenvoegen om zo de latency van de instructies te hiden. Op een SPU is dit redelijk eenvoudig om te doen omdat je zowel veel SIMD registers hebt als wel snelle L1 access. Jaymin legt hier uit hoe je dat voor een SPU doet. En hier in video format. Jou L1 is 4 cycles en je hebt een stuk minder SIMD registers maar het een en ander zou mogelijk moeten zijn.

Verder heeft de Sandy-Bridge van jou heeft 6 execution ports, 3 daavan zijn execution units (eg. doen werk) namelijk p0, p1 en p5 en 2 daarvan doen address calculations en/of reads (p2 & p3) en p4 is voor writes.

De VADDPS gebruikt bijvoorbeeld alleen execution units p1 en p23 (first come first serve), VMULPS gebruikt echter p0 en p23. Als ik het goed heb betekend dat dat je een VADDPS en een VMULPS tegelijk uit zou kunnen voeren omdat de ene p0 en de andere p1 gebruikt.

Je loads zou je eventueel ook nog async kunnen doen door een paar cachelines ahead te lezen (of prefetchen) nadeel daarvan is alleen dat je dan best een paar honder cycles vooruit zou moeten kijken.

[ Voor 8% gewijzigd door PrisonerOfPain op 02-09-2013 19:00 ]

[Verwijderd]

PrisonerOfPain schreef op maandag 02 september 2013 @ 18:47:
Ben je nog memory bound? Als je dat niet meer bent kun je je instructies handmatig pipelinen.

Dat doe ik al. Bij mijn assembly variant doe ik 4 operaties per 'inner loop'. Dat kan door de betere register allocaties dan msvc. Die gaat bij 3 al spillen. Terwijl het gewoon past.

Je hebt een aantal dingen waar je rekening mee moet houden. Je execution port, de latency en de thoughput van je instructies (en de snelheid van je L1). Cijfers hier.

Die heb ik al een paar dagen voor mij. Dat geld ook voor de intel 64 & IA32 manual. Ik heb echter nog niet nauwkeurig naar de gebruikte ports gekeken. Ik staar me voornamelijk blind op de instruction latency.


Mijn code ziet er nu zo uit:

C++:

    __declspec( align(32) ) float xArr[ BODY_COUNT];
    __declspec( align(32) ) float yArr[ BODY_COUNT];
    __declspec( align(32) ) float massArr[ BODY_COUNT];

    for( int i = 0; i < BODY_COUNT; i++ )
    {
        xArr[i] = _bodys[i].pos.x;
        yArr[i] = _bodys[i].pos.y;
        massArr[i] = _bodys[i].mass * GRAVITY;
    }


#define UNROLL 2

    delta = -delta;
    for( int outer = 0; outer < BODY_COUNT; outer += 8 * UNROLL )
    {
        __m256 innerX_1 = _mm256_load_ps( xArr + outer );
        __m256 innerY_1 = _mm256_load_ps( yArr + outer );

        __m256 innerX_2 = _mm256_load_ps( xArr + outer + 8);
        __m256 innerY_2 = _mm256_load_ps( yArr + outer + 8 );


        __m256 totalDX_1 = _mm256_setzero_ps();
        __m256 totalDY_1 = _mm256_setzero_ps();

        __m256 totalDX_2 = _mm256_setzero_ps();
        __m256 totalDY_2 = _mm256_setzero_ps();


        const float fBias[8] = {0.0001f, 0.0001f, 0.0001f, 0.0001f, 0.0001f, 0.0001f, 0.0001f, 0.0001f };
        const __m256 bias = _mm256_load_ps( fBias );
        const __m256 deltaSSE = _mm256_broadcast_ss( &delta );

        __m256 newX = _mm256_broadcast_ss( &xArr[0] );
        __m256 newY = _mm256_broadcast_ss( &yArr[0] );
        __m256 mass = _mm256_broadcast_ss( &massArr[0] );


        for( int inner = 0; inner < BODY_COUNT; inner++ )
        {

// calculate X/Y offset between body
            __m256 diffX_1 = _mm256_sub_ps( innerX_1, newX );
            __m256 diffY_1 = _mm256_sub_ps( innerY_1, newY );

            __m256 diffX_2 = _mm256_sub_ps( innerX_2, newX );
            __m256 diffY_2 = _mm256_sub_ps( innerY_2, newY );

// calculate Xoffset * Xoffset and Yoffset * Yoffset
            __m256 mulX_1 = _mm256_mul_ps( diffX_1, diffX_1 );
            __m256 mulY_1 = _mm256_mul_ps( diffY_1, diffY_1 );

            __m256 mulX_2 = _mm256_mul_ps( diffX_2, diffX_2 );
            __m256 mulY_2 = _mm256_mul_ps( diffY_2, diffY_2 );
            newX = _mm256_broadcast_ss( &xArr[inner + 1] );

            mulX_1 = _mm256_add_ps( mulX_1, bias );
            mulX_2 = _mm256_add_ps( mulX_2, bias );

            __m256 len_1 = _mm256_add_ps( mulX_1, mulY_1 );
            __m256 len_2 = _mm256_add_ps( mulX_2, mulY_2 );
            newY = _mm256_broadcast_ss( &yArr[inner + 1] );

// mass /  | v1- v2 |^3 --> mass * rsqrt( | v1 - v2 | ) * rcp( | v1 - v2 | )
// divides are slow ( 21- 29 cycles ), multiply and rsqrt are fast.
            __m256 lenRsqrt_1 = _mm256_rsqrt_ps( len_1 );
            __m256 lenRsqrt_2 = _mm256_rsqrt_ps( len_2 );

            __m256 lenRcp_1 = _mm256_rcp_ps( len_1 );
            __m256 lenRcp_2 = _mm256_rcp_ps( len_2 );


            len_1 = _mm256_mul_ps( lenRsqrt_1, mass );
            len_2 = _mm256_mul_ps( lenRsqrt_2, mass );
            mass = _mm256_broadcast_ss( &massArr[inner + 1] );

            len_1 = _mm256_mul_ps( len_1, lenRcp_1 );
            len_2 = _mm256_mul_ps( len_2, lenRcp_2 );


            diffX_1 = _mm256_mul_ps( len_1, diffX_1 );
            diffY_1 = _mm256_mul_ps( len_1, diffY_1 );

            diffX_2 = _mm256_mul_ps( len_2, diffX_2 );
            diffY_2 = _mm256_mul_ps( len_2, diffY_2 );

// update totalDX & DY
            totalDX_1 = _mm256_add_ps( diffX_1, totalDX_1 );
            totalDY_1 = _mm256_add_ps( diffY_1, totalDY_1 );

            totalDX_2 = _mm256_add_ps( diffX_2, totalDX_2 );
            totalDY_2 = _mm256_add_ps( diffY_2, totalDY_2 );

        }

        totalDX_1 = _mm256_mul_ps( totalDX_1, deltaSSE );
        totalDY_1 = _mm256_mul_ps( totalDY_1, deltaSSE );

        totalDX_2 = _mm256_mul_ps( totalDX_2, deltaSSE );
        totalDY_2 = _mm256_mul_ps( totalDY_2, deltaSSE );


        __declspec( align(32) ) float xfloats[8 * UNROLL];
        __declspec( align(32) ) float yfloats[8 * UNROLL];

        _mm256_store_ps( xfloats, totalDX_1 );
        _mm256_store_ps( yfloats, totalDY_1 );

        _mm256_store_ps( xfloats+8, totalDX_2 );
        _mm256_store_ps( yfloats+8, totalDY_2 );


        for( int i = 0; i < 8 * UNROLL; i++ )
        {
            _bodys[ outer + i ].delta.x += xfloats[i];
            _bodys[ outer + i ].delta.y += yfloats[i];
        }
    }

Lines of intrest zijn de eerste 10, waar de data in een 'optimale' structuur wordt gegoten en die variabelen met _1 of _2 erachter, die zijn handmatig gepipelined zeg maar. Verder op lijn 51-53 (en meer) zie je dat ik nieuwe data uit memory ophaal nadat ik de data heb gebruikt Dat beperkt de invloed van memory stalls hopelijk tot een minimum.

Vaker pipelinen heeft denk ik geen zijn. Daar zijn met deze (letterlijke) code niet genoeg registers voor als ik de compiler het werk laat doen. Je hebt er 2 nodig om de deltaX en deltaY in op te slaan voor elke keer dat je handmatig pipelined. Daarnaast heb je er het liefst ook nog 2 nodig om de X en Y positie in op te slaan. Verder heb je er 4 nodig om berekeningen te doen (of 3 als je het acceptabel vind om een register vrij te maken ten koste van een extra vsubps). En nog eentje voor bias. Echter spilt msvc 4 (!) registers, terwijl je volgens mij maar 1 spill nodig hebt...

Dat zijn er 7 of 8 per handmatige pipeline van de loop. Vaker pipelinen kan wel als ik dit doe:

C++:

for( outer; ; outer++ )
{
  for( inner; ; inner += 8 of 16 of 32 )
  {
    body;
  }
}

in plaats van omgekeerd. Dan kan ik 4 maal pipelinen zonder erge spills, maar lijk ik erg memory bound. ( 85-88 fps in plaats van 102-103 ). Wellicht omdat er 64/128/256 maal zo vaak over de inner loop geloopt wordt.

Dat gedoe met intrinsics is trouwens totaal onleesbaar. Ik moet eens mijn eigen vector klasse bouwen.
Edit: dat is onnodig: Agner heeft zijn vector library ge-open-sourced: http://www.agner.org/optimize/. Very nice.

[PrisonerOfPain]

Als ik er zo even naar kijk zou je tussen de _mm256_rcp_ps en de _mm256_mul_ps nog wat prefetches kunnen doen omdat je daar nog een gap van 3 cycles hebt van je rsqrt.

Verder zou je die stores kunnen vervangen waarschijnlijk met een combinatie van _mm256_maskstore_ps, en een horizontale sum (of een dot product met vec(1, 1, 1, 1) of zo). xfloats & yfloats zijn nergens voor nodig en zorgen volgens mij alleen maar voor een LHS.

Ook zit ik te denken of je de _mm256_broadcast_ss (voor newX etc) in je innerloop niet beter kunt vervangen door een load upfront die 8 elementen laad en ze vervolgens handmatig broadcast (splat) iedere iteratie.

Het lijkt er op dat je deltaSSE niet update tijdens je loop, dus die load zou je misschien er uit kunnen hoisten.

Voorlopig zou ik het bij intrinsics laten - dan weet je iig dat de compiler zo min mogelijk roet in het eten gooit.

Oh en die eerste 10 regels zijn natuurlijk helemaal niet nodig als je het uberhaupt al goed opslaat natuurlijk.

[ Voor 13% gewijzigd door PrisonerOfPain op 03-09-2013 11:22 ]

[Verwijderd]

PrisonerOfPain schreef op dinsdag 03 september 2013 @ 11:13:
Als ik er zo even naar kijk zou je tussen de _mm256_rcp_ps en de _mm256_mul_ps nog wat prefetches kunnen doen omdat je daar nog een gap van 3 cycles hebt van je rsqrt.

Goed punt, volgens de register timing pdf van agner kan je een multiply en fetch zelfs tegelijk uitvoeren.

Verder zou je die stores kunnen vervangen waarschijnlijk met een combinatie van _mm256_maskstore_ps, en een horizontale sum (of een dot product met vec(1, 1, 1, 1) of zo). xfloats & yfloats zijn nergens voor nodig en zorgen volgens mij alleen maar voor een LHS.

Dat was ook maar een vrij snel in elkaar gezet stuk code.

Ook zit ik te denken of je de _mm256_broadcast_ss (voor newX etc) in je innerloop niet beter kunt vervangen door een load upfront die 8 elementhttp://tweakimg.net/g/forum/images/icons/toolbar/quote_onderbreker.gifen laad en ze vervolgens handmatig broadcast (splat) iedere iteratie.

Ik snap deze niet. Een load upfront, waarin? Alle registers zitten vol.

Het lijkt er op dat je deltaSSE niet update tijdens je loop, dus die load zou je misschien er uit kunnen hoisten.

Dat klopt. De compiler doet dat al grotendeels voor mij.

Voorlopig zou ik het bij intrinsics laten - dan weet je iig dat de compiler zo min mogelijk roet in het eten gooit.

Ik heb een simpele library gemaakt welke basis operators (- + * rcp) 1:1 naar intrinsics vertaalt. Dat levert dezelfde assembly op. Zolang ik het simpel hou denk ik niet dat de compiler suboptimale code genereert.

Oh en die eerste 10 regels zijn natuurlijk helemaal niet nodig als je het uberhaupt al goed opslaat natuurlijk.

Dat is waar. Dat is een beetje een trade-off tussen leesbaarheid in niet-SSE aspecten van de code, en een klein beetje performance. Met de copy actie die O( n ) duurt en het algoritme zelf O( n² ) kan ik me daar niet heel druk om maken.


Ik ben momenteel een tooltje aan het maken waarmee ik de register pippeling kan visualiseren en meten. Met een beetje geluk kan ik ook nog wat extra pipelinen (bijvoorbeeld update van totalX/Y naar het begin van de loop verplaatsen).

[Verwijderd]

Ik heb nog wat zitten klooien met eventueel pipelinen van de code. Dat wil nog niet echt lukken.

Ik heb wel wat nieuwe dingen geleerd. Neem deze assembly:

code:

loop:
        vsubps  xDiff, xPos, xOrigin
        vbroadcastss    xPos,   [R13]
        vsubps  yDiff, yPos, yOrigin
        vbroadcastss    yPos,   [R13+4*4096]

        vmulps  x2, xDiff, xDiff
        add     R13,    4
        vmulps  y2, yDiff, yDiff

        vaddps  x2, x2, ymm15 ; bias

        vaddps  len, x2, y2

        vrsqrtps len2, len
        vrcpps  len, len

        vmulps len2, len2, mass
        vbroadcastss mass, [R13+4*4096*2]
        vmulps  len, len, len2

        vmulps  len2, xDiff, len    ; len2= x
        vmulps  len, yDiff, len   ; len = y

        vaddps  xTotal, xTotal, len
        vaddps  yTotal, yTotal, len2

        sub R15,    1
        jnz loop

Wat een simpele variant is van een deel van het N-body algoritme.
Je ziet hier: wat adds, wat mul's, wat rsqrt's, samen goed voor een latency boven de 30 clocks. Met optimale pippeling (en oneindig registers) zou de loop in 10 clock cycles kunnen. Wanneer deze loop as-is op mijn CPU word gedraaid halt hij 11.5 clock cycles per loop.

Dat is iets wat ik voorheen had onderschat. De CPU, tenminste die van mij, doet een uitstekende taak om instructies te reorderen. Op simpele hardware ( GPU's, PS3, low-end CPU's ) zal dat niet het geval zijn. Voorheen staarde ik mij lichtelijk blind op de instruction latency, maar dat is niet altijd terecht.

Het beste wat ik tot nu toe uit de compiler heb kunnen slaan is 11.10 clocks per loop. Mijn snelste assembly variant (met net iets ander algoritme) is ongeveer 11.05 clocks per loop. Hierbij is het memory geen bottleneck (lees: als ik de pointer update verwijder blijven de scores hetzelfde). De brakheid van de compiler valt dus best mee in mijn situaties, de winst zit hem er meer in dat je als programmeur het algoritme kan tweaken veranderen zodat er minder registers worden gebruikt, maar het hetzelfde resultaat oplevert.

[farlane]

Dus het verhaal over handcrafted asm versus compiler klopt (in jouw geval) ?

[Verwijderd]

Ik zie dat ik een typfout heb gemaakt in mijn vorige post. Mijn hand-crafted assembly doet geen 10.05, maar 11.05 clocks per loop.

Verder heb ik die vraag inderdaad nog niet beantwoord. Als ik mijn snelste assember variant in C++ implementeer genereert de compiler erg slechte code met veel ( 5! ) register spills. Deze klokt in op 11.53 clock cycles per loop. Behoorlijk traag dus. Als ik het snelste algoritme wat de compiler kan genereren pak (11.10 vs 11.05) scheelt het minder dan een procent.

Dus ja, hand-crafted assembly is in mijn geval sneller, maar het scheelt maar weinig, en in zakelijke omgeving was de aanschaf van een sneller systeem een zinvollere investering geweest.