Swappen

[ChristianWeddeling]

Hallo Florian Lohoff!

> On Tue, Aug 03, 1999 at 02:55:03PM +0200, Christian Weddeling wrote:
> > Hallo Leute!
> > 
> > Ich wollte gerade verschiedene Datenstrukturen testen, wie sie sich bei großen
> > Datenmengen verhalten. Die Datenmengen sind so groß, daß sie nicht im
> > Hauptspeicher gehalten werden können und geswapt werden müssen. Dabei mußte
> > ich feststellen, daß bei einer linearen Liste problemlos ausgelaget wird, bei
> > ausgeglichen Bäumen funktioniert das nicht.
> 
> > Desweiteren scheint das unabhängig vom Kernel und vom Unix zu sein, da die Sun
> > das gleiche Problem hatte. Hat vielleicht einer eine Idee?
> 
> Mit "funktioniert das nicht" meinst du wohl eher das die performance
> drastisch in den Keller geht - Richtig ?

Ne, eher das nicht ausgelagert wird und ich somit keinen Speicher allokieren
kann. Also kommt fürher oder später ein new mit null zurück.

> Es ist natuerlich immer so das die performance extrem leidet wenn
> nicht alles in den Speicher passt.

Das habe ich erwartet und wollte testen, welche Datenstruktur damit am besten
zurechtkommt.

> Ich bin im moment nicht sicher wie selektiert wird welche
> pages ausgepaged werden - Ich nehme an das es ein LRU
> aehnlicher Algorhythmus? ist.

Ist anzunehmen. Allerdings wundert mich, daß dies so statisch gehandhabt wird.
So wie es aussieht, wird erst nach einer bestimmten Zeit ausgelagert. Wenn die
am längsten unbenutzte Seite einfacht ausgelagert würden, dann wäre die Platte
zwar tierisch am rödeln, aber es würde trotzdem funktionieren.

> D.h. wenn du den baum immer von oben nach unten durchsuchst
> und deine einzelnen objekte in eine page passen dann fasst du 
> jedesmal mehr oder minder alle pages an und verhinderst
> damit unter LRU gesichtspunkten ein performantes arbeiten.
> Also solltest du metadaten von nutzdaten trennen.
> Den eigentlichen baum (den man ja organisationstechnisch braucht)
> seperat vom rest platzieren - Dadurch bleibt der orga baum
> fuer die geschwindigkeit vorhanden und die eigentlichen daten
> die du nur bei zugriff auf die daten brauchst paged du dir
> dann aus/ein.

Da habe ich auch schon dran gedacht. Nach meinem Urlaub werde ich mal einen
eigenen Baum implementieren, der einen getrennten Datensatz aufweist.
Allerdings fällt mir gerade ein, daß ich die Datenstrukturen nur mit
Schlüssel, aber nicht mit Daten gefüttert habe. Vielleicht sollte ich mal ein
paar Dummie-Daten erzeugen.

> Aber ich denke das ist extrem abhaengig von deinen zugriffs
> methoden/mustern.

Ich weiß. Bisher bin ich bis zum eigentlichen Suchen noch nicht gekommen. Ich
wollte erst mit einem Zufallsgenerator mit einer ziemlich guten
Gleichverteilung Schlüssel erzeugen, nach denen ich dann suche. Später wollte
ich das gleiche mit einem Generator machen, der eine frei verschiebbare
Gaußberteilung aufweist. Ich bin mir nur nicht im klaren darüber, wie ich die
Glocke verschieben werde.





	Ciao
		Christian