Tanpohp

Snippets

PLinq – und wann man es nicht nutzen sollte

by on Nov.03, 2011, under Snippets

Zur Zeit beschäftige ich mich mit Bildverarbeitung auf der GPU. Dabei muss ich auf eine Reihe von Bildern Faltungen und dergleichen anwenden. Viele Bilder – das schreit nach PLinq, so dachte ich. Aus organisatorischen Gründen habe ich 3 Bildpackte welche jeweils eine List sind. Diese enthalten dann wiederum das Graustufenbild als byte[].

List<List<byte[]>> allImagePackages;

PLinq bietet nun eine ausgesprochen einfache Möglichkeit die Bilder parallel zu bearbeiten. Der Code sieht dann etwa wie folgt aus:

allImagePackages.AsParallel().ForAll(
	imagePackage => imagePackage.AsParallel().ForAll(
		singleImage =>DoSomethingComplex(singleImage)));

Da es sich um verschachtelte Listen handelt kann, kann man auf jeder Ebene AsParallel nutzen um diese parallel zu bearbeiten. Nach einigem experimentiern mit meinen Bildern kam ich dabei auf ein interessantes Phänomen. Mein Bilder sind zu 3 Pakete gebündelt welche jeweils 50 oder 255 Bilder enthalten. Dabei ergaben sich folgende Bearbeitungszeiten:

Modus 50 Bilder 255 Bilder
Ohne AsParallel 30,4sec 140,8sec
AsParallel auf beiden Ebenen 7,1sec 25,4sec
AsParallel auf der untersten Ebene 5,7sec 22,8sec

Es scheint, als bringe das parallele abarbeiten von parallel abzuarbeiten Aufgaben keinen Geschwindigkeitsvorteil, im Gegenzug sogar ein Verwaltungsoverhead. Ich stecke zu wenig in der Materie drin um ein fundiert Erkärung für diese Phänomen zu liefern, aber ich habe eine Theorie: Das äußere AsParallel (im Folgenden AP1) hat lediglich die Aufgabe die Verarbeitung der einzelnen Pakete zu starten.  Das innere AsParallel (im Folgenden AP”) hingegen hat schwer zu tun. Ich meine mal gelesen zu haben, dass PLinq einzelne Threads gleichermaßen zum Zuge kommen lässt.  Das heißt sowohl AP1 als auch AP2 werden vielleicht 100 mal pro Sekunden an die CPU gelassen. Währen AP2 diese Zeit nutzt um die Bildverarbeitung voran zu treiben, stellt AP1 lediglich fest, das AP2 noch nicht fertig ist und gibt die CPU wieder frei. Dieser Overhead bremst dann das ganze Programm, wodurch dann die oben genannten Zahlen zustanden kommen.

Comments Off on PLinq – und wann man es nicht nutzen sollte :, , , more...

A* Algorithmus

by on May.12, 2011, under Snippets

Zur Zeit belege ich ein Fach names “AI for Games” in welchem es darum geht möglichst intelligente Programm zu schreiben. Eine der Aufgaben war einen Agent über ein Feld zu seinem Ziel zu schicken. Als Hilfestellung gab es einen Graphen der für die Navigation genutzt werden sollte, indem für diesen Graphen der A* Algorithmus implementiert werden sollte. Diese Implementation ist weiter unten zu sehen, jedoch verwendet die Wegfindung nicht zwangsweise den Algorithmus. Falls der Weg auch ohne den Graph gefunden werden kann, wird auf dieen verzichtet. Dabei durchläuft der Code folgende Schritte:

  1. Suche im Graph einen Knoten, welchem dem Startpunkt am nächsten ist und direkt einsehbar ist (nicht hinter einer Mauer).
  2. Suche im Graph einen Knoten, welchem dem Zielpunkt am nächsten ist und direkt einsehbar ist (nicht hinter einer Mauer).
  3. Wenn Start- und Zielknoten die selben sind, prüfe ob Ziel direkt einsehbar.
  4. Wenn Ja, laufe zum Zielpunkt.
  5. Wenn Nein
    1. Benutze A* um Weg zu generieren
    2. Laufe zum Startknoten
    3. Laufe Entlang des Graphen zum Zielknoten
    4. Laufen zum Zielpunkt.

