[C++] Meerdimensionale arrays met variabele grootte

[Opi]

Sinds enige tijd ben ik noodgedwongen bezig met C++.
Leuk en vrolijk programma (al prefereer ik Matlab, mar dat is soms gewoon te langzaam).

Het probleem waar ik nu al enige tijd mee zit is dat ik een meer dimensionale array wil gebruiken waarvan de grootte pas in het programma wordt vastgelegd. Vectoren van variabele grootte leveren geen probleem op, maar om een of andere reden lukt het me niet om hetzelfde bij een meerdimensionale array voor elkaar te krijgen. Is dit uberhaupt mogelijk en zo ja, hoe kan ik dit doen?

[whoami]

pointers.

[Glimi]

Uhm, je kunt toch een Vector van Vectoren maken? Dan heb je in princiepe hetzelfde

Maar iets meer info over wat niet lukt ed. zou wel makkelijk zijn

[whoami]

Ik zie, net als glimi het probleem niet an een vector binnen een vector.

[curry684]

Als je noodgedwongen bezig bent zou ik die vectors eens opzoeken idd, anders ga je erg snel erg veel sterretjes zien

Correct iig volgens de 'klassieke methode' voor bijv. een meerdimensionale array van ints:

C:

int** l_Ints;
int    l_Index;

l_Ints = new int*[ResolutieA];
for(l_Index = 0; l_Index != ResolutieA; l_Index++)
  l_Ints[l_Index] = new int[ResolutieB];
l_Ints[x][y] = value;   // etc

[MSalters]

curry684 schreef op 02 June 2003 @ 21:33:
Als je noodgedwongen bezig bent zou ik die vectors eens opzoeken idd, anders ga je erg snel erg veel sterretjes zien

Correct iig volgens de 'klassieke methode' voor bijv. een meerdimensionale array van ints:

C:

int** l_Ints;
int    l_Index;

l_Ints = new int*[ResolutieA];
for(l_Index = 0; l_Index != ResolutieA; l_Index++)
  l_Ints[l_Index] = new int[ResolutieB];
l_Ints[x][y] = value;   // etc

Nee, dat is geen meerdimensionale array. Dat is een array van pointers. Een meerdimensionale array is een array van arrays.

De correcte methode is

C++:

int* Arr2D;
Arr2D = new int[ ResolutieX * ResolutieY ];
Arr2D[x + y*ResolutieX] = value;

Niet echt handig, maar wel precies waar de TS om vroeg. Of hij dat zo bedoelde, dat weet ik natuurlijk niet. Het is wel de methode om de laatste procent snelheid te pakken.

_{nitpick:code=c en dan toch new}

[esf]

MSalters schreef op 02 juni 2003 @ 22:08:
[...]

Nee, dat is geen meerdimensionale array. Dat is een array van pointers. Een meerdimensionale array is een array van arrays.

De correcte methode is

C++:

int* Arr2D;
Arr2D = new int[ ResolutieX * ResolutieY ];
Arr2D[x + y*ResolutieX] = value;

Niet echt handig, maar wel precies waar de TS om vroeg. Of hij dat zo bedoelde, dat weet ik natuurlijk niet. Het is wel de methode om de laatste procent snelheid te pakken.

Dit is geen array van arrays, maar een enkelvoudige array, of heb ik het nou fout? De oplossing van curry684 lijkt me in ieder geval meer een tweedimensionale array..

[ Voor 12% gewijzigd door esf op 02-06-2003 22:32 ]

[curry684]

MSalters schreef op 02 juni 2003 @ 22:08:
Nee, dat is geen meerdimensionale array. Dat is een array van pointers. Een meerdimensionale array is een array van arrays.

Nou wil ik niet moeilijk doen maar ik gaf juist een array van arrays en jij niet?

Op zich is jouw methode even correct maar beperkt tot vierkante arrays, waar ik gehinderd door enige voorkennis van Matlab de methode gaf om net als in dat programma 'creatief' gevormde arrays te vormen

Grootste bezwaar is dat jij geen meerdimensionale array aanmaakt maar een 1-dimensionale die je mishandelt als meerdimensionale. Volgens mij klopt je claim over performance ook niet, omdat die ene memory lookup plus een lineaire lookup van mij volgens mij sneller is dan de arithmetic unit vragen om een vermenigvuldiging (waarbij ik er vanuit ga dat je niet met een const width van 2 ^ x gaat werken zodat er bitshifts ingeoptimaliseerd komen ). Maja dat zal ook van caches en code prediction afhangen, dus kan wellicht per CPU varieren.

_{nitpick:code=c en dan toch new}

[/quote]
Betrapt, ik was oprecht van plan malloc te gaan gebruiken toen ik die 2 backspaces over C++ uitvoerde

[hobbit_be]

curry684 schreef op 02 June 2003 @ 22:56:
Volgens mij klopt je claim over performance ook niet

Dat denk ik toch wel hoewel jouw Array idd meer een echte Array 2 Array is (zover dat bestaat in C++ - een int[3][4] is intern ook een int[12]. ) zoals we die gewend zijn van euh- scripting talen en je idd dus een niet reguliere array in jouw geval kunt hebben.

