Laden...

Fast and Simple Bitmap Filter

Erstellt von zommi vor 14 Jahren Letzter Beitrag vor 13 Jahren 15.059 Views
zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren
Fast and Simple Bitmap Filter

Hallo an alle,

ich habe gerade mit Reflection, CIL Generierung und Konsorten rumgespielt.
Heraus kam ein eine Klasse zur Anwendung von (homogenen) Punktoperationen auf Bitmaps.
(Bisher nur als Proof Of Concept, daher auch nur 24bit RGB als Farbmodell, usw...)
Aber ich wollte es euch nicht vorenthalten, und bin gespannt auf eure Meinungen.

Demonstrieren werd ich es anhand eines Bild-Farben-Invertierers.

Verwendung:
Man erzeugt einen neuen PunktFilter und übergibt einen Delegaten auf eine Methode, welche auf alle Pixel (genauer gesagt sogar auf jeden Farbkanal jedes Pixels) angewendet wird.


   BitmapFilter inverter = BitmapFilter.CreatePointFilter((byte b) => (byte)(255 - b));
   inverter.Filter(myBitmap);

Das wars. Einfacher könnte das eigentlich nicht sein 8).

Motivation:
Wer viel mit Bildverarbeitung zu tun hat - oder auch mit sonstigen Algorithmen, die zeitkritisch sind und möglichst schnell ablaufen sollen - verzettelt sich oft in Optimierungen. Oft kann man nicht auf vorgefertige Bibliotheken zurückgreifen und muss wirklich Low-Level sich den einzelnen Pixeln widmen.

Und jetzt wirds richtig knifflig, zugleich höchst performanten, aber troztdem sauberen + gut wartbaren Code zu schreiben. Im grunde nicht möglich. Und da man aber allein mit schönem Code ein Problem nicht effizient lösen kann, wirds oft hässlich. 😜

Viele Algorithmen haben zwar das selbe Gerüst, aber einen anderen Kern. Beispielsweise wird immer über das komplette Bild iteriert und irgendwas mit den Pixeln gemacht.

Nun kann man ganz abstrakt und in einem 3-Zeiler solche Algorithmen mit GetPixel/SetPixel umsetzen, ärgert sich dann aber schwarz über die Langsamkeit. Oder man überlegt sich eine 50 Zeilen lange, gut optimiertn, und noch parallel arbeitende Implementierung - aber dafür ist der Code ziemlich aufgeblät und nicht mehr sofort verständlich.
Aber Performance ist manchmal halt alles.

Natürlich ist die Wiederverwendbarkeit extrem eingeschränkt. Man kann zwar versuchen das Codegerüst mit Generikas und Delegaten "variabel" zu machen, aber dadurch verlangsamt sich wieder die Geschwindigkeit, weil zahlreiche Compiler und JITter-Optimierungen einfach nicht vorgenommen werden können und die zusätzlichen Indirektionsstufen die Performance wieder auffressen.

Bisher blieb für mich als einzig performante Möglichkeit nur die CopyPaste-Variante, das Code-Gerüst also stets zu duplizieren und manuell anzupassen. Doch so wird der Code noch aufgeblähter, fehleranfälliger, weniger gut wartbar und entspricht wohl gar nicht dem DRY-Prinzip.

Daher kam mir die Idee, die Code-Gerüst-Idee mittels Reflection und eigenem IL-Code-Umschreiber zu lösen.
So wie Generikas (zumindest bei Werttypen) ja auch dazu führen, dass der Code mehrfach mit den eingesetzten Typen neu kompiliert wird, wollte ich so etwas auch für Methoden implementieren !

Wie funktioniert das?
Intern habe ich eine (wie ich finde) hoch optimierte Pixel-Durchlauf-Routine, die allerdings nichts tut und eine kleine Dummy-Methode mit jedem Pixel aufruft.

Von dieser mache ich bei der Erzeugung des Filters eine "Kopie" in Form einer DynamicMethod. Also ich dupliziere den CIL-ByteCode, passe alle MetadatenToken an und injiziere die übergebene Pixel-Methode direkt hinein.
Im Grunde ist das ganz einfach, da ich nur nach Aufrufen zur Dummy-Methode suche und diese durch Aufrufe zur übergebenen Pixel-Verarbeitungs-Methode ersetze.
Trotz der Variabilität sind nun keine Delegaten-Aufrufe drin, sondern direkte Call-Befehle.
Und wenn die Methode so klein ist wie oben. (keine Schleifen, wenig Ifs, kurze Codelänge), dann kümmert sich der JITter sogar gratis um's Inlining. 👍

Die Funktion für "Ersetze in Methode x den Aufruf nach Methode y durch Methode z" hab ich selbst allgemein gehalten, sodass sie überall wiederverwendet werden kann. Die Signatur ist:

public static T ReplaceCall<T, S>(T mainMethod, S oldMethod, S newMethod)

Man darf sie nur mit Delegaten aufrufen, sonst gibts ne Exception. (Ich konnte die Typ-Parameter leider nicht auf Delegate einschränken, das mochte mein Compiler nicht 🤔 )
Aber von der Verwendung ist das dank C# auch praktisch, da ja Methoden-Namen auch direkt in Delegaten konvertiert werden können. Somit wäre ein Verwendungsbeispiel:


public class MyClass
{
	public delegate void CallDelegate();
	public static void Call()
	{
		Console.WriteLine("{0} World!", Foo());
	}

	public delegate string FooBarDelegate();
	public static string Foo()
	{
		return "Hello";
	}

