[Java] Grote hoeveelheden data tijdelijk opslaan

[Potatoman]

Ik ben bezig met een spelletje in java, waarbij ik naar schatting 256x256 tot 512x512 vakjes heb, allemaal met een stuk of 10 eigenschappen, die misschien nog uitgebreid worden. Ik wil makkelijk en snel vakjes kunnen benaderen.

Voorlopig heb ik de data opgeslagen in een tweedimensionale array, maar dat gaat erg langzaam zodra ik hem groter maak dan 256x256. Ik heb ook geprobeerd met linked lists (Vector) te werken, en het geheel te splitsen in een aantal kleinere arrays, maar dat helpt ook niks.

Nu ben ik aan het kijken naar het opslaan op de harddisk, met serializable. Dit heb ik geprobeerd, als gehele file en met het verdelen in blokken met verschillende groottes (van 16x16,32x32 en 64x64 vakjes), maar dit is mij eigenlijk ook nog te langzaam, zeker omdat ik elk vakje random wil accessen.

Heeft iemand een idee hoe ik het beste deze vakjes kan opslaan, en waar, en op een manier dat schrijven én lezen snel werkt? (in tegenstelling tot opslaan op de hd, waar lezen sneller gaat dan schrijven)

[ari3]

Wanneer je een tweedimensionale array maakt is het nog steeds langzaam? Gaat de JVM dan swappen (fysiek <-> disk) ?

Kijk ook eens naar de instellingen van de JVM die je gebruikt. De Sun JVM alloceert standaard maxoimaal 50% van het fysieke geheugen. Zet de heapsize op 100% van de fysieke geheugen en je kunt wellicht alles in het geheugen houden.

Helpt dit niet, dan gewoon wat extra geheugen in je computer prikken

[Verwijderd]

De heapsize instellingen veranderen maakt heel weinig uit voor de performance.

Waar je beter naar kan kijken is het object zelf. Als je 10 bytes in het object bespaart,
dan bespaar je dus 256x256x10 bytes aan geheugen.

Met de profiler (hprof) die in de vm zit kan je kijken waar hij het meeste geheugen gealloceerd heeft en vervolgens kan je gaan kijken of je dat op kan lossen.

[Marcj]

Kun je niet beter in plaats van heel veel Vak-objecten een Veld-object maken die heel veel eigenschappen bijhoudt? Dit is veel efficienter, omdat het aanmaken van Object nogal traag is.

Even een voorbeeld:
i.p.v. dit:

Java:

pubic class Vak
{
  private int kleur;

  public Vak(int kleur)
  {
    this.kleur = kleur;
  }
  ....
}

public class Spel
{
  ....
  Vak[][] veld = new Vak[256][256];
  for(int y = 0; y < 256; y++)
  {
    for(int x = 0; x < 256; x++)
    {
      veld[x][y] = new Vak(0);
    }
  }
  .....
}

dit:

Java:

public class Veld
{
  private int[][] kleur;

  public Veld(int aantal)
  {
    kleur = new int[aantal][aantal];
  }
  ...
}

public class Spel
{
  ....
  Veld veld = new Veld(256);
  for(int y = 0; y < 256; y++)
  {
    for(int x = 0; x < 256; x++)
    {
      veld.setKleur(x,y,0);
    }
  }
  ....
}

[ari3]

Verwijderd schreef op 07 March 2003 @ 08:30:
De heapsize instellingen veranderen maakt heel weinig uit voor de performance.

Bij te weinig geheugen zal de JVM objecten naar disk schijven -> langzaam.
Door de max. heap te vergroten kun je meer in het geheugen houden -> sneller.

Met de profiler (hprof) die in de vm zit kan je kijken waar hij het meeste geheugen gealloceerd heeft en vervolgens kan je gaan kijken of je dat op kan lossen.

Nu zeg je zelf dat er een relatie is met de het gealloceerde geheugen?

[Marcj]

ari3 schreef op 07 maart 2003 @ 09:25:
[...]

Bij te weinig geheugen zal de JVM objecten naar disk schijven -> langzaam.
Door de max. heap te vergroten kun je meer in het geheugen houden -> sneller.


[...]


Nu zeg je zelf dat er een relatie is met de het gealloceerde geheugen?

Lijkt het je niet beter om te voorkomen dat er zoveel geheugen nodig is? Als je zoveel geheugen gebruikt zal het altijd traag worden...

[wasigh]

