Machinecode binnen een c++ programma genereren

[Aaargh!]

Ik heb een programma waarin een user een expressie kan invoeren die dan door het programma gebruikt word bij een bepaalde berekening.
In de expressie zitten een of meerdere variabelen (max 26, a t/m z) de expressie blijft hetzelfde alleen de inhoud van de variabelen wijzigt.

Nu het probleem: deze expressies moeten zo snel mogelijk verwerkt worden. mijn code zoals ik die nu heb doet er bijvoorbeeld ongeveer 18 seconden over om de expressie "(3+b)*8" 40,800,000 keer door te rekenen. dit is veel te langzaam en moet minimaal 20 keer sneller.

Nu zat ik me af te vragen of het mogelijk is om runtime in een C++ programma machinecode te genereren die je vervolgens is datzelfde programma aanroept. met uiteraard de mogelijkheid de inhoud van de variabelen in die code te wijzigen.

iemand enig idee hoe dat aan te pakken ?

[Arzie]

Je kunt inline assembler gebruiken, maar daarmee genereer je geen code in realtime. Maar als alleen de waarden van de variabelen veranderen hoeft dat ook niet. Als je voorbeeldexpressie degene is die je werkelijk gebruikt zou je bijvoorbeeld de *8 kunnen vervangen door 3 keer een bitwise shiftleft. Dat kan ook al door je compiler gedaan worden, maar zeker weten doe je het niet.

[Aaargh!]

Arzie schreef op 06 februari 2003 @ 04:44:
Je kunt inline assembler gebruiken, maar daarmee genereer je geen code in realtime. Maar als alleen de waarden van de variabelen veranderen hoeft dat ook niet. Als je voorbeeldexpressie degene is die je werkelijk gebruikt zou je bijvoorbeeld de *8 kunnen vervangen door 3 keer een bitwise shiftleft. Dat kan ook al door je compiler gedaan worden, maar zeker weten doe je het niet.

De expressie staat niet vast, het is alleen zo dat een expressie relatief lang gebruikt word dus het omzetten van de expressie naar een formaat dat beter bruikbaar is mag relatief traag zijn. (gebeurt nu al door de expressie om te zetten naar reverse polish notation) Ik zat er dus aan te denken om de expressie ipv naar RPN meteen maar naar machine code om te zetten. Maar ik vraag me af of ik gewoon een stuk geheugen kan malloc()-en en daar een functiepointer naartoe zetten. en hoe krijg je daar dan weer data uit terug ?
Ik heb net getest hoe snel diezelfde expressie zou zijn als het in machinetaal gaat (dus op de plek waar ie normaal uitgerekend word gewoon die expressie in c++ neerzetten. en dat scheelt zeker een factor 30;

[ Voor 10% gewijzigd door Aaargh! op 06-02-2003 05:25 ]

[Super_ik]

je kunt zelf een compiler inbouwen

bv door verschillende bewerkingen die een gebruiker kan doen al in assambler geschreven hebben.
al die kleine stkjes assambler plak je dan aan elkaar afhankelijk van wat de gebruiker heeft opgegeven. dit compile je dan

[mbravenboer]

Runtime code generation is een populaire bezigheid in Java en .NET en vele minder bekende zeer dynamische talen, maar in deze omgevingen gaat dat allemaal een stuk minder makkelijk. Ik heb het nooit zelf gedaan, maar heb wel wat goede linkjes voor je.

ccg: dynamic code generation for C and C++

GNU lightning

Compiling for Runtime Code Generation, off-topic maar bevat wel een flink aantal verwijzingen naar gerelateerd werk.

Runtime code generation in JVM and CLR

[ Voor 7% gewijzigd door mbravenboer op 06-02-2003 09:30 ]

[kvdveer]

Deze techniek wordt ook wel PWP genoemd: program writing program. Er zijn wel mogelijkheden om die expressie sneller te maken, maar dan heb je, zoals gezegd een soort van assembler nodig in je programma. Dat te maken heeft nog behoorlijk wat haken en ogen. Je zult eerst voor jezef het een en ander naar op-codes moeten compileren om inzicht te krijgen in hoe je progamma in elkaar moet zitten.
Vervolgens moet je zelf opcodes gaan schrijven. Ik ben niet exact op de hoogte van de stuctuur van intel-opcodes, maar ik weet dat op PowerPC het echt bitneuken is... (bitje hier, drie bitjes daar).

[Janoz]

Op wat voor manier doe je het nu trouwens? Mischien zijn er namelijk ook wel andere mogenlijkheden tot het versnellen van je code.

[Verwijderd]

Ik zou als ik jou was, het eerst gewoon in C proberen op te lossen als C++ niet snel genoeg is (het zijn verschillende talen die verschillende code genereren o.h.a.) en als C niet snel genoeg is, zou ik C met inline assembly gebruiken en in het uiterste geval assembly... En machinecode gaan generen raad ik je wel af, gebruik liever geschakelde functiepointers e.d.

Tips (ik ga even uit van een x86 target):
- Kies in elk geval het meest gedetaileerde type: integers als het alleen om integer-waarden gaat, unsigned als het altijd >=0 is, en short als de variabelen binnen dat bereik vallen... Of floats i.p.v. doubles als dat ook kan, enz.
- Herorder en versimpel de formule: vervang (2*Pi*r) door de 2*Pi al van te voren eenmalig "uit te rekenen", het heeft geen zin om een dergelijke vermenigvuldiging 40800000 keer uit te voeren. Elke operatie-node moet voor de berekeningsreeks minstens een "variable" subnode hebben, anders doe je wat fout.
- Probeer zoveelmogelijk vermenigvuldigingen te voorkomen: gebruik bij voorkeur shift's als je vermenigvuldigt/deelt met een macht van 2, dus bovenstaande is het best te herschrijven naar "(b+3)<<3"
- Gebruik volledige loop-unrollment en inlining voor je code, het gaat je immers om snelheid, niet om codesize.
- Maak een doelstelling op voor de processors waar de code op moet kunnen draaien, en pas de compileeropties daaraan aan: dat is dus minimaal een pentium-mmx gezien jouw requirements, maar een i686, dus met SSE is misschien nog beter. Hierbij kunnen de berekeningen d.m.v. SIMD veel sneller en efficienter uitgevoerd worden.
- Maak gebruik van "regparm" functiecalls: de "standard C calling convention" de manier waarop C functies worden aangeroepen, dateert uit de tijd dat de x86 weinig registers had (voor de i386, zonder 32bits registers), en is niet erg efficient. "regparm" functiescalls zijn veel sneller, VC(++) en Borland C(++) herkennen ze als "__fastcall" en voor gcc kun je "__attribute__((__stdcall__,__regparm__(3)))" voor je functies zetten.
- Maak gebruik van alle beschikbare optimalisaties die de compiler biedt.
- Koop een snellere processor. Klinkt misschien stom, maar er is een beperking aan de rekenkracht van een processor, op een gegeven moment houdt het op en met assembly kun je nog wel wat tweaken, maar wonderen hoef je niet te verwachten, zeker niet bij de comerciële compilers.

Dit gaat dus alleen nog maar over oplossingen zonder zelf code te genereren in je aplicatie...

[ Voor 12% gewijzigd door Verwijderd op 06-02-2003 10:15 . Reden: "herorder en versimpel" toegevoegd ]

[mbravenboer]

Ik ben trouwens wel benieuwd waarvoor je deze extreme performance vereisten trouwens nodig hebt . Kan je iets vertellen over wat je aan het doen bent?

[kvdveer]

Verwijderd schreef op 06 februari 2003 @ 10:03:
- Maak gebruik van "regparm" functiecalls: de "standard C calling convention" de manier waarop C functies worden aangeroepen, dateert uit de tijd dat de x86 weinig registers had (voor de i386, zonder 32bits registers), en is niet erg efficient. "regparm" functiescalls zijn veel sneller, VC(++) en Borland C(++) herkennen ze als "__fastcall" en voor gcc kun je "__attribute__((__stdcall__,__regparm__(3)))" voor je functies zetten.

Wow. Dàt zijn pas waardevolle tips.
Een toevoeging: GCC 3.2 heeft ook __fastcall ondersteuning. Dit is ingebouwd na een verzoek van ReactOS, omdat je zonder fastcall geen windows-operatingsystems kunt maken.

[Verwijderd]

kvdveer schreef op 06 February 2003 @ 11:26:
[...]

Wow. Dàt zijn pas waardevolle tips.
Een toevoeging: GCC 3.2 heeft ook __fastcall ondersteuning. Dit is ingebouwd na een verzoek van ReactOS, omdat je zonder fastcall geen windows-operatingsystems kunt maken.

Dat gcc 3.2 ook een fastcall had, wist ik niet, maar ReactOS zou ook gewoon in de <ctype.h> deze kunnen define-n, dat was toch ook een prima optie geweest.

Moet ik d'r eigenlijk wel even bij zeggen dat de notatie die ik gebruikte, eenzelfde "__fascall" oplevert als bij Borland, voor VC++ moet je "...__regparm__(2)..." gebruiken, en moet je ook nog de volgorde van de gealloceerde regparm registers ergens instellen, te weten: eerst ecx, dan edx en dan verder... (Hoe dat ookalweer moet, ben ik nog aan het opzoeken... )

[MSalters]

Ik ermoed dat de TS functiepointers gebruikt, i.e. dat "(3*b)+8" de functiepointers van zijn * operator en + operator aanroept. Functiepointers zijn notoir traag, omdat ze de pipeline architectuur van een x86 ondermijnen. Je zou het in dit geval kunnen halveren door een composite mull_add te maken, en die de drie argumenten mee te geven. De consequentie is natuurlijk wel dat je alleen al voor de basis ops 16 functies nodig hebt, maar ook dat zal geen grote overhead zijn.

[Verwijderd]

MSalters schreef op 06 February 2003 @ 12:56:
Ik vermoed dat de TS functiepointers gebruikt, i.e. dat "(3*b)+8" de functiepointers van zijn * operator en + operator aanroept. Functiepointers zijn notoir traag, omdat ze de pipeline architectuur van een x86 ondermijnen. Je zou het in dit geval kunnen halveren door een composite mull_add te maken, en die de drie argumenten mee te geven. De consequentie is natuurlijk wel dat je alleen al voor de basis ops 16 functies nodig hebt, maar ook dat zal geen grote overhead zijn.

Ik vermoed dat niet, volgens mij parsed de TS de invoer "(3+b)*8" en genereert hier een operatie-boom uit, die hij vervolgens doorloopt met een behoorlijk aantal waarden voor b. Snelste manier zou het volgens mij hier zijn om een reeks van functiepointers te doorlopen... En het gebruik van regparms (AKA __fastcall) zou daarbij hier een hoop push/pop operaties overbodig maken, omdat de meeste wiskundige operaties niet meer dan twee/drie argumenten nodig hebben...

Overigens heeft de x86 niet echt iets wat de naam "pipeline architectuur" waardig is, het is bij een x86 vooral van belang dat het bestemmingsadres al binnen het L1 cache ligt (of anders hopelijk L2). Wel duurt een call naar een register-inhoud langer, anders zou het de beste oplossing zijn om niet een reeks functiepointers te genereren en af te lopen, maar een reeks van calls weg te schrijven in een "rw executable" sectie, alleen heb je dan weer het nadeel dat het wel erg lastig wordt om relatieve calls te gebruiken en ben je eigenlijk direct aangewezen op tragere absolute calls... En heb je eigenlijk nog weinig sneheidswinst

offtopic:
BTW: het is overigens een add_mull waar de TS mee opende

[ Voor 24% gewijzigd door Verwijderd op 06-02-2003 13:28 ]

[Tomatoman]

Je kunt ook een heel andere benadering kiezen. Schaf per pc waar jouw programma op moet draaien een command-line compiler aan. Daarvoor zijn ook een heleboel gratis alternatieven. Schijf in de taal van die compiler een simpel programma dat op de achtergrond kan draaien. Het enige wat je in de broncode nog niet invult, is de uit te voeren expressie. Zodra de gebruiker die in jouw programma invult, zorg je dat die als platte tekst in de programmacode wordt ingevuld. Met de compiler je code compileren en runnen maar. Er draaien dan dus twee programma's: jouw eigen programma en het net gecompileerde rekenprogrammaatje. Op deze manier hoef je niet zelf een compiler te bouwen en dat spaart je ongelooflijk veel programmeertijd

Nog een andere benadering, die ik erg elegant vind ): gebruik een database management systeem (DBMS) dat stored procedures ondersteunt. Maak van de expressie die de gebruiker in jouw programma opgeeft een stored procedure en roep deze aan. Dat heeft nog twee extra voordelen: DBMS'en optimaliseren zo'n query vaak op de een of andere manier en bovendien kunnen zij de resultaten van al die miljoenen functieaanroepen heel eenvoudig in een tabel opslaan. Onder de talen die stored procedures ondersteunen vallen onder meer DB2, Oracle, SQL Server, Interbase en de gratis Interbase-variant Firebird.

