Essay für schnelle Listen

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	Vertex Betreff: Essay für schnelle Listen	Fr, Sep 07, 2007 0:28 Antworten mit Zitat
Linked Lists sind recht lahm und verbrauchen Dank den Links eine Menge Speicher. Arrays sind recht schnell, haben nur das Problem mit dem Speichermanagement. Wenn ein Eintrag hinzukommen soll, dann muss i.d.R. ein neuer, größerer Speicherblock erstellt und der Alte kopiert werden -> lahm. In C# gibt es da eine gute Lösung die mit 2^n Kapazitäten arbeitet. Für 10 Einträge sehe das bspw. so aus: 1 Eintrag -> Kapazität 1 2 Einträge -> Kapazität 2 3 Einträge -> Kapazität 4 4 Einträge -> Kapazität bleibt 4 5 Einträge -> Kapazität 8 6 Einträge -> Kapazität bleibt 8 7 Einträge -> Kapazität bleibt 8 8 Einträge -> Kapazität bleibt 8 9 Einträge -> Kapazität 16 10 Einträge -> Kapazität bleibt 16 Man hätte hier zwar 6 überflüssige Einträge, aber sich 4 Speicheralloziierungen + Kopien erspart. Klingt noch nicht gut, aber auf 100 Einträgen kommen gerade mal 7 "Vorgänge", auf 1000 Einträge 10 Vorgänge usw. Das ganze ist also in Sachen Geschwindigkeit höchst effektiv. Wenn nicht gerade 2^n Einträge vorliegen, bleibt immer ein Teil Speicher ungenutzt. Weiterhin kann man auch mit Startkapazitäten arbeiten um nicht so viel Leistung bei den ersten Einträgen zu verbraten. Ist noch nicht ganz durchdacht. Werde dazu aber mal noch ein paar Formeln wegen Effiziens und Speicherkosten aufstellen. Würde sich aber als TList Ersatz ganz gut machen. mfg olli Hierzu noch ein Benchmark: Code: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Framework BRL.Blitz Import BRL.LinkedList Const NUM_ENTRIES : Int = 10000 Global Start : Int, .. List1 : TList, .. List2 : TData[], .. List3 : TData[], .. Data : TData, .. Index : Int Start = MilliSecs() List1 = New TList For Index = 0 Until NUM_ENTRIES Data = New TData List1.AddLast(Data) Next WriteStdout("Linked List: " + (MilliSecs() - Start) + "ms~n") List1.Clear() List1 = Null GCCollect() Start = MilliSecs() For Index = 0 Until NUM_ENTRIES Data = New TData List2 = List2[..List2.Length + 1] List2[List2.Length - 1] = Data Next WriteStdout("Array standard: " + (MilliSecs() - Start) + "ms~n") List2 = Null GCCollect() Start = MilliSecs() List3 = New TData[1] For Index = 0 Until NUM_ENTRIES Data = New TData If Index >= List3.Length Then List3 = List3[..(List3.Length Shl 1)] List3[Index] = Data Next WriteStdout("Array with capacity: " + (MilliSecs() - Start) + "ms~n") List3 = Null GCCollect() End Type TData Field Foo : String Field X : Int Field Y : Int Field Z : Int End Type Wenn man NUM_ENTRIES erhöht, sollte man die 2 Methode gleich auskommentieren. Sie dauert Ewigkeiten. Generell kann man sagen, dass Linked Lists und Arrays mit Kapazitäten in etwa gleich schnell sind, wenn es um Anlegen von Einträgen geht. Output: Zitat: Linked List: 4ms Array standard: 1380ms Array with capacity: 2ms Wenn man alle Einträge von vorn bis hinten durchgeht, sind Arrays minimal schneller als Linked Lists. Der große Vorteil bei Arrays ist aber der direkte Zugriff aus Indizes, was bei Linked Lists erst über n Repitationen möglich ist. Weiterhin lassen sich Linked Lists nur über Bubble Sort sortieren, bei Arrays, vorallem mit 2^x Kapazität, geht auch Quick Sort und Co. Arrays mit den Kapazitäten sind also auf den ersten Blick höchst effizient.
vertex.dreamfall.at \| GitHub

Vertex

Betreff: Essay für schnelle Listen

Fr, Sep 07, 2007 0:28
Antworten mit Zitat

Linked Lists sind recht lahm und verbrauchen Dank den Links eine Menge Speicher.
Arrays sind recht schnell, haben nur das Problem mit dem Speichermanagement. Wenn ein Eintrag hinzukommen soll, dann muss i.d.R. ein neuer, größerer Speicherblock erstellt und der Alte kopiert werden -> lahm.

