[JAVA] Snel data verwerken met array's

[Funcracker]

Kan geen goede topic titel verzinnen, maar dit is het probleem:

Voor een practicum moet ik in Java een algoritme schrijven wat heel snel moet zijn (ja ik weet het.. maar JAVA was verplicht). Volgens de opdrachtomschrijving is er een reeks van objecten die elk 3 waarden aan kunnun nemen.

Dus ik zit nu te denken, wat is sneller?
- één byte array
- 3 boolean array's
- Iets anders??

In het algoritme moet ik iets van een paar miljoen iterations maken, waarbij in elke iteration 2 dingen moeten worden aangepast in de bovenstaande data, en een aantal dingen eruit gechecked (if-statements). De array('s) zou zo'n 3000 waarden moeten bevatten.

[Bosmonster]

Proberen en timen zou ik zeggen... dan weet je toch wat het snelste is?

[Funcracker]

Op woensdag 08 mei 2002 12:10 schreef Bosmonster het volgende:
Proberen en timen zou ik zeggen... dan weet je toch wat het snelste is?

Ja.. Maar ik moet het ook verantwoorden.
't Zou leuk zijn als iemand hier me de theorie ervan kon uitleggen, oftewel: waarom het 1 sneller is dan het ander.
Of wat hints die kant op.

[Dash2in1]

Begrijp ik het goed dat als je van bytes gebruik wilt maken, dat je slechts 3 bits per byte feitelijk nodig hebt?

[Woy]

Volgens mij heb je zelfs maar 2 bits nodig want daar kan je al 4 waardes mee weer geven. Dus je zou de byte dus ook in 4 delen van 2 bits op kunnen delen en dan met bitmasks werken. Dan kan je array weer 4 keer zo klein

[Dash2in1]

Uhm, ja, had topicstarter niet goed gelezen (hij droeg zelf 3 booleans aan). 3 waardes .. 2 bits .. 00 01 10. Kan je per 4 in 1 byte gooien, denk dat dat het makkelijkste is (zo op voorhand, dus kan er weinig werkelijk zinnigs over zeggen)

edit:
Alhoewel, als je 2 booleans gebruikt, je kan checken op de 'linker' boolean .. als die 1 is weet je al genoeg

[udenjpg]

Geef eens een betere omschrijving van de opdracht?

[Funcracker]

Op woensdag 08 mei 2002 14:59 schreef udenjpg het volgende:
Geef eens een betere omschrijving van de opdracht?

Ik heb 'iets' dat 3 waarden kan aannemen.
En daar heb ik er veel van.

Een boolean kan maar 2 waarden aannemen, dus werkt niet.
Een byte is de eerstvolgende optie, maar is al trager te checken dan een boolean.

Ik wil de snelste oplossing om deze waarden op te slaan, te wijzigen en te checken (in de opdracht zoals boven beschreven).

2 boolean array's is inderdaad al voldoende (zoals Dash2in1 zei), 3 is wat overdreven.
Maar de vraag is: Is dit sneller dan een byte array te gebruiken (worst case)?

[Funcracker]

Op woensdag 08 mei 2002 12:22 schreef rwb het volgende:
Volgens mij heb je zelfs maar 2 bits nodig want daar kan je al 4 waardes mee weer geven. Dus je zou de byte dus ook in 4 delen van 2 bits op kunnen delen en dan met bitmasks werken. Dan kan je array weer 4 keer zo klein

Hoe groot de array is maakt me nix uit.
Als ik met bitshifts ga moeten werken zullen operaties op die array's weer meer tijd kosten. Ik ben dus op zoek naar de meest efficiente oplossing qua tijd.

[Verwijderd]

K programmeer zelf niet in Java, maar eh kan je niet een stukje ASM dr tussendoor gooien?

[Uiligheid]

om te checken is een StackedList het snelst geloof ik, maar ik heb al 3 maanden JAVA niet meer aangeraakt, dus ik ben een beetje roestig...

[Woy]

Nou dan is het denk vrij makkelijk gewoon even een klein test programmatje maken wat kijkt wat sneller is 2 booleans vergelijken of 1 byte

[udenjpg]

En een vector van enumerated types?

[kim72]

Als je de hele array door moet kan je gewoon byte[] gebruiken. Een processor kan net zo snel een byte vergelijken of aanpassen dan een boolean.

Als je moet zoeken in de array zou ik kiezen voor een HashMap oid.

Succes!

[Uiligheid]

sorry, ik bedoelde geen stackedlist, maar een linkedlist.. schijnt echt supersnel te zijn.

[Funcracker]

Op woensdag 08 mei 2002 15:18 schreef anaconda het volgende:
K programmeer zelf niet in Java, maar eh kan je niet een stukje ASM dr tussendoor gooien?

Ehhmm.. Dat heb eerlijk gezegd nog nooit in Java geprobeerd..

Op woensdag 08 mei 2002 15:28 schreef rwb het volgende:
Nou dan is het denk vrij makkelijk gewoon even een klein test programmatje maken wat kijkt wat sneller is 2 booleans vergelijken of 1 byte

Kan.. maar wil het graag onderbouwen, zie ook mijn 2e post hierboven. Bovendien vroeg ik me dus ook af of het misschien nog intelligenter kon..

Op woensdag 08 mei 2002 15:30 schreef udenjpg het volgende:
En een vector van enumerated types?

?? Is dat niet juist ongelovelijk langzaam.. Een vector.. Of leg es iets duidelijker uit als je wilt..

[Funcracker]

Op woensdag 08 mei 2002 15:33 schreef harry13131 het volgende:
Als je de hele array door moet kan je gewoon byte[] gebruiken. Een processor kan net zo snel een byte vergelijken of aanpassen dan een boolean.

Als je moet zoeken in de array zou ik kiezen voor een HashMap oid.

Succes!

Is dat zo? Dat checken of een byte == 0 qua tijd even lang duurt als aan een boolean == false vragen?
Dat moet toch wel ergens verschil maken toch?
Bedankt btw

Op woensdag 08 mei 2002 15:34 schreef Uiligheid het volgende:
sorry, ik bedoelde geen stackedlist, maar een linkedlist.. schijnt echt supersnel te zijn.

ehmm.. is het wel geloof ik ja.
Probleem alleen is dat dat geloof ik erg klote aanpast.
Ik moet namelijk ook zoeken in de array..
Maar dat zou kunnen werken..

[Bosmonster]

Op woensdag 08 mei 2002 15:39 schreef Funcracker het volgende:

Kan.. maar wil het graag onderbouwen, zie ook mijn 2e post hierboven. Bovendien vroeg ik me dus ook af of het misschien nog intelligenter kon..

Je tests zijn dan toch je onderbouwing??

[Funcracker]

Op woensdag 08 mei 2002 15:46 schreef Bosmonster het volgende:

[..]

Je tests zijn dan toch je onderbouwing??

Hmm.. tjah.. Maar zo werkt het hier niet echt
Maar je hebt wel gelijk. Die zal ik ook zeker gebruiken.
Maar ik weet vrij zeker dat er heel wat meer prijs op zal worden gesteld als ik ook vertel waardoor dat komt.

edit:
Ik ga nu naar huis, en zal dit topic tot vanavond 22:45 niet kunnen checken. Iig bedankt voor jullie reacties tot nu toe, als jullie nog goede ideeën hebben hoor ik het graag.

[Sjaaky]

Op woensdag 08 mei 2002 15:42 schreef Funcracker het volgende:
Is dat zo? Dat checken of een byte == 0 qua tijd even lang duurt als aan een boolean == false vragen?
Dat moet toch wel ergens verschil maken toch?
Bedankt btw

Het is echt beide even snel. En dat komt omdat de hardware max 32 bit aankan (is afhankelijk van de processor). Dus vergelijken van alles dat 32 bit of minder is gaat heel snel. Als het meer dan 32 bit is duurt het iets langer.
Maar als het een opdracht is voor school zul je je waarschijnlijk meer moeten richten op het algoritme zelf dan op de representatie van de data. Dus neem gewoon een byte of een int. Dingen als bit masks heb je echt niet nodig 3000 waarden passen makkelijk in het geheugen. Van bitmasks wordt het alleen maar langzamer.

Ik weet niet precies wat je moet doen, maar als je je algoritme van bijv. O(3) naar O(2) krijgt, score je veel beter dan dat je data representatie ge-fine-tuned hebt.

[Hydra]

Intern kent java geen boolean BTW, booleans worden vertaalt naar integers.

Een int gebruiken is sneller dan een byte, meeste CPUs kunnen het best met 32-bits waardes omgaan. Als ik jou was zou ik dus gewoon een int-array gebruiken (geen linked list oid, je hebt kennelijk alleen numerieke waardes nodig). Wat moet er tijdens die iteraties nu precies gedaan worden?

[.oisyn]

aangezien java bij elke array access de index controleerd op de grenzen, is het dus noodzaak om dit te reduceren naar zo min mogelijk checks

Je kunt dus het beste een array van longs gebruiken, dan hoef je minder vaak elementen uit de array te vissen. Je hebt maar 2 bits nodig per uitkomst, dus 1 long (van 64 bits) kun je opdelen in 32 waarden.

.edit: hmm ik had hier nog wat bij gezet, maar dat was bij een volgende edit weer verdwenen door een gare proxy hier op school
Anyway, dit gaat alleen maar op als je alle elementen na elkaar nodig hebt... bij random access heb je er natuurlijk helemaal geen reet aan

.edit: nog wat andere optimalisatie technieken
gebruik zoveel mogelijk lokale variabelen, of variabelen in dezelfde klasse. Als je een variabele uit een andere klasse wil opvragen dan duurt dat weer ietsjes langer.
Ook moet je zorgen dat je zo min mogelijk functioncalls hebt, en maak de functies die je wel moet aanroepen final.

Maar het allerbelangrijkste is natuurlijk een goed algoritme

[Hydra]

Op woensdag 08 mei 2002 17:08 schreef .oisyn het volgende:
aangezien java bij elke array access de index controleerd op de grenzen, is het dus noodzaak om dit te reduceren naar zo min mogelijk checks

Je kunt dus het beste een array van longs gebruiken, dan hoef je minder vaak elementen uit de array te vissen. Je hebt maar 2 bits nodig per uitkomst, dus 1 long (van 64 bits) kun je opdelen in 32 waarden.

Get gebruik van longs kost extra tijd, evenals bitchecks. Qua performace denk ik dus niet dat je er op vooruitgaat.

Maar ik ben nog steeds erg benieuwd naar wat het probleem precies is. Verdere beslissingen zullen daar op gebaseerd moeten worden.

[.oisyn]

Op woensdag 08 mei 2002 17:21 schreef Hydra het volgende:

[..]

Get gebruik van longs kost extra tijd, evenals bitchecks. Qua performace denk ik dus niet dat je er op vooruitgaat.

Maar ik ben nog steeds erg benieuwd naar wat het probleem precies is. Verdere beslissingen zullen daar op gebaseerd moeten worden.

de extra tijd voor bit-bewerkingen is echt verwaarloosbaar met de tijd die het kost om de array te benaderen

welke JDK versie wordt eigenlijk gebruikt?

[Verwijderd]

Op woensdag 08 mei 2002 17:21 schreef Hydra het volgende:

[..]

Get gebruik van longs kost extra tijd, evenals bitchecks. Qua performace denk ik dus niet dat je er op vooruitgaat.

Dat denk ik ook en daar komt nog eens bij dat de voorgestelde optimalisatie alleen daadwerkelijk tijdswinst op KAN leveren als je telkens sequentieel door de array fietst. Bij 'random' accesses scheelt het helemaal niets en kost het waarschijnlijk zelfs meer tijd (omdat je telkens een long op moet halen ipv een int).

over die checks van array indexes, ik weet niet hoe slim die java VM's tegenwoordig zijn, maar het lijkt me toch een vrij gemakkelijke optimalisatie om in een stukje code als

code:

for(int i=0;i<array.length;i++)
   doeIets(array[i]);

slechts 1 x te checken op array boundries en vast te stellen dat dit safe is ipv dit tijdens elke stap te doen, maar goed, misschien heb ik wel een te hoge pet op van die VM's (en ja dan zul je waarschijnlijk ook even wat analyses uit moeten voeren om te checken of bijv andere threads de array variabele niet veranderen en zo, maar 't is zeker niet onmogelijk).

