Arrayoperationen beschleunigen

[alzaimar]

Also das mit den 172% oder 176% oder was auch immer habe ich auch schon gehört, deckt sich aber nicht mit meinen Versuchen. Ich habe meine Arrays einfach immer von der Größe her verdoppelt. Das ist unterm Strich schneller als die 176% und auch nachvollziehbar: Es wird ja seltener vergrößert.

Kann mir jemand mathematisch beweisen, das die 172/176% optimal sind? Also ich meine, das es umso optimaler wird, je größer der Vergrößerungsfaktor ist. Nur praktikabel ist es nicht.

[Der_Unwissende]

Zitat:

Zitat von alzaimar

Kann mir jemand mathematisch beweisen, das die 172/176% optimal sind? Also ich meine, das es umso optimaler wird, je größer der Vergrößerungsfaktor ist. Nur praktikabel ist es nicht.

Nicht dass das noch ansatzweise zum eigentlichen Topic gehört, aber optimal in Bezug auf was? Laufzeit oder Speicherausnuztung? Und für Letzteres wäre sicherlich mehr reservieren suboptimal. Aber ich glaube, dass keiner behauptet hatte, dass die 172/176% optimal sind, oder?

Aber mal interesse halber, mit welcher Größe startest du denn? Da hast du doch sicherlich auch einen Erfahrungswert, denke nicht dass du erst 1 Element hast und dann immer verdoppelst.

Gruß Der Unwissende

[alzaimar]

Zitat:

Zitat von Der_Unwissende

Nicht dass das noch ansatzweise zum eigentlichen Topic gehört, aber optimal in Bezug auf was? Laufzeit oder Speicherausnuztung? Und für Letzteres wäre sicherlich mehr reservieren suboptimal. Aber ich glaube, dass keiner behauptet hatte, dass die 172/176% optimal sind, oder?

Aber mal interesse halber, mit welcher Größe startest du denn? Da hast du doch sicherlich auch einen Erfahrungswert, denke nicht dass du erst 1 Element hast und dann immer verdoppelst.

Doch, ich finde, das gehört zum Topic "Arrayoperationen beschleunigen". Und da es um "Beschleunigen" geht, ist logischerweise das "optimal" auf die Geschwindigkeit bezogen, insofern ist deine Frage überflüssig. Und es wird behauptet, die 172/176% seien irgendwie 'besser' als andere Faktoren, nicht unbedingt in diesem Thread, aber allgemein. Ich halte diese "magische Zahl" übrigens für einen Hoax, aber das nur am Rande.

Ich habe eine TStringDictionary , die arbeitet mit einer Hashmap, und die ist als ein Array implementiert. Wenn die Hashmap voll ist, muss ich das Array vergrößern. Ich habe mit 1.72 2/3, Fibbionacci etc. experimentiert und bin schlussendlich bei der 2 geblieben (als Vergrößerungsfaktor). 4 ist noch besser, aber so marginal, das mir da die 2 lieber ist.

Meine Anfangsgröße ist 997 (Primzahl, ist so bei Hashmaps), wobei es wirklich egal ist ob man mit 1 oder 997 anfängt. Jedenfalls bei meinen Versuchen, die 1-10 Millionen Strings in die Liste eingefügt haben.

Bis 2^31 Einträge in der Liste sind, wird diese bei einer Anfangsgröße von 997 Elementen 20x vergrößert. Ob ich beim Einfügen von 2^31 Elementen nun 30 (Anfangsgröße = 1) oder 20x vergrößere ist völlig egal: Das Laufzeitverhalten bleibt gleich, denn die 10 anfänglichen Vergrößerungen (Anfangsgröße=1, bis auf 1000 Elemente) geht einfach zu schnell und gehen in der Messung über die 1.000.000 Elemente unter.

Damit die StringDictionary auch für kleinere Mengen praktikabel ist, habe ich die Anfangsgröße doch auf 997 gesetzt. Damit kommen normale Anwendungen gänzlich ohne dynamische Vergrößerung aus.