[ Voor 4% gewijzigd door Tomatoman op 06-02-2003 13:48 ]

[Aaargh!]

Janoz schreef op 06 February 2003 @ 09:35:
Op wat voor manier doe je het nu trouwens? Mischien zijn er namelijk ook wel andere mogenlijkheden tot het versnellen van je code.

Op dit moment word de expressie geparsed en omgezet naar RPN (reverse polish notation) de expressie (3+b) * 8 bijvoorbeeld word dan 3 b + 8 * op die manier kan ik 'm in een van link naar rechts verwerken. verder word dit natuurlijk niet als string opgeslagen maar ik maak er eerst een soort bytecode van die dan geinterpreteerd word.

[Aaargh!]

mbravenboer schreef op 06 February 2003 @ 10:06:
Ik ben trouwens wel benieuwd waarvoor je deze extreme performance vereisten trouwens nodig hebt . Kan je iets vertellen over wat je aan het doen bent?

De bedoeling is een scriptable winamp/xmms plugin. streven is dat de boel op 800x600 op een redelijke snelheid draait. Nu zijn er voor waveforms en colormaps niet zo veel berekeningen nodig, maar vooral de deltafields vreten cpu power. elke pixel word afgebeel op een andere volgens een bepaalde user definerbare functie, dit moet dus voor 480 000 pixels en het liefst met een fatsoenlijke framerate (85 hz)
Ik had trouwens al bedacht dat ik ook deltafields vantevoren kan berekenen (dus een array maken met source/destination posities) maar dan verlies je flexibiliteit zoals b.v. deltafields die reageren op de muziek e.d.

[ Voor 14% gewijzigd door Aaargh! op 06-02-2003 14:06 ]

[Verwijderd]

Ik weet niet of het nu nog zo is, maar toen ik nog wel 's iets grafisch programmeerde in asm, maakte ik altijd gebruik van fixed point integers, ipv floats... Dat was vele malen sneller. Misschien is dat ook een optie..

[ Voor 9% gewijzigd door Verwijderd op 06-02-2003 14:05 ]

[Verwijderd]

tomatoman schreef op 06 February 2003 @ 13:46:
Nog een andere benadering, die ik erg elegant vind ): gebruik een database management systeem (DBMS) dat stored procedures ondersteunt.

Nee, en dat gaat sneller dan welk alternatief in C/C++ dan ook?!