[Hydra]

Op woensdag 08 mei 2002 17:27 schreef .oisyn het volgende:
de extra tijd voor bit-bewerkingen is echt verwaarloosbaar met de tijd die het kost om de array te benaderen

Ik betwijfel het, aangezien je zelf ook nog eens een for-loop gebruikt om de bits binnen de long te benaderen.

Dus:

code:

int[] array = new int[1000000];
int x;
for(int i = 0;i < 1000000;i++) {
   x = array[i];
   //doe iets met x;
}

Vs.

code:

long[] array = new long[31250];
long x;
int pos;
for(int i = 0;i < 31250;i++) {
  x = array[i];
  for(j = 0;j < 32;j++) {
    pos = 2*j;
    //doe iets met bits op posisitie pos binnen long x;
  }
}

Een veel lelijker stuk code, dat tegen de Java conventies indruist, en bovendien waarschijnlijk langzamer is.

[Hydra]

Op woensdag 08 mei 2002 17:40 schreef hondass50 het volgende:
over die checks van array indexes, ik weet niet hoe slim die java VM's tegenwoordig zijn,

Slim genoeg. Ik weet in ieder geval zeker dat boundry-checks als dat mogelijk is runtime-geoptimaliseerd worden. Maar zelfs als die optimalisatie niet werkt, denk ik nog dat simpelweg arrays gebruiken sneller is. Java is erg int-georienteerd.

