Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » C++ performance auf großen dateien
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
16.06.2012, 14:48 Uhr
kronos
Quotenfisch
(Operator)


Hallo,

ich bin in der Verlegenheit mit großen Dateien hantieren zu müssen. Beispiel: ein paar Millionen (relative kurze) Zeilen, lösche Zeilen gleichen Inhalts. Sowas in der Art.
Momentan lese ich per ifstream::getline in eine list<string> und benzutze auch sonst die üblichen C++-Methoden zum vergleichen der strings usw.
Meine Frage wäre nun, ob sich bei der Datenmene performancemäßig was tut wenn man
- erst die Zeilen zählt, dann die Listegröße reserviere, dann einlese
- char* statt string verwende
- was anderes als std::list verwende
- sonst irgendwelche tollen tipps...?

Danx für Antworten!

kronos
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
16.06.2012, 22:55 Uhr
Hans
Library Walker
(Operator)


... vielleicht mal eine Kopie von den Dateien auf exakt 1000 Zeilen zurecht kürzen, und dann beide Programmversionen mit einem Profiler untersuchen... - Ansonsten fällt mir nichts klügeres ein.
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
17.06.2012, 18:45 Uhr
ao

(Operator)


Hi.

Faustregel: Wer Performance gewinnen will, muss Arbeitsspeicher investieren. Und die Anzahl der Laufwerkszugriffe minimieren. Besser wenige große Blöcke lesen als ganz viele kleine.

Ich würde zuerst beim Betriebssystem fragen, wie groß die Datei ist, dann entsprechend viel Speicher holen (mit new) und dann alles in einem Rutsch einlesen und die nachfolgenden Operationen (Zerlegen in Zeilen, gleiche Zeilen suchen usw.) nur noch auf dem Speicherabbild machen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
18.06.2012, 12:39 Uhr
kronos
Quotenfisch
(Operator)


Hey,
danke fuer die Antworten. Es geht wirklich um viele GB, daher bringt mir komplett einlesen nicht so viel, da er ohnehin wieder swappen muss, oder?
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
18.06.2012, 16:51 Uhr
ao

(Operator)



Zitat von kronos:
Es geht wirklich um viele GB, daher bringt mir komplett einlesen nicht so viel


Na gut, das ist was anderes. Bei "ein paar Millionen kurze Zeilen" war ich von Dateigrößen von wenigen hundert MB ausgegangen, und das kann man heutzutage durchaus an einem Stück allokieren. Zumindest könnte man es versuchen und als Fallback eine Routine vorsehen, die mit kleineren Blöcken klarkommt - falls der Speicher gerade mal zu stark fragmentiert ist.

Mehrere Gigabytes am Stück einlesen, das wird mit oder ohne Swapping nicht klappen, es sei denn, dein Computer ist ein echtes Speichermonster und hat tatsächlich so viel RAM zur Verfügung.


Zitat:
... da er ohnehin wieder swappen muss, oder?


Wenn du mit mehreren Blöcken hantierst, die zusammen ein paar GB groß sind, aber jeder einzelne klein genug, um ins RAM zu passen, dann würde das hingegen funktionieren. Und ich schätze, der Swapping-Mechanismus des Betriebssystems ist um einiges besser als das, was du (oder ein anderer von uns) mal eben runterprogrammieren oder mit Files emulieren könntest.
Dieser Post wurde am 18.06.2012 um 16:54 Uhr von ao editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
18.06.2012, 17:11 Uhr
kronos
Quotenfisch
(Operator)



Zitat von ao:
Mehrere Gigabytes am Stück einlesen, das wird mit oder ohne Swapping nicht klappen, es sei denn, dein Computer ist ein echtes Speichermonster und hat tatsächlich so viel RAM zur Verfügung.

Bin nicht so der I/O-Held... warum klappt das auch mit Swapping nicht?

Und: Den Algorithmus zu 'blocken' macht Sinn - was ist denn eine vernuenftige Groesse? Ungefaehr? Habe wenige Erfahrung damit...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
18.06.2012, 18:04 Uhr
ao

(Operator)



Zitat von kronos:
Bin nicht so der I/O-Held... warum klappt das auch mit Swapping nicht?

Weil man nur solche Speichergrößen allokieren kann, die zusammenhängend im Heap frei sind. Es geht soweit ich weiß nicht, dass EINE Alloc-Einheit zum Teil im RAM und zum Teil auf der Swapdisk liegt. Oder habe ich da Unrecht?


Zitat:
Und: Den Algorithmus zu 'blocken' macht Sinn - was ist denn eine vernuenftige Groesse? Ungefaehr? Habe wenige Erfahrung damit...

So groß wie möglich. Ich würde einfach mit der vollen Dateigröße anfangen und so lange halbieren, bis es klappt. Oder irgendeinen Systemaufruf benutzen, der mir verrät, wie groß der größte zusammenhängende Heap-Block ist.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
19.06.2012, 00:05 Uhr
kronos
Quotenfisch
(Operator)