	public static string Bar()
	{
		return "Bye";
	}

	public static void Main(string[] args)
	{
		CallDelegate test = ILWeaver.ReplaceCall<CallDelegate, FooBarDelegate>(Call, Foo, Bar);
		test.Invoke();
	}
}

Ausgegeben wird eben nicht "Hello World", was die Implementierung von Call() wäre, sondern "Bye World".

Noch als Zusatz:
Die verwendete Pixel-Durchlauf-Routine nutzt zudem auch MultiCores aus und splittet dazu das Bild in Streifen und arbeitet diese parallel ab. (Jede CPU bekommt einen Streifen, abgearbeitet wird im ThreadPool)
Wenn man nun auch das als CodeGerüst per CopyPaste verwendet, wird man echt bekloptt und verzettelt sich dermaßen mit CopyPaste-Fehlern. (Aber man kann mit seinen LinesOfCode angeben 😉)

Benchmarks
Ich habe vier Implementierungen zur Invertierung des 24Bit Bildes gegeneinander antreten lassen:1.Die obligatorische GetPixel/SetPixel Routine 1.Die 3-fach verschachtelte Byte-Buffer-Schleife 1.Die All-In-One und Hauptsache-Kurz Methode 1.Die Neue

Hier die SourceCodes:


for (int y = 0; y < bitmap.Height; y++)
{
	for (int x = 0; x < bitmap.Width; x++)
	{
		Color col = bitmap.GetPixel(x, y);
		byte R = (byte)(255 - col.R);
		byte G = (byte)(255 - col.G);
		byte B = (byte)(255 - col.B);
		bitmap.SetPixel(x, y, Color.FromArgb(R, G, B));
	}
}


BitmapData bd = bitmap.LockBits(
	new Rectangle(new Point(), bitmap.Size),
	ImageLockMode.ReadWrite,
	PixelFormat.Format24bppRgb);


// in den Buffer kopieren
byte[] buffer = new byte[bd.Stride * bd.Height];
Marshal.Copy(bd.Scan0, buffer, 0, buffer.Length);

for (int y = 0; y < bd.Height; y++)
{
	for (int x = 0; x < bd.Width; x++)
	{
		for (int c = 0; c < 3; c++)
		{
			byte value = buffer[y * bd.Stride + 3 * x + c];
			buffer[y * bd.Stride + 3 * x + c] = (byte)(255 - value);
		}
	}
}

// zurück kopieren
Marshal.Copy(buffer, 0, bd.Scan0, buffer.Length);
bitmap.UnlockBits(bd);


BitmapData bd = bitmap.LockBits(
	new Rectangle(new Point(), bitmap.Size),
	ImageLockMode.ReadWrite,
	PixelFormat.Format24bppRgb);

byte[] buffer = new byte[bd.Stride * bd.Height];
Marshal.Copy(bd.Scan0, buffer, 0, buffer.Length);

for (int i = 0; i < buffer.Length; i++)
{
	buffer[i] = (byte)(255 - buffer[i]);
}

Marshal.Copy(buffer, 0, bd.Scan0, buffer.Length);
bitmap.UnlockBits(bd);


inverter.Filter(bitmap);

Allerdings sind zwei Dinge zu beachten: 1. Der Filter muss natürlich (wie ganz oben gezeigt) erst erzeugt, also "compiliert" werden. Im Prinzip wie auch bei Regular Expressions. Und 2. Alle vier Methoden arbeiten direkt auf dem Bitmap. Also auch das Lock-Bits und Marshal.Copy geht in die Rechnung in jeden Lauf mit ein. Das ist irgendwie mehr "aus dem Stand" und darüber hinaus auch fairer der GetPixel-Variante gegenüber 😉.
(Im Gegensatz dazu ist die MemBitmap-Klasse gerade so ausgelegt, diese mehrfache Copys zu vermeiden. Perfekt wäre ein Fusion beider Konzepte)

Aber nun zu den Ergebnissen:
24Bit Bild mit 1024x768 Pixeln auf einem Core2Quad Q9300 @ 2,5Ghz1.GetPixel = 0,47 fps 1.3fachLoop = 92 fps 1.All-In-One = 164 fps 1.Die Neue = 750 fps 1.:::

Und wie schon erwähnt, kann man natürlich alle Varianten (bis auf GetPixel) noch mit ausgelagertem LockBits und Marshal.Copy beschleunigen.

Ausblick:
Weiter ausbauen, dass auch lokale Filter und später auch globale Filter möglich sind. Am besten noch mit weiterer automatischer Optimierung =) Na mal schaun.

Anhang (update)
Im Zip sind sowohl Binaries wie auch der SourceCode. (Die interne Filter-Implementierung und der Code zum Injecten des Delegaten)
Und jetzt auch mit der unten aufgeführten unsafe-variante

beste Grüße
zommi

6.911 Beiträge seit 2009
vor 14 Jahren

Hallo zommi,

schaut sehr interessant aus (muss mir den Code noch genau anschauen 😉). 👍

Super Sache. Vor allem das Ersetzen von IL-Code ist cool.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

C
114 Beiträge seit 2008
vor 14 Jahren

Mhh, das klingt wirklich sehr interessant. Muss ich mir auch direkt mal anschauen. Immerhin könnte damit so manche langwierige Operazion nochmal schneller gehn.

„Heute back ich, morgen brau ich,
übermorgen cast ich die Königin nach int;
ach, wie gut dass niemand weiß,
dass ich Rumpelstilzchen heiß!“