overigens: (3+b)*8 en dat 40,800,000 keer en dat 20 keer sneller dan in 18 secondie, dat betekend dat er hooguit:

40800000 berekeningen in 18/20 seconde => 0.000,000,022 seconde voor elke berekening is!

Stel dat alles 1 clockcycle zou duren en je compileert de code totaal optimaal dan geldt:
[zolang er een nieuwe waarde is:]

klok operatie
1 Zijn we al aan het einde van de reeks van 40800000 getallen?
2 Zo ja spring voorbij 7
3 Laad een nieuwe waarde voor b
4 Tel 3 op bij b
5 Vermenigvuldig resultaat met 8
6 Sla het resultaat op.
7 Spring terug naar 1

Dan mag een klokcycle hooguit duren: 0.000,000,022 sec / 7

dat zou betekenen dat je een processor nodig hebt die niets anders doet dan jouw berekening, en die minimaal op 317MHz draait. Heb je ook nog een besturingssysteem en een gebruikelijke processor die niet overal (load/store) maar een clockcycle over doet, dan heb je een probleem... Wel kun je SIMD gebruiken om nog een stuk verder te komen door berekingen parallel te laten lopen, maar dan nog moet je waarschijnlijk een eigen compiler schrijven om dit resultaat te bereiken in de door jouw gewenste tijd...

[ Voor 4% gewijzigd door Verwijderd op 06-02-2003 14:15 ]

[.oisyn]

MSalters schreef op 06 February 2003 @ 12:56:
Ik ermoed dat de TS functiepointers gebruikt, i.e. dat "(3*b)+8" de functiepointers van zijn * operator en + operator aanroept. Functiepointers zijn notoir traag, omdat ze de pipeline architectuur van een x86 ondermijnen. Je zou het in dit geval kunnen halveren door een composite mull_add te maken, en die de drie argumenten mee te geven. De consequentie is natuurlijk wel dat je alleen al voor de basis ops 16 functies nodig hebt, maar ook dat zal geen grote overhead zijn.

dit dacht ik dus ook, maar ik heb een tijdje terug een test gedaan met virtual functions:

opstelling 1:

C++:

struct A
{
    virtual void doeIets () = 0;
};

struct B : public A
{
    void doeIets ();
};

struct C : public A
{
    void doeIets ();
};

tegenover opstelling 2:

C++:

struct A
{
    enum { IB, IC } type;
    void doeIets ();
}

struct B : public A
{
    B () { type = IB; }
    void doeIets ();
};

struct C : public A
{
    C () { type = IC; }
    void doeIets ();
};

void A::eenFunctie ()
{
    if (type == IB)
        (reinterpret_cast<B *> (this))->doeIets ();
    else if (type == IC)
        (reinterpret_cast<C *> (this))->doeIets ();
}

Wat B::doeIets () en C::doeIets () doen is verder niet echt belangrijk, zolang het maar in constante tijd uitgevoerd kan worden.

Tot mijn verbazig was opstelling 1 ietsjes sneller dan opstelling 2 op mijn athlon xp 1400 MHz, terwijl je echt zou denken dat opstelling 1 veel langzamer zou zijn omdat het gebruik maakt van virtual functions en dus functie pointers, terwijl de functies bij opstelling 2 direct aangeroepen werden
Ik heb er natuurlijk voor gezorgd dat alles zo geoptmimalizeert mogelijk was, behalve dat functions niet worden geinline'd.
Gemeten in VC++ 7.1

.edit: oh, ik herinner me ineens weer dat de werkelijke implementatie van deze test ook een expressieboom was, die dus sneller werd uitgerekend als er gebruik werd gemaakt van virtual functies

Wat trouwens ook opgemerkt moet worden is dat de Pentium 4 hier meer moeite van ondervindt, aangezien die nogal een slechte reputatie heeft kwa pipelining en branch prediction

[ Voor 16% gewijzigd door .oisyn op 06-02-2003 14:23 ]

[_js_]

Vergeet niet je functie zo veel mogelijk te vereenvoudigen.
24 + 8*b is ongeveer twee keer zo snel als 8*3 + 8*b
Maak uitzondering voor vermenigvuldigingen als het gaat om vermenigvuldigen met 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, etc. omdat je compiler deze vermenigvuldigingen sneller zou moeten compileren (bitshifts en optellen/aftrekken in plaats van een vermenigvuldiging), en ook
Probeer zo weinig mogelijk gebruik te maken van functies, want de overhead van een functie is relatief groot.
Probeer groepen van pixels tegelijk te verwerken met behulp van matrices, en kijk in de documentatie van je compiler om te zien hoe dit precies moet om te zorgen dat je compiler gebruik maakt van SSE/3Dnow/MMX waar mogelijk.

[.oisyn]

[nohtml]

Verwijderd schreef op 06 February 2003 @ 13:12:
Overigens heeft de x86 niet echt iets wat de naam "pipeline architectuur" waardig is, het is bij een x86 vooral van belang dat het bestemmingsadres al binnen het L1 cache ligt (of anders hopelijk L2).

zeker wel, de cpu's van tegenwoordig hebben een pipeline van ongeveer 20 instructies, die worden gevuld aan de hand van branch prediction. Een call naar een pointer waarvan het adres afhankelijk is van de vorige instructie kan dus niet voorspeld worden, en dus worden alle al ingelezen instructies fijn uit de pipeline geflikkerd, wat in het ergste geval een vertraging oplevert van het aantal instructies dat uit de pipeline werden gegooid: 20 cycles dus. Dat heeft nogal een impact op performance als dit erg vaak gebeurt

maar een reeks van calls weg te schrijven in een "rw executable" sectie, alleen heb je dan weer het nadeel dat het wel erg lastig wordt om relatieve calls te gebruiken en ben je eigenlijk direct aangewezen op tragere absolute calls... En heb je eigenlijk nog weinig sneheidswinst

schrijven naar code sections die kort daarna uitgevoerd worden, self-modifying code dus, is echt een van de traagste dingen die je kunt doen tegenwoordig. Vroeger, op oude 8086 machines, had dit nog wel nut, maar tegenwoordig is het echt uit den boze. Dat komt omdat de instructiecache niet rekent op veranderingen, en als deze verandering dan toch optreedt moet de hele cache ververst worden, en de pipeline ook nog eens aangezien de instructies behoorlijk kunnen veranderen door zo'n wijziging

[kvdveer]

Verwijderd schreef op 06 February 2003 @ 12:26:
[...]
Moet ik d'r eigenlijk wel even bij zeggen dat de notatie die ik gebruikte, eenzelfde "__fascall" oplevert als bij Borland, voor VC++ moet je "...__regparm__(2)..." gebruiken, en moet je ook nog de volgorde van de gealloceerde regparm registers ergens instellen, te weten: eerst ecx, dan edx en dan verder... (Hoe dat ookalweer moet, ben ik nog aan het opzoeken... )

offtopic:
Nee, de exacte registerindeling is dan anders. En voor binaire compatibiliteit is het erg belangrijk dat je registers glijk blijven. Voor GCC3.x gebruiken ze een aangepaste versie van GCC2.x. Het probleem zit 'm er in dat code van verschillende compilers elkaar aanroept.

Ik zag ooit een plugin voor winamp, die werkte op 256x256 (opgeschaald naar 512x512), en die maakte ook zelf zijn assemblercode. Ik zou zeggen: kijk er eens naar. Deze plugin is het bewijs dat het werkt... Het ding gebruikt tabellen voor bijna alles wat los en/of vast zit. Leuk voor optimalisatie, maar een ramp voor flexibiliteit...

[ Voor 3% gewijzigd door kvdveer op 06-02-2003 14:36 ]

[Aaargh!]

Verwijderd schreef op 06 February 2003 @ 14:12:
[...]

Nee, en dat gaat sneller dan welk alternatief in C/C++ dan ook?!