Maar een array[y*w+x] is een imul (als ie voor een of andere reden niet alignd zou zijn anders gaat ie gewoon shl) + een add wat mooi in 1 lea past. Maw 1 clock om de plaats te vinden + grotere kans dat ze in dezelfde mem cache-lijn zitten.

Tis maar of je een multidimensionele wilt of een array of arrays wat toch conceptueel net iets anders is. persoonlijk zou ik voor dit geval gewoon std:vector loslaten... (dus een Array Of Arrays . Of effe een Matrix klasse maken

[curry684]

hobbit_be schreef op 02 June 2003 @ 23:07:
Maar een array[y*w+x] is een imul (als ie voor een of andere reden niet alignd zou zijn anders gaat ie gewoon shl) + een add wat mooi in 1 lea past. Maw 1 clock om de plaats te vinden + grotere kans dat ze in dezelfde mem cache-lijn zitten.

* curry684 heeft zich sinds de MC68000 niet meer beziggehouden met klokcycli-per-instructie ratios en gaat zich dus maar gewoon in een hoekje schamen of zo

[Eelis]

.

[ Voor 98% gewijzigd door Eelis op 18-02-2015 19:46 ]

[farlane]

Ik vraag me af wat precies de reden is dat je Matlab verkiest boven C++ ?

Het ene is een wiskundig pakket met scripting mogelijkheid, het andere een programmeertaal. Zijn dit niet de spreekwoordelijke appels en peren ?

[curry684]

Om de Matlab taal 'een scripting mogelijkheid' vind ik wat disrespectvol voor een pakket waarin je tot op zekere hoogte applicaties kunt ontwikkelen. Aan de andere kant heb je volledig gelijk als je stelt dat je het dan nog steeds niet mag vergelijken met een fully fledged taal als C++

[.oisyn]

MSalters schreef op 02 June 2003 @ 22:08:
[...]

Nee, dat is geen meerdimensionale array. Dat is een array van pointers. Een meerdimensionale array is een array van arrays.

De correcte methode is

C++:

int* Arr2D;
Arr2D = new int[ ResolutieX * ResolutieY ];
Arr2D[x + y*ResolutieX] = value;

Niet echt handig, maar wel precies waar de TS om vroeg. Of hij dat zo bedoelde, dat weet ik natuurlijk niet. Het is wel de methode om de laatste procent snelheid te pakken.

_{nitpick:code=c en dan toch new}

grappig, ik meen me te herinneren dat dit probleem een jaar geleden ook was, en toen kwam ik met deze oplossing, en jij als reactie daarop met een std::vector<std::vector<T> > oplossing

En ja, ik zweer nog steeds bij contiguous memory blocks en dus een enkeldimensionale arrays waar je zelf de indexing regelt (al dan niet geencapsuleerd in een klasse)

[.oisyn]

hobbit_be schreef op 02 June 2003 @ 23:07:
Maar een array[y*w+x] is een imul (als ie voor een of andere reden niet alignd zou zijn anders gaat ie gewoon shl) + een add wat mooi in 1 lea past. Maw 1 clock om de plaats te vinden + grotere kans dat ze in dezelfde mem cache-lijn zitten.

De enige imuls die in een lea passen zijn *1, *2, *4 en *8, dat gaat dus niet helemaal op. Bovendien was het dynamisch, dus dan zul je ook dynamisch je assembly moeten genereren... dat lijkt me een beetje overkill voor simpele arrays

Bovendien is een imul tegenwoordig ook gewoon 1 cycle, en dus denk ik dat je er wat cache betreft meer voordeel van zult hebben dan een array van pointers

[Opi]

Alvast bedankt voor de hulp die geboden is, ik zal alles doornemen, maar wil van tevoren mijn dank al uitspreken.

Matlab gebruik ik voor het maken van simulaties en controllers. Het nadeel is dat Matlab erg traag is met loops en dus niet meer real-time gebruikt kan worden. Het grootte voordeel van Matlab is het gemak waarmee je kan prutsen met arrays (ook multidimensionaal ).

Vectoren klus is als volgt:

C:

double  *variabele;
int var2;

var2 = 10 //voorbeeldwaarde

variabele = new double[var2];

Ik heb eerder al problemen gehad die hier op leken maar toen heb ik hetzelfde gedaan als MSalters. Nu wil ik eigenlijk gewoon (?) proberen om een meerdimensionale array te maken op een ietwat inzichtelijkere manier. Normaliter kan je ook een array aan maken die uit meer dimensies bestaat (zie hieronder), maar dit gaat niet langer op als je de grootte niet van te voren al definieerd.

C:

double variabele[4][5];

[hobbit_be]

.oisyn schreef op 03 June 2003 @ 10:56:
[...]
De enige imuls die in een lea passen zijn *1, *2, *4 en *8, dat gaat dus niet helemaal op. Bovendien was het dynamisch, dus dan zul je ook dynamisch je assembly moeten genereren... dat lijkt me een beetje overkill voor simpele arrays

idd what die LEA betreft. Maar je vergeet dat een imul edx vuil maakt wat erg rot is voor een optimizing assembler. Wat dat dynamisch inhoud = sizeof(X)*5 = 5*sizeof(X). Zolang je array dus element van hetzelfde type inhoud gaat de compiler automatisch dit toepassen (wat de size van je array ermee te maken heeft?). Overigens nog een 'leuke' list:

http://www.azillionmonkeys.com/qed/amultl2.html

er nog wel bijzeggen dat als je de meeste compilers loslaat hij elke struct gaat power of 2 alignen wat dus een shl is + add (en die shl heeft dan weer niet de nefaste edx gevolg).

[.oisyn]

hobbit_be schreef op 03 June 2003 @ 13:23:
Maar je vergeet dat een imul edx vuil maakt wat erg rot is voor een optimizing assembler.

imul eax, ebx -> eax wordt vermenigvuldigd met ebx

jij bent waarschijnlijk in de war met de single-operand imul, die idd een 64 bits resultaat wegschrijft naar edx:eax

Wat dat dynamisch inhoud = sizeof(X)*5 = 5*sizeof(X). Zolang je array dus element van hetzelfde type inhoud gaat de compiler automatisch dit toepassen (wat de size van je array ermee te maken heeft?).

Hier snap ik niets van. Wat bedoel je precies?

er nog wel bijzeggen dat als je de meeste compilers loslaat hij elke struct gaat power of 2 alignen wat dus een shl is + add (en die shl heeft dan weer niet de nefaste edx gevolg).

de meeste compilers alignen op veelvouden van 4 of 8 bytes, en dus niet op machten van 2. Ik heb zelfs nog nooit een compiler gezien die bijvoorbeeld van een 48 byte struct een 64 byte struct maakt

[hobbit_be]

.oisyn schreef op 03 June 2003 @ 15:43:
[...]
jij bent waarschijnlijk in de war met de single-operand imul, die idd een 64 bits resultaat wegschrijft naar edx:eax

nooit geweten dat daar een verschil tussen bestond. (ik neem aan dat dit PII>?) aldus toch . imul dus

[MSalters]

.oisyn schreef op 03 juni 2003 @ 10:35:
[...]


[1D array mishandelen als 2D]grappig, ik meen me te herinneren dat dit probleem een jaar geleden ook was, en toen kwam ik met deze oplossing, en jij als reactie daarop met een std::vector<std::vector<T> > oplossing

En ja, ik zweer nog steeds bij contiguous memory blocks en dus een enkeldimensionale arrays waar je zelf de indexing regelt (al dan niet geencapsuleerd in een klasse)

[/quote]Oh, ik zou zelf nog steeds die vector<vector<T> > gebruiken. M'n reactie was alleen het ophelderen van het verschil tussen twee bijna dezelfde dingen (array van array vs array van pointers)

[.oisyn]

hobbit_be schreef op 03 juni 2003 @ 18:07:
[...]


nooit geweten dat daar een verschil tussen bestond. (ik neem aan dat dit PII>?) aldus toch . imul dus

386 and above
http://home.attbi.com/~fb...docb.html#section-B.4.118

[ Voor 14% gewijzigd door .oisyn op 03-06-2003 21:48 ]

[AFR]

OpifexMaximus schreef op 03 juni 2003 @ 10:59:
...
Matlab gebruik ik voor het maken van simulaties en controllers. Het nadeel is dat Matlab erg traag is met loops en dus niet meer real-time gebruikt kan worden. Het grootte voordeel van Matlab is het gemak waarmee je kan prutsen met arrays (ook multidimensionaal ).
...

Als de C++ code die je wilt gaan maken verband houdt met MATLAB zaken, moet je eens kijken naar de mogelijkheden van MATLAB MEX en S-Functies. Deze functies kun je o.a. schrijven in C/C++ en tegelijkertijd gebruik maken van de MATLAB API waarin veel bruikbare functies zitten voor matrix bewerkingen. De gecompileerde code is snel (ter illustratie: op mijn P600 stuur ik real-time een complexe controller aan op 5kHz, terwijl graphics gewoon via simulink worden geupdate )

[Opi]

AFR schreef op 03 June 2003 @ 23:54:
[...]


Als de C++ code die je wilt gaan maken verband houdt met MATLAB zaken, moet je eens kijken naar de mogelijkheden van MATLAB MEX en S-Functies. Deze functies kun je o.a. schrijven in C/C++ en tegelijkertijd gebruik maken van de MATLAB API waarin veel bruikbare functies zitten voor matrix bewerkingen. De gecompileerde code is snel (ter illustratie: op mijn P600 stuur ik real-time een complexe controller aan op 5kHz, terwijl graphics gewoon via simulink worden geupdate )

Ben ik nu ook druk mee bezig. Helaas waren mijn C++-skills nagenoeg nul. Helaas wordt een groot deel van de code die bij C++ toegevoegd wordt om er een S-functie van te maken maar erg summier uitgelegd op de site van Mathworks.

[AFR]

OpifexMaximus schreef op 04 juni 2003 @ 09:52:
[...]

Ben ik nu ook druk mee bezig. Helaas waren mijn C++-skills nagenoeg nul. Helaas wordt een groot deel van de code die bij C++ toegevoegd wordt om er een S-functie van te maken maar erg summier uitgelegd op de site van Mathworks.

De online handleiding was altijd nogal beperkt, maar versie 5 van de gedrukte manual "Simulink - Writing S-Function" geeft een redelijke introductie. Dit document is ook als pdf-versie beschikbaar. Hierin staat ook een grafische versie van de S-function builder beschreven die minder flexibel is als zelf geschreven code, maar wel handig is voor een beginner.

Ook kun je via de matlab forums voorbeeld code vinden, voornamelijk in C ipv C++

[Opi]

* Klein schopje omdat m'n nieuwe vraag veel overeenkomsten heeft met dit probleem. *

Hoe kan je in hemelsnaam een array maken waarvan het aantal dimensies vooraf niet bepaald is? Je zou dan een n-aantal loops moeten definiëren, maar ook een pointer die n * er voor heeft (beetje dubieus uitgelegd ). Is zoiets mogelijk? Het lijkt mij wel aangezien Matlab gebaseerd is op C++ en het hierin ook mogelijk is.

[curry684]

Ga je eens snel verdiepen in het concept OOP Je maakt gewoon template-objecten die arrays bevatten, en die dus ook arrays van arrays van arrays van arrays kunnen bevatten

[MSalters]

curry684 schreef op 13 June 2003 @ 13:02:
Ga je eens snel verdiepen in het concept OOP Je maakt gewoon template-objecten die arrays bevatten, en die dus ook arrays van arrays van arrays van arrays kunnen bevatten

OOP != templates. Templates vallen onder Generic Programming, dat is een ander gebied.

Evengoed is er met templates of OO nog steeds het probleem dat je pointers geen dynamisch aantal * kan bevatten. Als je een pointer twee maal dereferencet heb je een 2D array; met 3 een 3D array. Types zijn statisch.

Maar zoals mijn code boven laat zien heb je voor echte arrays van arrays ( en arrays van arrays van arrays ) maar een * nodig. De vermenigvuldigingen die nodig zijn kun je wel in een loopje zetten.

[Korben]

MSalters schreef op 13 June 2003 @ 23:10:
[...]

Evengoed is er met templates of OO nog steeds het probleem dat je pointers geen dynamisch aantal * kan bevatten.

Als je je template(klasse) goed schrijft, hoeft dat ook niet.

[ Voor 16% gewijzigd door Korben op 14-06-2003 01:51 ]

[curry684]

MSalters schreef op 13 June 2003 @ 23:10:
OOP != templates. Templates vallen onder Generic Programming, dat is een ander gebied.

Dat zei ik ook niet. Ik zei: ga je verdiepen in OOP zodat je een nested class-tree kunt bouwen om je multidimensionale arrays te bouwen. Dat ik als suggestie het bijwoord 'template' toevoegde was enkel een technische hint die het resultaat vele malen sneller maakt dan met virtual base classes

[Opi]

Wellicht overbodig, maar conform de policy van P&W post ik toch maar het resultaat.

C++:

#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


main()
{
    int rows;
    int columns;
    int i, j;
    double a;

    srand ( time(NULL) );

    rows = 5;
    columns = 10;

    /* initiate 2D array */
    double **array_1;
    array_1 = new double*[rows];
    array_1[0] = new double[rows*columns];
    for (i = 1; i < columns; i++)
    {
        array_1[i] = array_1[i-1] + columns;
    }
    
    /* input random values between 0 and 1 */
    for (i=0; i < rows; i++) 
    {
        for (j=0; j < columns; j++) 
        {
            a = rand();
            array_1[i][j]= a/RAND_MAX;
        }
    }

    /* print data to make sure it works */
    for (j = 0; j < columns; j++)
    {
        for (i=0;i<rows;i++) 
        {
            cout << i << " " << j << " " << array_1[i][j] << endl;
        }
    }

    delete array_1[0];
    delete array_1;

    return 0;
}

[.oisyn]

Wel een beetje vage constructie, waarom alloceer je niet gewoon rows keer columns doubles?

En die delete's op het eind moeten delete[]'s zijn

[Opi]

.oisyn schreef op 22 September 2003 @ 16:29:
Wel een beetje vage constructie, waarom alloceer je niet gewoon rows keer columns doubles?

Was ook lang zoeken hoor. Ik wilde expres een 2D-array hebben, zodat het overzichtelijker zou zijn.

En die delete's op het eind moeten delete[]'s zijn

Dank u.

[bille]

@TS: MOET je persee met C++ werken? of kan je ook gebruik maken van JAVA? JAVA heeft als ik dit zo lees een stuk eenvoudigere (en waarschijnlijk ook snellere, afhankelijk van compiler that is bijv. Jikes) implementatie van multidimensionale arrays.

Misschien een beetje buiten de scope van de vraag, maar als je graag iets sneller met multidimensionale arrays wilt werken t.b.h.v. deceision support systems of NLP problemen dan kan ik je aanraden om eens te kijken naar bijvoorbeeld AIMMS of Lingo8.

Houdt er wel rekening mee dat doorgaans de snelheid uit zo'n systeem komt door intelligente data pruning e.d. dus het verminderen van het aantal mogelijkheden van de beslissingsvariabelen e.d.

[.oisyn]

bille schreef op 22 September 2003 @ 16:49:
@TS: MOET je persee met C++ werken? of kan je ook gebruik maken van JAVA? JAVA heeft als ik dit zo lees een stuk eenvoudigere (en waarschijnlijk ook snellere, afhankelijk van compiler that is bijv. Jikes) implementatie van multidimensionale arrays.

please, don't make me laugh
Dat je meer moet doen wil nog niet zeggen dat het langzamer is. Array acces is in Java gewoon trager dan in C++, dat is een keiharde feit waar je gewoon niet onderuit komt. Dat komt omdat er in java gekeken moet worden naar de array boundaries, zodat er een IndexOutOfBounds exceptie gegooid kan worden als er buiten het bereik van de array wordt gelezen of geschreven. En ja, dat kost nu eenmaal tijd, hoe je het ook optimaliseert

[bille]

[offtopic]

Dat komt omdat er in java gekeken moet worden naar de array boundaries

en

Dat je meer moet doen wil nog niet zeggen dat het langzamer is

lol.. spreek jij jezelf ff tegen

behalve dan dat de TS nu gebruik maakt van een zelf geconstrueerde methode die hoogstwaarschijnlijk verre van efficient is... terwijl je in JAVA gebruik maakt van een uiterst geoptimimaliseerde array methode, die nog eens gehotspot compiled wordt naar machiene code die zeker zo snel kan zijn als iedere C++ methode..

Je probeert waarschijnlijk te zeggen dat je denkt dat C++ altijd sneller is omdat het niet door een virtual machine gedraaid hoeft te worden. Ik denk dat je je hier wel eens in kan gaan vergissen, gezien de hedendaagse JAVA compilers ook naar geoptimaliseerde machiene code compilen net zoals C++ compilers. JAVA is wel iets trager in het opstarten idd, omdat de VM ff geboot moet worden, maar je zal zien als je een app. voor de 2e keer draait dat je dezelfde performance kan halen als een C++ app.

[Soultaker]

Daarbij komt nog eens dat Java helemaal geen multidimensionale arrays kent (zoals bijvoorbeeld .NET die wil kent) maar alleen de al eerder genoemde jagged arrays, oftewel arrays van arrays. Het aanmaken en benaderen van de laatstgenoemde soort array is minder efficient aangezien per dimensie een extra indirectiestap genomen moet worden, terwijl voor een 'echte' multidimensionale array slechts eenmaal de index berekend hoef te worden, waarna een enkele indirectiestap genoeg is (net als bij een eendimensionale array).

Daarbij komt dat arrays in Java (en ook in .NET, trouwens) gerepresenteerd worden als een soort objecten. Een multidimensionale Java array is dus meer te vergelijken met het eerder genoemde voorbeeld van vectoren met vectoren erin.

C/C++ biedt wel beperkte ondersteuning voor meerdimensionale arrays, maar uitsluitend at compile time (dus niet 'dynamisch'). At run time zul je de berekeningen die normaal gesproken door de compiler voor je uitgevoerd worden, zelf moeten doen, zoals MSAlters al voordeed. Als snelheid niet van kritiek belang is, dan kun is de keuze voor vectors-in-vectors ook gewoon geschikt. Eventueel kun je als tussenvorm nog kiezen voor de methode die curry beschreef, waarbij je arrays-in-arrays maakt.

[.oisyn]

bille schreef op 22 september 2003 @ 17:02:

offtopic:
[...]
en
[...]
lol.. spreek jij jezelf ff tegen

ik had het over "meer code", en spreek mezelf dus verre van tegen.
in java kun je een new int[3][4] doen, in C++ moet je iets moeilijker doen. Ik dacht dat je daarop ook doelde

behalve dan dat de TS nu gebruik maakt van een zelf geconstrueerde methode die hoogstwaarschijnlijk verre van efficient is... terwijl je in JAVA gebruik maakt van een uiterst geoptimimaliseerde array methode, die nog eens gehotspot compiled wordt naar machiene code die zeker zo snel kan zijn als iedere C++ methode..

Een array is gewoon een stuk geheugen. De snelste manier is gewoon heel simpel met wat pointer arithmetic, en een asm mov instructie. C++ code compileert hiernaar, in Java heb je er nog een VM tussen zitten. In het voordeligste geval compileert java naar dezelfde code, maar dan is het dus nog niet sneller. Het is hoogstens even snel. Dus waarom je zegt dat java sneller is vraag ik me af.

En daar komt dus nog eens bij dat in java de array bounds gecontroleerd moeten worden, zodat je niet buiten de array kan lezen/schrijven. Die extra check, die onder water gebeurt, kost ook tijd, en dat heb je in C++ niet

Je probeert waarschijnlijk te zeggen dat je denkt dat C++ altijd sneller is omdat het niet door een virtual machine gedraaid hoeft te worden. Ik denk dat je je hier wel eens in kan gaan vergissen, gezien de hedendaagse JAVA compilers ook naar geoptimaliseerde machiene code compilen net zoals C++ compilers. JAVA is wel iets trager in het opstarten idd, omdat de VM ff geboot moet worden, maar je zal zien als je een app. voor de 2e keer draait dat je dezelfde performance kan halen als een C++ app.

Zoals ik hierboven al zei, net zo snel != sneller, en dat is wel wat jij beweerde

[Soultaker]

bille schreef op 22 September 2003 @ 17:02:
Je probeert waarschijnlijk te zeggen dat je denkt dat C++ altijd sneller is omdat het niet door een virtual machine gedraaid hoeft te worden. Ik denk dat je je hier wel eens in kan gaan vergissen, gezien de hedendaagse JAVA compilers ook naar geoptimaliseerde machiene code compilen net zoals C++ compilers. JAVA is wel iets trager in het opstarten idd, omdat de VM ff geboot moet worden, maar je zal zien als je een app. voor de 2e keer draait dat je dezelfde performance kan halen als een C++ app.

Je vertelt een bekend verhaal, dat ik al erg vaak gehoord heb, maar dat in de praktijk steeds niet van toepassing blijkt te zijn. Ik heb het verhaal dan ook nooit onderbouwd gezien met praktijkgegevens zoals benchmarks op reeele toepassingen.

Ik heb al een aantal keer optimistisch een projectje geschreven in Java en dat dan later omgezet in C/C++ om te vergelijken of het verschil inderdaad verwaarloosbaar is. Nog steeds kwam ik elke keer op een constante factor (zeg, 2 tot 5) snelheidsverschil uit; dat is niet acceptabel!

Het probleem is dat je de mogelijkheden van compilers en optimizers overschat. Weliswaar is er een heleboel mogelijk, maar een compiler zal nooit de intentie van je programma volledig doorgronden. Een conservatieve optimizer zal dus altijd optimalisatiemogelijkheden onbenut laten. De Java taal en platform bieden een vrij beperkt aantal mogelijkheden om een programma mee te implementeren. Je ontkomt er dus niet aan dat je bij Java moet kiezen voor concepten die niet optimaal aansluiten bij het probleem dat je probeert op te lossen. Je kunt dan hopen dat de compiler die ineffecientie herkend en omzeilt, maar meestal gebeurt dat niet.

[.oisyn]

Vergeet ook niet dat simpele integer en pointer arithmetic gewoonweg niet meer te optimaliseren is door een compiler. De CPU's van tegenwoordig hebben een uitstekende branchprediction en cache, en het boeit dus ook weinig met wat voor code je bij de data kan komen. En dan maakt het ook niet uit of het op een athlon of op een pentium draait, het kan gewoon niet sneller.

Dat is een ander verhaal met ingewikkelde floating point berekeninge, want dan komen de verschillen tussen verschillende types CPU's aan de orde. Denk aan speciale instructiesets zoals 3dnow, SSE en SSE2. Pas dan maakt het uit dat je goed optimaliseert, en ook dan kan een JIT compiler pas veel uitmaken tov van tevoren gecompileerde code.

Nou doe ik zelf veel met computer graphics en gamedevelopment, en daarin is performance essentieel. Ik heb serieus een idee uit zitten denken waarbij je in een soort C-like taal vector en matrix-operaties kunt definieren, wat vervolgens naar byte-code gecompileerd wordt. Bij het opstarten van het programma wordt deze bytecode vervolgens omgezet naar een zo efficient mogelijke machinetaal, waarbij je de specificaties van de huidige processor in acht neemt. Dit scheelt je ten eerste het coden van extra codepaths voor verschillende CPU's, en ten tweede kan er bij een nieuwe processor met weer extra instructies simpelweg een nieuwe translation unit worden gebruikt voor de bytecode, en kan er gelijk gebruik van gemaakt worden.

Dus geloof me, het nut van JIT compiling zie ik echt wel hoor, alleen je moet wel de juiste toepassing ervoor gebruiken, en bij het probleem van de topicstarter is het dus totaal niet van belang

[bille]

Ik dacht dat je daarop ook doelde

nah dat bedoelde ik niet, dus ik heb jouw antwoord ook niet helemaal goed geinterpreteerd.

Waar ik op doelde: de methode die de TS gebruikt voor het het werken met multidimensionale arrays is niet een geoptimaliseerd algoritme. Bijv: wat doe je als je een array gaat kopieren? of het toevoegen van een object aan een array. Je kan het zelf programmeren, maar als je niet een wiskundige bent raad ik je dat af.

De methoden die je ervoor gebruikt in JAVA zijn zo ontworpen dat ze vertaald naar bijv. Assembler (waar er feitelijk geen verschil meer zou mogen zijn tussen JAVA en C++) zo efficient mogelijk zijn (dus zo min mogelijk clockcycli etc). Wanneer je dus je eigen methoden gaat verzinnen voor C++ dan heb je kans dat je (door onwetendheid) misschien wel functies gaat gebruiken die vertaald naar Assembler een stuk inefficienter zijn dan de JAVA tegenhangers.

Wellicht dat wanneer je alle functies puur in 10 zou schrijven dat je met C++ sneller zou kunnen zijn.. Nog afgezien van het feit dat je in C++ dan weer extra functies moet gaat utilizen om te voorkomen dat je buiten je array gaat schrijven en bufferoverflows gaat krijgen. JAVA kent daar geoptimaliseerde functies voor die onderdeel zijn van de VM dus direct in machine code zijn gecompiled (net als je met C++ doet) .. geen de-langzame-VM smoesjes meer dus .. Om nog maar te zwijgen over het feit dat als je met ontzettend grote hoeveelheiden data werkt in de arrays je in C++ handmatig je geheugen moet gaan schoonmaken of zeg ik nou iets heels stoms

maar goed.. genoeg offtopic gemeuk, deze discussie gaat door totdat we met harde bewijzen komen waarschijnlijk.. en die zijn een stuk moeilijker te procuderen dan alleen maar ff een arraytest proggie draaien.. want zoals ik zeg: je programma doet niet alleen iets met arrays.. er zijn meer factoren die invloed hebben op de totale performance + dat de tijd ik investeer om die buggy C++ app. opnieuw op te starten niet meegerekend wordt in de totale rekentijd

owja: ik heb het wel met je eens dat er idd wel een zooi trage java apps zijn.. maarja... niet iedereen kan goed programmeren helaas.. er wordt echt veel zooi gemaakt door omgeschoolde politieagentjes die van toeten-nog-blazen weten

[ Voor 3% gewijzigd door bille op 22-09-2003 17:41 . Reden: blabla ]

[.oisyn]

bille schreef op 22 September 2003 @ 17:35:
Waar ik op doelde: de methode die de TS gebruikt voor het het werken met multidimensionale arrays is niet een geoptimaliseerd algoritme. Bijv: wat doe je als je een array gaat kopieren? of het toevoegen van een object aan een array. Je kan het zelf programmeren, maar als je niet een wiskundige bent raad ik je dat af.

dat is niet een verschil in taal, maar een verschil in het gebruik van libraries. Java vs. C++ is dan ook totaal niet relevant. In C++ heb je de STL, die met een zooi containers komt. Pak daar boost bij, en je hebt ook nog eens multidimensional containers. En ja, het is natuurlijk wel een kwestie van de juiste container kiezen voor de juiste taak, maar de taal is dan compleet niet meer relevant. Je hebt het dan immers over algoritmen.

Om nog maar te zwijgen over het feit dat als je met ontzettend grote hoeveelheiden data werkt in de arrays je in C++ handmatig je geheugen moet gaan schoonmaken of zeg ik nou iets heels stoms

In java gebeurt dat idd onder water, maar dat is overigens helemaal geen probleem als je een wat ervarender programmeur bent. Maar dat maakt Java wel gelijk bloated en wat instabieler kwa timing, omdat je geen controle hebt over wanneer je je geheugen vrij wilt geven.

maar goed.. genoeg offtopic gemeuk, deze discussie gaat door totdat we met harde bewijzen komen waarschijnlijk.. en die zijn een stuk moeilijker te procuderen dan alleen maar ff een arraytest proggie draaien.. want zoals ik zeg: je programma doet niet alleen iets met arrays.. er zijn meer factoren die invloed hebben op de totale performance.

http://www.oisyn.nl/homeboxx/
Array snelheid zijn voor het tekenen van de view essentieel voor die applet. Een leuk weetje: er wordt (zoals gewoonlijk) gebruik gemaakt van een z-buffer op per pixel diepteinformatie bij te houden. Dat is gewoon een lineaire array. De access van de z-buffer tijdens het tekenen zorgt gewoon voor een daling van bijna factor 2 in snelheid. Oftewel, als ik de zbuffer wegcomment dan loopt de app bijna 2x zo snel. En dat voor simpelweg een waarde opvragen uit een array, en die evt. weer aanpassen! Dat is gewoon niet normaal! De rede hiervoor is mijns inziens gewoon de checks voor de index, dat zijn natuurlijk 2 compares en conditional jumps per array access, en dat voor 2x een arrayaccess (1x lezen, en evt. nog 1x schrijven) doet het het hele renderproces de das om

Multitexturing is in zo'n geval gewoon onbegonnen werk. De rekencapaciteit is er wel, maar het is gewoonweg veel en veel te traag om er nog een array bij te hebben voor de andere texture

owja: ik heb het wel met je eens dat er idd wel een zooi trage java apps zijn.. maarja... niet iedereen kan goed programmeren helaas.. er wordt echt veel zooi gemaakt door omgeschoolde politieagentjes die van toeten-nog-blazen weten

gelukkig hoef ik me niet te orienteren op voorbeelden van anderen, ik heb eigen ervaringen met zowel C++ als Java

[Opi]

bille schreef op 22 September 2003 @ 16:49:
@TS: MOET je persee met C++ werken?

Ik ben bang van wel aangezien deze code voor S-functies in matlab gebruikt gaat worden. Alternatieven zijn overigens heel erg welkom; kan ik beter de vector.h-klasse gebruiken (zal wel geen fatsoenlijk jargon zijn)? Of zijn er nog andere alternatieven?

[Soultaker]

off-topic:

.oisyn schreef op 22 September 2003 @ 17:52:
http://www.oisyn.nl/homeboxx/

Cool; je hebt shading en (meer) textures toegevoegd! Echt vlot is 'ie nog niet, trouwens (9.4 FPS onder FreeBSD met een Pentium III op 550MHz) en daardoor is het soms moeilijk om de trappen op te lopen; het lijkt alsof je sneller terugvalt met een lagere framerate (ik neem aan dat dat niet de bedoeling is!).

Die applet geeft trouwens wel aan dat er in de praktijk wel degelijk problemen zijn met de performance van Java, want als je daar in de jaren 90 mee aan was komen zetten (draaiende op een 486 DX) dan zou je in de demoscene keihard uitgelachen zijn!

[.oisyn]

Ja, HTC heeft gevraagd of dingen geupdate konden worden, er zijn een aantal muren en een lift enzo bijgekomen. Gelijk van de gelegenheid gebruik gemaakt om wat prerendered textures te maken. Ik heb mijn renderroutine wat geoptimaliseert door gebruik te maken van een ander algoritme, maar echt veel meer is er niet aan te doen. Dat is ook het grote verschil met de demoscene van toen. Toen ging je van C source naar assembly, en alle instructies zo rangschikken zodat je optimaal gebuik maakt van de pipeline. Dat kan in java niet, en de compilers zijn nog altijd niet zo goed dat ze dergelijke optimalisaties aankunnen.

Vervelende van java is dat je ook geen floating point hacks kunt uithalen. In C++, als iets snel moet zijn, dan ga ik wat prutsen met de bits van een float (de *(int *)&f constructie zeg maar). Gaat ook niet in Java. Ja, via Float.floatToIntBits (), maar of je een functioncall wilt doen daarvoor is ook maar de vraag

Hier doet ie trouwens 29 fps, athlon xp 1400

[JayVee]

Uhm.... WOW!

HIER lopen dus de mensen met verstand rondt! 8 )