"Bei Stylefragen sollteste nen Mac-User oder ne Frau fragen."

0
767 Beiträge seit 2005
vor 14 Jahren

Tolle Sache, aber würde sich der JIT nicht ohnehin um das inlining des Delegaten kümmern?

Was ich in unserem Projekt gemerkt hab ist, dass die Methode auch ruhig länger sein kann und dennoch gejittet wird.

In unserem Fall waren das um die 30 Zeilen, möglicherweise auch mit Schleife. Die Methode hat keine weitere aufgerufen, war private und nur an einer Stelle verwendet.

Gemerkt haben wirs, weil diese Methode eine NullReferenceException warf, im Stacktrace der Release allerdings die übergeordnete Methode als Ursache angegeben war (an genau der Stelle wo der Aufruf war, und nie eine Nullreference sein konnte).

loop:
btst #6,$bfe001
bne.s loop
rts

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Hi 0815Coder,

So ein Delegat wird ja leider zur Laufzeit nur über eine zusätzliche Indirektionsstufe aufgerufen. Dafür kann man ihn aber auch zur Laufzeit austauschen.

Nimm dir als Beispiel die Array.Sort Methode. Der kannst du beispielsweise einen Delegaten vom Typ Comparison<T> mitgeben, mit dem sortiert wird.

Trotzdem ist die Array.Sort Methode selbst schon fertig in Maschinencode übersetzt. (Weil sie a) vielleicht schonmal aufgerufen wurde und der JITter sie schonmal durch hat, oder b) weil das .Net Framework meines Wissens eh mit Ngen bereits vorkompiliert wurde) Insofern sind alle möglichen Optimierungsschritte - und darunter auch das Inlining - bereits hinter uns, bevor überhaupt der Delegat, geschweige denn das Aufrufziel bekannt ist !

Der an Array.Sort übergeben Delegat wird eben nur über Umwege aufgerufen.

Bei meinem Code wird von einer bereits existierende Methode der Byte-Code analysiert und die Methode des Delegaten direkt in IL reingeschrieben. Wenn diese Methode dann beim Aufruf erstmals an der JITter übergeben wird, kann er die aufgerufene Methode dann auch wirklich inlinen. (Da er jetzt das Aufrufziel auch kennt; sofern noch zusätzliche Bedingungen erfüllt sind)

beste Grüße
zommi

PS: Erster Beitrag oben geupdated.
//Edit: assemlber -> Maschinencode

6.911 Beiträge seit 2009
vor 14 Jahren

Hallo zommi,

selbst schon fertig in assembler kompiliert.

Maschinencode != Assembler(code)

Hallo 0815Coder,

dass die Methode auch ruhig länger sein kann und dennoch gejittet wird.

GeJITet wird jede Methode egal wie lang - sonst könnte sie gar nicht ausgeführt werden 😉
Der JITer verwendet eine Heuristik (die sich aber in den Versionen der CLR ändern kann) um zu bestimmen ob/wann eine Methode geinlined wird. Hier ein kurzer Auszug einiger entscheidenden Punkte:*Methoden mit weniger als 32 byte IL-Code werden geinlined. *virtuelle Methoden (auch die von Interfaces) werden nicht geinlined. *Methoden mit komplexeren Kontrollfluss werden nicht geinlined (zB wenn eine while-Schleife drin ist). *Methoden mit Exception-Handling werden nicht geinlined wobei Methoden die eine Exception werfen (können) können fürs Inlining in Betracht gezogen werden (-> das trifft bei 0815Coder zu) *wenn ein Argument eine Struct ist wird kein Inlining vorgenommen.

Es sollte aber vermieden werden den Code explizit auf diese Richtlinien anzupassen. Wenn es sich zufällig ergibt gut so und wenn nicht steht die Lesbar-/Wartbarkeit und alle sonstigen Vorteile eines übersichtlichen Codes im Vordergrund!

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

0
767 Beiträge seit 2005
vor 14 Jahren

dass die Methode auch ruhig länger sein kann und dennoch gejittet wird.
GeJITet wird jede Methode egal wie lang - sonst könnte sie gar nicht ausgeführt werden 😉]

sorry, ich meinte nicht gejitted, sondern ge-inlined...

Bezüglich deinem 4. Punkt hab ich das Gegenteil in "CLR via C#" gelesen... wenn ein explizites throw vorkommt wird nicht geinlined (bei mir wars ja eine NullReference). try/catch/finally beeinflussen das inlining aber nicht.

Deswegen wird im Framework auch häufig ein ThrowHelper verwendet, dessen kleine Methode die Exception wirft. Somit kann nämlich die eigentliche Methode noch inlined werden und falls die Exception geworfen werden muss (was hoffentlich selten ist) wird eben die Methode zum werfen aufgerufen.

loop:
btst #6,$bfe001
bne.s loop
rts

6.911 Beiträge seit 2009
vor 14 Jahren

Hallo 0815Coder,

Bezüglich deinem 4. Punkt hab ich das Gegenteil in
>
gelesen... wenn ein explizites throw vorkommt wird nicht geinlined... try/catch/finally beeinflussen das inlining aber nicht.

Mir ist das bekannt was ich oben geschrieben habe. Offizielle Dokumentation über den JITer gibt es nicht und daher kann jeder der nicht bei MS in der JITer-Entwicklung ist nur mutmaßen. Mein Statement oben bezieht sich auf die Blogs der JIT-Entwickler und auf die Tests die ich gemacht habe.
Von .net 2.0 zu .net 3.5SP1 hat sich die Handhabung von structs, lokalen Variablen und der bevorzugten Verzweigungen von if-Statements in der Heutistik verändert/gebessert.
Du kannst mal folgende Code laufen lassen und feststellen dass die 2. Methode um das ~6 fache schneller ist -> Folgerung sie wird geinlined obwohl ein throw dabei ist.