overigens: (3+b)*8 en dat 40,800,000 keer en dat 20 keer sneller dan in 18 secondie, dat betekend dat er hooguit:

40800000 berekeningen in 18/20 seconde => 0.000,000,022 seconde voor elke berekening is!

C++ zelf doet dezelfde expressie in 0,016 usec, mijn huidige methode kost ongeveer 0,4 usec.

Stel dat alles 1 clockcycle zou duren en je compileert de code totaal optimaal dan geldt:
[zolang er een nieuwe waarde is:]

klok operatie
1 Zijn we al aan het einde van de reeks van 40800000 getallen?
2 Zo ja spring voorbij 7
3 Laad een nieuwe waarde voor b
4 Tel 3 op bij b
5 Vermenigvuldig resultaat met 8
6 Sla het resultaat op.
7 Spring terug naar 1

Dan mag een klokcycle hooguit duren: 0.000,000,022 sec / 7

dat zou betekenen dat je een processor nodig hebt die niets anders doet dan jouw berekening, en die minimaal op 317MHz draait. Heb je ook nog een besturingssysteem en een gebruikelijke processor die niet overal (load/store) maar een clockcycle over doet, dan heb je een probleem... Wel kun je SIMD gebruiken om nog een stuk verder te komen door berekingen parallel te laten lopen, maar dan nog moet je waarschijnlijk een eigen compiler schrijven om dit resultaat te bereiken in de door jouw gewenste tijd...

Het streven is dat het gaat draaien vanaf ong. een p2-500

[Aaargh!]

.oisyn schreef op 06 februari 2003 @ 14:32:
schrijven naar code sections die kort daarna uitgevoerd worden, self-modifying code dus, is echt een van de traagste dingen die je kunt doen tegenwoordig. Vroeger, op oude 8086 machines, had dit nog wel nut, maar tegenwoordig is het echt uit den boze. Dat komt omdat de instructiecache niet rekent op veranderingen, en als deze verandering dan toch optreedt moet de hele cache ververst worden, en de pipeline ook nog eens aangezien de instructies behoorlijk kunnen veranderen door zo'n wijziging

Bedenk wel dat die wijziging 1 keer gedaan wordt waarna hij 40 miljoen keer word uitgevoerd.

[Aaargh!]

_js_ schreef op 06 februari 2003 @ 14:24:
Vergeet niet je functie zo veel mogelijk te vereenvoudigen.
24 + 8*b is ongeveer twee keer zo snel als 8*3 + 8*b
Maak uitzondering voor vermenigvuldigingen als het gaat om vermenigvuldigen met 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, etc. omdat je compiler deze vermenigvuldigingen sneller zou moeten compileren (bitshifts en optellen/aftrekken in plaats van een vermenigvuldiging), en ook
Probeer zo weinig mogelijk gebruik te maken van functies, want de overhead van een functie is relatief groot.

Helaas moeten er een aantal functies aangeroepen kunnen worden (sin, cos, tan, pow, ... )

[Gerco]

Aaargh! schreef op 06 February 2003 @ 14:45:
Helaas moeten er een aantal functies aangeroepen kunnen worden (sin, cos, tan, pow, ... )

Wat allemaal functies zijn die een fpu prima in zn eentje aankan. Ik snap het probleem daarvan niet?

[Tomatoman]

Verwijderd schreef op 06 February 2003 @ 14:12:
[...]
Nee, en dat gaat sneller dan welk alternatief in C/C++ dan ook?!

Nee, maar het gaat wel veel sneller dan met een interpreter. Bovendien had de topicstarter nog geen enkele indicatie gegeven waarvoor hij dit wilde doen. In eerste instantie dacht ik aan een iteratief proces waarbij de tussentijdse resultaten moesten worden bewaard. Zijn bedoeling was echter totaal. Dat geeft maar weer eens aan hoe belangrijk het is om de context van je probleem aan te geven.

[.oisyn]

Aaargh! schreef op 06 February 2003 @ 14:38:
[...]

Bedenk wel dat die wijziging 1 keer gedaan wordt waarna hij 40 miljoen keer word uitgevoerd.

Dat ligt natuurlijk aan hoe je het opzet, maar op de manier zoals jij het waarschijnlijk bedoelt ben je al bezig met code-generatie voor je expressieboom, en niet zozeer het optimalizeren van de aanroepen van de verschillende functies

Maar in principe kan het genereren van de code vrij simpel als je gebruik maakt van een stack-based evaluator. Daarbij heb je een stack met waarden, en een operator pop't de bovenste 2 waarden van de stack, doet de operatie, en push't dan de uitkomst weer op de stack

De assembler code in jouw voorbeeld wordt dan zoiets:

GAS:

push dword 3
push dword ptr [vars + 1]   // <-- b staat op vars[1] zeg maar
call add
push dword 8
call mul

de code voor add wordt dan bijvoorbeeld:

GAS:

pop ecx   // return address
pop eax
pop ecx
add eax, edx
push eax
push ecx
ret

aangezien je expressiecode uit simpele instructies bestaat is het ook vrij simpel om er een op te bouwen zonder kennis te hebben van de hele x86 instructieset

Met floating point berekeningen gaat het zelfs nog makkelijker, aangezien die intern met een stack werkt Maar dan kunnen er wel maar maximaal 8 waarden op de stack staan

[Aaargh!]

.oisyn schreef op 06 February 2003 @ 14:52:

[...]


Dat ligt natuurlijk aan hoe je het opzet, maar op de manier zoals jij het waarschijnlijk bedoelt ben je al bezig met code-generatie voor je expressieboom, en niet zozeer het optimalizeren van de aanroepen van de verschillende functies

Maar in principe kan het genereren van de code vrij simpel als je gebruik maakt van een stack-based evaluator. Daarbij heb je een stack met waarden, en een operator pop't de bovenste 2 waarden van de stack, doet de operatie, en push't dan de uitkomst weer op de stack

Dat gebruik ik nu dus ook, maar momenteel word dit dus geinterpreteerd

De assembler code in jouw voorbeeld wordt dan zoiets:

GAS:

push dword 3
push dword ptr [vars + 1]   // <-- b staat op vars[1] zeg maar
call add
push dword 8
call mul

de code voor add wordt dan bijvoorbeeld:

GAS:

pop ecx   // return address
pop eax
pop ecx
add eax, edx
push eax
push ecx
ret

aangezien je expressiecode uit simpele instructies bestaat is het ook vrij simpel om er een op te bouwen zonder kennis te hebben van de hele x86 instructieset

Inderdaad, het enige punt is dan ook hoe hang je zoiets in je c++ programma.

Met floating point berekeningen gaat het zelfs nog makkelijker, aangezien die intern met een stack werkt Maar dan kunnen er wel maar maximaal 8 waarden op de stack staan

Ik werk overal met double's dus op zich moet dat niet zo'n probleem zijn om dit zo te fixen. En dat maximum van 8 items op de stack moet ook niet zo'n probleem zijn. voor echt complexe dingen moet het nl. mogelijk worden effecten als .dll / .so in te laden.

[Soultaker]

In dit geval lijkt me tomatoman's suggestie nog het meest zinnig; genereer assembly code voor je expressie en haal die door een externe assembler, die er een dll van maakt. Die kun je vervolgens laden en gebruiken. Je zou ook zelf direct machine code kunnen genereren (in het geheugen) wat netter is, omdat je niet afhankelijk bent van een extern programma, maar dat is natuurlijk veel meer werk. Bovendien wist je niet hoe je assembly code op correcte wijze kon uitvoeren. (Ik denk echter dat je prima in een malloced stukje geheugen machine code kunt schrijven en daar een function pointer naar forceren; onder Windows en de x86 architectuur maakt dat voor zover ik weet niets uit).

[ Voor 28% gewijzigd door Soultaker op 06-02-2003 15:09 ]

[mbravenboer]

Ik zou nog eens naar ccg kijken wat ik eerder linkte. Volgens mij is dat wel wat als je op deze manier gaat werken.

[.oisyn]

kwestie van de instructieset erbij pakken en uitvinden wat de opcodes zijn

bij doubles is het een stuk makkelijker, daar wordt het zoiets als

GAS:

fld qword ptr [constants]     // hier staat 3
fld qword ptr [vars + 1]    // b
faddp ST1
fld qword ptr [constants + 1]  // 8
fmulp ST1

en dit zijn de opcodes:

code:

FLD mem64                     ; DD /0                [8086,FPU]
FADDP fpureg                  ; DE C0+r              [8086,FPU] 
FMULP fpureg                  ; DE C8+r              [8086,FPU]

voor FLD heb je effective address encoding nodig om het adres weer te geven, hoe dat gaat staat hier beschreven
[quote]B.2.5 Effective Address Encoding: ModR/M and SIB
An effective address is encoded in up to three parts: a ModR/M byte, an optional SIB byte, and an optional byte, word or doubleword displacement field.

The ModR/M byte consists of three fields: the mod field, ranging from 0 to 3, in the upper two bits of the byte, the r/m field, ranging from 0 to 7, in the lower three bits, and the spare (register) field in the middle (bit 3 to bit 5). The spare field is not relevant to the effective address being encoded, and either contains an extension to the instruction opcode or the register value of another operand.

The ModR/M system can be used to encode a direct register reference rather than a memory access. This is always done by setting the mod field to 3 and the r/m field to the register value of the register in question (it must be a general-purpose register, and the size of the register must already be implicit in the encoding of the rest of the instruction). In this case, the SIB byte and displacement field are both absent.

In 32-bit addressing mode (either BITS 16 with a 67 prefix, or BITS 32 with no 67 prefix) the general rules (again, there are exceptions) for mod and r/m are:

[list]• The mod field gives the length of the displacement field: 0 means no displacement, 1 means one byte, and 2 means four bytes.
• If only one register is to be added to the displacement, and it is not ESP, the r/m field gives its register value, and the SIB byte is absent. If the r/m field is 4 (which would encode ESP), the SIB byte is present and gives the combination and scaling of registers to be added to the displacement.
If the SIB byte is present, it describes the combination of registers (an optional base register, and an optional index register scaled by multiplication by 1, 2, 4 or 8 ) to be added to the displacement. The SIB byte is divided into the scale field, in the top two bits, the index field in the next three, and the base field in the bottom three. The general rules are:

[list]• The base field encodes the register value of the base register.
The index field encodes the register value of the index register, unless it is 4, in which case no index register is used (so ESP cannot be used as an index register).
• The scale field encodes the multiplier by which the index register is scaled before adding it to the base and displacement: 0 encodes a multiplier of 1, 1 encodes 2, 2 encodes 4 and 3 encodes 8.
The exceptions to the 32-bit encoding rules are:

• If mod is 0 and r/m is 5, the effective address encoded is not [EBP] as the above rules would suggest, but instead [disp32]: the displacement field is present and is four bytes long, and no registers are added to the displacement.
• If mod is 0, r/m is 4 (meaning the SIB byte is present) and base is 4, the effective address encoded is not [EBP+index] as the above rules would suggest, but instead [disp32+index]: the displacement field is present and is four bytes long, and there is no base register (but the index register is still processed in the normal way).

[Verwijderd]

.oisyn schreef op 06 February 2003 @ 14:32:
[nohtml]
[...]


zeker wel, de cpu's van tegenwoordig hebben een pipeline van ongeveer 20 instructies, die worden gevuld aan de hand van branch prediction. Een call naar een pointer waarvan het adres afhankelijk is van de vorige instructie kan dus niet voorspeld worden, en dus worden alle al ingelezen instructies fijn uit de pipeline geflikkerd, wat in het ergste geval een vertraging oplevert van het aantal instructies dat uit de pipeline werden gegooid: 20 cycles dus. Dat heeft nogal een impact op performance als dit erg vaak gebeurt


[...]


schrijven naar code sections die kort daarna uitgevoerd worden, self-modifying code dus, is echt een van de traagste dingen die je kunt doen tegenwoordig. Vroeger, op oude 8086 machines, had dit nog wel nut, maar tegenwoordig is het echt uit den boze. Dat komt omdat de instructiecache niet rekent op veranderingen, en als deze verandering dan toch optreedt moet de hele cache ververst worden, en de pipeline ook nog eens aangezien de instructies behoorlijk kunnen veranderen door zo'n wijziging

En dus is de eerste opties een stuk optimaler dan de tweede. Overigens meen ik me te herinneren dat een call naar een register-inhoud geen 20 cycles duurt, dus valt het met die pipeline wel mee, want het aantal cyclecounts dat een dergelijke call duurt, is afhankelijk van de pipeline...

[.oisyn]

Verwijderd schreef op 06 februari 2003 @ 15:18:
Overigens meen ik me te herinneren dat een call naar een register-inhoud geen 20 cycles duurt, dus valt het met die pipeline wel mee, want het aantal cyclecounts dat een dergelijke call duurt, is afhankelijk van de pipeline...

die 20 was een worst-case geval voor een 20 instructie pipeline. Ik bedoelde ook dat het afhankelijk was van de pipeline, niet dat het altijd 20 cycles duurt

[Verwijderd]

.oisyn schreef op 06 February 2003 @ 14:52:Dat ligt natuurlijk aan hoe je het opzet, maar op de manier zoals jij het waarschijnlijk bedoelt ben je al bezig met code-generatie voor je expressieboom, en niet zozeer het optimalizeren van de aanroepen van de verschillende functies

Maar in principe kan het genereren van de code vrij simpel als je gebruik maakt van een stack-based evaluator. Daarbij heb je een stack met waarden, en een operator pop't de bovenste 2 waarden van de stack, doet de operatie, en push't dan de uitkomst weer op de stack

De assembler code in jouw voorbeeld wordt dan zoiets:

GAS:

push dword 3
push dword ptr [vars + 1]   // <-- b staat op vars[1] zeg maar
call add
push dword 8
call mul

de code voor add wordt dan bijvoorbeeld:

GAS:

pop ecx   // return address
pop eax
pop ecx
add eax, edx
push eax
push ecx
ret

aangezien je expressiecode uit simpele instructies bestaat is het ook vrij simpel om er een op te bouwen zonder kennis te hebben van de hele x86 instructieset

niet helemaal netjes, als je gebruik zou maken van een stdcall waarbij de callee de stack terugzet, mag je de eerste code gebruiken, en de oplossing die je daarvoor geeft in het tweede stuk code, (afgezien van het 2x ecx pop foutje wat een edx had moeten zijn... en dat de pop's niet in evenwicht zijn met de push's) is dan niet erg netjes, beter en korter is dan:

GAS:

mov eax,4[esp]
mov edx,8[esp]
add eax,edx
ret 8

[Verwijderd]

Aaargh! schreef op 06 februari 2003 @ 14:45:
[...]

Helaas moeten er een aantal functies aangeroepen kunnen worden (sin, cos, tan, pow, ... )

voor cos en tan kan het handig zijn om een van te voren gemaakte tabel te raadplegen, dat gaat ook heel snel

[.oisyn]

[nohtml]

Verwijderd schreef op 06 February 2003 @ 15:32:
niet helemaal netjes

dat het niet netjes is is om de topicstarter het wat duidelijker te maken dan gelijk een voorbeeld te posten met allerlei optimalisaties zodat ie er niets meer van snapt. Als je een wiskundig document leest geven ze eerst ook gewoon de volledige formules, en daarna gaan ze pas optimalizeren