In C# gibt es da eine gute Lösung die mit 2^n Kapazitäten arbeitet.
Für 10 Einträge sehe das bspw. so aus:
1 Eintrag -> Kapazität 1
2 Einträge -> Kapazität 2
3 Einträge -> Kapazität 4
4 Einträge -> Kapazität bleibt 4
5 Einträge -> Kapazität 8
6 Einträge -> Kapazität bleibt 8
7 Einträge -> Kapazität bleibt 8
8 Einträge -> Kapazität bleibt 8
9 Einträge -> Kapazität 16
10 Einträge -> Kapazität bleibt 16

Man hätte hier zwar 6 überflüssige Einträge, aber sich 4 Speicheralloziierungen + Kopien erspart. Klingt noch nicht gut, aber auf 100 Einträgen kommen gerade mal 7 "Vorgänge", auf 1000 Einträge 10 Vorgänge usw. Das ganze ist also in Sachen Geschwindigkeit höchst effektiv. Wenn nicht gerade 2^n Einträge vorliegen, bleibt immer ein Teil Speicher ungenutzt.

Weiterhin kann man auch mit Startkapazitäten arbeiten um nicht so viel Leistung bei den ersten Einträgen zu verbraten.

Ist noch nicht ganz durchdacht. Werde dazu aber mal noch ein paar Formeln wegen Effiziens und Speicherkosten aufstellen. Würde sich aber als TList Ersatz ganz gut machen.

mfg olli

Hierzu noch ein Benchmark:
Code: [AUSKLAPPEN]

SuperStrict

Framework BRL.Blitz
Import BRL.LinkedList

Const NUM_ENTRIES : Int = 10000

Global Start : Int, ..
List1 : TList, ..
List2 : TData[], ..
List3 : TData[], ..
Data : TData, ..
Index : Int

Start = MilliSecs()
List1 = New TList
For Index = 0 Until NUM_ENTRIES
Data = New TData
List1.AddLast(Data)
Next
WriteStdout("Linked List: " + (MilliSecs() - Start) + "ms~n")
List1.Clear()
List1 = Null
GCCollect()

Start = MilliSecs()
For Index = 0 Until NUM_ENTRIES
Data = New TData
List2 = List2[..List2.Length + 1]
List2[List2.Length - 1] = Data
Next
WriteStdout("Array standard: " + (MilliSecs() - Start) + "ms~n")
List2 = Null
GCCollect()

Start = MilliSecs()
List3 = New TData[1]
For Index = 0 Until NUM_ENTRIES
Data = New TData
If Index >= List3.Length Then List3 = List3[..(List3.Length Shl 1)]
List3[Index] = Data
Next
WriteStdout("Array with capacity: " + (MilliSecs() - Start) + "ms~n")
List3 = Null
GCCollect()

End

Type TData
Field Foo : String
Field X : Int
Field Y : Int
Field Z : Int
End Type

Wenn man NUM_ENTRIES erhöht, sollte man die 2 Methode gleich auskommentieren. Sie dauert Ewigkeiten. Generell kann man sagen, dass Linked Lists und Arrays mit Kapazitäten in etwa gleich schnell sind, wenn es um Anlegen von Einträgen geht.

Output:
Zitat:

Linked List: 4ms
Array standard: 1380ms
Array with capacity: 2ms

Wenn man alle Einträge von vorn bis hinten durchgeht, sind Arrays minimal schneller als Linked Lists. Der große Vorteil bei Arrays ist aber der direkte Zugriff aus Indizes, was bei Linked Lists erst über n Repitationen möglich ist. Weiterhin lassen sich Linked Lists nur über Bubble Sort sortieren, bei Arrays, vorallem mit 2^x Kapazität, geht auch Quick Sort und Co.

Arrays mit den Kapazitäten sind also auf den ersten Blick höchst effizient.

vertex.dreamfall.at | GitHub

	Artemis	Fr, Sep 07, 2007 15:21 Antworten mit Zitat
Nette Sache. Danke für das kleine Essay.

Artemis

Fr, Sep 07, 2007 15:21
Antworten mit Zitat

Nette Sache.

Danke für das kleine Essay.

	Dreamora	Fr, Sep 07, 2007 15:30 Antworten mit Zitat