using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace ConsoleApplication1
{
	class Program
	{
		static void Main(string[] args)
		{
			Foo1(666);
			Foo2(666);

			Stopwatch sw = new Stopwatch();
			const int N = 100000000;

			sw.Start();
			for (int i = 0; i < N; i++)
				Foo1(666);
			sw.Stop();
			Console.WriteLine(sw.ElapsedTicks);

			sw.Reset();
			sw.Start();
			for (int i = 0; i < N; i++)
				Foo2(666);
			sw.Stop();
			Console.WriteLine(sw.ElapsedTicks);
		}
		//---------------------------------------------------------------------
		[MethodImpl(MethodImplOptions.NoInlining)]
		private static void Foo1(int a)
		{
			if (a < 0)
				throw new ArgumentException();
		}
		//---------------------------------------------------------------------
		private static void Foo2(int a)
		{
			if (a < 0)
				throw new ArgumentException();
		}
	}
}

Ticks für Foo1: 1542157
Ticks für Foo2: 269132
Wenn du ein try-catch(-finally) einbaust sind beide gleich schnell.
Nur weil etwas in einem Buch steht muss es noch nicht stimmen - glaube dem was du selbst verfiziert hast 😁
Getestet mit .net 3.5 SP1 (natürlich im Release Build 😉)

Aber daher mein Vorsatz dass sich das ändern kann und der Nachsatz dass man sich nicht darauf verlassen soll 😉

Deswegen wird im Framework auch häufig ein ThrowHelper verwendet, dessen kleine Methode die Exception wirft. Somit kann nämlich die eigentliche Methode noch inlined werden...

Das hat meiner Meinung nach einen anderen Hintergrund und zwar den von DRY. Nachteilig dabei ist dass suggeriert wird der Fehler stammt von der Methode aus ThrowHelper. Daher ist es zu bevorzugen - und wird von MS in neueren Klassen auch so umgesetzt - dass eine Hilfsmethode die Exception an die eigentliche Methode zurückgibt und dort wird sie geworfen.
Der Vorteil der Hilfsmethode für das Erzeugen einer Instanz von Exception hat auch die Hintergründe darin dass es so einfacher zu lokalisieren ist.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zommi,

hört sich ja sehr interessant an. Soweit ich sehe, hast du aber nicht deinen optimierten Algorithmus mit Aufruf des "richtigen" Delegaten und deinen optimierten Algorithmus mit Ersetzen des Dummy-Delegaten gebenchmarkt. DAS würde mich mal interessieren. Denn das würde zeigen, dass das "manuelle Inlinen" wirklich der ausschlaggebende Faktor ist.

Deine Argumentation mit dem JIT-Compiler (Delegate wurde schonmal aufgerufen und kompiliert und wird deshalb später nicht mehr geinlined) finde ich etwas naiv - denn so arbeitet ein (guter) JIT-Compiler nicht. Beim ersten Aufruf - da soll die Antwortzeit möglichst kurz sein - kommt der Baseline-Compiler dran. Der übersetzt einfach IL nach Maschinencode. "Nebenbei" läuft noch ein Profiler/Sampler mit, um zu entscheiden, wann dann später(!) mal optimiert werden soll und was genau optimiert wird (constant propagation, dead code elimination, constant folding, common subexpression elimination, copy propagation, loop unrolling, partial redundancy elimination, method inlining, etc). Jikes z.B. hat vier solche Optimierungsstufen. Eine Methode wird also nicht zwingend nur ein einziges Mal vom JIT-Compiler kompiliert, sondern - je nach Verwendung - mehrfach adaptiv in verschiedenen Optimierungen. Von daher würde es mich wie gesagt echt interessieren, ob das manuelle Entfernen einer einzigen Indirektionstufe durch Anwenden einer einzigen Optimierungsmöglichkeit wirklich signifikante Performanzverbesserungen bringt.
EDIT: Zuviel Wissen über Konzepte in VMs - das trifft auf .NET nicht zu.
Schöner Artikel dazu: How Are Methods Compiled Just-In-Time and Only Then?

Allerdings ist taucht der Delegate-Code - da hast du vollkommen recht - nicht im (statischen) Aufrufsbaum aus. Von daher ist fraglich, inwiefern der (in der herkömmlichen Methode) geinlined werden kann.

Beste Grüße,
dN!3L

6.911 Beiträge seit 2009
vor 14 Jahren

Hallo dN!3L,

der JITer bei .net kompiliert nur einmal und das wars dann (dies gilt bis .net 2.0, für .net 3.x hab ich aber nichts anderes gesehen).

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Hi dN13L,

hier nun das Ergebnis des erweiterten Benchmarks. Dabei sind:1.GetPixel (s.o.) 1.3Loop (s.o.) 1.AllInOne (s.o.) 1.Delegate (der Algo ruft den übergeben Delegaten auf) 1.No Inline Call (Der Aufruf ist als Call fest codiert, aber ZielMethode hat NoInline-Attribute) 1.Inject (Der Aufruf zur Methode des Delegaten wird direkt reingeschrieben und der JITter durfte inline optimieren) 1.Inject* (wie drüber nur mit jedesmal neuer Code-Erzeugung)

Also das mit dem Delegate ist immernoch (erstaunlich) schnell. Aber das liegt an meiner phantastischen Implementierung der Drumherum-Pixel-Durchlauf-Routine 8).
(alle anderen sind ja beispielsweise gar nicht parallelisiert)
Und der normale Call ohne Inlining ist auch nicht viel weiter vorn.

Die mit dem injizierten Call-Aufruf ge-inlinete ist natürlich schneller. Sogar mehr als doppelt so schnell. Nunja, bei 1024·768·3=2359296 Subpixeln und genauso vielen Aufrufen spürt man jede unnötige Indirektionsstufe.

Und wie oft und gut nun der JITter im Konkreten ist, ist glaub ich auch irrelevant. Wichtig ist, dass obiges Verfahren schneller ist. Und bei meiner Testsituation mehr als 2x so schnell. Bei komplexeren Pixel-Berechnungen verringert sich natürlich das Verhältnis zwischen Delegate-Overhad zu gesamter Berechnung. Aber schneller wird's wohl immer sein.

Interessant ist, dass bei der aktuellen Implementierung/Filteraufgabe und aktuellen Bildgröße sogar der Inject* schneller ist, der erst vorher den Code neuerstellt.

Aber bei kleineren Bildern ist die Filteroperation insgesamt früher fertig, wohingegen die "Kompilierung" genauso lange dauert. Also auch dort verschiebt sich das Verhältnis. Ist also alles nicht als absolut anzusehen. (Aber ich hab ja eine realistische Bildgröße gewählt)

beste Grüße
zommi

PS: Code-Anhang oben wurde ausgetauscht und durch Delegate-Test und NoInline-Test erweitert.

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Nochmal Fazit bis hierher:

Wichtig ist also gar nicht so sehr der Zeitunterschied zwischen Delegate-Aufruf und direktem Call. (Das haben die .NET-Jungs schon performant gemacht)

Sondern vielmehr die Tatsache, dass die Methode beim der Verwendung des direkten Calls auch wirklich inline umgesetzt wird.

Insofern wird mein nächster Schritt sein: Nicht nur dafür sorgen, dass ein Call zu meiner Methode drin steht, sondern dass sie wirklich ge-inlined wird. Egal wie. Auch wenn ich das selbst implementieren muss. (So schwer isses ja auch nicht, müssen nur die Argumente/Lokale Variablen umgeändert und neu numeriert werden; sowie manche Sprungziele angepasst werden; und MaxStackSize neu berechnet werden)
(Aber das war eh mein weiterer Vorgehensweise-Plan. Weil erst wenn ich den Code inline hintereinander weg hab, kann ich gezielt Loop Unswitching, Loop invariant Code Motion, Loop Splitting usw. umsetzen. Das brächte bei solchen Algorithmen nämlich richtig viel. Und wenn ich dann noch lustig bin, denk ich vielleicht über automatische SSE Optimierungen nach. Jaja... der Intel Compiler kann sich schonmal warm anziehen 😄)

beste Grüße
zommi

6.911 Beiträge seit 2009
vor 14 Jahren

sondern dass sie wirklich ge-inlined wird. Egal wie. Auch wenn ich das selbst implementieren muss. ...kann ich gezielt Loop Unswitching, Loop invariant Code Motion, Loop Splitting usw. umsetzen. Das brächte bei solchen Algorithmen nämlich richtig viel. Und wenn ich dann noch lustig bin, denk ich vielleicht über automatische SSE Optimierungen nach

Du willst also einen Präcompiler für den JITer erstellen der die Kunst des Optimierens beherrscht. Viel Glück 😉

Ideal wäre dann auch wenn über Attribute der Optimierungs-Level gesteuert werden kann. ZB bis zu welcher Codegröße wird geinlined, wie groß ist der Unroll-Grad bei Schleifen, etc.

Bei den SSE-Optimierungen kann ich mir vorstellen dass der JITer dir da eine Strich durch die Rechnung machen wird - außer du kannst das JITen umgehen. Dies kann ich mir aber nicht vorstellen es sei denn du erzeigts unmanged Code zur Laufzeit (sollte ja auch irgendwie möglich sein).

Wirklich interessantes Vorhaben!

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Bei den SSE-Optimierungen kann ich mir vorstellen dass der JITer dir da eine Strich durch die Rechnung machen wird - außer du kannst das JITen umgehen. Dies kann ich mir aber nicht vorstellen es sei denn du erzeigts unmanged Code zur Laufzeit (sollte ja auch irgendwie möglich sein).

Wenn ich soweit bin, dass ich aus dem CIL-Code sowas wie nen anständigen, optimierten Syntaxbaum gebaut bekomme, dann kann ich den Code auch in lowlevel C/C++ wieder übersetzen, mit sse-intrinsics versehen und durch den nativen compiler jagen.
Wenn sich jetzt wer fragt, warum ich's dann nich gleich in C/C++ schreibe? Na weils ja zig Sprachen gibt, die in CIL münden, das ist also viel allgemeiner.

beste Grüße
zommi

6.911 Beiträge seit 2009
vor 14 Jahren

Wenn ich soweit bin, dass ich aus dem CIL-Code sowas wie nen anständigen, optimierten Syntaxbaum gebaut bekomme, dann kann ich den Code auch in lowlevel C/C++ wieder übersetzen, mit sse-intrinsics versehen und durch den nativen compiler jagen.

Dann könntest du aus dem Syntaxbaum gleich in eine "native" Sprache übersetzen und den nativen Compiler alle Optimierungen durchführen lassen (auch die SSE-Optimierungen). Somit kannst du dir das sparen.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