Der Algorithmus hat in der Implementation eine kleine Abweichung. Der Agent läuft nicht bis zum jeweils nächsten Knoten, sondern orientiert sich um sobald dieser in der Nähe des Knotens ist. In dem folgenden Video kann man dies daran erkennen, dass der Agent vor dem Knoten abbiegt:

Die Implementation des A* in Java:

public class AStarAlgorithm {

	Graph graph;
	PriorityQueue notYetVisited;

	public AStarAlgorithm (Graph graph){
		this.graph = graph;
	}

	public Queue SearchPath(Node start, Node aim){
		notYetVisited = new PriorityQueue(64, new NodeCostComperator(SortMode.ASCENDING));
		notYetVisited.addAll(graph.GetNodes());

		//set cost to maximum and predecessor to null
		PrepareGraph(notYetVisited);
		//System.out.println();
		//System.out.println(graph.toString());
		Node currentNode = start;
		currentNode.SummedCosts = CalculateDistance(currentNode, aim);
		currentNode.SummedRealCosts = 0;
		//walk through all nodes until aim is reached
		while(currentNode != aim){
			notYetVisited.remove(currentNode);
			ExpandGraph(currentNode, aim);
			currentNode = notYetVisited.peek();
			System.out.println();
			//System.out.println(graph.toString());
		}
		//reconstruct path from aim
		return ReconstructPath(aim);
	}

	/**
	 * The resulted list of nodes is inverted.
	 * @param aim
	 * @return
	 */
	private PriorityQueue ReconstructPath(Node aim) {
		PriorityQueue result = new PriorityQueue(16,new NodeRealCostComperator(SortMode.ASCENDING));
		Node currentNode = aim;
		while(currentNode.Predecessor != null){
			//System.out.println(currentNode.Index);
			result.add(currentNode);
			currentNode = currentNode.Predecessor;
		}
		//finally add start point
		result.add(currentNode);
		return result;
	}

	private void PrepareGraph (Collection nodes){
		for(Node node : nodes){
			node.SummedCosts = Double.MAX_VALUE;
			node.SummedRealCosts = 0;
			node.Predecessor = null;
			node.PresentationColor = Color.GRAY;
		}
	}
	private void ExpandGraph (Node currentNode, Node aim){
		//System.out.println("Node: "+currentNode.Index+" =>");
		Iterator
 outLinks = currentNode.GetOutboundLinks();
		while(outLinks.hasNext()){

			Link link = outLinks.next();
			Node destination = link.GetDestination();
			if(currentNode.Predecessor == destination) continue;

			double cost = currentNode.SummedRealCosts + link.Cost + CalculateDistance(destination, aim);
			//System.out.println("          "+destination.Index+": "+currentNode.SummedRealCosts + " + " +link.Cost+" + "+CalculateDistance(destination, aim)+" = "+cost);
			if(cost < destination.SummedCosts) {
				destination.SummedRealCosts = currentNode.SummedRealCosts + link.Cost;
				destination.SummedCosts = destination.SummedRealCosts + CalculateDistance(destination, aim);
				destination.Predecessor = currentNode;
				//this ensures that queue is sorted correctly
				notYetVisited.remove(destination);
				notYetVisited.add(destination);
			}
		}
	}
	private double CalculateDistance(Node currentNode, Node aim){
		return currentNode.Coordinate.distance(aim.Coordinate);
	}
}
Comments Off on A* Algorithmus :, , , more...

Optimierung in C# mittels Pointer

by on Oct.23, 2010, under Snippets

Ich habe mich in den letzten Tagen viel mit Farbraumkonvertierung, sowie Pixelextrahierung und dessen Beschleunigungsmöglichkeiten und C# beschäftigt. Mich hat besonders interessiert, ob das Pointerkonzept in C# das Potenzial hat, Anwendungen derart zu beschleunigen, dass es sich lohnt sich damit zu beschäftigen. Dabei habe ich einige sehr interessante Entdeckungen gemacht.

Der folgende Code wandelt ein byte[] im RGB Format in YCbCr um.