Ik ben net bezig mijn 3d engine van Java naar C++ te porten (dus past perfect in dit topic) enneuh, ik wil ook een multidimensional array.

Omdat ik daar de vertices in wil stoppen moet het snel zijn en graag beetje makkelijk te adresseren. Daarnaast wil ik het array graag op de free store.

En als ik het goed begrijp dan zit het zo:

C++:

int x;
int a[x]; //array op stack
int * a[x]; // array van pointers op de stack
int * a = new int[x]; //array op heap (free store)

<edit> x moet idd voor de eerste twee constant zijn. Daarnaast staat deze code in een functie...</edit>

Iemand een idee? Die Booster template leek mij wel wat, maar die wil net niet met mijn compiler (Borland 5.5.1). Op zich geen probleem van compiler te switchen... maar als er nog een andere oplossing bestaat...

offtopic:
homeboxx doet het bij mij met 36fps! HISCORE! Ahw yieah!

[ Voor 7% gewijzigd door JayVee op 27-09-2003 23:24 ]

[MSalters]

In zo'n code fragment is het lastig te zien of je object op de stack danwel global staan. Als je code uit een functie komt, dan zijn het inderdaad stack objectenWel heb je een bugje ( [x] is geen valide array grens, moet constante zijn in regels 2&3 )