Zitat von ao:

Zitat:
Bin nicht so der I/O-Held... warum klappt das auch mit Swapping nicht?

Weil man nur solche Speichergrößen allokieren kann, die zusammenhängend im Heap frei sind. Es geht soweit ich weiß nicht, dass EINE Alloc-Einheit zum Teil im RAM und zum Teil auf der Swapdisk liegt. Oder habe ich da Unrecht?

Interessante Frage - wie bekommen wir das jetzt raus?


Zitat von ao:


Zitat:
Und: Den Algorithmus zu 'blocken' macht Sinn - was ist denn eine vernuenftige Groesse? Ungefaehr? Habe wenige Erfahrung damit...

So groß wie möglich. Ich würde einfach mit der vollen Dateigröße anfangen und so lange halbieren, bis es klappt. Oder irgendeinen Systemaufruf benutzen, der mir verrät, wie groß der größte zusammenhängende Heap-Block ist.

Mir geht's bei der Frage um die Performance beim Falten der Daten. Einlesen ist ja linear, das ist nicht so wild. Der Plan ist anstatt

Code:
FOR x = 0 TO N
  FOR y = 0 TO N
     COMBINE(data[x],data[y])

sowas in der Art

Code:
FOR a = 0 TO N / block_size
  FOR b = 0 TO N / block_size
    FOR x = a * block_size TO (a+1)*block_size
      FOR y = b * block_size TO (b+1)*block_size
        COMBINE(data[x],data[y])

zu machen. So sind sind z.T. die BLAS/LAPACK Sachen implementiert.
Allerdings ist das was ich bisher gebastelt habe für kleinere Portionen drastisch langsamer als die normale Version - hoffe es lohnt sich bei den dicken Brummern....


Bearbeitung:
Nested quotes...

--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
Dieser Post wurde am 19.06.2012 um 00:07 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
19.06.2012, 12:00 Uhr
TOSHMAX
Zitat von kronos:

Zitat:
Weil man nur solche Speichergrößen allokieren kann, die zusammenhängend im Heap frei sind. Es geht soweit ich weiß nicht, dass EINE Alloc-Einheit zum Teil im RAM und zum Teil auf der Swapdisk liegt. Oder habe ich da Unrecht?

Interessante Frage - wie bekommen wir das jetzt raus?

Wenn ein Prozess gestartet wird und Speicher alloziert und kurz danach ein anderer Prozess den kompletten restlichen physischen RAM wegschnappt, sollte neuer Speicher auch vom Swap geholt werden. Damit befindet sich theoretisch ein Teil des Heaps im RAM und ein anderer im Swap. Das sollte meiner Meinung nach auch für einen alloc-Aufruf möglich sein, aber ob es Betriebssysteme gibt die das unterstützen weiß ich leider nicht.
Im Heap muss aber definitv ein Bereich in der gewünschten Größe frei sein, egal wo er dann physikalisch abgebildet wird.


Zitat von kronos:
Allerdings ist das was ich bisher gebastelt habe für kleinere Portionen drastisch langsamer als die normale Version - hoffe es lohnt sich bei den dicken Brummern....

Falls du alle gleichen Zeilen entfernen willst, besteht ein weiteres Problem. Die Bereiche, die du bereits bearbeitet und wieder freigegeben hast, müssten mit allen weiteren Bereichen verglichen werden. Da könnte schnell ein vielfaches der Datenmenge auf der Festplatte hin- und hergeschoben werden müssen. Besser wäre es wenn die Daten sortiert oder anders vorbereitet vorliegen.
Dieser Post wurde am 19.06.2012 um 12:06 Uhr von TOSHMAX editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
19.06.2012, 15:25 Uhr
0xdeadbeef
Gott
(Operator)


Geht es um aufeinanderfolgende, gleiche Zeilen oder auch um getrennt voneinander auftauchende doppelte Zeilen? Und ein wie großer Anteil der Zeilen wird ungefähr aussortiert werden?

Ansonsten ist std::list generell eine performanetechnisch schlechte Wahl, wenn man keine sehr guten Gründe dafür hat. Mit einer std::deque bist du im Zweifel besser dran. Wie viel das bringt, hängt allerdings davon ab, ob der Flaschenhals bei I/O oder bei Aussortieren doppelter Zeilen liegt.

Wenn es dir auch um getrennt voneinander auftauchende, doppelte Zeilen geht, ist ein sequentieller Container so oder so aber keine wirklich gute Wahl - das Suchen dauert bei mehreren Millionen Einträgen in einem unsortierten Container ja ewig. Mit einiger Wahrscheinlichkeit solltest du ein std::unordered_set oder etwas derartiges für die Suche heranziehen. Um doppelte Datenhaltung zu vermeiden dann halt entweder die deque oder das unordered_set mit Zeigern in den anderen Container.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: