swap bei nichtvorhersehbaren speicherzugriffen langsamer ?
-
hola leute
wie sieht das eigendlich mit dem tauschen von variablen aus, wenn so wie bei qsort nicht sequeniell auf den speicher zugegriffen wird, sondern wahllos ?
kann dadurch das swappen um etliches langsamer werden ?kurzes beispiel:
hab ein struct wo nur drei ints drinnen sind. wenn ich das mit zwei variablen mache die hintereinder im speicher liegen, braucht er grad mal paar takte. beim quicksort brauchte er aber ploetzlich ueber 400 takte pro swap.
jo ich weiß, das da andere prozesse auch dazwischen funken, aber so extrem duerfte das eigendlich nicht ausfallen.weiß da jemand genauer bescheid ?
Meep Meep
-
ich hab ernsthaft versucht, schnelle sortierfunktionen zu schreiben.
habe nie gesehen, daß std::swap irgend einen nachteil hätte. ich vermute sogar compilermagie darin.
-
Meep Meep schrieb:
wie sieht das eigendlich mit dem tauschen von variablen aus, wenn so wie bei qsort nicht sequeniell auf den speicher zugegriffen wird, sondern wahllos ?
kann dadurch das swappen um etliches langsamer werden ?dadurch dass die pc-osse alle mit virtual memory hantieren und wenn das kopieren über page-grenzen hinausgeht, kann ich mir schon vorstellen, dass das etwas langsamer ist. zumindest beim ersten zugriff (page-fault, thread anhalten, seite in den virtuellen adressraum mappen, thread wieder starten usw.)
-
re
@net: den effekt hab ich auch bei ein paar kilobytes.
@volkard: ich versteh jetz nicht, was du mir damit sagen willst
bin noch immer bei meinem problem mit den doppelten strings. aber das geht alles viel zu traege. quicksort braucht fuer 1 mio. strings (laenge 8 - 16 byte) scho fast 3 sekunden (auf nem 1800 MHz prozi). das kommt mir einfach viel zu lange vor
Meep Meep
-
Meep Meep schrieb:
@net: den effekt hab ich auch bei ein paar kilobytes.
eine page (unter win zumindest) ist 4k gross
Meep Meep schrieb:
bin noch immer bei meinem problem mit den doppelten strings. aber das geht alles viel zu traege. quicksort braucht fuer 1 mio. strings (laenge 8 - 16 byte) scho fast 3 sekunden (auf nem 1800 MHz prozi). das kommt mir einfach viel zu lange vor
3 sekunden ist doch gar nicht so schlecht. oder hast du 'ne 0 vergessen?
-
Also mal angenommen, deine Messung hundertprozentig korrekt und weiterhin angenommen, es liegt am caching, so verstehe ich immer noch nicht, was das mit std:swap zu tun haben soll. Wenn du was zu vertauschen hast, ist es leider so.
Immerhin bleibt dir der Trost, dass Quicksort nach einem Durchgang nur noch auf halb so großen Teil arbeitet, was das caching evtl. vermindert. Gibt auch Algorithmen, die nicht so krassen random access brauchen. Und dann stellt sich natürlich noch die Frage, warum du eigentlich nicht std::sort verwendest?
-
@optimizer
weil std::sort auch net viel schneller is. grad mal 0.1 sek bei 2.7 sek.Meep Meep
-
Gut, mag sein, wenn du wirklich gut arbeitest (kann aber auch sein, dass std::sort besser ist und es nur bei dir gerade nicht zum Tragen kommt). Aber der Aufwand ist doch unnötig? Hat es einen bestimmten Grund, dass du das selber codest?
-
re
erstens mal, weil std::sort mit meinem vector bzw. string net funktioniert.
zweitens uebung
dann mehr speedhab jetzt die sortierung immerhin scho mal auf 1.3 sekunden runtergebracht.
vielleicht gehts ja noch ein bissl weiter...
Meep Meep
-
Kann ich mir kaum vorstellen, dass das nicht funktioniert. Du musst ja nur einen passenden Comparator schreiben. Aber wenn du üben willst, wird schon nicht schaden.
-
Kannst du uns mal Code zeigen, der das unterlegt?
-
Bezog sich das auf mich (und wenn ja, was meinst du)?
-
Optimizer schrieb:
Bezog sich das auf mich (und wenn ja, was meinst du)?
Das bezog sich auf den Originalposter.