Ook als de boost code niet werkt is het idee handig; een array template class is ook in Borland 5.5 te maken. Als je met losse new[]s/delete[]s gaat werken door je hele programma heen heb je dikke ellende. Stop ze in de ctors&dtor, en je hebt het overzicht.

[JayVee]

Als je zo een declaratie dus buiten een functie zet (of in main) dan komt het dus op het vrije geheugen te staan? Ik heb in Java een filewriter geschreven die de .ase modellen uit Doom³ (ja ja!!) uit kan lezen. Die maakt een Body object aan (waar gewoon alle data instaat).

Zo iets wil ik dus nu ook maken. Moet met dynamic mem en ik weet niet hoe veel models ik in ga laden dus dat moet idd allemaal in een functie gebeuren.

Heb het nu zo "opgelost":

C++:

//dit staat in de header
struct model {
  v_3d worldpos;    // world space position
  
  int num_verts;    // number of vertices
  v_3d* p_verts;    // vertices array
  
  int num_faces;    // number of faces
  int** p_faces;        // pointer to array of face-array-pointers
  int* p_face_clrs; // color of faces
  v_3d* p_norms;    // normals array
};

// dit staat in de declaratie van een test functie,
// komt later in de modelreader
test() {
  model * dude = new model;
  // -- ff wat onbelangrijk spul skippen --
  int* face0 = new int[3];
  face0[0] = 0;
  face0[1] = 1;
  face0[2] = 2;
  
  int* face1 = new int[3];
  face1[0] = 5;
  face1[1] = 6;
  face1[2] = 7;
  
  int** p_face_arrays = new int*[numfaces]; // array of pointers
  p_face_arrays[0] = face0;
  p_face_arrays[1] = face1;
  dude->p_faces = p_face_arrays;

  // -- en zo kom ik er weer aan: (PSEUDO CODE)
  { (dude->p_faces[X])[0]  ,  (dude->p_faces[X])[1] , (dude->p_faces[0])[2]  }
  // krijg ik met x = 0 {0, 1, 2}
}

Vind het erg lelijk. Uiteindelijk zal ik misschien tussenpointers gebruiken. Wordt het wel langzamer door (toch?)... ik zie wel.

Maareuh, is dit een "workable" oplossing? Zodra ik OpenGL of DirectX ga gebruiken komen de vertices toch heel ergens anders terecht.

<edit> btw, kan je een array zoals in regels 19 en 24 "direct" initializen, dus met zoiets als *face0 = { 1, 2, 3 }?
Dit compiled niet...</edit

[ Voor 6% gewijzigd door JayVee op 27-09-2003 23:41 ]