[...] alle Optimierungen [...]

Das ist es ja gerade, welcher Compiler kann schon alle Optimierungen? Und welcher kann dann noch automatisch und gut SSE? Und jetzt die Killerfrage: welcher ist zudem kostenlos?

Aber wir kommen wieder vom aktuellen Projekt-Thema ab. Das ist ja eh Zukunftsmusik.

6.911 Beiträge seit 2009
vor 14 Jahren

welcher Compiler kann schon alle Optimierungen

zB Lahey Fujitsu Fortran 95
Der kann wirklich alle. Es lässt sich sogar der ganze Code inlinen und alle Schleifen aufrollen. Hab das mal probiert und der hat tatsächlich eine For-Schleife mit 100000 Iterationen aufgerollt - die Größe der exe ist aber explodiert.
Die Verwendung C#-Fortran ist (im Gegensatz zu mancher Meinung möglich denn der FTN-Compiler kann auch C-style DLLs erstellen).

Und jetzt die Killerfrage: welcher ist zudem kostenlos?

Das trifft auf obigen nicht zu. Das Know-How des Compilers lassen sie sich gut bezahlen 😉

SSE ist schon ziemlich tief unten auf Maschinenebene so dass Assembler-Code erstellt werden könnte und mit MASM compiliert.

Die GNU-Compiler können i.d.R. auch ziemlich viel. Die SSE-Optimierung könnte dort dann zB im Quelltext vorgenommen werden (außer die findest einen der SSE schon kann).

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 14 Jahren

Bitte kommt nicht zu sehr vom Thema ab.

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zommi,

ich habe deine verschiedenen Versionen mal bei mir gebenchmarkt. (Achtung: Etwas anderer Benchmark. Ich habe alle Algorithmen das "Bach"-Beispielbild 50000 filtern lassen und die benötigte Zeit gemessen.)
Zudem hatte ich mich gefragt, warum du das Problem nicht gleich - statt die Algorithmen durch Delegates auszulagern - mittels Template Methods erschlagen hast (dann würde der Code auch im statischen Callstack auftauchen). Aber soweit ich es mitbekommen habe, würden die nicht geinlined werden (weil sie virtual sind). Trotzdem habe ich sie mal mit in den Benchmark genommen- und sie schneiden nicht mal schlecht ab. Sehr verwunderlich ist allerdings, dass die NoInlineCall-Variante am schnellsten ist.
EDIT: Benchmark nochmal richtig durchgeführt und Werte aktualisiert.


Duration for superParallelerDelegatenInjecter:  1:42 min
Duration for superParallelerDelegatenInjecter*: 2:17 min
Duration for TemplateMethod:                    3:08 min
Duration for NoInlineCall:                      3:13 min
Duration for Delegate:                          4:24 min
Duration for All In One:                        4:24 min
Duration for 3xSchleife:                        8:16 min

Aber nichtstdestotrotz: Tolles Projekt, direkt IL-Code auszutauschen 👍

Beste Grüße,
dN!3L

R
104 Beiträge seit 2006
vor 14 Jahren

Hallo!

Etwas in der Art müsste doch auch sehr Schnell sein!?!


        public struct Pixel
        {
            public byte B;
            public byte G;
            public byte R;
        }

System.Drawing.Imaging.BitmapData bd = bmp.LockBits(new Rectangle(0, 0, bmp.Size.Width, bmp.Size.Height), System.Drawing.Imaging.ImageLockMode.ReadWrite, System.Drawing.Imaging.PixelFormat.Format32bppArgb);
            
            int xsize = bmp.Size.Width;
            int ysize = bmp.Size.Height;

            unchecked
            {
                unsafe
                {

                    Pixel* p1 = (Pixel*)bd.Scan0.ToPointer();
                    
                    for (int i = (ysize*xsize); i > 0; i--, p1++)
                    {
                        p1->R= 255-p1->R;
                        p1->G= 255-p1->G;
                        p1->B= 255-p1->B;

                    }

                }
            } 

Vielleicht hat ja jemand lust das zu Benchmarken?
Ich glaube kaum, dass es viel langsamer als die neue Methode ist, dafür aber leider unsave^^

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Hi Richter,

durch die Verwendung von unsafe Pointer-Operationen lassen sich wohl alle oben präsentierten Verfahren (bis auf GetPixel) noch beschleunigen.
Zum einen, weil dann das Marshal.Copy in ein managed byte[]-Array wegfällt und zudem etwaige Range-Checks eliminiert werden können.
(wobei ich bei meiner Implementierung schon darauf geachtet hab, dass möglichst die RangeChecks entfallen können)

Aber wie eingangs schon erwähnt:
Ziel war ja nicht nur "so schnell wie möglich zu sein". Sondern eleganten, guten, wartbaren (jetzt könnte sich an dieser Stelle noch "nicht unsafe" einreihen) Code zu schreiben, der trotzdem schnell ist.

@ dN!3L
Das ist schon komisch, dass die NoInlineCall am schnellsten ist. Es scheint so, als würde bei dir gar kein Inlining stattfinden?! (Dann bringt natürlich das Vorgehen insgesamt nicht so viel... Ziel ist ja gerade durch den direkten Call ein Inlining zu ermöglichen)