[Verwijderd]

Ow ja, nog een tipje, begin gewoon met een simpele int[] implementatie en check hoe snel je algoritme gaat. Als dan dus idd blijkt je algoritme een half uur duurt en je vindt dat te lang dan kun je gaan nadenken of allerlei grote (ander algoritme) en kleine optimalisaties (verschillende representaties van je data).

Ik bedoel, zometeen blijkt dat je super geoptimaliseerde programma in een seconde klaar is terwijl je ongeoptimaliseerde programma er 10 seconden over zou doen..In een hoop situaties zou dat ook nog best acceptabel zijn en waren al die optimalisaties die je code vaak een stuk onduidelijker maken eigenlijk niet nodig.

[.oisyn]

Op woensdag 08 mei 2002 17:41 schreef Hydra het volgende:

[..]

Ik betwijfel het, aangezien je zelf ook nog eens een for-loop gebruikt om de bits binnen de long te benaderen.

moet je toch wel, aangezien je maar 2 bits nodig hebt per waarde. Dus bij ints moet je m ook nog opdelen in 16 waarden (wat overigens supersnel gaat. bitberekeningen zijn echt de basis-berekeningen van een processor, anders dan bijvoorbeeld een vermenigvuldiging)

BTW, ik had het een keer getest met mijn 3d engine, maar dat was wel jdk 1.1.8 (MS implementatie trouwens... die was een stukkie sneller dan die van sun)