BTW Vector is geen Linked List
Vector is een wrapper om een Array heen die zorgt voor automatisch resizen van die Array indien hij te klein wordt.

Wat is snel? Hoe lang doet hij er nu over om de data te benaderen?

Kun je misschien iets meer vertellen over de structuur van de vakjes? Heeft elk vakje alle 10 de eigenschappen nodig? Hoe sla je die eigenschappen op? Maak je voor elk vakje een object aan, of laat je vakjes met dezelfde eigenschappen naar hetzelfde object wijzen?

Er valt waarschijnlijk heel wat te optimaliseren maar dan moet ik iets meer over de objcten weten die je gebruikt

[Verwijderd]

wasigh schreef op 07 maart 2003 @ 09:35:
BTW Vector is geen Linked List
Vector is een wrapper om een Array heen die zorgt voor automatisch resizen van die Array indien hij te klein wordt.

Volgens mij is dat niet gespecificeerd of het om een array implementatie of een linked list implementatie gaat. Reden te meer om gebruik te maken van een List klasse...

[Potatoman]

ari3 schreef op 07 maart 2003 @ 08:16:
Wanneer je een tweedimensionale array maakt is het nog steeds langzaam? Gaat de JVM dan swappen (fysiek <-> disk) ?

Kijk ook eens naar de instellingen van de JVM die je gebruikt. De Sun JVM alloceert standaard maxoimaal 50% van het fysieke geheugen. Zet de heapsize op 100% van de fysieke geheugen en je kunt wellicht alles in het geheugen houden.

Helpt dit niet, dan gewoon wat extra geheugen in je computer prikken

Dat lijkt me niet dat dat het probleem is, want ik heb 1 Gigabyte geheugen, en het loopt dan net zo brak als met 256 mb
Maar ik zal es ff wat gaan pielen met de heapsize

[wasigh]

Verwijderd schreef op 07 March 2003 @ 10:19:
[...]

Volgens mij is dat niet gespecificeerd of het om een array implementatie of een linked list implementatie gaat. Reden te meer om gebruik te maken van een List klasse...

Uit de API-DOC:

The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

en een stukje verder:

protected Object[] elementData

The array buffer into which the components of the vector are stored. The capacity of the vector is the length of this array buffer, and is at least large enough to contain all the vector's elements.
Any array elements following the last element in the Vector are null.

hij implementeerd de List interface zodat hij kan werken met de Collections framework

http://java.sun.com/j2se/...api/java/util/Vector.html

(ik heb er toevallig laatst ook al een discussie over gehad )

[wasigh]

Potatoman schreef op 07 March 2003 @ 12:23:
[...]


Dat lijkt me niet dat dat het probleem is, want ik heb 1 Gigabyte geheugen, en het loopt dan net zo brak als met 256 mb
Maar ik zal es ff wat gaan pielen met de heapsize

Je kunt dan beter je programma efficienter maken imho

[TaXaN]

Ik weet niet welke eigenschappen die vakjes allemaal hebben en in welke mate ze eventueel gelijk zijn maar je zou het Flyweight design pattern kunnen overwegen. In plaats van voor elk vakje een object te maken, maak je een pool van de mogelijke objecten en link je elk vakje aan zo'n object. Op die manier kunnen verschillende vakjes een zelfde object delen en bespaar je dus op object creatie en destructie.

[Glimi]

wasigh schreef op 07 March 2003 @ 12:53:
hij implementeerd de List interface zodat hij kan werken met de Collections framework

http://java.sun.com/j2se/...api/java/util/Vector.html

(ik heb er toevallig laatst ook al een discussie over gehad )

offtopic:
Gebruik liever een ArrayList, die valt niet zo buiten de collections boot

[Potatoman]

Ik heb even goed zitten kijken in mijn code, en vond ergens in een recursieve tekenmethode een || wat een && had moeten zijn
Dit heb ik nu veranderd, en de hele boel loopt vloeiend met vakjes tot 768x768

Wat is nu eigenlijk de beste manier om deze data op te slaan? Het staat nu (naar al mijn probeersels) nog steeds in een tweedimensionale array. Kan ik ze beter opslaan in een Vector, of een linkedlist, of iets compleet anders?

TaXaN schreef op 07 March 2003 @ 15:09:
Ik weet niet welke eigenschappen die vakjes allemaal hebben en in welke mate ze eventueel gelijk zijn maar je zou het Flyweight design pattern kunnen overwegen. In plaats van voor elk vakje een object te maken, maak je een pool van de mogelijke objecten en link je elk vakje aan zo'n object. Op die manier kunnen verschillende vakjes een zelfde object delen en bespaar je dus op object creatie en destructie.

