Multithreaded Linear Search

[momesana]

Hi,
Ich hatte kürzlich die Aufgabe als Übung drei Suchalgorithmen zu schreiben. LinearSearch, BinarySearch und MultiCoreLinearSearch und die Performance derselben zu vergleichen. Leider ist die MultiCoreLinearSearch (die mehrere Threads verwendet) 3-5 mal langsamer als die MultiCoreLinearSearch, obgleich meine CPU 4 Kerne hat. 4 Leute haben sich bisher die Zähne daran ausgebissen den Grund für die schlechte Performance zu finden. ich wäre sehr sehr dankbar wenn mir jemand sagen könnte woran es bei meinem Code hapert.

Ich habe 3 Stunden gebraucht um das ganze zu programmieren und suche seit drei Tagen nach dem Performance-Flaschenhals ... Ich habe im Zuge dessen den Code in großen Teilen fünf mal neugeschrieben aber die Performance hat sich weder verschlechtert noch verbessert. Egal was ich unternehme es bleibt gleich schlecht. Ich bin den Code mit diversen Testcases im Debugger durchgegangen. Er verhält sich eigentlich genau wie er soll. Der Profiler (jvisualvm ... ich bin aber ein Noob wenn es um Profiling geht) hat mir bisher auch nicht mehr Einblicke verschaffen können .

Der Code ist gut dokumentiert (fast schon überkommentiert), relativ kurz (Ohne Kommentare ca. 90 Zeilen Code) und eigentlich auch recht simple gestrickt.
Ich habe es unten reingepastet. Das gesamte (Eclipse) Projekt samt (Junit) Testcases und einer Main Klasse welche den Performance Vergleich durchführt könnt Ihr hier Anhang anzeigen pi2-uebung01.zip beziehen.

Aufgabe 4 - Multithreading

... Erzeugt eine neue Klasse MultiCoreLinearSearchUtils, die iSearchUtils implementiert. Definiert die Methode search so, dass die lineare Suche nun auf mehreren Prozessorkernen laufen kann. Zu diesem Zweck werden 2 Threads erzeugt, die sich die Sucharbeit aufteilen. Der erste Thread untersucht alle geraden Indices der ArrayList, der zweite alle ungeraden. Denkt daran, dass sich beide Threads gegenseitig über das Antreffen des gesuchten Elements benachrichtigen sollen.

Das Projekt einfach importieren, ausführen und sich die MultiCoreLinearSeachUtils anschauen. Die Anzahl der Threads lässt sich einstellen (Zeile 15 in MultiCoreLinearSearchUtils). Tendenziel wird der Code langsamer je mehr Threads ich verwende. Interessanterweise ist es auch sehr langsam wenn ich nur ein Thread verwende. Die Aufgabe ist schon abgegeben und so eilt es nicht wirklich, aber ich würde mich sehr freuen wenn sich jemand das ganze mal anschaut und mir eventuell einen Hinweis gibst, was ich falsch mache. Das Problem lässt mir einfach keine Ruhe . Man hört schon ... ich bin mit meinem Latein am Ende.

Paar Sachen noch:
* Ich habe das ganze auch mit - durch Executors erzeugte - Threadpools probiert aber auch da war die Suche langsamer als die lineare Suche, wenngleich sie fast gleichauf waren ...!
* Ich habe auch Code verwendet, wo ich gänzlich auf AtomicInteger und die Synchronized Sektion verzichtet habe ... Die Performance wurde nicht besser!
* Ich habe statt CountDownLatch auch Thread.join() verwendet ... gleiche Performance!
* Ich habe statt LinearFinder als Thread Subclass auch LinearFinder ohne Vererbung implementiert (sondern als Implementierung von Runnable), mir ganz zu Anfang die benötigte Anzahl der Obejkte davon erstellt und diese dann über Thread instanzen (new Thread(runnable)) ausgeführt: gleiche bzw. schlechtere Performance!

Als Ausgangspunkt für die Implementierung der MultiCoreLinearSearch Klasse diente mir meine LinearSearchUtils Klasse, die ebenfalls dem Projekt beiliegt:

package org.pi2.uebung01;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * An implementation of the iSearchUtils interface.
 * @author Mehdi Salem Naraghi
 *
 */
public class LinearSearchUtils implements iSearchUtils {

	/**
	 * Searches the given key in the provided sorted ArrayList
	 * using the given comparator. If the element is found the
	 * index where the element was located is returned. Otherwise
	 * the incremented insertion point (where the element would've been found
	 * will be returned as a negative number.
	 * This function utilizes a linear search
	 * algorithm.
	 * @param a The ArrayList to be searched in.
	 * @param key the Key to be searched for.
	 * @param Comparator The comparator used in the search
	 */
	@Override
	public <T> int search(ArrayList<T> arrayList, T key, Comparator<? super T> comparator) {
		
		int i = 0;
		// iterate through the elements of the list
		for (; i < arrayList.size(); ++i) {
			
			// compare  current element with key
			final int comparisonResult = comparator.compare(key, arrayList.get(i));

			// this option is most likely, so we evaluate it first 
			if (comparisonResult > 0) { continue; }
			
			// element cannot be found anymore
			else if (comparisonResult < 0) { break; }
			
			else { return i; }
		}

		// if the array is empty or we couldn't find the element
		return -(i + 1);
	}

}

Führt man die Main Klasse aus werden drei Dateien (allesamt Wikipedia Einträge) daraufhin getestet ob die darin enthaltenen Wörter in einem vorgegeben Dictionary vorhanden sind oder nicht (alle Dateien befinden sich in einem Unterverzeichnis misc).

Die Such algorithmen sollen entweder den Index zurückgeben wo ein Wort/Objekt in einer ArrayList gefunden wurde oder den insertion point + 1 als negative Zahl. Wenn ich also eine ListArray mit dem Inhalt [b, d, f] habe würden die folgende Schlüssel die angegeben Resultate liefern:

a --> -1
b --> 0
c --> -2
d --> 1
e --> -3
f --> 2
g --> -4

Liebe Grüße - Mehdi

Ergebnis des Performance-Vergleichs:

========================
1 Thread:
========================
Chess (15401 Wörter):
- LinearSearchUtils: 2259ms
- BinarySearchUtils: 30ms
- MultiCoreSearchUtils: 8970ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 2955ms
- BinarySearchUtils: 18ms
- MultiCoreSearchUtils: 14556ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2896ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 14187ms


========================
2Threads: (Schneller als mit nur einem Thread ... hebt wohl den Overhead der Threaderstellung auf)
========================
Chess (15401 Wörter):
- LinearSearchUtils: 2368ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 8248ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3062ms
- BinarySearchUtils: 25ms
- MultiCoreSearchUtils: 9261ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2991ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 7773ms



========================
4Threads:
========================
Chess (15401 Wörter):
- LinearSearchUtils: 2385ms
- BinarySearchUtils: 32ms
- MultiCoreSearchUtils: 9026ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 2965ms
- BinarySearchUtils: 22ms
- MultiCoreSearchUtils: 10704ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2940ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 10674ms


========================
8Threads:
========================
Chess (15401 Wörter):
- LinearSearchUtils: 2317ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 13758ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 2964ms
- BinarySearchUtils: 21ms
- MultiCoreSearchUtils: 16233ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2970ms
- BinarySearchUtils: 18ms
- MultiCoreSearchUtils: 15911ms

package org.pi2.uebung01;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * An implementation of the iSearchUtils interface.
 * @author Mehdi Salem Naraghi
 *
 */
public class MultiCoreLinearSearchUtils implements iSearchUtils {

    private final int NUM_OF_THREADS = 2; // The number of Threads to be used
    private AtomicInteger index = new AtomicInteger(); // stores the result
    private ThreadGroup threadGroup = new ThreadGroup("multicore"); // Thread group
    private CountDownLatch latch = null;
    /**
     * A Finderthread that searches a ListArray for a certain key.
     * @author Mehdi Salem Naraghi
     * @param <T>
     */
    class LinearFinder <T> extends Thread {

        private ArrayList<T> arrayList;
        private T key;
        private Comparator<? super T> comparator;
        private int startIndex;

        /**
         * Constructs a LinearFinder Thread
         * @param a The Array we search in
         * @param k The key to be searched for
         * @param c The Comparator used to compare the key with the elements of the array
         * @param i The startingIndex for this thread
         * @param g the Threadgroup to which this Thread belongs
         */
        public LinearFinder(ArrayList<T> a, T k, Comparator<? super T> c, int i, ThreadGroup g) {
            super(g, "thread" + i);
            arrayList = a;
            key = k;
            comparator = c;
            startIndex = i;
        }

        @Override
        public void run() {

            int i = startIndex;

            // iterate through the elements of the list, each time skipping NUM_OF_THREADS elements
            for (; i < arrayList.size(); i += NUM_OF_THREADS) {

                // if the current thread is interrupted we drop out of the loop
                if(Thread.currentThread().isInterrupted()) {
                    latch.countDown();
                    return;
                }

                // compare  current element with key
                final int comparisonResult = comparator.compare(key, arrayList.get(i));

                // this option is most likely, so we evaluate it first
                if (comparisonResult > 0) { continue; }

                // element cannot be found anymore
                else if (comparisonResult < 0) { break; }

                else { // Found the Key
                    // we store the index and notify the other threads before returning
                    index.set(i);
                    latch.countDown(); // we decrement the countdown latch
                    Thread.currentThread().getThreadGroup().interrupt();
                    return;
                }
            }

            // we save the idx only if the thread isn't interrupted
            if (!Thread.currentThread().isInterrupted()) {

                // calculate the insertion point
                final int idx = -(i + 1);

                // lock this critical area using a synchronized block
                synchronized(index) {
                    // if the new index is lower than the currently stored
                    // on we save the new one
                    if (idx > index.get()) { index.set(idx); }
                }
            }

            // in any case we decrement the countdown latch
            latch.countDown();
        }
    }

    /**
     * Searches for the given key in the provided sorted ArrayList
     * using the given comparator. If the element is found the
     * index where the element was located is returned. Otherwise
     * the incremented insertion point (where the element would've been found
     * will be returned as a negative number.
     * This function utilizes a linear search
     * algorithm using two threads.
     * @param a The ArrayList to be searched in.
     * @param key the Key to be searched for.
     * @param Comparator The comparator used in the search
     */
    @Override
    public <T> int search(ArrayList<T> a, T k, Comparator<? super T> c) {

        index.set(Integer.MIN_VALUE);

        // we use a latch to know where we can resume
        latch = new CountDownLatch(NUM_OF_THREADS);

        // we create the desired number of finder threads (no need to keep refs) and start them
        for (int i = 0; i < NUM_OF_THREADS; ++i) {
            new LinearFinder<T>(a, k, c, i, threadGroup).start();
        }

        try {
            latch.await();
        } catch (InterruptedException e) {
            /* ignore */
        }

        // return result
        return index.get();
    }
}

 

[Paddelpirat]

Also da können schon ein paar Dinge zusammen kommen, wieso das bei mehreren Threads langsamer läuft. Z.B. ein ganz einfacher, dass der gesuchte Key eigentlich relativ weit am Anfang steht und er einfach von den ersten Threads in der Liste übersprungen wird, weil sie nur jedes x-te Feld aus der ArrayList überprüfen. In deinem Fall könntest du z.B. einfach pech haben, dass erst der 8. Thread auf der richtigen Spur ist den gesuchten Key findet. Dann haben aber schon 7 Threads die ganze übrige ArrayList durchsucht...
Auf der anderen Seite gibt es noch von der CPU her Funktionen wie TurboBoost, s.d. ein einzelner Kern übertaktet wird und schneller arbeitet, als wenn alle 4 Kerne gleichzeitig arbeiten. In dem Fall könnte es noch einen größeren Zeitunterschied geben, wenn der gesuchte Wert in einem der ersten Felder liegt.

Es gäbe bei 8 Threads daher einen großen Laufzeitunterschied, wenn der Key dem 8. (je nachdem wie man zählt 7.) Feld in der ArrayList entspricht.


Was du machen könntest um das ganze zu verbessern, wäre die ArrayList anders auf die Threads zu verteilen. Sprich die ArrayList in k=Anzahl der Threads Teile zu zerlegen und jedem Thread einen dieser Teile abarbeiten lassen. Dann hättest du sicherlich eine bessere Laufzeit bei gesuchten Keys, die relativ weit vorne in der ArrayList liegen. Es sei denn TurboBoost kommt zum Einsatz ;-)

 

[momesana]

...
Auf der anderen Seite gibt es noch von der CPU her Funktionen wie TurboBoost, s.d. ein einzelner Kern übertaktet wird und schneller arbeitet, als wenn alle 4 Kerne gleichzeitig arbeiten. In dem Fall könnte es noch einen größeren Zeitunterschied geben, wenn der gesuchte Wert in einem der ersten Felder liegt.
...
Was du machen könntest um das ganze zu verbessern, wäre die ArrayList anders auf die Threads zu verteilen. Sprich die ArrayList in k=Anzahl der Threads Teile zu zerlegen und jedem Thread einen dieser Teile abarbeiten lassen. Dann hättest du sicherlich eine bessere Laufzeit bei gesuchten Keys, die relativ weit vorne in der ArrayList liegen. Es sei denn TurboBoost kommt zum Einsatz ;-)

Hi und danke für die Antwort. Leider gab die Aufgabe vor dass man die zwei Threads verwendet, von denen einer die geraden und der andere die ungeraden Indizes durchläuft. Die Test-Dateien waren wohl auch mit Bedacht (von den Tutoren) gewählt worden, so dass die Performance-Steigerungen bei richtiger Implementierung gleich ausfallen würden (Wir sollten diese sogar auch auf identischen Rechnern in der Uni testen).

Bei allen anderen Kommillitonen waren immer jeweils 30% Performance-Boost zu verbuchen. Bei meiner Implementierung leider nicht. Desweiteren habe ich das auf 4 verschiedenen Rechnern getestet. Sowohl desktops als auch Notebooks mit einem oder mehreren CPUs. Ich glaube dass die Performance-Probleme durch meinen Code verursacht sind. Übrigens steigt die Performance rasant an wenn ich ein ThreadPool verwende (siehe unten den neuen Code) weswegen ich einfach eine falsche Herangehensweise bei mir vermute.

=================
Vier Threads
=================
Chess (15401 Wörter):
- LinearSearchUtils: 2355ms
- BinarySearchUtils: 32ms
- MultiCoreSearchUtils: 1496ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3013ms
- BinarySearchUtils: 18ms
- MultiCoreSearchUtils: 1548ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 3021ms
- BinarySearchUtils: 19ms
- MultiCoreSearchUtils: 1516ms


==================
2 Threads
==================
Chess (15401 Wörter):
- LinearSearchUtils: 2392ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 1584ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3074ms
- BinarySearchUtils: 23ms
- MultiCoreSearchUtils: 2093ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2949ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 2184ms

Der neue Code:

package org.pi2.uebung01;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * An implementation of the iSearchUtils interface.
 * @author Mehdi Salem Naraghi
 *
 */
public class MultiCoreLinearSearchUtils implements iSearchUtils {

	private final int NUM_OF_THREADS = 4; // The number of Threads to be used
	private AtomicInteger index = new AtomicInteger(); // stores the result
	private ThreadGroup threadGroup = new ThreadGroup("multicore"); // Thread group
	private CountDownLatch latch = null;
	ExecutorService threadPool = Executors.newFixedThreadPool(NUM_OF_THREADS);
	/**
	 * A Finderthread that searches a ListArray for a certain key.
	 * @author Mehdi Salem Naraghi
	 * @param <T>
	 */
	class LinearFinder <T> implements Runnable {

		private ArrayList<T> arrayList;
		private T key;
		private Comparator<? super T> comparator;
		private int startIndex;

		/**
		 * Constructs a LinearFinder Thread
		 * @param a The Array we search in
		 * @param k The key to be searched for
		 * @param c The Comparator used to compare the key with the elements of the array
		 * @param i The startingIndex for this thread
		 * @param g the Threadgroup to which this Thread belongs
		 */
		public LinearFinder(ArrayList<T> a, T k, Comparator<? super T> c, int i, ThreadGroup g) {
			//super(g, "thread" + i);
			arrayList = a;
			key = k;
			comparator = c;
			startIndex = i;
		}

		@Override
		public void run() {

			int i = startIndex;

			// iterate through the elements of the list, each time skipping NUM_OF_THREADS elements
			for (; i < arrayList.size(); i += NUM_OF_THREADS) {

				// if the current thread is interrupted we drop out of the loop
				if(Thread.currentThread().isInterrupted()) {
					latch.countDown();
					return;
				}

				// compare  current element with key
				final int comparisonResult = comparator.compare(key, arrayList.get(i));

				// this option is most likely, so we evaluate it first 
				if (comparisonResult > 0) { continue; }

				// element cannot be found anymore
				else if (comparisonResult < 0) { break; }

				// found the Key!
				else {
					// we store the index and notify the other threads before returning
					index.set(i);
					latch.countDown(); // we decrement the countdown latch
					Thread.currentThread().getThreadGroup().interrupt();
					return;
				}
			}

			// we save the idx only if the thread isn't interrupted
			if (!Thread.currentThread().isInterrupted()) {

				// calculate the insertion point
				final int idx = -(i + 1);

				// lock this critical area using a synchronized block
				synchronized(index) {
					// if the new index is lower than the currently stored
					// on we save the new one
					if (idx > index.get()) { index.set(idx); }
				}
			}
			
			// in any case we decrement the countdown latch
			latch.countDown();
		}
	}
	
	/**
	 * Searches the given key in the provided sorted ArrayList
	 * using the given comparator. If the element is found the
	 * index where the element was located is returned. Otherwise
	 * the incremented insertion point (where the element would've been found
	 * will be returned as a negative number.
	 * This function utilizes a linear search
	 * algorithm using two threads.
	 * @param a The ArrayList to be searched in.
	 * @param key the Key to be searched for.
	 * @param Comparator The comparator used in the search
	 */
	@Override
	public <T> int search(ArrayList<T> a, T k, Comparator<? super T> c) {
		
		index.set(Integer.MIN_VALUE);

		// we use a latch to know where we can resume
		latch = new CountDownLatch(NUM_OF_THREADS);

		// we create the desired number of finder threads (no need to keep refs) and start them
		for (int i = 0; i < NUM_OF_THREADS; ++i) {
			threadPool.submit(new LinearFinder<T>(a, k, c, i, threadGroup));;
		}

		try {
			latch.await();
		} catch (InterruptedException e) {
			/* ignore */
		}

		// return result
		return index.get();
	}
}

 

[Paddelpirat]

Dann bin ich auch gerade zu blind dafür da einen Fehler zu sehen, habs mir aber zugegebenermaßen auch nicht so genau angesehen. Ich benutze sonst auch immer Threadpools dafür, schließlich gibt es sie dafür. Schätze mal, dass da die Verteilung der Ressourcen etwas geschickter vonstatten geht.


Edit: was du evtl bei der alten Version ausprobieren könntest, wäre zuerst die LinearFinder zu erzeugen und anschließend sie gesammelt zu starten:

Etwa so :

        List<LinearFinder> finders = new ArrayList<LinearFilter>();

        for (int i = 0; i < NUM_OF_THREADS; ++i) {
            finders.add(new LinearFinder<T>(a, k, c, i, threadGroup));
        }

        for (int i = 0; i < NUM_OF_THREADS; ++i) {
            ((LinearFinder)finders.get(i)).start();
        }

 

[momesana]

Dann bin ich auch gerade zu blind dafür da einen Fehler zu sehen, habs mir aber zugegebenermaßen auch nicht so genau angesehen. Ich benutze sonst auch immer Threadpools dafür, schließlich gibt es sie dafür. Schätze mal, dass da die Verteilung der Ressourcen etwas geschickter vonstatten geht.

Bei ThreadPools habe ich das Problem dass der Prozess am Leben bleibt. Da ich ein spezielles Interface implementiere kann ich dem Benutzer auch keine Funktionen anbieten der den ThreadPool über shutdown beendet. Das ist natürlich auch ärgerlich.

 

[Paddelpirat]

Siehe edit im letzten Post. Ist aber auch nur eine Idee...

 

[Marco13]

Du kannst einen newCachedThreadPool verwenden: Der erstellt die Threads so, wie sie benötigt werden, und killt sie nach einer Weile automatisch (Standard 60 Sekunden, kann man aber ändern).

Ansonsten ... für Spekulationen, warum der erste Ansatz langsamer ist, muss ich mir erst den Code genauer ansehen...

 

