# SuchEngine verschnellern



## The_S (16. Sep 2005)

Hi,

ich programmiere gerade für mein Programm eine Suche. Meine Frage ist jetzt: wie kann ich die suche noch ein stückchen schneller machen? Zur Zeit brauche ich für 891 Dateien und 155 Ordner mit insgesamt 256 MB ca. zwischen 780 und 860 Millisekunden.


```
void search(final File dir, final String search) {
		
		new Thread(new Runnable() {
			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file); // treffer ist ein Vector
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
				end = new GregorianCalendar();
			}
		}).start();
	}
```


----------



## Bleiglanz (16. Sep 2005)

allzuviel dürfte da nicht drin sein, du könntest von vektor auf ArrayList umsteigen und diese durchschleifen, so dass zu den Zugriff nicht synchronisieren musst (bringt aber wahrscheinlich nix)

und

das starten von threads kostet i.A. viel zeit, und du schmeisst für jedes Directory einen neuen thread an; vielleicht ist es schneller du startest nur einen, und in diesem dann eine rekursive funktion


----------



## The_S (16. Sep 2005)

Das mit den Threads hatte ich zu beginn auch nicht so, also alles in einem. Nur war es dann ein bisschen arg langsam! Zum vergleich

mit Threads durchschnittlich 810 Millisekunden 

ohne Threads durchschnittlich 9500 Millisekunden

ich frag mich aber auch, warum das so viel langsamer ist. Die Arraylist werde ich ausprobieren, aber jetzt ist erstmal Frühstückspause :wink:

[edit]

Nein, eine ArrayList verlangsamt das ganze auch so um die 100 Millisekunden. Kann man vielleicht bei den if-Abfragen nochma an der Performance kitzeln?


----------



## AlArenal (16. Sep 2005)

Könnte es sein, dass es nunmal ne Weile dauert bis das Betriebssystem die entsprechenden Daten ausgelesen und an die VM übergeben hat? Große Verzeichnisse zu Öffnen dauert ja auch schonmal nen Moment... Roundabout 900 Dateien und 155 Ordner - da braucht der Explorer von Windows auch nen Moment für.


----------



## The_S (16. Sep 2005)

Hab grad ma ausprobiert, und ich bin (arbeite hier mit Windows 2000) schneller als die Suche von Windows 2000  . Kann ja aber sein, dass es ne Möglichkeit gibt, das Ding nochmal ein wenig zu tunen (z. B. mit anderen, schnelleren Datentypen, ...)


----------



## AlArenal (16. Sep 2005)

Der Pferdefuß dürfte die Geschwindiogkeit sein, in der das OS die Daten liefert, da wirst du schon MS bitten müssen, zu optimieren


----------



## The_S (16. Sep 2005)

OK, werd aber trotzdem noch ein wenig rumprobieren, ob ich noch ein paar Millisekunden schneller bekomm :wink: .

Mir kommt da gerade ein anderes Problem, wie stelle ich fest, dass die Suche fertig ist, also das kein Thread mehr läuft?


----------



## Bleiglanz (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> OK, werd aber trotzdem noch ein wenig rumprobieren, ob ich noch ein paar Millisekunden schneller bekomm :wink: .
> 
> Mir kommt da gerade ein anderes Problem, wie stelle ich fest, dass die Suche fertig ist, also das kein Thread mehr läuft?



schwierig, hab mich auch schon gefragt wie du überhaupt auf deine Zeiten kommst?

kann mir eigentlich nicht vorstellen, dass die ThreadVariante wirklich so viel schneller ist


----------



## The_S (16. Sep 2005)

@ bleiglanz

auf was war dein post bezogen? Darauf, dass es schwierig ist, da noch was an geschwindigkeit rauszukitzeln oder dass es schwierig ist festzustellen, ob die Suche noch läuft?

Code is ja da, kannst ja mal ausprobieren, wenns dir schwer fällt zu glauben, dass der Unterschied so trastisch ist (konnts ja auch kaum glauben)

Hab grad nochman größer Angelegten Vergleich zwischen der Win 2000 Suche und meiner Suche gestartet. Ergebnis: bei 233328 Dateien und  28957 Ordner

Windows 2000: 3 Minuten 34 Sekunden

ich: genau 102428 Millisekunden => 1 Minute 42 sec.

Was macht Windows 2000 so lange?

Trotzdem bleib immernoch mein anderes Problem: Wie stelle ich fest, dass die Suche beendet ist?


----------



## Bleiglanz (16. Sep 2005)

ich habs mal in eine main gepackt und mit einem shutdownHook das ende ermittelt