Dat klinkt wel interresant, daar ga ik ff wat meer over opzoeken Ik neem aan dat het dan ook mogelijk is om een nieuw object te creëren zodra je twee vakjes niet meer hetzelfde object wilt laten delen?

Edit: kleine correctie: met grotere heapsize draait een grid van 1024x1024 ook perfect

[ Voor 5% gewijzigd door Potatoman op 07-03-2003 20:33 ]

[-Tibo-]

Een snellere manier van opslaan als je veel moet zoeken is bijvoorbeeld een b-boom maar je kan ook al je veldjes in een hash-table gaan opslaan..

[hobbit_be]

een Vector / ArrayList / of pure array zijn eigen que structuur hetzelfde. zolang je weet hoe groot je field is maakt het qua storage niets uit. Maar een [][] heeft wel 1 erg voordeel is dat zowel optimal use van geheugen is. (Vector or Vectors / AL of AL / heeft wat overhead.) ook access is heel snel met een pure array (alleen range check in native code terwijl een Vector/AL constant gaat kijken per access of ie moet 'groeien'). dus hou het gewoon op myFieldObject[][]. Ik denk niet dat het sneller kan.

edit:
Flyweight pattern is interessant maar ik denk dat het meer rompslomp gaat geven dan raw speed onder java: alleen voor waar min geheugen een issue is dus.

een HashMap voor opslagen van een playfield ? euh waarop moet ie dan gaan zoeken? find all grass nodes? als je access tot grote hopen van distributed data hebt kun je een reindex (lees als Look Up Table) gebruiken. een Hash Creeren in Java is niet echt snel.

int[] mGreenGrassFieldsX = new int[maxGreenGrassFields] //misschien een plek voor een vector?

dan mField[mGreenGrassFieldX[tIndex], mGreenGrassFieldY[tIndex]]; // en als je zelf al je indexing doet gebruik je gewoon een 1D field ...

als de volgorde van GreenGrassFields niet nodig is kun je een Pool gebruiken - bestaat er eigenlijk een Pool type in Java?

[ Voor 45% gewijzigd door hobbit_be op 07-03-2003 20:55 ]

[Soultaker]

edit
Ik had de grap verkeerd begrepen, laat meer weer zitten dan.

[ Voor 255% gewijzigd door Soultaker op 07-03-2003 21:17 ]

[Verwijderd]

Potatoman schreef op 07 maart 2003 @ 20:32:
Ik heb even goed zitten kijken in mijn code, en vond ergens in een recursieve tekenmethode een || wat een && had moeten zijn
Dit heb ik nu veranderd, en de hele boel loopt vloeiend met vakjes tot 768x768

Wat is nu eigenlijk de beste manier om deze data op te slaan? Het staat nu (naar al mijn probeersels) nog steeds in een tweedimensionale array. Kan ik ze beter opslaan in een Vector, of een linkedlist, of iets compleet anders?

Een array is best snel, redelijk geordend maar heeft meestal een vaste grootte. Een Vector is een array met een variabele grootte. Een linked-list zal waarschijnlijk niet gaan omdat deze niet random-access is. Je hebt een reference naar de eerste, die heeft een reference naar de volgende, maar als je de 200ste moet hebben moet je eerst nummers 1 t/m 199 doorlopen.

Ik vermoedde al dat het niet je data-opslag was wat voor problemen zorgt. 500x500x10 is niets voor een computer.

[ Voor 7% gewijzigd door Verwijderd op 07-03-2003 21:25 ]

[Verwijderd]

ari3 schreef op 07 March 2003 @ 09:25:
[...]

Bij te weinig geheugen zal de JVM objecten naar disk schijven -> langzaam.
Door de max. heap te vergroten kun je meer in het geheugen houden -> sneller.


[...]


Nu zeg je zelf dat er een relatie is met de het gealloceerde geheugen?

1) Een JVM zal NOOIT naar disk schrijven, dat is een taak van het operating system.
Het OS doet dat zelfs als je je Heapsize groot zet. De enige performance winst
die je kan halen uit je heapsize is niet door de max te verhogen, maar door de minimale size te vergroten. Hij hoeft het dan niet meer te alloceren op het moment dat hij het nodig heeft.

2) Die relatie gaat over dat alloceren tijd kost en zonde is als het niet nodig is.