[momesana]

Du kannst einen newCachedThreadPool verwenden: Der erstellt die Threads so, wie sie benötigt werden, und killt sie nach einer Weile automatisch (Standard 60 Sekunden, kann man aber ändern).

Ansonsten ... für Spekulationen, warum der erste Ansatz langsamer ist, muss ich mir erst den Code genauer ansehen...

Hi Marco, hatte meine ersten Experimente auch mit newCachedThreadPool gemacht aber irgendwie war/ist die Performance bei den FixedThreadPools besser. Nur ca. zwischen 4-8 Threads ist die Performance des newCachedThreadPool besser als bei einer einfachen LinearSearch. Ich frage mich ob der Ansatz überhaupt richtig ist. Vielleicht sollte ich zwei Objekte erstellen die in anderen Threads laufen und in der run methode eine Schleife haben wo sie etwas abarbeiten ... sich dann schlafen liegen und darauf warten über notify geweckt zu werden ... somit würde die Objekt-/Threaderzeugung außer bei der Initialisierung der Klasse gänzlich wegfallen. Müsste ich mal testen wenn ich etwas Zeit finde.

===========================
2 Threads (newCachedThreadPool)
===========================
Chess (15401 Wörter):
- LinearSearchUtils: 2310ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 3771ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3007ms
- BinarySearchUtils: 27ms
- MultiCoreSearchUtils: 5832ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2979ms
- BinarySearchUtils: 19ms
- MultiCoreSearchUtils: 5168ms

===========================
3 Threads (newCachedThreadPool)
===========================
Chess (15401 Wörter):
- LinearSearchUtils: 2389ms
- BinarySearchUtils: 33ms
- MultiCoreSearchUtils: 2743ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3039ms
- BinarySearchUtils: 27ms
- MultiCoreSearchUtils: 3728ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 3023ms
- BinarySearchUtils: 16ms
- MultiCoreSearchUtils: 3934ms

===========================
4 Threads (newCachedThreadPool)
===========================
Chess (15401 Wörter):
- LinearSearchUtils: 2378ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 1727ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3068ms
- BinarySearchUtils: 21ms
- MultiCoreSearchUtils: 2191ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 3009ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 2331ms

===========================
8 Threads (newCachedThreadPool)
===========================
Chess (15401 Wörter):
- LinearSearchUtils: 2296ms
- BinarySearchUtils: 31ms
- MultiCoreSearchUtils: 2766ms

Roman Emipre (18752 Wörter):
- LinearSearchUtils: 3107ms
- BinarySearchUtils: 23ms
- MultiCoreSearchUtils: 2754ms

RMS Titanic (129316 Wörter):
- LinearSearchUtils: 2964ms
- BinarySearchUtils: 14ms
- MultiCoreSearchUtils: 2698ms

 

[momesana]

Edit: was du evtl bei der alten Version ausprobieren könntest, wäre zuerst die LinearFinder zu erzeugen und anschließend sie gesammelt zu starten:

Hatte ich schon durchprobiert. Leider Kein Performance-Zuwachs :-(

 

[Marco13]

Ah ja sicher... Hatte das ganze jetzt runterkondensiert auf was, wo ich mit

Runnable runnable = new LinearFinder<T>(a, k, c, i, threadGroup);
//new Thread(null, runnable, "T"+i, 0).start();
threadPool.submit(runnable);

durch ein/auskommentieren der letzten beiden Zeilen umschalten konnte, und mich gewundert, warum das zweite doppelt so schnell ist - mich aber DANN gewundert, warum er für 15000 Worte überhaupt etliche Sekunden braucht, und genauer geschaut: Die Methode wird ja tausende Male aufgerufen! Dann sollte man natürlich nicht jedes mal neue Threads erstellen und starten (durch den Executor wird ja genau das versteckt).

Das, was du zuletzt beschrieben hast (mit dem notify()) wäre ein gangbarer Weg. Aber eigentlich nicht nötig, weil ziemlich low-level. Man könnte die Runnables einfach in eine BlockingQueue legen, die von Workern abgearbeitet wird. Aber ... das würde dann darauf rauslaufen, dass man auf rudimentärste Weise das nachbaut, was eben genau der ThreadPoolExecutor macht