//Edit hab mal mit unsafe gearbeitet.
Ist natürlich schneller (das Marshal.Copy entfällt komplett), wodurch sich die Geschwindigkeit nochmal merklich steigern lässt.
Man könnte natürlich überlegen, ob man die interne Pixel-Routine nicht doch unsafe lässt. Schließlich kann man die einmal so gut und "sicher" programmieren, dass nichts passieren kann. Und dann wär es nach außen hin wieder sicher. Von außen merkt man ja bei der Verwendung auch gar nicht, obs intern safe oder unsafe durchs array wandert. Verlockend ist das schon 😉

beste Grüße
zommi

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zommi,

Das ist schon komisch, dass die NoInlineCall am schnellsten ist. Es scheint so, als würde bei dir gar kein Inlining stattfinden?!

boa, ich Depp. Man sollte den Benchmark natürlich nicht aus dem VS mit F5 starten... Ich habe meine Werte oben mal korrigiert - die stimmen jetzt auch mit deinen Beobachtungen überein. Dazu nochmal nen Daumen für die IL-Ersetzung: 👍

Eine Bemerkung hätte ich aber noch: Dein Algorithmus hat mir bei einer bestimmten Konstellation (mehr als 100 Filterdurchläufe auf bitmap und Anzeige in der PictureBox) oft eine InvalidOperation-Exception beim completenEvent.WaitOne() geworfen - Begründung "Das Bitmap wurde bereits gesperrt" (oder so). Als ich dann die Anzeige in der PictureBox entfernt habe, kam die nicht mehr.

Beste Grüße,
dN!3L

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

boa, ich Depp. Man sollte den Benchmark natürlich nicht aus dem VS mit F5 starten

Full Ack 😉 Oder du startest einfach mit "Strg+F5". Dann is auch ok.

Das mit dem InvalidOperation: könnt mir vorstellen, dass Windows das manchmal gern neuzeichnen will. Also greift sowohl Windows und der jeweilige Algo asynchron aufs Bild zu. Wäre zumindest denkbar. Man sollte wohl kein Bild direkt bearbeiten, was grad in der Anzeige ist - aber für sonen kleinen Benchmark sei das erlaubt. 🙂

beste Grüße
zommi

2.921 Beiträge seit 2005
vor 14 Jahren

@Zommi: Mir gefällt die Idee sehr gut, vor allem dass man über den Lambda-Ausdruck die Funktion für den Kanal zur Laufzeit erstellt ist schön und wirklich nicht viel Aufwand.

Was spricht jetzt aber dagegen, z.B. wenn eine Klasse so oder so ähnlich aussieht:


using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;

namespace LowLevelGraphics
{
    public class UnsafeBitmap : IDisposable, LowLevelGraphics.IBitmap
    {
        private Bitmap m_Bitmap = null;
        private System.IntPtr Scan0 = IntPtr.Zero;
        private BitmapData bmData = null;
        private int nLineOffset = -1;
        private int nWidth = -1;
        private List<int> m_aPixel = new List<int>();
        public UnsafeBitmap(Bitmap _bitmap)
        {
            m_Bitmap = _bitmap;
            Test();
        }

        public int Width
        {
            get { return m_Bitmap.Width; }
        }

        public int Height
        {
            get { return m_Bitmap.Height; }
        }