unter Linux ist die "single-thread" variante auf jeden Fall schneller!

dass du Windows schlägst wundert mich nicht wirklich, die Suche hat ja wesentlich mehr features


aber die Frage bleibt: wie stellst du eigentlich fest dass du fertig bist?


----------



## The_S (16. Sep 2005)

komisch, dass bei dir single-thread schneller ist ???:L .

Wie du sicher bemerkt hast, habe ich am ende meiner Methode ein


```
end = new GregorianCalendar()
```

ich hab auch ein start, was die Zeit zu beginn speichert. Wenn ich jetzt insgesamt fertig bin, vergleiche ich die beiden Daten und bekomme so die Zeit raus.

[edit] kA, was da jetzt gerade gelaufen ist, aber jetzt ist die single-Thread Suche nur noch halb so langsam wie die Multi-Thread Lösung


----------



## AlArenal (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> komisch, dass bei dir single-thread schneller ist ???:L .



Warum? Mehr Threads bedeuten mehr Verwaltungsaufwand für die VM, also mehr Performance, die nicht deinem Programm zugute kommt. Und wenn ich mein Betriebssystem gleichzeitig 30 Anfragen für unterschiedliche Verzeichnisse stelle, wirds vermutlich auch nicht schneller, als wenn ich es nacheinander mache, weil meine Platte nicht an 30 Stellen gleichzeitig die Informationen lesen kann


----------



## AlArenal (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> [edit] kA, was da jetzt gerade gelaufen ist, aber jetzt ist die single-Thread Suche nur noch halb so langsam wie die Multi-Thread Lösung



Alte Weisheit: Wer misst, misst Mist.


----------



## The_S (16. Sep 2005)

AlArenal hat gesagt.:
			
		

> Hobbit_Im_Blutrausch hat gesagt.:
> 
> 
> 
> ...



Ja, is mir scho klar, nur warum isses unter windows schneller mit Multithreads zu arbeiten und unter linux net?


----------



## AlArenal (16. Sep 2005)

P.S.:
Aus eigenrer Erfahrung dürften die meisten auch wissen, das parallele Vorgänge auf Datenträgern, unverhältnismäßig länger dauern als sequenzielle. Beim Versuch des Betriebssystems alle Anfragen per Mutlitaksing quasi-gleichzeitig zu erledigen, entsteht ne Menge Overhead durch zusätzliche Positionierung des Schreib-/Lesekopfs, die bei sequenzieller Abarbeitung nicht notwendig wäre.


----------



## AlArenal (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Ja, is mir scho klar, nur warum isses unter windows schneller mit Multithreads zu arbeiten und unter linux net?



Warum hatte mein Ex-Wagen bei 1.8 Litern 116 PS, der davor 136 PS und der aktuelle nur 90 PS? Und warum hängt der neue VW mit 1.4 Litern alle ab? 

Rückfrage: Was soll eigentlich "halb so langsam" bedeuten? LOL


----------



## The_S (16. Sep 2005)

Hast du Windows? Währst du so net und würdest beide varianten mal testen?

[edit] halb so langsam *g* heißt, dass ich für das auslesen der großen Festplatte (2. Vergleich) mit Multi-Threading genau 102428 Millisekunden benötige und mit Single-Threading 195080 Millisekunden. Also ungefähr das doppelte an Zeit vom Multithreading! :wink:


----------



## AlArenal (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Hast du Windows? Währst du so net und würdest beide varianten mal testen?



Yo, XP.
Wärst du so nett mir beide zuzuschicken?


----------



## The_S (16. Sep 2005)

Will da selbstverständlich noch ne GUI drumbauen, also net wundern 8) .

Multithreading


```
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;

public class Search extends JFrame implements ActionListener {
	
	Vector treffer = new Vector();
	GregorianCalendar start = new GregorianCalendar();
	GregorianCalendar end = new GregorianCalendar();
	
	public Search() {
		
		search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + das wonach du suchen willst
		try {
			Thread.sleep(1000); // Bitte eine Zeit eintragen in der die Suche abgeschlossen sein sollte, hatte noch keine Zeit mir dafür was anderes zu überlegen
		}
		catch (Exception e) {
		}
		for (int i = 0; i < treffer.size(); i++) {
			System.out.println(treffer.elementAt(i));
		}
		System.out.println(end.getTimeInMillis() - start.getTimeInMillis());
	}
	
	void search(final File dir, final String search) {
		
		new Thread(new Runnable() {
			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file);
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
				end = new GregorianCalendar();
			}
		}).start();
	}
		
	public static void main(String[] args) {
		
		Search sc = new Search();
		sc.setVisible(true);
	}
	
	public void actionPerformed(ActionEvent evt) {
	}
}
```