public static void Rgb2YCbCr24Bit(ref byte[] rgb)
{
    int y = 0, cr = 0, cb = 0, cg = 0;
    for (int pos = 0; pos < rgb.Length-2; pos += 3)
    {
        r = rgb[pos + 1];
        g = rgb[pos + 2];
        b = rgb[pos + 3];
        lum = ((r + g + b) / 3);
        rgb[pos + 1] = (byte)lum;
        rgb[pos + 2] = (byte)(lum - b);
        rgb[pos + 3] = (byte)(lum - r);
    }
}

Ich habe diesen Code mehrfach mit einem 36MPixel Bild getestet damit eventuelle Störungen durch andere Programme nicht so stark ins Gewicht fallen. Ergebnis: 2023ms.
Darauf hin habe ich das gleich mit Pointern umsetzt:

public static void Rgb2YCbCr24Bit(ref byte[] rgb)
{
    int r = 0, g = 0, b = 0, lum = 0;
    unsafe
    {
        fixed (byte* p1 = rgb)
        {
            byte* p = p1;
            for (int pos = 0; pos < rgb.Length - 2; pos += 3)
            {
                r = *(p);
                g = *(p + 1);
                b = *(p + 2);
                lum = ((r + g + b) / 3);
                *(p) = (byte)lum;
                *(++p) = (byte)(lum - b);
                *(++p) = (byte)(lum - r);
                ++p;
            }
        }
    }
}

Mit den selben Bild: 1572ms. Das heißt eine Beschleunigung um 23%. An dem Code ist zu sehen, das der Grünkanal nur einmal benötigt wird und die Zwischenspeicherung damit redundant ist. Darauf hin änderte ich den Code wie folgt ab.

public static void Rgb2YCbCr24Bit(ref byte[] rgb)
{
    int r = 0, b = 0, lum = 0;
    unsafe
    {
        fixed (byte* p1 = rgb)
        {
            byte* p = p1;
            for (int pos = 0; pos < rgb.Length - 2; pos += 3)
            {
                r = *(p);
                b = *(p + 2);
                lum = ((r + *(p + 1) + b) / 3);
                *(p) = (byte)lum;
                *(++p) = (byte)(lum - b);
                *(++p) = (byte)(lum - r);
                ++p;
            }
        }
    }
}

Interessanter Weise wurde der Code damit nicht schneller, sondern langsamer. Gegenüber der Implementierung mit Arrays betrug die Beschleunigung nur noch 12%. Würde mich sehr stark interessieren, warum das so ist.

An einer anderen Stelle extrahierte ich RGB-Werte aus einer Bitmap. Als erstes ist zu sagen, dass obgleich eines der Formate PixelFormat.Format32bppArgb heißt, entspricht dies nicht der Ordnung der Pixel um Speicher. Diese liegen genau anderes herum im Speicher des Bitmap: Gbra.
Mit folgende Code laß ich die Rgb-Werte aus einer Bitmap aus.

public static byte[] GetPixelsRgb(Bitmap source)
{
    int width = source.Width, height = source.Height;
    byte[] result = new byte[width * height * 3];
    BitmapData bd = source.LockBits(
                            new Rectangle(0, 0, width, height),
                            System.Drawing.Imaging.ImageLockMode.ReadOnly,
                            source.PixelFormat);
    unsafe
    {
        byte* bp = (byte*)bd.Scan0;
        fixed (byte* rPtr = result)
        {
            byte* rp = rPtr;
            int count = result.Length;
            for (int i = 0; i < count; i += 3)
            {
                *rp = *(bp + 2);
                *(rp + 1) = *(bp + 1);
                *(rp + 2) = *(bp);
                bp += 3;
                rp += 3;
            }
        }
    }
    source.UnlockBits(bd);
    return result;
}

Zu beachten ist, das der Code nur wie zu erwarten funktioniert, wenn (source.width*3)%4==0, da ein Stride (siehe MSDN) mit 0 aufgefüllt wird. Mit dem 36MPixel Bild bedarf es 799ms zum Auslesen des Bildes.