Sehr gut. Das ganze kannst du noch erweitern um 2 Dinge wenn du es noch weiter ausreizen willst: 1. Speicher in Element 0 rein wieviele Felder effektiv genutzt werden. (heisst im klartext den Index des nächsten nicht genutzten Elementes). Wenn diese Nummer = Length musst du den Array vergrössern. 2. Wenn weniger als c * Length Einträge genutzt werden, wird der Array via slice wieder halbiert. Bei mir ist c = 0.35 ibs 0.4, damit habe ich bisher sehr gute Erfahrungen gemacht (grösser ist gefährlich wenn kurzzeitig viel hinzugefügt und wieder entfernt wird wird unnötig viel gesliced, darum lieber ein wenig "Übertrag"). Dies musst du übrigens nur testen, nachdem ein Element aus der Datenstruktur entfernt wurde. Ich habe das selbst bei mir auch in die THeap Datenstruktur integriert um Geschwindigkeit und RAM Verschleiss unter kontrolle zu bekommen. Arrays die so genutzt werden, sind nicht nur auf den ersten Blick höchst effizient sondern auch auf den letzten Nicht nur wegen den Sort Algorithmen, sondern weil man BinärBäume und weitere Datenstrukturen auch mit Arrays aufbauen kann, nicht nur mit Pointern. Darüber hinaus kommen wie du schon erkannt hast, auch die Sortieralgorithmen zum tragen, die nicht selten in der einen oder anderen Form auf Arrays oder zusammenhängenden Strukturen im Speicher basieren. PS: Die Verwendung von 2^k für Dinge wie Grössen etc ist ein standard Vorgehen in der Algorithmik, mindestens bis Quantencomputer der Standard sein werden.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Sep 07, 2007 15:30
Antworten mit Zitat

Sehr gut.

Das ganze kannst du noch erweitern um 2 Dinge wenn du es noch weiter ausreizen willst:

1. Speicher in Element 0 rein wieviele Felder effektiv genutzt werden. (heisst im klartext den Index des nächsten nicht genutzten Elementes). Wenn diese Nummer = Length musst du den Array vergrössern.

2. Wenn weniger als c * Length Einträge genutzt werden, wird der Array via slice wieder halbiert. Bei mir ist c = 0.35 ibs 0.4, damit habe ich bisher sehr gute Erfahrungen gemacht (grösser ist gefährlich wenn kurzzeitig viel hinzugefügt und wieder entfernt wird wird unnötig viel gesliced, darum lieber ein wenig "Übertrag").
Dies musst du übrigens nur testen, nachdem ein Element aus der Datenstruktur entfernt wurde.

Ich habe das selbst bei mir auch in die THeap Datenstruktur integriert um Geschwindigkeit und RAM Verschleiss unter kontrolle zu bekommen.

Arrays die so genutzt werden, sind nicht nur auf den ersten Blick höchst effizient sondern auch auf den letzten Smile

Nicht nur wegen den Sort Algorithmen, sondern weil man BinärBäume und weitere Datenstrukturen auch mit Arrays aufbauen kann, nicht nur mit Pointern. Darüber hinaus kommen wie du schon erkannt hast, auch die Sortieralgorithmen zum tragen, die nicht selten in der einen oder anderen Form auf Arrays oder zusammenhängenden Strukturen im Speicher basieren.

PS: Die Verwendung von 2^k für Dinge wie Grössen etc ist ein standard Vorgehen in der Algorithmik, mindestens bis Quantencomputer der Standard sein werden.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Farbfinsternis	Fr, Sep 07, 2007 16:56 Antworten mit Zitat
Mir stellt sich bei solchen Aufstellungen immer direkt die Frage nach der Realitätsnähe. Diese Benchmarks erzeugen doch in der Regel den worst-case um verschiedenen Tests in Zahlen abbilden zu können. Direkte Frage: Wenn ich folgendes Konstrukt habe: Code: [AUSKLAPPEN] [EINKLAPPEN] Type TType Global _list:Tlist Field dummy:String Function AddEntry:TType(dummy:String) Local entry:TType = New TType If entry._list = Null Then entry._list = New TList entry._list.AddLast(entry) entry.dummy = dummy Return entry End Function End Type Local myEntry:TType = TType.AddEntry("Hallo Welt") ' ... irgendwas ... For Local test:TType = EachIn myEntry._list Print test.dummy Next Sagen wir ich erzeuge davon 10.000 Instanzen, was würdest Du raten um eine ähnliche Funktionalität zu erhalten und die Geschwindigkeit zu steigern wenn ich pro Frame die komplette Liste durchgehen? (Target wäre 60FPS)
Farbfinsternis.tv

Farbfinsternis

Fr, Sep 07, 2007 16:56
Antworten mit Zitat

Mir stellt sich bei solchen Aufstellungen immer direkt die Frage nach der Realitätsnähe. Diese Benchmarks erzeugen doch in der Regel den worst-case um verschiedenen Tests in Zahlen abbilden zu können.

Direkte Frage:

Wenn ich folgendes Konstrukt habe:
Code: [AUSKLAPPEN]

Type TType
Global _list:Tlist
Field dummy:String

