Hallo zusammen,
ich habe hier folgenden Code (Borland C++ V6) für WIN32 OS geschrieben,
den ich modifizieren möchte. Problem: Aus einer sehr großen Datei (ca.
700MB..2GB) muss eine 10Byte Sequenz gesucht werden. Diese kann
innerhalb der Datei entweder 0x,1x oder 2x auftreten. Die Sequenz kann
nur an Vielfachen von 0x800 Adr auftreten. Mit dem Code dauert es
trotzdem noch ca. 45s auf meinem System, bis eine Sequenz, die am Ende
der Datei vorkommt, gefunden wird. Info: Die Datei wird an dieser Stelle
weiter bearbeitet. Daher auch der R/W Zugriff auf die Datei.
Geht das noch schneller?
1
boolsuccess=false;
2
DWORDadr,f_pointer;
3
WORDpuffer[10];
4
unsignedlongBytes_read;
5
6
fhnd=CreateFile(f_ilename.c_str(),
7
GENERIC_WRITE|GENERIC_READ,
8
FILE_SHARE_WRITE|FILE_SHARE_READ,
9
NULL,
10
OPEN_EXISTING,
11
FILE_ATTRIBUTE_NORMAL,
12
NULL);
13
if(fhnd!=INVALID_HANDLE_VALUE)
14
{
15
f_len=GetFileSize(fhnd,&f_lenh);
16
for(adr=0x800;adr<f_len;adr+=0x800)
17
{
18
//
19
// relative Positionierung mit 0x800-10,FILE_CURRENT
TK schrieb:> Mit dem Code dauert es> trotzdem noch ca. 45s auf meinem System, bis eine Sequenz, die am Ende> der Datei vorkommt, gefunden wird.
wie schnell ist dein System?
Normale Festplatte kommt kaum über 100Mbyte/s bei 2GB sind das
mindestens 20sekunden - und wenn nebenbei noch andere dinge laufen kommt
man schnell auf die 45 Sekunden.
Die Datei wird, auch wenn du nur ein paar Byte liest, komplett gelesen
weil die clustergröße oft bei 2k liegt.
Lösung: SSD
Möglicherweise geht es deutlich schneller, die Datei mit mmap() an den
fraglichen Stellen in den Speicher einzublenden und über einen Zeiger
direkt nach deiner Sequenz zu suchen.
Hallo PeterII,
System ist ein WIN-XP32 (AMD 3GHz DualCore).
Es läuft sonst nichts mehr nebenbei.
Ich dachte auch nur daran, z.B. die for evtl in eine do-while zu ändern,
oder evtl. bei CreateFile mit weiteren Attr. zu arbeiten. Daher meine
Frage, ob es sinnvolle Modifizierungen an diesem Code gibt, die sich auf
die Geschw. auswirken.
Gruß
TK
TK schrieb:> Es läuft sonst nichts mehr nebenbei.
es läuft immer etwas nebenbeil. Und die schreibst ja selber
> Die Datei wird an dieser Stelle weiter bearbeitet> Ich dachte auch nur daran, z.B. die for evtl in eine do-while zu ändern,> oder evtl. bei CreateFile mit weiteren Attr. zu arbeiten. Daher meine> Frage, ob es sinnvolle Modifizierungen an diesem Code gibt, die sich auf> die Geschw. auswirken.
das wird nichts bringen, 2GB im Ram suchen dauert keine Sekunde. Das
lesen der Datei macht 99.9% der Zeit aus und da ist der Flaschenhals die
Festplatte.
TK schrieb:> mmap() kennt mein Borland nicht (ich denke das ist eine MemoryMap> Funktion - oder?)
Ja. Unter Windows siehe CreateFileMapping() und MapViewOfFile().
Es wäre auszuprobieren statt der vielen kleinen Blöcke die Datei in
großen Blöcken (mehrere MB bis zu 100 MB) zu lesen und dann im Speicher
zu durchsuchen.
Durch die vielen kleinen Lesevorgänge wird das definitiv nicht
schneller, weil der Plattencontroller ggf. jedesmal darauf warten muss
bis der richtige Sektor wieder am Lesekopf vorbeikommt.
Mit einer SSD dürfte das dann völlig anders aussehen.
Da Du die Datei sowieso komplett lesen musst, solltest Du größere Blöcke
(z.B. 4 MB, am besten experimentieren) in einen Puffer zu lesen und
darin nach dem Code suchen. Das reduziert die Anzahl der Systemaufrufe
deutlich.
Das Kopieren in einen eigenen Puffer kannst Du Dir sparen, wenn Du die
Datei wie erwähnt direkt in den Speicher einblendest (Stichwort Memory
Mapped File). Im Win32-API heißen die Funktionen CreateFileMapping und
MapViewOfFile.
Aber auch da musst Du Dich für einen bestimmten Ausschnitt entscheiden,
den Du in der Schleife verschiebst, da Du in einem 32-Bit-Programm nicht
die komplette 2GB-Datei in den Adressraum mappen kannst.
TK schrieb:> Ich dachte auch nur daran, z.B. die for evtl in eine do-while zu ändern
Wenn das einen auch nur messbaren Geschwindigkeitsunterschied ergibt,
taugt der Compiler nichts.
Hallo Rufus,
das mit for und do-while habe ich zwar noch nicht probiert - aber z.B.
ist ein SetFilePointer(..,FILE_BEGIN) auch schneller als ein
SetFilePointer(0x800,FILE_CURRENT) => merklich! Damit hätte ich auch
nicht gerechnet, ist aber so bei mir.
an alle anderen
CreateFileMapping() / MapViewOfFile() muss ich mir mal ansehen.
Danke für den Hinweis.
Gruß
TK
Ich habe das mal ausprobiert, allerdings nicht mit Windows, sondern mit
Linux und nicht mit Borland C++, sondern mit GCC und nicht mit WinAPI-
sondern mit Standard-I/O-Funktionen (fopen, fseek und fread). Hier sind
die gemessenen Zeiten (jeweils nach Leeren der Lesepuffer im RAM):
1
interne SSD 2.0s
2
externe HD über USB 3.0 9.0s
3
externe HD über USB 2.0 25.1s
Diese Zeiten entsprechen praktisch exakt denen für das bloße Lesen der
kompletten Datei. Das ist auch nicht verwunderlich, da die fseek-Sprünge
kleiner als die Blockgröße (4KiB) sind. Deswegen würde vermutlich auch
Memory-Mapping keinen Vorteil bringen. Die ca. 2,5 Millionen 16-Bit-
Vergleiche fallen gegenüber dem Einlesen der Datei überhaupt nicht ins
Gewicht.
Schau doch mal nach, wie lange bei dir das reine Einlesen der Datei
dauert. Vielleicht ist deine Festplatte ja auf Grund eines Treiber- oder
Schnittstellenproblems tatsächlich so langsam. Dann weißt du immerhin,
dass es nicht an deiner Software liegt.
Yalu X. schrieb:> Deswegen würde vermutlich auch> Memory-Mapping keinen Vorteil bringen.
Es kann schon etwas ausmachen, weil einmal Umkopieren im Speicher
entfallen wird.
Versuch macht kluch...
Klaus W. schrieb:> Es kann schon etwas ausmachen, weil einmal Umkopieren im Speicher> entfallen wird.
Arbeitsspeicher kopiert mit weit über 1Gbyte/s - kann also nicht
wirklich entscheidend sein.
Ob fread() aber ohne kopieren direkt Seiten aus dem OS-File-Cache in den
Prozess mapped, ist fraglich. Mit MemoryMappedFile hat man den
direktesten Zugang zu den Daten und sieht das einfach als Array an. Und
das OS tut seinen Teil, die Daten an der richtigen Stelle im Speicher
auftauchen zu lassen. Speicherkopieren ist natürlich kein Vergleich zum
Plattenzugriff, aber allein die vereinfachte Programmierung hat was.
Gelesen wird natürlich mit Anlegen eines Mappings noch garnichts, erst
bei Zugriff werden die betroffenen Speicherseiten von der Platte geholt.
TK schrieb:> das mit for und do-while habe ich zwar noch nicht probiert - aber z.B.> ist ein SetFilePointer(..,FILE_BEGIN) auch schneller als ein> SetFilePointer(0x800,FILE_CURRENT) => merklich!
Mag ja sein, aber du sprachest von der Schleife. Und da ist es voellig
wurst ob du eine for, while, oder do-while schleife nimmst. Aber ja,
wenn da tatsaechlich merkliche unterschiede rauskommen, schmeiss den
Compiler weg und besorg dir einen vernueftigen.
Peter II schrieb:> wie groß war die Datei? Bei 1GB sind das 40Mbyte/s - das schafft man> kaum durch USB2.0
Mir kam die Geschwindigkeit auch etwas hoch vor. Von meinem alten PC bin
ich nur etwa 32MB/s gewohnt.
Die Dateigröße ist 1024^3+10+1 Byte = 1073741835 Byte. Sie setzt sich
aus 1Gi Nullen, dem String "0123456789" und einem LF am Ende zusammen.
Um sicher zu gehen, dass bei der Übertragung nicht geschummelt wird,
habe ich eine neue Datei erstellt, die statt der Nullen Zufallswerte
enthält. Den Rechner habe ich vor dem Test mitsamt der externen
Festplatte komplett aus- und wieder eingeschaltet, so dass sämtliche
Hardware- und Softwarepuffer gelöscht sein sollten. Die Zeiten sind
jetzt 27,6s für das Testprogramm und 27,3s für cat file >/dev/null.
Das wären aber immer noch 39MB/s.
Wo liegt denn die theoretische Grenze bei USB High Speed?
Aber wie auch immer: Es scheint auf jeden Fall möglich zu sein, selbst
mit einer langsamen Festplatte die vom TE gemessenen 45s deutlich zu
unterbieten, was darauf hindeutet, dass da irgendwo noch ein anderes
Problem ist.
Yalu X. schrieb:> Wo liegt denn die theoretische Grenze bei USB High Speed?
bei wiki steht was von 60Mbyte/s - im netzt findet man aber nur werte
zwischen 30 und 35Mbyte/s was ich auch kenne.
> Aber wie auch immer: Es scheint auf jeden Fall möglich zu sein, selbst> mit einer langsamen Festplatte die vom TE gemessenen 45s deutlich zu> unterbieten, was darauf hindeutet, dass da irgendwo noch ein anderes> Problem ist.
er schreibt das nebenbei auch in der Datei geschrieben wird. Lass doch
mal ein Prozess nebenbei Daten anfügen. Schon spielt die Zugriffszeit
eine entscheidende Rolle und sind bei den 45s.
fprintf(stderr,"Short read at %zx, ignoring this block!\n",i);
87
}
88
89
if(memcmp(buf,pattern,sizeof(pattern))==0){
90
printf("Pattern found at offset %0zx\n",i);
91
}
92
}
93
printf("read: %lu seconds\n",time(NULL)-t0);
94
95
close(fd);
96
}
Pattern found at offset 7ffff800
mmap: 19 seconds
Pattern found at offset 7ffff800
read: 18 seconds
Die getestete Datei ist ein 2 GiB großer Ausschnitt aus /dev/urandom,
das gesuchte Muster ist halt das, was an der letzten Vergleichsstelle in
der Datei zu finden war.
Test lief mit interner HD. Das Leeren der Caches benötigt root-Rechte,
es macht allerdings mit oder ohne keinen nennenswerten Unterschied.
EDIT:
Die mmap()-Variante ist einfach kürzer. Bei 32-Bit wird das so
allerdings nicht klappen, da muss dann auch mehrfach gemappt werden.
Außerdem hat mmap so seine Überaschungen, wenn z.B. ein anderer Prozess
die Datei inzwischen verkleinert hat (SIGBUS und tschüss).
flolix schrieb:> Du stoppst die Zeit (t0 = time(NULL);) erst NACH dem mmap Aufruf!
Recht du hast. Gerade mal noch einen Satz gettimeofday()s um mmap()
gebaut...mmap() braucht zwischen 5 und 6 µs.
Peter II schrieb:> Yalu X. schrieb:>> Wo liegt denn die theoretische Grenze bei USB High Speed?> bei wiki steht was von 60Mbyte/s - im netzt findet man aber nur werte> zwischen 30 und 35Mbyte/s was ich auch kenne.
Die 60MB/s sind die Bruttodatenrate (480Mbit/s). Im Vergleich zu
Ethernet u.ä. scheint das USB-Protokoll aber einen sehr großen Overhead
zu haben.
> er schreibt das nebenbei auch in der Datei geschrieben wird. Lass doch> mal ein Prozess nebenbei Daten anfügen. Schon spielt die Zugriffszeit> eine entscheidende Rolle und sind bei den 45s.
Ich habe ihn so verstanden, dass er erst nach der Suche beginnt, neue
Daten in die Datei zu schreiben.
Yalu X. schrieb:> Ich habe ihn so verstanden, dass er erst nach der Suche beginnt, neue> Daten in die Datei zu schreiben.
es scheint wohl ein 2.Prozess zu geben, der darin rumschreibt.
> FILE_SHARE_WRITE | FILE_SHARE_READ,
Peter II schrieb:> Yalu X. schrieb:>> Ich habe ihn so verstanden, dass er erst nach der Suche beginnt, neue>> Daten in die Datei zu schreiben.>> es scheint wohl ein 2.Prozess zu geben, der darin rumschreibt.>>> FILE_SHARE_WRITE | FILE_SHARE_READ,
Ja, wenn das tatsächlich so ist, braucht man nicht mehr weiter nach der
Bremse zu suchen.
Der TE schreibt allerdings auch:
TK schrieb:> Mit dem Code dauert es trotzdem noch ca. 45s auf meinem System, bis> eine Sequenz, die am Ende der Datei vorkommt, gefunden wird. Info: Die> Datei wird an dieser Stelle weiter bearbeitet. Daher auch der R/W> Zugriff auf die Datei.
Da die Datei "an dieser Stelle weiter bearbeitet" wird, schließe ich
daraus, dass die Suche abgeschlossen ist, bevor der erste Schreibzugriff
erfolgt.
TK schrieb:> Es läuft sonst nichts mehr nebenbei.
Vielleicht ist auch einfach nur seine Festplatte stark fragmentiert. Bei
meinen Tests war die externe Festplatte noch relativ leer, weswegen ich
davon ausgehe, dass die Gigabyte-Datei weitgehend zusammenhängend
abgelegt wurde.
Hallo zusammen,
ich komme kaum mit dem Mitlesen hinterher!
Nochmal zur Info:
Ich suche zuerst nach dem Muster, wenn ich es gefunden habe, schreibe
ich hinter diesem Muster etwas in die Datei. Mir geht es hauptsächlich
darum die Zeit für die Suche zu reduzieren! Momentan habe ich mich etwas
mit dem CreateFileMapping() und dem MapViewOfFile() beschäftigt.
Allerdings klappt das noch nicht so, wie es soll (AccessViolation).
Im übrigen habe ich die Zeit für eine 1GB-Datei OHNE Vorkommen der
Sequenz nochmals mit 47s gemessen (bei dem Code wie Anfangs angegeben).
Gut - die Festplatte kann durchaus stark fragmentiert - obwohl nur
halbvoll - sein, damit möchte ich mich jetzt nicht beschäftigen.
Gruß
TK
TK schrieb:> Im übrigen habe ich die Zeit für eine 1GB-Datei OHNE Vorkommen der> Sequenz nochmals mit 47s gemessen (bei dem Code wie Anfangs angegeben).> Gut - die Festplatte kann durchaus stark fragmentiert - obwohl nur> halbvoll - sein, damit möchte ich mich jetzt nicht beschäftigen.
solltest du aber.
wie lange dauert ein
copy Datei.ext NUL
TK schrieb:> Problem: Aus einer sehr großen Datei (ca.> 700MB..2GB)
Das ist nicht "sehr groß", das ist höchstens groß.
> muss eine 10Byte Sequenz gesucht werden. Diese kann> innerhalb der Datei entweder 0x,1x oder 2x auftreten. Die Sequenz kann> nur an Vielfachen von 0x800 Adr auftreten
Hilft garnix. Du musst die komplette Datei lesen. Und zwar sequentiell,
ohne nutzlose und sinnlos zeitfressende Seeks. Erst wenn das mögliche
Vorkommen der gesuchten Sequenz auf Vielfache von 0x2000 beschränkt
wäre, könnten Seeks vielleicht einen Vorteil bringen. Wahrscheinlich
liegt die Grenze aber noch viel höher, vielleicht so ca. bei 0x10000.
> if ((puffer[0] == 0) &&> (puffer[1] == 0x0815) &&> (puffer[2] == 0x4711) &&> (puffer[3] == 0xDEAD) &&> (puffer[4] == 0xFEED))
Das ist Mist. Auf modernen Maschinen kann man locker 128Bit am Stück
vergleichen. Und 16Bit-Zugriffe sind sogar schon seit Jahrzehnten
langsamer als nötig.
Allerdings: dieser Mist spielt wohl im Vergleich zum IO-Kram sowieso
keine nennenswerte Rolle, kann man also in diesem Fall wohl einfach so
lassen, wie es ist.
Wenn einer weiß, wie man eine solch große 2GB Ramdisk erzeugt, wäre das
auch eine Idee zur Beschleunigung. Allerdings ist D-RAM vergesslich,
sobald Strom weg ist!!!
oszi40 schrieb:> Wenn einer weiß, wie man eine solch große 2GB Ramdisk erzeugt, wäre das> auch eine Idee zur Beschleunigung. Allerdings ist D-RAM vergesslich,> sobald Strom weg ist!!!
auf so einen Computer?
> WIN-XP32 (AMD 3GHz DualCore).
Da ist eine 32GB SSD vermutlich einfacher.
oszi40 schrieb:> Wenn einer weiß, wie man eine solch große 2GB Ramdisk erzeugt, wäre das> auch eine Idee zur Beschleunigung. Allerdings ist D-RAM vergesslich,> sobald Strom weg ist!!!
mount -t tmpfs -o size=2G none /some/where
Aber...
Peter II schrieb:> auf so einen Computer?>> WIN-XP32 (AMD 3GHz DualCore).>> Da ist eine 32GB SSD vermutlich einfacher.
Ist natürlich die Frage, wiveiel RAM der hat. Bei mehr als 3 GiB wäre
ein Wechsel des OS ohnehin angebracht ;-)
> SSD vermutlich einfacher.
Stimmt und ist nicht so vergesslich. Fragt sich nur, ob es unbedingt
eine solch kleine 32GB sein muß, daß er sie bald gegen eine größere
tauschen wird. Eine schnelle SSD für das System beschleunigt alle
Prozesse, eine kleine NUR für diese ein Datei wäre rausgeschmissenes
Geld. Zur Orientierung :https://www.alternate.de/SSD
Etwas zur Suche auf unterster Ebene:
Wird die Sequenz 123456 gesucht und das erste Zeichen [0] ist 2, so
lohnt es nicht, noch die Zeichen Nummer [1]...[5] zu überprüfen.
Es hilft also wenn Du erst mal nur das erste Zeichen überprüfst und nur
in positivem Falle Dich mit den folgenden beschäftigst.
Amateur schrieb:> Wird die Sequenz 123456 gesucht und das erste Zeichen [0] ist 2, so> lohnt es nicht, noch die Zeichen Nummer [1]...[5] zu überprüfen.>> Es hilft also wenn Du erst mal nur das erste Zeichen überprüfst und nur> in positivem Falle Dich mit den folgenden beschäftigst.
das macht der Compiler schon selber. Im solche Kleinigkeiten muss man
sich nicht kümmern.
hi,
also ich verstehe nix von borlandpascal, aber ist das eine
lineare suche ???
wenn ja würde ich mal über einen sinnvollen suchalgo nachdenken
... datei in der mitte teilen und gleichzeitig nach vorn und hinten
suchen ... oder wenn das pattern nur im letzen drittel vorkommen kann,
brauchst du ja auch nur das letzte drittel durchsuchen ... sowas
in der art halt ... stichworte für google würde ich pattern matching
oder sowas in der art versuchen ...
guest0815 schrieb:> wenn ja würde ich mal über einen sinnvollen suchalgo nachdenken> ... datei in der mitte teilen und gleichzeitig nach vorn und hinten> suchen ... oder wenn das pattern nur im letzen drittel vorkommen kann,> brauchst du ja auch nur das letzte drittel durchsuchen ... sowas> in der art halt ... stichworte für google würde ich pattern matching> oder sowas in der art versuchen ...
und wenn er nicht weiß wo es steht (was zu vermuten ist, sonst würde er
nicht suchen)?
Und gleichzeitig auf einer normales Festplatte zu suchen ist das
langsamste was man machen kann, dann muss der Lesekopf ständig den
Sektor ändern.
Peter II schrieb:> Amateur schrieb:>> Per default?>> ja>> https://de.wikipedia.org/wiki/Kurzschlussauswertung
hm. ich weiß noch aus einer implementierung des lzw algorithmus zu
meiner schulzeit (~vor 25 jahren), das ein blankes "repz cmpsb"
langsamer war als die prüfung des ersten bytes auf übereinstimmung und
anschließender stringsuche.
aber da ging es auch nicht um feste adressen, sondern darum das gesamte
file byteoffset-weise nach strings zu durchsuchen.
So, ich habe jetzt mal CreateFileMapping() / MapViewOfFile()
implementiert und kann jetzt die Suche in einer 1GB Datei OHNE Vorkommen
der Sequenz von ursprünglich 47s auf jetzt 16s reduzieren. Das ist doch
mal ein Wort. Danke an Klaus Wachtler und die anderen, die den Hinweis
auf diese Funktionen gegeben haben.
Ich denke, für mich ist hiermit die Frage (und damit der Thread)
beantwortet.
Gruß
TK
FILE_FLAG_SEQUENTIAL_SCAN bei CreateFile als Hint mit angeben, könnte
ggf. auch nicht verkehrt sein:
"Specifying the FILE_FLAG_SEQUENTIAL_SCAN flag can increase performance
for applications that read large files using sequential access.
Performance gains can be even more noticeable for applications that read
large files mostly sequentially, but occasionally skip forward over
small ranges of bytes."
Hallo,
Was ist das für eine Datei?
Suchst du darin öfters?
Durch welche Prozesse wird die Datei verändert?
Auf was ich hinaus will, kann man die Datei nicht 1x lesen und sich
jeden 0x0800-sten Wert in eine extra Datei als Index schreiben?
Für mich hört sich das so an, als suchst du nach den Marker eines
Datenloggers o.ä.
Evtl beschreibst du dein Problem etwas über den Tellerrand hinaus, so
dass hier vielleicht noch der ein oder andere interessante Impuls kommt
Gruß
Roland