Single-Threading


```
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;

public class Search extends JFrame implements ActionListener {
	
	Vector treffer = new Vector();
	GregorianCalendar start = new GregorianCalendar();
	GregorianCalendar end = new GregorianCalendar();
	
	public Search() {
		
		search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + Suchbegriff
		end = new GregorianCalendar();
		for (int i = 0; i < treffer.size(); i++) {
			System.out.println(treffer.elementAt(i));
		}
		System.out.println(end.getTimeInMillis() - start.getTimeInMillis());
	}
	
	void search(final File dir, final String search) {
		
//		new Thread(new Runnable() {
//			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file);
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
//			}
//		}).start();
	}
		
	public static void main(String[] args) {
		
		Search sc = new Search();
		sc.setVisible(true);
	}
	
	public void actionPerformed(ActionEvent evt) {
	}
}
```


----------



## Bleiglanz (16. Sep 2005)

wie gross stellst du Thread.sleep denn ein?

bei mir ist auch unter windows die SingleThread Variante schneller (getestet in einer reinen main mit shutdownhook)


----------



## The_S (16. Sep 2005)

Also das verwirrt mich jetzt ... moment, da kommt mir eine Idee!!! Ich glaube (kanns net nachgucken, auf der Arbeit is immer alles mögliche gesperrt) dass ich nen Prozessor mit HT Technologie hab von Intel. Kanns sein, dass es daran liegt?

Also für den 1. Versuch reichen die 1000 Millisekunden, man kann ja auch als spaß an der Freude mal 10 Minuten angeben, ändert aber auch nichts am ergebnis. Nur zu wenig darf man nicht angeben, aber das merkt man dann, wenn man als ergebnis bekommt, dass über den angegebenen Millisekunden liegt. Für meinen 1. Versuch (auslesen von Laufwerk Z, das kleine Laufwerk mit den 256 MB) die 1000 Millisekunden.


----------



## AlArenal (16. Sep 2005)

Macht nicht viel Sinn die Zeit zwischen der Erzeugung zweier Kalender-Instanzen zu ermitteln


----------



## The_S (16. Sep 2005)

AlArenal hat gesagt.:
			
		

> Macht nicht viel Sinn die Zeit zwischen der Erzeugung zweier Kalender-Instanzen zu ermitteln



???


----------



## AlArenal (16. Sep 2005)

Die Multi-threaded Variante liefert ne Zeit, aber listet keine Treffer...


----------



## AlArenal (16. Sep 2005)

GregorianCalendar start = new GregorianCalendar();
GregorianCalendar end = new GregorianCalendar(); 
System.out.println(end.getTimeInMillis() - start.getTimeInMillis());


----------



## The_S (16. Sep 2005)

Doch, musst wie gesagt momentan noch die Zeit erhöhen, die der Thread schlafen soll. Bin noch auf der Suche, wie ich das am besten mach, damit ich weiß, wann die Suche beendet ist ohne viel Performanceeinbusen zu haben.


----------



## The_S (16. Sep 2005)

AlArenal hat gesagt.:
			
		

> GregorianCalendar start = new GregorianCalendar();
> GregorianCalendar end = new GregorianCalendar();
> System.out.println(end.getTimeInMillis() - start.getTimeInMillis());



Und was willst du mir damit sagen? Du weißt scho, dass dazwischen meine suchmethode ist und end darin abgedatet wird!?


----------



## AlArenal (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Und was willst du mir damit sagen? Du weißt scho, dass dazwischen meine suchmethode ist und end darin abgedatet wird!?



Ach, wo in deinem Code soll dieses *Up*date denn stattfinden?


----------



## Bleiglanz (16. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Also das verwirrt mich jetzt ... moment, da kommt mir eine Idee!!! Ich glaube (kanns net nachgucken, auf der Arbeit is immer alles mögliche gesperrt) dass ich nen Prozessor mit HT Technologie hab von Intel. Kanns sein, dass es daran liegt?



ja, könnte sein

es heisst ja eh immer, dass das Threading unter Windows bei Java wesentlich besser ist


----------



## The_S (16. Sep 2005)

AlArenal hat gesagt.:
			
		

> Hobbit_Im_Blutrausch hat gesagt.:
> 
> 
> 
> ...



Multi-Threading:


```
new Thread(new Runnable() { 
         public void run() { 
            File[] files = dir.listFiles(); 
            for (File file : files) { 
               if (file.getName().equalsIgnoreCase(search)) { 
                  treffer.addElement(file); 
               } 
               if (file.isDirectory()) { 
                  search(file, search); 
               } 
            } 
            end = new GregorianCalendar(); // hier!!!
         } 
      }).start();
```

Single-Threading:


```
search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + Suchbegriff 
      end = new GregorianCalendar(); // hier
```

Hast dus jetzt mal ausprobiert wenn du den Thread länger schlafen lässt?

@ Bleiglanz

ich werds daheim ma unter XP und 100pro sicher ohne HT Prozessor :wink: ausprobieren


----------



## Guest (16. Sep 2005)

Verwende noch folgendes statt listFiles()
	
	
	
	





```
String fileNames[] =  dir.list();
for(String fileName : fileNames) {
  File file = new File(dir, fileName);
  if (fileName.equalsIgnoreCase(search)) { 
    treffer.addElement(file); 
  } 
  if (file.isDirectory()) { 
    search(file, search); 
  }
}
```
In listFiles() wird immer ein File-Array mit gleicher Länge wie der String-Array erzeugt.
Dadurch sparst Du bei jedem Aufruf 

- das Erzeugen dieses Arrays in listFiles()
- die Schleife in listFiles()
- den Methodenaufruf von file.getName()


----------



## The_S (16. Sep 2005)

Hilft leider nicht ...  , aber trotzdem danke!


----------



## The_S (17. Sep 2005)

OK, bei mir daheim, ohne HT ist Singlethreading schneller. Dann werd ich wohl zwei Suchmöglichkeiten einbauen!


----------



## Wikinator (17. Sep 2005)

Hallo,

ich habe eine kleine Frage nebenbei:
Wie misst du so genau die Performance?


----------



## byte (18. Sep 2005)

ich weiss nicht wie er es macht, aber eine einfache möglichkeit ist:


```
long start = System.currentTimeMillis();

//... der zu messende Code

System.out.println("Vergangene Zeit: "+(System.currentTimeMillis()-start));
```


----------



## The_S (19. Sep 2005)

Wikinator hat gesagt.:
			
		

> Hallo,
> 
> ich habe eine kleine Frage nebenbei:
> Wie misst du so genau die Performance?



Ich erstelle zwei Variablen des Typs GregorianCalendar, die 1. Wird beim Starten des Suchvorgangs erstellt, die 2. bei beenden. Beide voneinader abgezogen = Performance :wink:


----------



## The_S (19. Sep 2005)

Was ist eigentlich schneller und warum?


```
for (int i = 0; i < files.length; i++)
```

oder


```
for (File file : files)
```


----------



## AlArenal (19. Sep 2005)

Du bist doch der große Performance-Messer, sag du es uns!


----------



## Bleiglanz (19. Sep 2005)

beide absolut völlig gleich - unterschied ist unmessbar -, das zweite wird ja intern zum ersten, sowas wie

```
for (int i = 0, len=files.length; i < len; i++){
    File file = files[i];
...
}
```

allerdings kannst du beim ersten den Zugriff auf files_ weglassen wenn du ihn nicht brauchst, während beim zweiten immer eine lokale Variable file erzeugt wird (und beim zweiten kannst du das array nicht verändern...)_


----------



## The_S (19. Sep 2005)

AlArenal hat gesagt.:
			
		

> Du bist doch der große Performance-Messer, sag du es uns!



Das ist ja gerade das komische ... Manchmal habe ich bei methode 1 extrem mehr Zeit verbraucht, als bei Methode 2, aber meistens ist beides gleich. Deswegen meine Verwirrung.

@ bleiglanz danke!


----------



## Bleiglanz (19. Sep 2005)

> Manchmal habe ich bei methode 1 extrem mehr Zeit verbraucht, als bei Methode 2


unmöglich!


----------



## The_S (19. Sep 2005)

Ist aber so, hab mir dafür extra nen Testcode geschrieben. Ich mache sonst nichts und es scheint auch nur dann zu sein, wenn der Code frisch compiliert ist. Könnte auch sein, dass es an der IDE (JCreator) liegt ...


----------



## The_S (20. Sep 2005)

So, bin jetzt gerade dabei, dass man auch nach Dateien/Ordner suchen kann, dessen Namen man nicht genau kennt. Was ist da jetzt schneller? indexOf() oder contains()?


----------



## bygones (20. Sep 2005)

is voellig egal.

intern ist beides die gleiche Methode !

Unterschied ist nur - indexOf hat einen String als Parameter, contains eine CharSequence


----------



## The_S (20. Sep 2005)