[Verwijderd]

Op woensdag 08 mei 2002 17:55 schreef .oisyn het volgende:

[..]

moet je toch wel, aangezien je maar 2 bits nodig hebt per waarde. Dus bij ints moet je m ook nog opdelen in 16 waarden (wat overigens supersnel gaat. bitberekeningen zijn echt de basis-berekeningen van een processor, anders dan bijvoorbeeld een vermenigvuldiging)

BTW, ik had het een keer getest met mijn 3d engine, maar dat was wel jdk 1.1.8 (MS implementatie trouwens... die was een stukkie sneller dan die van sun)

ehh, maar door die tweede loop om de verschillende bits van de long af te lopen heb je dus in totaal precies even veel array accesses nodig (namelijk 1 per getal access, of ze nou samen gepropt zijn in een long of gewoon in allemaal int's staan), het enige dat je er dus mee wint is geheugen ruimte, maar dat is dus niet zo'n issue bij 3000 getallen

[Hydra]

Op woensdag 08 mei 2002 17:55 schreef .oisyn het volgende:
moet je toch wel, aangezien je maar 2 bits nodig hebt per waarde. Dus bij ints moet je m ook nog opdelen in 16 waarden (wat overigens supersnel gaat. bitberekeningen zijn echt de basis-berekeningen van een processor, anders dan bijvoorbeeld een vermenigvuldiging)

Ik had het niet over bit-bewerkingen. Gewoon een int-array voor alle waarders. Who cares dat 30 van de 32 bits niet gebruikt worden, snelheid is hier het belangrijkste item.

[Janoz]

Voor een practicum moet ik in Java een algoritme schrijven wat heel snel moet zijn (ja ik weet het.. maar JAVA was verplicht). Volgens de opdrachtomschrijving is er een reeks van objecten die elk 3 waarden aan kunnun nemen.

De grootste snelheidswinst is te halen door juist je algoritme te optimaliseren. Het verschil tussen die drie types is in vergelijking daarmee maar marginaal.

[.oisyn]

Op woensdag 08 mei 2002 19:19 schreef Hydra het volgende:

[..]

Ik had het niet over bit-bewerkingen. Gewoon een int-array voor alle waarders. Who cares dat 30 van de 32 bits niet gebruikt worden, snelheid is hier het belangrijkste item.

okee, we nemen de proef op de som:

code:

public class Test
{
    final static int NUM_VALUES = 1 << 16;
    final static int ITERATIONS = 1024;
    static int bla;

    public static void doeIets (int waarde)
    {
        bla = waarde;
    }

    public static void main (String args[])
    {
        int[] intArray;
        long time;
        
        intArray = new int[NUM_VALUES];
        
        time = -System.currentTimeMillis ();
        for (int it = 0; it < ITERATIONS; it++)
        {
            for (int i = 0; i < NUM_VALUES; i++)
                doeIets (intArray[i]);
        }
        time += System.currentTimeMillis ();
        
        System.out.println ("full int array: " + time + " millis");
        
        
        intArray = new int[NUM_VALUES >> 4];
    
        time = -System.currentTimeMillis ();
        for (int it = 0; it < ITERATIONS; it++)
        {
            for (int i = 0; i < NUM_VALUES >> 4; i++)
            {
                int value = intArray[i];
                for (int j = 0; j < 16; j++)
                {
                    doeIets (value & 3);
                    value >>= 2;
                }
            }
        }
        time += System.currentTimeMillis ();
    
        System.out.println ("bit int array: " + time + " millis");
    }
}

uitkomst:

code:

full int array: 481 millis
bit int array: 280 millis

(jdk 1.3.1 op een athlon 1600+)

.edit:
even de code voor een long bit array erbij

code:

        longArray = new long[NUM_VALUES >> 5];

        time = -System.currentTimeMillis ();
        for (int it = 0; it < ITERATIONS; it++)
        {
            for (int i = 0; i < NUM_VALUES >> 5; i++)
            {
                long value = longArray[i];
                int ivalue = (int)value;
                for (int j = 0; j < 16; j++)
                {
                    doeIets (ivalue & 3);
                    ivalue >>= 2;
                }
                ivalue = (int)(value >> 32);
                for (int j = 0; j < 16; j++)
                {
                    doeIets (ivalue & 3);
                    ivalue >>= 2;
                }
            }
        }
        time += System.currentTimeMillis ();

        System.out.println ("bit long array: " + time + " millis");

(nieuwe) uitkomst:

code:

full int array: 491 millis
bit int array: 271 millis
bit long array: 250 millis

i rest my case

[Aaargh!]

Moet je de items allemaal in volgorde benaderen of pak je er steeds een 'willekeurige' tussen uit ?
Worden de 'ietsen' geidentificieerd aan de hand van hun positie in de array of spreek je ze aan mbv een sleutel ?
moet het een OO datastructuur zijn of niet ?

[Jelmer]

Om nog ff wat meteen maar eens wat meer benchmarks neer te zetten:
JDK 1.4 op een Ahtlon 900

full int array: 721 millis
bit int array: 651 millis
bit long array: 581 millis


JDK1.3.1 op een Duron 750

full int array: 1673 millis
bit int array: 613 millis
bit long array: 688 millis

[Aaargh!]

Op woensdag 08 mei 2002 11:56 schreef Funcracker het volgende:
Volgens de opdrachtomschrijving is er een reeks van objecten die elk 3 waarden aan kunnun nemen.

Objecten, als in: een array van ints kan niet ? (op z'n minst dan een array van Integer objecten)

Als je het echt snel wilt kan je er natuurlijk altijd voor kiezen het in C/C++ te doen en die dan met JNI aan te spreken.

[.oisyn]

Op donderdag 09 mei 2002 00:46 schreef Jelmer Barhorst het volgende:
JDK1.3.1 op een Duron 750

full int array: 1673 millis
bit int array: 613 millis
bit long array: 688 millis

hmm toch wel opmerkelijk dat ie er met longs op een duron langer over doet... Ik denk dat dat te maken heeft met het verschil in cache tussen de duron en de athlon (moet ook haast wel, verder is er geen verschil tussen de twee). Aangezien het long-gedeelte meer bytecode oplevert, moet er dus ook meer gefetched worden. Maar goed, toch blijf ik het raar vinden...

heb je m meerdere keren gerund? Kan natuurlijk ook net een toevallig dipje in het systeem zijn...

[Jelmer]

Heb trouwens nu even mn distributed.net client uit gezet en m een aantal maal laten testen. Verder zijn er geen processen die het resultaat kunnen beinvloeden.

Athlon 900 (jdk 1.4):
full int array: 721 millis
bit int array: 631 millis
bit long array: 581 millis


Duron 750 (jdk 1.3.1):
full int array: 1470 millis
bit int array: 525 millis
bit long array: 592 millis


Trouwens best wazig dat met de bit-int 1.3.1 op een Duron 750 sneller is dan 1.4 op een Athlon 900.. De enige oorzaak die ik daar eigenlijk voor kan bedenken is dat ik op mn Duron linux 2.4.18 draait en op mn Athlon windows XP..

Ik zal voor de gein eens jdk1.4 voor linux downloaden, ben erg benieuwd wat dat uit gaat maken.

Update
Duron 750 (jdk1.4):
full int array: 1301 millis
bit int array: 780 millis
bit long array: 731 millis

Kortom, jdk1.4 is een stuk trager met bit bewerkingen, maar wel iets sneller met full int array's... vaag

[.oisyn]

en compile ze nou eens met -O (voor optimisation)? Of had je dat al gedaan?

(het maakte bij mij (jdk 1.3.1) niets uit iig)

[Baron]

Wat parameters meegeven tijdens het compileren en executen levert toch tijdwinst op.

javac Test.java

java Test
full int array: 701 millis
bit int array: 731 millis

java -server Test
full int array: 70 millis
bit int array: 411 millis

javac -O Test.java

java Test
full int array: 691 millis
bit int array: 732 millis

java -server Test
full int array: 90 millis
bit int array: 401 millis

[.oisyn]

het zou fijn zijn als je de betreffende JDK en je systeemspecs ook even vermeld, want dit zegt me natuurlijk helemaal niets

en wat doet zo'n server?

[Hydra]

Op woensdag 08 mei 2002 23:53 schreef .oisyn het volgende:
i rest my case

Gadver, nooit geweten dat array-checks zo ontzettend duur zijn. IMHO in ieder geval een mooi verbeterpunt

Proficiat

[Hydra]

Op vrijdag 10 mei 2002 16:28 schreef .oisyn het volgende:
en wat doet zo'n server?

Vraag het me ook af, heb die resultaten hier niet kunnen reproduceren.

[MisterData]

Op vrijdag 10 mei 2002 16:28 schreef .oisyn het volgende:

en wat doet zo'n server?

Door -server mee te geven start je de 'server' VM. Deze is voor normale applicaties misschien trager, maar aangezien deze VM is bedoeld voor server applicaties mag de opstarttijd langer zijn maar moeten berekeningen e.d. sneller worden uitgevoerd. Ook heeft het te maken met de garbage collection en met een hele hoop andere dingen (caching enzo)