        public void Test()
        {
            // GDI+ still lies to us - the return format is BGR, NOT RGB.
            bmData = m_Bitmap.LockBits(new Rectangle(0, 0, m_Bitmap.Width, m_Bitmap.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

            int stride = bmData.Stride;
            Scan0 = bmData.Scan0;

            unsafe
            {
                byte* p = (byte*)(void*)Scan0;

                int nOffset = 0;
                nLineOffset = stride - m_Bitmap.Width * 3;
                nWidth = m_Bitmap.Width * 3;

                int y = 0;
                int x = 0;
                m_aPixel.Add(nOffset);
                for (y = 0; y < m_Bitmap.Height; ++y)
                {
                    for (x = 0; x < m_Bitmap.Width; ++x)
                    {
                        nOffset += 3;
                    }
                    nOffset += nLineOffset;
                    m_aPixel.Add(nOffset);
                }
            }

        }

        public Color GetPixel(int x, int y)
        {
            int nOffset = m_aPixel[y]+x*3;
            byte r = Marshal.ReadByte(Scan0,nOffset +2);
            byte g = Marshal.ReadByte(Scan0, nOffset+1);
            byte b = Marshal.ReadByte(Scan0, nOffset);
            return Color.FromArgb(r, g, b);
        }

        public bool SetPixel(int x,int y,Color _color)
        {
            int nOffset = m_aPixel[y]+x*3;
            Marshal.WriteByte(Scan0, nOffset + 2, _color.R);
            Marshal.WriteByte(Scan0, nOffset + 1, _color.G);
            Marshal.WriteByte(Scan0, nOffset, _color.B);
            return true;
        }

        public Bitmap InternalBitmap
        {
            get { return m_Bitmap; }
        }

        #region IDisposable Member

        public void Dispose()
        {
            m_Bitmap.UnlockBits(bmData);
        }

        #endregion
    }
}

Anmerkung: nur ungefähre Implementation
Hier ist ebenfalls ein GetPixel / SetPixel implementiert. Über ein Dispose müsste hier am Ende wieder freigegeben werden.

Das dann nicht so zu machen, und davon ebenso die Syntax abzuleiten, dass man eben über einen Lambda Ausdruck dann diese Methode zur Funktion heranruft?

Also eben:


BitmapFilter inverter = BitmapFilter.CreatePointFilter((byte b) => (byte)(255 - b));
   inverter.Filter(myBitmap);

ruft auf eine wie auch immer geartete Weise
die UnsafeBitmap Funktion wie benötigt auf.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Hi dr4g0n76,

mir wird leider nicht ganz klar, worauf du hinauswillst 🤔?

Geht es dir darum, überhaupt unsafe Pointer Arithmetik zu nutzen? Oder darum, dass das IL-Call-Replacement nicht nötig ist? Oder darum, dass intern die Aufrufe an eine bestehende, von dir angedeutete Implementierung weitergeleitet wird ?
?(

Was mich bei deinem Code insgesamt etwas wundert: Dieser Mix !
Zum einen verwendest du eh unsafe-Code, aber auf der anderen Seite liest du extra mit Marshal.ReadByte die einzelnen Pixel.
(Wobei du den byte*-Pointer p doch gar nicht nutzt?!?!)

Also das musst du mir nochmal genauer erklären, sorry =)

beste Grüße
zommi

2.921 Beiträge seit 2005
vor 14 Jahren

Hi dr4g0n76,

Hi Zommi. 😉

mir wird leider nicht ganz klar, worauf du hinauswillst Baby ?

Geht es dir darum, überhaupt unsafe Pointer Arithmetik zu nutzen? Oder darum, dass das IL-Call-Replacement nicht nötig ist? Oder darum, dass intern die Aufrufe an eine bestehende, von dir angedeutete Implementierung weitergeleitet wird ?
verwirrt

Nein, es geht mir nicht um die unsafe Pointer Arithmetik. Lass es mich noch mal so umschreiben: Es gibt ja auch Möglichkeiten eine schnelle Implementierung zu machen, bei der nichts rekompiliert wird und IL-Injection oder Enhancer benötigt werden, bitte nicht falsch auffassen, ich bin nicht dagegen.

Ich habs einfach mal so versucht bisher:

UnsafeBitmap.SetPixel / UnsafeBitmap.GetPixel, intern werden quasi nur die Byte-Offsets anhand x,y errechnet und SO das Pixel gelesen bzw. gesetzt.
Und ich hatte einfach beide Varianten ausprobiert und den Code momentan noch so gelassen. Dieser Teil klar?

Was mich bei deinem Code insgesamt etwas wundert: Dieser Mix !
Zum einen verwendest du eh unsafe-Code, aber auf der anderen Seite liest du extra mit Marshal.ReadByte die einzelnen Pixel.
(Wobei du den byte*-Pointer p doch gar nicht nutzt?!?!)

Eine Anmerkung von mir dazu, das ist noch(!) experimenteller Code, wahrscheinlich hat das posten aber in diesem Fall mehr verwirrt als geholfen. Rein theoretisch könnte ja man den Code nehmen (wenn er nicht mehr experimentell ist), Lambda Aufruf dazu, so dass man wie bei Deinem Konzept die einzelnen Kanäle bearbeitet und fertig. Dann muss nichts per IL-Code gemacht werden.

Also das musst du mir nochmal genauer erklären, sorry

Also (sehr) langer Rede (ganz) kurzer Sinn:

Gibt es dann trotzdem noch eine Motivation deinen Code zu benutzen, wenn man sich einen Überbau wie UnsafeBitmap.GetPixel/UnsafeBitmap.SetPixel?

Das sollen keine Argumente GEGEN Dein Konzept sein, sondern ich möchte nur, noch eine klarere Herausstellung.

Hoffentlich wirds jetzt klarer und ich hoffe ich habe mich deutlich genug ausgedrückt.

Ist alles nicht böse sondern nur sachlich gemeint.

beste Grüße
zommi

sehr freundliche Grüße zurück. aus dem noch(!) warmen Südwesten. g

Hoffentlich siehst Du jetzt etwas klarer. g

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo dr4g0n76,

Rein theoretisch könnte ja man den Code nehmen (wenn er nicht mehr experimentell ist), Lambda Aufruf dazu, so dass man wie bei Deinem Konzept die einzelnen Kanäle bearbeitet und fertig. Dann muss nichts per IL-Code gemacht werden.

Und genau das ist der Knackpunkt - einserseits muss durch Übergeben des Lambda-Ausdrucks ein extra Call des Delegats durchgeführt werden, andererseits taucht auch der Methodenrumpf des Delegats nicht im statischen Calltree auf. Daher kann der JIT-Compiler nicht optimieren (z.B. durch Inlining) und der Code ist langsam.
Aus diesem Grund hat zommi das Konzept entwickelt, dass der Code des Delegaten direkt als IL injiziert wird und so der Code optimiert werden kann.

Wenn du dir mal die Benchmarks anguckst, wurde dort ja auch nochmal explizit die Deleaten-Variante mit dem IL-Injizieren verglichen.

Gruß,
dN!3L

2.921 Beiträge seit 2005
vor 14 Jahren

Hab mir jetzt noch mal den kompletten Thread durchgelesen, ist ja ganz klar, sollte einfach nach 13 Stunden Vollgas das hier nicht mehr überfliegen sondern erst am nächsten Tag.

@dN!3L / Zommi

Verstehe was Du meinst. Und jetzt auch was Du meinst Zommi.

Sorry.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 13 Jahren

Hallo,

an dieser Stelle verweise ich mal auf meinen neuen Blog: http://zommi.bplaced.net

Dort bin ich gerade dabei die Ideen dieses Posts von vor einem Jahr aufzugreifen, nochmal darzulegen und vor allem zu verbessern! Durch einen neuen Ansatz, der nicht IL-Code, sondern Expression Trees verwendet.

Ein paar Posts hab ich schon, weitere werden noch folgen.

beste Grüße
zommi