MergeSort - Threads in Anwendung bremsen alles!

[Mujahiddin]

Einen guten Tag...
Ich habe heute den Sortieralgorithmus MergeSort auf Zahlen geschrieben.
Dieser arbeitet mit Vectoren, die zuerst in der Rekursion aufgeteilt werden, sortiert zusammengefasst werden, bis schließlich das angeforderte sortiert ist...
Alles klappt wunderbar... Ich dachte mir aber, wenn ich Threads laufen lasse, womit ich diese 'Unteraufteilung / Sortierung', die nicht voneinander abhängen, gleichzeitig von statten bringe, wäre die Aktion viel schneller fertig, und man müsste nicht immer alles Schritt für Schritt machen...
Zu meiner Überraschung stellte sich genau das Gegenteil heraus: Mit Threads dauert alles 15 mal so lange... (Bei ca. 4050 Einträgen: ~680-800 Millisekunden, Threadlos: ~30 Millisekunden)
Den Sortiervorgang selber, also zwei sortierte Listen in eine sortierte Liste einzufügen, ist bei beiden Vorgängen / Klassen gleich.
Der Unterschied liegt nur darin, dass beim einen die Unterteilung und der Splittvorgang im Thread ausgeführt wird, der, wenn nötig, auf einen anderen Thread wartet, bis dieser fertig ist, auch wenn nötig.

Hier mal ein Quellcode:

public class Algorithm 
{
	Vector<Integer> toMerge = new Vector<Integer>();
	public Algorithm()
	{
		toMerge.addElement(new Integer(3));
		toMerge.addElement(new Integer(2));
		toMerge.addElement(new Integer(44));
		toMerge.addElement(new Integer(5));
		toMerge.addElement(new Integer(4));
		[...]
	}
	public Vector<Integer> sort(Vector<Integer> firstSorted, Vector<Integer> secondSorted)
	{
		int fusionedLength = firstSorted.size() + secondSorted.size();
		Vector<Integer> fusioned = new Vector<Integer>();
		for(int i=0; i<fusionedLength; i++)
			if(secondSorted.size() == 0 && firstSorted.size() > 0 || firstSorted.size() > 0 && firstSorted.get(0) <= secondSorted.get(0))
				fusioned.addElement(firstSorted.remove(0));
			else
				fusioned.addElement(secondSorted.remove(0));
		return fusioned;
	}

<< Dieser Auszug is bei beiden Klassen gleich...

Klasse mit Threads:

	public Algorithm()
	{
		[...]
		toMerge.addElement(new Integer(10));
		System.out.println(toMerge.size());
		long start = new Date().getTime();
		System.out.println(start);
		Thread sortThread = new Thread(new SortThread(toMerge, this));
		sortThread.start();
		try 
		{
			sortThread.join();
		} catch (InterruptedException e) 
		{
			e.printStackTrace();
		}
		System.out.println(toMerge);
		long end = new Date().getTime();
		System.out.println(end);
		long duration = end-start;
		System.out.println("Dauer: " + duration);
	}
	
	
	
	class SortThread implements Runnable
	{
		Vector<Integer> toSort = null;
		Vector<Integer> firstPart = null;
		Vector<Integer> secondPart = null;
		SortThread starterThread = null;
		Algorithm starter = null;
		boolean first = false;
		SortThread(Vector<Integer> toSort, SortThread starterThread, boolean first)
		{
			this.first = first;
			this.toSort = toSort;
			this.starterThread = starterThread;
		}
		SortThread(Vector<Integer> toSort, Algorithm starterThread)
		{
			this.toSort = toSort;
			this.starter = starterThread;
		}
		public void run()
		{
			int toSortLength = toSort.size();
			firstPart = new Vector<Integer>();
			secondPart = new Vector<Integer>();
			for(int i=0; i<toSortLength; i++)
				if(i%2 == 0)
					firstPart.addElement(toSort.get(i));
				else
					secondPart.addElement(toSort.get(i));
			Thread firstPartThread = null;
			int firstPartLength = firstPart.size();
			if(firstPartLength > 1)
			{
				firstPartThread = new Thread(new SortThread(firstPart, this, true));
				firstPartThread.start();
			}
			Thread secondPartThread = null;
			int secondPartLength = secondPart.size();
			if(secondPartLength > 1)
			{
				secondPartThread = new Thread(new SortThread(secondPart, this, false));
				secondPartThread.start();
			}
			try
			{
				if(firstPartThread != null)
					firstPartThread.join();
				if(secondPartThread != null)
					secondPartThread.join();
			} catch(InterruptedException e)
			{
				e.printStackTrace();
			}
			toSort = sort(firstPart, secondPart);
			if(starterThread != null)
				if(first)
					starterThread.firstPart = toSort;
				else
					starterThread.secondPart = toSort;
			else
				starter.toMerge = toSort;
		}
	}

Klasse ohne Threads (wesentlich kürzer):

	public Algorithm()
	{
		[...]
		toMerge.addElement(new Integer(10));
		long start = new Date().getTime();
		System.out.println(start);
		toMerge = merge(toMerge);
		System.out.println(toMerge);
		long end = new Date().getTime();
		System.out.println(end);
		long duration = end-start;
		System.out.println("Dauer: " + duration);
	}


	public Vector<Integer> merge(Vector<Integer> toSort)
	{
		int toSortLength = toSort.size();
		Vector<Integer> firstPart = new Vector<Integer>();
		Vector<Integer> secondPart = new Vector<Integer>();
		for(int i=0; i<toSortLength; i++)
			if(i%2 == 0)
				firstPart.addElement(toSort.get(i));
			else
				secondPart.addElement(toSort.get(i));
		int firstPartLength = firstPart.size();
		if(firstPartLength > 1)
			firstPart = merge(firstPart);
		int secondPartLength = secondPart.size();
		if(secondPartLength > 1)
			secondPart = merge(secondPart);
		Vector<Integer> sorted = new Vector<Integer>();
		sorted = sort(firstPart, secondPart);
		return sorted;
	}

Habe ich vielleicht einen Fehler im Quellcode, der alles umsonst bremst? Oder liegt das daran, dass einen Thread zu starten enorm viel mehr Zeit kostet, als einfach alles nacheinander zu machen?

Danke für euren Tipp!

Muja

 

[andiv]

MergeSort ist ein Easy-Split/Hard-Join-Algorithmus, d.h. das Aufteilen der Ausgangsliste auf zwei Teillisten geht schnell während das Zusammenfügen zur sortierten Liste eher aufwändig ist.

Wenn du hier optimieren wilst, dann musst du eher beim zweiten Teil ansetzen.

Dementsprechend sollte auch klar sein, das der Einsatz mehrerer Threads zum Aufteilen kaum Nutzen bringt.

Dass Threads das ganze sogar langsamer machen lässt sich damit erklären, dass das Erstellen eines Threads und insbesondere die Synchronisierung relativ teuer sind.

 

[Mujahiddin]

Okay, das verstehe ich ja, aber wie sollte ich, deiner Meinung nach, den Algorithmus (den Join Algorithmus) optimieren? Wenn ich mir meinen Code anschaue, dann kann ich mir gar nichts Kürzeres vorstellen.. Und wie sollte ich da Threads anwenden? Synchronität wäre hier doch schwachsinnig, da man sowieso immer auf das nächste Objekt warten muss... Findest du nicht auch?

 

[Schandro]

vllt. wäre es schneller, intern mit Arrays statt Vectoren-Objekten zu arbeiten!? Instanzen kosten schließlich einiges.

 

[SlaterB]

ich schau mir nachher noch den Code an, falls da was zu tun ist,
vorher bisschen blahblah

Ich dachte mir aber, wenn ich Threads laufen lasse, womit ich diese 'Unteraufteilung / Sortierung', die nicht voneinander abhängen, gleichzeitig von statten bringe, wäre die Aktion viel schneller fertig, und man müsste nicht immer alles Schritt für Schritt machen...
Zu meiner Überraschung stellte sich genau das Gegenteil heraus: Mit Threads dauert alles 15 mal so lange...

Threads sind unendlich langsam und können von sich aus nichts besser, jedenfalls nicht Richtung Geschwindigkeit wenn nicht gerade wirklich mehrere CPUs gleichzeitig genutzt werden können,
klassischerweise hat man ja eher eine CPU und die Threads müssen sich abwechseln,
die Erstellung und das Hin- und Herschalten kann Ewigkeiten dauern,
der Vorteil der Threads liegt in ersten Linie in der Möglichkeit zur natürlichen Organisation mehrere Vorgänge

zwei entfernte Analogien:
1.
System.out.println("Test") vs eine GUI mit Textfeld und darin "Test", letzteres bringt den User auch nicht viel mehr Infos, dauert 1000fach länger, verbraucht MB an zusätzlichen Speicher,
dafür hat man Eventhandling und andere komfortable Möglichkeiten

2.
fünf Assembler/ Maschensprachen-Befehle vs. ein einfaches Java-Programm mit System.out.println("Test"),
letztes ist zwar viel schneller als ne GUI, für sich aber auch 1000fach langsamer als was ein PC wirklich könnte mit seinen GHz an Arbeitsgeschwindigkeit,
die Hochsprache mit ihren aufwendigen Interpretationssystem, Hintergrundthreads, 1 sec + 10 MB allein zum Starten nimmt man in Kauf,
weil man dabei auch wieder jede Menge Komfort erhält, einfache Programmierbefehle, Speichermanagement, direkt verfügbare Input + Output usw.



edit:
zum Code: mehr als Entfernen der Threads ist dabei wohl als wichtigster Schritt nicht zu tun,
wenn überhaupt, dann kannst du überlegen, bei sehr vielen Elementen in den obersten Schichten zu trennen, so dass vielleicht 2, 4 oder 8 laufen, die jeweils paar tausend bis Millionen sortieren,
aber auf den unteren Ebenen neue Threads, das macht im besonderen Maße keinen Sinn