Beim betrachten dieses Codes viel mit folgendes auf: für jeden Pixel wird in der for-Schleife eine Addition +=3 ausgeführt und ein Vergleich ausgeführt, ob der Code am Ende des Bitmap angekommen ist. Die meisten Bilder haben eine Breiten die zumindest durch 4 teilbar ist, viele haben Breiten die durch 8 oder 16 teilbar sind. Damit könnten unnötige Überprüfungen unterbunden werden. Daraus resultiert folgender Code:

public static byte[] GetPixelsRgbFast(Bitmap source)
{
    int width = source.Width, height = source.Height;
    byte[] result = new byte[width * height * 3];

    BitmapData bd = source.LockBits(
                            new Rectangle(0, 0, width, height),
                            System.Drawing.Imaging.ImageLockMode.ReadOnly,
                            source.PixelFormat);
    unsafe
    {
        byte* bp = (byte*)bd.Scan0;
        fixed (byte* rPtr = result)
        {
            byte* rp = rPtr;

            for (int i = 0; i < result.Length; i += 24)
            {
                //pixel 0
                *rp = *(bp + 2);
                *(rp + 1) = *(bp + 1);
                *(rp + 2) = *(bp);
                //pixel 1
                *(rp + 3) = *(bp + 5);
                *(rp + 4) = *(bp + 4);
                *(rp + 5) = *(bp + 3);
                //pixel 2
                *(rp + 6) = *(bp + 8);
                *(rp + 7) = *(bp + 7);
                *(rp + 8) = *(bp + 6);
                //pixel 3
                *(rp + 9) = *(bp + 11);
                *(rp + 10) = *(bp + 10);
                *(rp + 11) = *(bp + 9);
                //pixel 4
                *(rp + 12) = *(bp + 14);
                *(rp + 13) = *(bp + 13);
                *(rp + 14) = *(bp + 12);
                //pixel 5
                *(rp + 15) = *(bp + 17);
                *(rp + 16) = *(bp + 16);
                *(rp + 17) = *(bp + 15);
                //pixel 6
                *(rp + 18) = *(bp + 20);
                *(rp + 19) = *(bp + 19);
                *(rp + 20) = *(bp + 18);
                //pixel 7
                *(rp + 21) = *(bp + 23);
                *(rp + 22) = *(bp + 22);
                *(rp + 23) = *(bp + 21);
            }
        }
    }
    source.UnlockBits(bd);
    return result;
}

Der Code behandelt 8 Pixel auf einmal und erspart sich damit 7 Additionen und 7 unnötige Vergleiche. Zeit zum auslesen des 36MPixel Bildes: 410ms. Das ist eine satte Beschleunigung um 49%.

Es zeigte sich, dass das Pointer-Konzept in C# einige Leistungsreserven anzapfen kann und es sich in zeitkritischen Anwendungen lohnt diese Umzusetzten. Viel überraschender fand ich die Ergebnisse des zweiten Experimentes, die relativ unanhängig von Pointern oder C# sind. Hier zeigt sich was mit ein wenig Mehraufwand in der Implementierung geschafft werden kann.

Comments Off on Optimierung in C# mittels Pointer :, more...

Ordner nach bestimmten Dateien durchsuchen

by on Apr.23, 2010, under Snippets

Hier ein kleines Skript welches einen Ordnername übergeben bekommt und diesen rekursiv nach Dateien mit einer gegebenen Endung durchsucht und diese Pfade zurück liefert:

function getFiles ($path, $extension){
   $result = array();
   if(is_dir($path) && $path!="." && $path!=".."){
      $dh = opendir($path);
      if($dh != false){
         while (false !== ($subpath = readdir($dh))) {
            if($subpath== "." || $subpath=="..") continue;

            $files = HTMLInputReader::getFiles($path."/".$subpath, $extension);
            if(is_array($files)){
               $result = array_merge($result, $files);
            }else if($files!= ""){
               array_push($result, $files);
            }
         }
      }
   }else{
      //it's not a directory
      if(ends($path, $extension)){
         return $path;
      }else{
         return "";
      }
   }
   return $result;
}
function ends($file, $extension){
   $parts = explode(".", $file);
   if($parts == false || count($parts)==0) return false;

   return $parts[1] == $extension;
}
Comments Off on Ordner nach bestimmten Dateien durchsuchen :, , , , more...

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Visit our friends!

A few highly recommended friends...