Function AddEntry:TType(dummy:String)
Local entry:TType = New TType
If entry._list = Null Then entry._list = New TList
entry._list.AddLast(entry)
entry.dummy = dummy

Return entry
End Function
End Type

Local myEntry:TType = TType.AddEntry("Hallo Welt")

' ... irgendwas ...

For Local test:TType = EachIn myEntry._list
Print test.dummy
Next

Sagen wir ich erzeuge davon 10.000 Instanzen, was würdest Du raten um eine ähnliche Funktionalität zu erhalten und die Geschwindigkeit zu steigern wenn ich pro Frame die komplette Liste durchgehen? (Target wäre 60FPS)

Farbfinsternis.tv

	Dreamora	Fr, Sep 07, 2007 17:07 Antworten mit Zitat
Wenn du nur durchgehen musst ist der Unterschied minimal. Wobei auch dann bei 60 * 10'000 also 600'000 Zugriffen auf den Iterator vermutlich der Array definitiv schneller sein müsste. Solltest du aber aus irgend einem Grund auf ein spezielles Objekt in der Liste (zb 2213) zugreifen müssen, wird der Array um einige Welten schneller sein. Auch solltest du es sortieren müssen. Es kommt hier definitiv darauf an, was du mit der Struktur genau machen willst. Für ein Partikelsystem zb wär der Array komplett unbrauchbar. (die LinkedList in direkter Nutzung aber auch, da muss man noch mit Pooling erweitern, sonst wird man vom GC übelst ausgebremst)
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Sep 07, 2007 17:07
Antworten mit Zitat

Wenn du nur durchgehen musst ist der Unterschied minimal.
Wobei auch dann bei 60 * 10'000 also 600'000 Zugriffen auf den Iterator vermutlich der Array definitiv schneller sein müsste.

Solltest du aber aus irgend einem Grund auf ein spezielles Objekt in der Liste (zb 2213) zugreifen müssen, wird der Array um einige Welten schneller sein. Auch solltest du es sortieren müssen.

Es kommt hier definitiv darauf an, was du mit der Struktur genau machen willst.

Für ein Partikelsystem zb wär der Array komplett unbrauchbar. (die LinkedList in direkter Nutzung aber auch, da muss man noch mit Pooling erweitern, sonst wird man vom GC übelst ausgebremst)

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	LordArtus	Fr, Sep 07, 2007 18:56 Antworten mit Zitat
Hi, Sehr nett das Ganze. Mich würde aber interresieren , wie lange das Löschen des 'Arrays with capacity' dauert , weil mit Code: [AUSKLAPPEN] [EINKLAPPEN] List3 = Null ist es nicht getan. MfG LordArtus p.s. QuickSort geht mit LinkedList , bloss ist es halt langsamer

LordArtus

Fr, Sep 07, 2007 18:56
Antworten mit Zitat

Hi,

Sehr nett das Ganze.
Mich würde aber interresieren , wie lange das Löschen des 'Arrays with capacity' dauert , weil mit
Code: [AUSKLAPPEN]

List3 = Null

ist es nicht getan.

MfG

LordArtus

p.s. QuickSort geht mit LinkedList , bloss ist es halt langsamer Wink

	Dreamora	Fr, Sep 07, 2007 19:59 Antworten mit Zitat
Löschen gibt es garnet, das ist auch irrelevant. Denn der GC arbeitet per definition NICHT zeitnahe. Sprich du kannst nie darauf zählen das er etwas JETZT macht. Wenn etwas jetzt gemacht werden muss, musst du das selbst machen. Davon abgesehen ist die Liste eine stärkere Belastung was erzeugen und löschen betrifft, weil es den Speicher fragmentiert und nicht zack einen fixen Block erzeugt.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Sep 07, 2007 19:59
Antworten mit Zitat

Löschen gibt es garnet, das ist auch irrelevant.
Denn der GC arbeitet per definition NICHT zeitnahe. Sprich du kannst nie darauf zählen das er etwas JETZT macht. Wenn etwas jetzt gemacht werden muss, musst du das selbst machen.

Davon abgesehen ist die Liste eine stärkere Belastung was erzeugen und löschen betrifft, weil es den Speicher fragmentiert und nicht zack einen fixen Block erzeugt.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	LordArtus	Fr, Sep 07, 2007 20:30 Antworten mit Zitat
Ah , ok , danke. Muss mich nochmal in Grundlagen einarbeiten. MfG LordArtus

LordArtus

Fr, Sep 07, 2007 20:30
Antworten mit Zitat

Ah , ok , danke.
Muss mich nochmal in Grundlagen einarbeiten. Smile

MfG

LordArtus

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

Essay für schnelle Listen

Betreff: Essay für schnelle Listen