(afgezien van het 2x ecx pop foutje wat een edx had moeten zijn... en dat de pop's niet in evenwicht zijn met de push's)

die 2e ecx was idd een typefout, maar verder klopt hij wel hoor

GAS:

push 3
push 8
call add
// einde expressie, de uitkomst staat bovenaan op de stack

add:
pop ecx   // return address
pop eax
pop edx
add eax, edx
push eax
push ecx
ret

dat gaan we eens doorlopen
allereerst wordt er een 3 op de stack gepushed, daarna een 8
dan wordt add aangeroepen. De stack ziet er dan als volgt uit:

code:

3
8
return_address

Dan wordt het returnadres in ecx geladen, en 3 en 8 gaan in resp. edx en eax.
De stack is nu leeg. 3 wordt bij 8 opgeteld, wat 11 geeft in eax. Dat wordt gepushed op de stack. Vervolgens weer het returnadres. De ret zorgt ervoor dat er terug wordt gesprongen naar het returnadres. De stackinhoud is dan slechts een 11, wat dus de uitkomst is van 3 + 8. Die moet op de stack blijven zodat het gebruikt kan worden in een volgende subexpressie

Wat jij doet is het resultaat teruggeven in eax. Maar wat heb je daaraan? Dan moet het alsnog weer op de stack gepushed worden. De getallen komen immers op de stack te staan, niet in registers

Een geoptimalizeerde versie van mijn add zou dan zijn:

GAS:

pop ecx
pop eax
add [esp], eax
jmp ecx

[ Voor 10% gewijzigd door .oisyn op 06-02-2003 15:49 ]

[MisterData]

Ik ben laatst een runtime-assembler tegengekomen. Gewoon een bestand met ASM inladen, en de API aanroepen en de code werd uitgevoerd www.flipcode.com en dan ergens bij 'code of the day' Het heet softwire trouwens, http://softwire.sourceforge.net:

SoftWire is a run-time x86 assembler. It can be used as a JIT compiler back-end for scripting languages, or for dynamic code generation of optimized inner loops.

Flexible software is mostly slower than dedicated software, and especially slower than dedicated hardware. Take for example 3D rendering. Popular API's like OpenGL and Direct3D often have software implementations which support all the different rendering modes also supported by hardware, but are terribly slow. Dedicated software engines like the one in the Unreal game use hand-optimized assembly and have good performance but lack flexibility. This is because it's nearly impossible to write all different combinations of render modes in optimized assembly. Hardware accelerated 3D rendering is very fast and flexible, but you're still restricted to the implemented features and certain quality. To have total flexibility and to keep good performance, the inner loops should be generated at run-time, which requires some sort of self-modifying code.

This is how SoftWire was born. It is capable of compiling an assembly source file at run-time and selecting those instructions which are needed for a certain situation by using conditional compilation, linking it with external data in your project and loading it into memory so it can be called directly. It combines the flexibility of hardware with the performance of optimized assembly. It's like rewiring the instructions in your inner loop to have the right code for every situation, hence the name of the project. It also doesn't have any limitations like hardware since the CPU is 'general purpose' and all memory is shared. It supports the newest SIMD instruction sets like MMX, 3DNow!, SSE and SSE2 which, together with the high clock frequency of the CPU, results in an acceptable alternative for hardware.

[ Voor 79% gewijzigd door MisterData op 06-02-2003 15:57 ]

[Verwijderd]

.oisyn schreef op 06 February 2003 @ 15:45:
[nohtml]
[...]

Wat jij doet is het resultaat teruggeven in eax. Maar wat heb je daaraan? Dan moet het alsnog weer op de stack gepushed worden. De getallen komen immers op de stack te staan, niet in registers

Een geoptimalizeerde versie van mijn add zou dan zijn:

GAS:

pop ecx
pop eax
add [esp], eax
jmp ecx

Een geoptimalizeerde versie van mijn add zou dan zijn:

GAS:

mov eax,4[esp]
add 8[esp], eax
ret 8

[Verwijderd]

Overigens zou ik er dan voor kiezen de stack te vullen met de functiepointers, en edi naar de argumenten te laten wijzen. volgens mij kun je dan:

GAS:

add:    lodsd       ; load [edi] to eax and increment/decrement edi
    add [edi], eax
    ret     ; jumps to next functionpointer on stack

sub:    lodsd
    sub [edi], eax
    ret

Maar je houd het probleem van een reeks: 6 b + 3 b - *, daar kun je deze noch de esp oplossing voor gebruikenj, je zou in beide gevallen per node maar een subbranch mogen hebben...

[ Voor 41% gewijzigd door Verwijderd op 06-02-2003 17:17 ]

[.oisyn]

Verwijderd schreef op 06 februari 2003 @ 16:29:
[...]

Een geoptimalizeerde versie van mijn add zou dan zijn:

GAS:

mov eax,4[esp]
add 8[esp], eax
ret 8

behalve dat jij dan nog de eax moet pushen voor de volgende functie

[Aaargh!]

Code generatie is imho niet het probleem hier. het probleem is : hoe hang ik dit runtime gegenereerde stukje code in m'n C++ programma ? en hoe krijg ik data vanuit dat stukje code naar c++ ?
Mijn programma heeft ergens een routine setExpression(); deze scanned en parsed de expressie en maakt er RPN van in een soort bytecode. in plaats hiervan is het natuurlijk niet al te moeilijk om IA32 code te genereren. Maar nu heb ik die IA32 code in een buffer staan, en wat dan ?

[Verwijderd]

.oisyn schreef op 06 February 2003 @ 17:15:

[...]


behalve dat jij dan nog de eax moet pushen voor de volgende functie

Dat in elk geval niet, maar het had "ret 4" moeten zijn om identiek aan jouw code te zijn...

[ Voor 12% gewijzigd door Verwijderd op 06-02-2003 17:24 ]

[.oisyn]

wat je kunt doen is een buffer alloceren waar je de code inzet, en dan nog een buffer voor de constanten en de variabelen. Het eindresultaat moet je in ST0 zetten (bovenop de floating point stack dus), en dan gewoon een ret doen. De code kun je dan aanroepen door een je buffer als een functie aan te roepen, dus gewoon de pointer casten naar een functiepointer, en die aanroepen:

C++:

void * buffer = parseExpression (exp);
double (*func) () = (double (*)()) buffer;
double resultaat = func ();

Van de variabele en constante data maak je automatisch gebruik als je de adressen goed zet in de gegenereerde code

[ Voor 4% gewijzigd door .oisyn op 06-02-2003 17:26 ]

[Aaargh!]

Dat ga ik vanavond eens ff proberen.

[madwizard]