Wenn ich dagegen mit kleineren Faktoren spiele, wird das Teil doch etwas langsamer. Also habe ich mich für 200% entschieden, was im Code auch irgendwie cooler aussieht, also (*1.72), obwohl das Geschmackssache ist.

Übrigens ist es entgegen meiner anfänglichen Meinung nicht so, das es umso schneller ist, je höher der Vergrößerungsfaktor ist. Ich hab mal die Kurve der zu Gesamtanzahl der zu verschiebenden Elemente ggü dem Vergrößerungsfaktor aufgezeichnet und das lokale Minimum liegt irgendwo bei 4-5 (sofern meine Formel stimmt).

[Der_Unwissende]

Zitat:

Zitat von alzaimar

Doch, ich finde, das gehört zum Topic "Arrayoperationen beschleunigen". Und da es um "Beschleunigen" geht, ist logischerweise das "optimal" auf die Geschwindigkeit bezogen, insofern ist deine Frage überflüssig.

Entschuldige, war gerade geistig noch in einem anderen Thread, nehme alles zurück! :oops: Erst lesen, dann schreiben, da war doch was. Tut mir echt leid!

An die Messungen und die Hashmaps (gab doch einmal eine String und einmal eine Integer basierte?) kann ich mich (wieder ohne nochmal zu lesen) noch erinnern, die waren/sind echt gut/flink!

Ja, sorry nochmal, nichts für ungut! Hier in dem Thread gebe ich dir natürlich völlig recht!

Gruß Der Unwissende

[alzaimar]

Ich hab mich schon gewundert, aber lass man, liegt am Wetter: Ich war dafür gestern dumm wie Brot.

[himitsu]

Zitat:

Zitat von Der_Unwissende

An die Messungen und die Hashmaps (gab doch einmal eine String und einmal eine Integer basierte?) kann ich mich (wieder ohne nochmal zu lesen) noch erinnern, die waren/sind echt gut/flink!

Hier geht es mehr um das Array selber, wie man die Datenverarbeitung innerhalb des Arrays beschleunigt ist 'ne andere Sache.



[add]
klar sind die kurzen Inlineversionen schnell und schön ... verwende die kleinen Zwei-/Dreizeiler auch recht oft ... hab's da oben zwar schön in Funktionen verpackt (weil etwas übersichtlicher), aber nimand verbietet es einem, wenn man es direkt im Code verwendet (so wie z.B. bei 1.)

[negaH]

Zitat:

1.) Neuere Delphi-Compiler sollten den inlinen
2.) ja. geht bestimmt auch per boolescher Verknüpfungen... aber das kann ich nicht^^
3.) Naja... man kann dafür auch eine zusätzliche variable deklarieren^^
4.) Wärs die lieber als typisierte private Konstante? Wink Kann man natürlich jederzeit innerhalb der am nchsten gelegenen Klasse deklarieren Wink

Hm, meine Antwort, einfach mal als Kontrapunkt betrachten

1.) davon weiß ich nichts und ich kenne keinen Compiler der einfach mal so aus überschwenglicher Eigenkreativität eine Funktion als Inline compiliert bei der der Programierer es nicht explizit vorgegeben hat. Viel eher ist meine Erfahrung, egal ob PASCAL/C Compiler, das Inline Funktionen bei weitem eben nicht das gleiche sind wie zb. Makros oder direkter Code. Viele Compiler machen da einen Unterschied wenn es um die Optimierung geht.

2.) Nein geht per Boolscher Verknüpfung eben nicht. Du multiplizierst mit einer Fließkommazahl und das kannst du nicht in Boolscher Algebra rechnen. Integer mod 256 = 0 geht degeben sehr wohl, da der Compiler das in Integer and $FF = 0 umsetzten kann.

3.) Und noch eine zusätzliche globale Variable, obwohl doch nur 3 zusätzliche Zeile im Sourcecode das Problem lokal lösen können.