Danke, dann nehme ich indexOf, damit ich net erst in ne CharSequence wandeln muss. Woher weißt du das eigentlich oder besser gefragt, kann man das irgendwo nachlesen? Dann müsst ich nämlich net immer fragen :wink:


----------



## na-oma (20. Sep 2005)

steht zum einen in der Java-Doku, gibts von sun.
Zum andern in jeder Datei die du benutzt z.b. in diesem Fall java/lang/String.class in deinem jdk.

da steht:


```
public boolean contains(CharSequence s) {
        return indexOf(s.toString()) > -1;
    }
```

und

```
public int indexOf(int ch) {
	return indexOf(ch, 0);
    }
```

da kann man immer toll nachschaun, wie das ganze eigentlich arbeitet und was es so alles für methoden gibt.

wenn du mit eclipse arbeitest (geht sicher auch in anderen editoren ähnlich) gehst du mit der Maus über den Methodennamen in deinem Quelltext, drückst Strg und die Linke Maustaste. Damit gelangst du in der Datei wo die Klasse (in dem Fall String) definiert ist an die Stelle, wo die angeklickte methode definiert ist. dort steht im KOmmentar auch noch allerhand anderes nützliches 

oder halt gleich die doku. so isses aber spannender


----------



## The_S (20. Sep 2005)

Hm, danke! Benutze kein Eclipse und mein JDK zu durchsuchen hab ich keine lust ... :wink:


----------



## bygones (22. Sep 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Danke, dann nehme ich indexOf, damit ich net erst in ne CharSequence wandeln muss.


schau dir mal die APi an... CharSequence ist das Oberinterface von String / StringBuffer usw... ergo String = CharSequence...


----------



## The_S (22. Sep 2005)

deathbyaclown hat gesagt.:
			
		

> Hobbit_Im_Blutrausch hat gesagt.:
> 
> 
> 
> ...



Also langsam wirds peinlich ... ich sollte mittlerweile doch die API nutzen können  . Danke!


----------



## Bennidi (18. Jan 2006)

hey blutender Hobbit,

multithreading lohnt sich nur bei sehr häufigen kontextwechseln (ip und register auf stack sichern usw.). [bei HT Technologie sind die wichtigsten "geshadowed", d.h. doppelt vorhanden]. Jetzt zu dem code:
wenn ein rechenintensiver thread (z.B. eine Suche)ansteht erkennt ein intelligenter time-scheduling algorithmus das eigentlich und räumt dementsprechen mehr Zeit dafür ein. Somit sollte deine suche single-threaded schneller laufen, da es (wie schon von einigen erwähnt) weniger overhead gibt.
ich frage mich übrigens, ob du mit deiner messung nicht nur das ende des ersten threads misst (oberste verzeichnisstufe) und in wirklich die anderen noch laufen. Bin aber kein kenner was threads angeht. hab es nur ein bisschen in der Theorie kennen gelernt.


----------



## The_S (19. Jan 2006)

Hui, da wird altes zeug rausgekramt ...  .

Kenne meinen Code zwar nicht mehr (schau bei Gelegenheit mal nach), aber normalerweiße müsste ich das so programmiert haben, dass er wartet bis der letzte Thread beendet ist (wenn ich mich recht erinnere, zähle ich wie viele Threads gestartet und wie viele beendet wurden).

Und ansonsten habe ich weiterhin festgestellt, dass bei Dual-Core und Prozessoren mit HT die Multithreading variante deutlich schneller ist. Bei jeder "normalen" CPU is Singlethreading schneller.


----------



## Ilja (2. Feb 2006)

die thread-variante kann nicht schneller sein...

wenn dein end nicht synchronized gesetzt wird, kann es sein, dass der wert misst ist ^^


----------



## The_S (2. Feb 2006)

Ilja hat gesagt.:
			
		

> die thread-variante kann nicht schneller sein...
> 
> wenn dein end nicht synchronized gesetzt wird, kann es sein, dass der wert misst ist ^^



zum 100sten mal: der Wert passt, weil

1. Merk ich wenn ich den Computer wieder bedienen kann ohne dass ich 10 Minuten warten muss, bis ein Fenster (z. B. Explorer) aufgeht
2. Habe ich auch bei der Multithreading Variante wenn das Ende erzeigt wird alle Ergebnisse korrekt angezeigt
3. Zähle ich bei jeden neu gestarteten Thread eine Variable hoch und beim beenden wieder runter. Wenn der Wert wieder auf 0 ist, weiß ich das alles fertig ist.

oder gibts sonst noch ne Möglichkeit, warum meine Messungen falsch seien könnten???


----------