Als het echt om pure snelheid gaat kan je het best alle functies (+ - * sin cos etc.) inline gebruiken, geen calls. Calls hebben weer argumenten op de stack nodig (tenzij je het in registers doet maar dan zit je aan real4's vast en bovendien kan je FPU registers niet direct in een integer register zetten).
Als je de expressie al in RPN hebt is FPU code genereren niet lastig, het optimaliseren is een ander verhaal. Een voorbeeldje, neem de expressie:
a * a + 2 + 3 * a
in RPN:
a a * 2 + 3 a * +
Een recht-toe-recht-aan vertaling is:

code:

finit
fld     [a]
fld     [a]
fmulp   st(1), st(0)
fld     [val2]
faddp   st(1), st(0)
fld     [val3]
fld     [a]
fmulp   st(1), st(0)
faddp   st(1), st(0)

Maar beter had geweest:

code:

finit
fld     [val2]          ;   2
fld     [a]             ;   2,a
fld     st(0)           ;   2,a,a
fmul    st(1), st(0)    ;   2,a*a,a
fmul    [val3]          ;   2,a*a,a*3
faddp   st(1), st(0)    ;   2,a*a+a*3
faddp   st(1), st(0)    ;   2+a*a+a*3

Bovenstaande is wel *veel* lastiger te genereren, compilers doen hun uiterste best om dit soort geoptimaliseerde dingen te genereren en dat is niet makkelijk.

Maar zelfs de bovenste versie zal waarschijnlijk wel winst opleveren vergeleken met een interpreter.

Wat de penalty van self modifying code betreft, die is inderdaad vrij hoog (zeker naarmate de processor nieuwer is) maar te verwaarlozen als de code daarna zovaak wordt uigevoerd (penalty is 150-130 cycles op PII/PIII (P4 weet ik niet uit m'n hoofd)). Ik weet niet of malloc/new garandeert dat het geheugen wat gereserveerd wordt executable is, vast niet. Het hangt af van de implementatie (het hoeft namelijk niet zo te zijn, kan ook alleen read/write zijn). De GlobalAlloc API geeft in ieder geval executable memory terug, en anders VirtualAlloc daar kan je het helemaal zelf regelen. Ook moet je in windows FlushInstructionCache gebruiken nadat je de code gegenereerd hebt anders kan de CPU mogelijk gecachte code uitvoeren.

Ik zou ook eens naar SoftWire kijken, heb het wel eens eerder gezien (maar niet serieus mee gewerkt), scheelt je het gedoe van opcodes genereren.

[Aaargh!]

madwizard schreef op 06 February 2003 @ 18:32:
Wat de penalty van self modifying code betreft, die is inderdaad vrij hoog (zeker naarmate de processor nieuwer is) maar te verwaarlozen als de code daarna zovaak wordt uigevoerd (penalty is 150-130 cycles op PII/PIII (P4 weet ik niet uit m'n hoofd)). Ik weet niet of malloc/new garandeert dat het geheugen wat gereserveerd wordt executable is, vast niet.

Word er onderscheid gemaakt tussen executable en niet executable geheugen dan ? iirc kan het IA32 gebeuren dit onderscheid helemaal niet maken.

Het hangt af van de implementatie (het hoeft namelijk niet zo te zijn, kan ook alleen read/write zijn). De GlobalAlloc API geeft in ieder geval executable memory terug, en anders VirtualAlloc daar kan je het helemaal zelf regelen. Ook moet je in windows FlushInstructionCache gebruiken nadat je de code gegenereerd hebt anders kan de CPU mogelijk gecachte code uitvoeren.

Een bijkomend probleem: de code moet zowel onder windows als onder Linux draaien, alhoewel dit op zich wel meevalt omdat er alleen een expressie geevalueerd word en er verder geen interactie met het OS is

Ik zou ook eens naar SoftWire kijken, heb het wel eens eerder gezien (maar niet serieus mee gewerkt), scheelt je het gedoe van opcodes genereren.

Ik zal 't eens bekijken.

[tomato]

Aaargh! schreef op 06 februari 2003 @ 19:26:
Word er onderscheid gemaakt tussen executable en niet executable geheugen dan ? iirc kan het IA32 gebeuren dit onderscheid helemaal niet maken.

Ik geloof dat het vooral bij RISC architecturen wenselijk is deels van Von Neumann af te stappen en exetutables en data te scheiden in het geheugen (of er zelfs een aparte bus voor te gebruiken).

Ik zou niet weten of en hoe dit in de praktijk gebeurt, verder heb ik er niet zoveel verstand van

Naar mijn weten is IA32 een CISC structuur (met wat kleine RICS trekjes), dus ik denk dat het onderscheid inderdaad niet gemaakt kan worden.

[.oisyn]

Aaargh! schreef op 06 februari 2003 @ 19:26:

Word er onderscheid gemaakt tussen executable en niet executable geheugen dan ? iirc kan het IA32 gebeuren dit onderscheid helemaal niet maken.

kan wel, lees de protected mode specs van intel er maar eens op na. Een data segment kan r of r/w zijn, een code segment kan r of r/x zijn.
In win32 toepassingen is het over het algemeen zo dat de code segment die in het register cs staat en het data segment wat in ds staat naar het zelfde geheugen wijzen (de selectors zijn wel anders, de data van cs moet tenslotte executable zijn). En aangezien ze naar hetzelfde stuk geheugen wijzen kun je ook gewoon je data beschrijven via ds en dan uitvoeren via cs, wat dus de default is als je data schrijft of springt naar een bepaald adres

[Aaargh!]

tomato schreef op 06 februari 2003 @ 20:01:
[...]
Naar mijn weten is IA32 een CISC structuur (met wat kleine RICS trekjes), dus ik denk dat het onderscheid inderdaad niet gemaakt kan worden.

Ik meen ooit een niet al te vriendelijk artikel gelezen te hebben waarin intel beschuldigd werd voor een groot deel v/d buffer overflow exploits juist omdat ze geen onderscheid maakten tussen executable en niet executable.

[Aaargh!]

NEways, weet iemand of er verschil is tussen de manier waarop je vanuit machine code blok data returned naar je c++ progje onder windows (C++ builder 6) en Linux (gcc) ? of is dat standaard ?

[.oisyn]

Aaargh! schreef op 06 February 2003 @ 20:05:
NEways, weet iemand of er verschil is tussen de manier waarop je vanuit machine code blok data returned naar je c++ progje onder windows (C++ builder 6) en Linux (gcc) ? of is dat standaard ?

je bedoelt het resultaat van een functieaanroep?

Dat is compilerspecifiek, maar over het algemeen wordt een 32 bits int geretourneerd in eax, een 64 bits int in edx:eax, en een floating point getal in ST(0) (bovenop de FPU stack dus)

Maar goed, dat is compilerspecifiek, dus het hoeft niet zo te zijn zoals ik het hier beschreef. Ik geloof dat VC++ z'n structs tot 64 bits ook in edx:eax teruggeeft, en anders heeft de functie een extra parameter waar het resultaat in moet komen te staan

[Soultaker]

.oisyn schreef op 06 February 2003 @ 20:08:
Maar goed, dat is compilerspecifiek, dus het hoeft niet zo te zijn zoals ik het hier beschreef. Ik geloof dat VC++ z'n structs tot 64 bits ook in edx:eax teruggeeft, en anders heeft de functie een extra parameter waar het resultaat in moet komen te staan

Je kunt natuurlijk altijd de standaard C calling convention forceren. Om je code nog enigszins portable te houden, is dat misschien verstandiger dan uitzoeken wat voor optimalere conventies je eigen compiler allemaal bedenkt.

Ik denk trouwens dat de default calling convention wel gestandaardiseerd is, want volgens mij is het geen enkel probleem om object files die door verschillende compilers gegenereerd zijn, aan elkaar te linken tot een werkend programma.

[ Voor 18% gewijzigd door Soultaker op 06-02-2003 20:23 ]

[Aaargh!]

Soultaker schreef op 06 februari 2003 @ 20:22:
[...]
Ik denk trouwens dat de default calling convention wel gestandaardiseerd is, want volgens mij is het geen enkel probleem om object files die door verschillende compilers gegenereerd zijn, aan elkaar te linken tot een werkend programma.

Volgens mij zijn er tussen gcc 2.9x en gcc 3.x wel problemen als je libraries (.a) uitwisselt

[.oisyn]

[nohtml]

Soultaker schreef op 06 February 2003 @ 20:22:
Je kunt natuurlijk altijd de standaard C calling convention forceren. Om je code nog enigszins portable te houden, is dat misschien verstandiger dan uitzoeken wat voor optimalere conventies je eigen compiler allemaal bedenkt.

hoe moet je dat forceren dan?
functies zijn in VC++ default __cdecl, maar er staat in de C standaard niet hoe een functie aangeroepen moet worden, of hoe iets geretourneerd moet worden. Je kan er weinig meer aan doen dan simpelweg doen hoe je compiler het ook doet

.edit: dat geldt overigens ook voor preservation van registers. In VC++ moeten ebx, esi en edi weer teruggebracht worden in hun oorspronkelijke staat als de functie retourneert. Van de segment registers weet ik het trouwens niet, maar het lijkt me dat es en ds (en uiteraard cs, maar dat is impliciet als je terug wil springen naar de caller ) bewaard moeten blijven. Maar goed, dat is VC++, misschien wil GCC weer heel wat anders

[ Voor 27% gewijzigd door .oisyn op 06-02-2003 20:40 ]

[Aaargh!]

Desnoods genereer ik 2 verschillende stukken code voor gcc en borland

[madwizard]

Met segment registers (cs/ds/es enzo) heb je weinig te maken in win32. Als het goed is raak je die nooit aan (met uitzondering van fs voor SEH (structured exception handling)). Ik weet niet of ergens in een standaard gedefinieerd is hoe de conventies zijn voor een C funtie maar vrijwel alle compilers die ik ken retourneren iig in eax, en ebx/esi/edi (en ebp/esp natuurlijk) moeten bewaard blijven (dat zijn ook de registers waar de win32 API niet aan komt dus wel een logische keus). Voor 64-bits is het meestal edx:eax dacht ik maar weet ik alleen zeker voor VC. Floating point idd op st0. Als je het zo onafhankelijk mogelijk wilt houden van de compiler kan je ook een varabele by reference meegeven waar het resultaat in opgeslagen wordt ipv return.

[MisterData]

Even tussendoor, waar halen jullie al die kennis over assembly vandaan?

[.oisyn]

Ik ben begonnen in een oud ms-dos boek ("200 utilities voor PC-DOS en MS-DOS"), daar heb ik basis asm uit geleerd. Kennis van de instructieset heb ik vooral uit de nasm documentatie (een opensource assembler). Verder zijn er nog allemaal asm optimization documenten te vinden. En kennis met betrekking tot protected mode en alles wat daarbij komt kijken heb ik uit de intel specs

[Aaargh!]

Ik heb nu het volgende stukje code:

code:

        tstmem = (char*) malloc(200);
        tstmem[0] = 0x9B; // finit
        tstmem[1] = 0xDB;
        tstmem[2] = 0xE3;
        tstmem[3] = 0xC7; // mov eax, 0004
        tstmem[4] = 0x00;
        tstmem[5] = 0x04;
        tstmem[6] = 0x00;
        tstmem[7] = 0x00;
        tstmem[8] = 0x00;
        tstmem[9] = 0xDB; // fild eax
        tstmem[10] = 0x00;
        tstmem[11] = 0xC7; // mov eax, 0002
        tstmem[12] = 0x00;
        tstmem[13] = 0x02;
        tstmem[14] = 0x00;
        tstmem[15] = 0x00;
        tstmem[16] = 0x00;
        tstmem[17] = 0xDB; // fild eax
        tstmem[18] = 0x00;
        tstmem[19] = 0xDE;
        tstmem[20] = 0xC9;
        tstmem[21] = 0x9B; // fwait
        tstmem[22] = 0xC3; // ret
        testfunc = (ffunc) tstmem;

        cout << testfunc() << endl;
        cout << testfunc() << endl;

Deze code runt prima de eerste keer dat ie gerunt word (gereturnde waarde is zoals verwacht), echter de 2e keer dat ik 'm aanroep krijg ik een segfault.

Iemand een idee wat er hier fout gaat ?

[madwizard]

Dit kan nooit goede code zijn, de mov eax, 4 die je in commentaar zet is volgens de hex codes een mov [eax], 4 en dat is heel wat anders (eerste zet 4 in eax, tweede zet 4 in de dword waar eax naar wijst. Eax wijst in jouw geval nergens naar dus hij zet een 4 op 1 of andere geheugenplaats. Afhankelijk van de assembler die de C++ code genereert is die plaats geldig (maar natuurlijk niet zinnig) of ongeldig, blijkbaar gaat het de eerste keer toevallig goed.
fild eax bestaat zelfs niet, je kunt alleen een geheugenadres meegeven waar de waarde (een real4/real8/real10 (=float/double/long double)) staat.
Dit is je code nu:

code:

 00000000: 9BDBE3         finit
 00000003: C70004000000   mov       d,[eax],000000004
 00000009: DB00           fild      d,[eax]
 0000000B: C70002000000   mov       d,[eax],000000002
 00000011: DB00           fild      d,[eax]
 00000013: DEC9           fmulp     st(1),st(0)
 00000015: 9B             fwait
 00000016: C3             retn

Ik kan wel een werkend voorbeeldje maken, zet hem zo wel in m'n post.

edit: hier is een werkend programma, doet wel iets anders (a*b+c^2).

code:

const unsigned char g_testCode[] =  //  calculates a * b + c * c
{
    0x9B,0xDB,0xE3,             // finit                    
    0xD9,0x44,0x24,0x04,        // fld       d,[esp][0004]  ; a         
    0xD8,0x4C,0x24,0x08,        // fmul      d,[esp][0008]  ; a*b       
    0xD9,0x44,0x24,0x0C,        // fld       d,[esp][000C]  ; a*b,c     
    0xD9,0xC0,                  // fld       st(0)          ; a*b,c,c   
    0xDE,0xC9,                  // fmulp     st(1),st(0)    ; a*b,c*c   
    0xDE,0xC1,                  // faddp     st(1),st(0)    ; a*b+c*c   
    0xC3,                       // retn
};

void main()
{
    typedef float (_cdecl * PtrFunc)(float a, float b, float c);

    unsigned char *pMem = new unsigned char[sizeof(g_testCode)];
    memcpy(pMem, g_testCode, sizeof(g_testCode));
    PtrFunc pFunc = reinterpret_cast<PtrFunc>(pMem);

    float a,b,c;

    a = 1.0f; b = 2.0f, c = 3.0f;
    cout << a << " * " << b << " + " << c << " * " << c << " = " << pFunc(a,b,c) << endl;
    
    a = 4.0f; b = 6.0f, c = 2.0f;
    cout << a << " * " << b << " + " << c << " * " << c << " = " << pFunc(a,b,c) << endl;

    delete[] pMem;
}

[ Voor 45% gewijzigd door madwizard op 08-02-2003 20:13 ]

[Zoijar]

Zoek ook eens op "BURS code generation"

[Aaargh!]

madwizard schreef op 08 February 2003 @ 19:45:
Dit kan nooit goede code zijn, de mov eax, 4 die je in commentaar zet is volgens de hex codes een mov [eax], 4 en dat is heel wat anders (eerste zet 4 in eax, tweede zet 4 in de dword waar eax naar wijst. Eax wijst in jouw geval nergens naar dus hij zet een 4 op 1 of andere geheugenplaats. Afhankelijk van de assembler die de C++ code genereert is die plaats geldig (maar natuurlijk niet zinnig) of ongeldig, blijkbaar gaat het de eerste keer toevallig goed.
fild eax bestaat zelfs niet, je kunt alleen een geheugenadres meegeven waar de waarde (een real4/real8/real10 (=float/double/long double)) staat.

Ik zie 't probleem ja, duurde ff voordat ik die adressing methodes doorhad. (zijn er ook veel te achterlijk veel)
Beetje vreemd dat de fpu alleen uit een geheugenlocatie kan lezen en geen immediate adressing ondersteund, dat zou in dit geval nl. veel handiger zijn, dit kost weer een extra geheugen access.

[Aaargh!]

De simpele instructies zitten er nu in. (+, -, *, /, sin, cos) en een aantal wat complexere moeten er nog in (tan, atan, modulo, machtsverheffen).
De functie is nu een factor 20 sneller