4.) Hm, wieder ein Kniff obwohl die Lösung doch simpel ist

Ich meine das man die Logik beim Programmieren nicht so ansetzten sollte das man für alles eine fertige Klasse oder Bibliothek benötigt, schon garnicht für so wirklich simple Sachen. Manchesmal denke ich das viele Leute ein Problem versuchen viel komplizierter zu machen, ganz im Gegensatz zur Grundaufgabe eines Programmieres -> lösen von Problemen auf die einfachste Art.

Das soll jetzt keine Kritik an deiner Person oder deinem Vorschlag sein. Einfach nur so'n par Argumente die mir spontan in der Birne rumsausen ;)

@alzaimar:

Ähnliche Erfahrungen habe ich auch gemacht. Bisher habe ich noch nie eine Faustformel gefunden die auf alle Algorithmen und Problemstellungen und Datenaufkommen und underlaying Bibliotheksimplementierungen anwendbar ist. Die bisher beste durchschnittliche Vorgehensweise war die binäre Quadratische Annäherung, also die Verdopplung/Halbierung in unserem Fall. Am besten 2'er Potenzen. Das deckt sich in irgendeinerweise auch mit vielen anderen Verfahren wie "Binary Splitting-Divide & Conquer", "Binäre Suche", "QuickSort" etc.pp. Allerdings bin ich bei der Speicherallokation sehr sehr konservativ und alloziere lieber linear um einen Betrag +X. Am besten ist es aber wenn man schon von vornherein das Datenaufkommen kennt und dann gezielt reagieren kann. Und exakt das ist möglich wenn man im Gesamtkonzept seiner Programmierung darauf Einfluß nehmen kann. Die beste Optimierung findet also an diesem Punkt statt.

Man muß fairerweise aber auch sagen das wir hier über "Details" diskutieren, denn sehr oft sind es nicht solche Allozierungen wie diese hier im Forum die den Flaschenhals darstellen.

Gruß Hagen

[himitsu]

Was das zuviele Length-Aufrufen angeht:

Bis auf die ersten beiden Varianten gibt's da wohl nicht mehr sooooviel Unterschied,

Delphi-Quellcode:

// if length(Arr) = 0 then
if Arr = nil then

// If Length(Arr) <> 0 Then
// If Length(Arr) > 0 Then
If Arr <> nil Then

// If Length(Arr) > 123 Then
If (Arr <> nil) and (PInteger(Integer(Arr) - 4)^ > 123) Then

// If Length(Arr) < 123 Then
If (Arr = nil) or (PInteger(Integer(Arr) - 4)^ < 123) Then

...

wenn man sich dagegen die Funktion ansieht ... abgesehen von dem zusetzlichen 2 Sprüngen (zur Funktion und zurück).

den nach Pascal übersetzt sieht die ja in etwa so aus:

Code:

Function Length(Arr): Integer;
  Begin
    If Arr = nil Then Result := 0
    Else Result := PInteger(Integer(Arr) - SizeOf(Integer))^;
  End;

PS an Borland: wie wäre es ohne die Funktion und direkt Inline (wie oben)? :zwinker:



Aber wer auf Kurz steht ... hier nochmal die Zwei-/Dreizeiler as InlineCode:

Code:

// entspricht 2.
[b]If[/b] [color=red]Arr[/color] <> nil [b]Then[/b] PInteger(Integer([color=red]Arr[/color]) - 4)^ := (PInteger(Integer([color=red]Arr[/color]) - 4)^ + [color=green]255[/color]) [b]and[/b] -[color=green]255[/color]; 
SetLength([color=red]Arr[/color], ([color=blue]NewSize[/color] + [color=green]255[/color]) [b]and[/b] -[color=green]255[/color]); 
[b]If [color=red]Arr[/color] <> nil [b]Then[/b] PInteger(Integer([color=red]Arr[/color]) - 4)^ := [color=blue]NewSize[/color];

Code:

// ist zwar schneller/kürzer, aber es wird immer die Längen-Variable benötigt
SetLength([color=red]Arr[/color], ([color=blue]NewSize[/color] + [color=green]255[/color]) and -[color=green]255[/color]); 
[color=red]ArrLen[/color] := [color=blue]NewSize[/color];

// und will man mal das Array ohne ArrLen weitergeben, 
// sollte/muß die tatsächliche Länge nochmals angepaßt werden:
SetLength([color=red]Arr[/color], [color=red]ArrLen[/color]);

Dann sei nochmals darauf hingewiesen, daß "einige" eurer Codes das Array nur vergrößern
und speziell Hagen's Methoden mit MOD setzen voraus, daß immer ein bestimmter Punkt getroffen wird, bevor vergrößert/geändert wird.

Gut, bei mir ist es dagegen dann zwar nicht mehr ganz optimal, aber dafür kann/darf man dort auch mal in unterschiedlichen Schritten ändern und natürlich das Array auch wieder verkleinern.



Und ja, Methode 7 (siehe negaH) ist natürlich das Optimum, da dort nur einmal und genau auf das was nötig ist geändert wird.

[alzaimar]

Hmitsu: Ich verstehe Dein bestreben, inline-Code zu erzeugen, aber wäre es nicht wirklich sinnvoller, die Array-Größe zu verdoppeln (oder zu vereinskommasiebenzweifachen :mrgreen: )? Dann ist es doch völlig egal, wie die SetLength-Routine arbeitet, nur bei der 'Length'-Funktion könnte man sich einen Funktionsaufruf sparen. Hier allerdings wäre es sicherlich noch einen Tick schneller, die aktuelle Größe des Arrays in einem Feld zu speichern... Wäre das nicht *noch* schneller?

[himitsu]

Ich hab ja nichts dagegen, wenn man die aktuelle Größe in einer Extravariable speichert (siehe 1.),
nud kann das auch mal schnell unübersichtlich/unpraktisch werden.
z.B. bei vielen Arrays, oder wenn man das Array dann an andere (fremde) Funktionen übergeben möchte, denn da muß man dann entweder die zusätzliche Variable mitgeben, wenn das überhaupt geht).


Ansonsten mag verdoppeln, oder bei raschem anwachsen ein vermehrfachen recht schick,
aber bei "sehr" großen Arrays wohl auch nicht mehr gut (z.B. Speicherauslagerung durch Windows und massig ungenutzt reservierten Speicher).
Da ist dann wohl ein gut gewählter, fester Wert auch nicht zu verachten.



PS: auch wenn ich selber oftmals InlineCode verwende, waren die Inlines von mir nur wegen der "Funktions-Hasser" (nicht böse und ganz ernst gemeint).


Naja, daß die Standardfunktionen nicht so ganz optimal sind ist wohl klar und inzwischen sind hier wohl auch schon 'ne ganze Menge Möglichkeiten zusammengekommen, wie man da was verbessern könnte.
Und am Ende kommt es eh auf jeden Programmierer und das Programm drauf an, was wohl die bessere Lösung ist.


Und bei wenigen/seltenen Größenänderungen lohnt sich der "Aufwand" eh kaum.

Zitat:

Zitat von negaH

Man muß fairerweise aber auch sagen das wir hier über "Details" diskutieren, denn sehr oft sind es nicht solche Allozierungen wie diese hier im Forum die den Flaschenhals darstellen.

Na ja, ein Flaschenhals ist es dennoch.

Alleine mit sowas konnte ich z.B. in h-Sync die Verarbeitung von vielleicht 3 bis 4 Dateien die Sekunde auf knapp 1000 raufschrauben ... zum Ende hin, bei 'ner 7-stelligen Anzahl an Dateien.

Klar ist das nicht die einzige Engstelle, aber jede "kleine" vorteil verbessert das Gesamtergebnis.
Und vorallem dann, wenn es sich um soeine winzige Veränderung handelt, welche dennoch große Wirkungen zeigen kann.