Ich habe ein Bash-Skript ausprobiert, aber es hat zu lange gedauert, eine einfache 1-MB-Datei zu erstellen. Ich denke, die Antwort liegt in der Verwendung von /dev/random
oder /dev/urandom
, aber in anderen Beiträgen wird nur gezeigt, wie man mit diesen Dingen alle Arten von Daten zu einer Datei hinzufügt, aber ich möchte nur Zahlen hinzufügen.
Gibt es einen Befehl, mit dem ich eine zufällige Datei mit einer Größe von 1 GB erstellen kann, die nur Zahlen zwischen 0 und 9 enthält?
Edit: Ich möchte, dass die Ausgabe so ähnlich ist
0 1 4 7 ..... 9
8 7 5 8 ..... 8
....
....
8 7 5 3 ..... 3
Der Bereich ist 0 - 9, was bedeutet, dass nur die Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8 und 9 verwendet werden. Außerdem müssen sie durch Leerzeichen getrennt sein und 100 pro Zeile, bis zur n
Anzahl der Zeilen. Dies ist mir egal, ich möchte, dass meine endgültige Größe 1 GB beträgt.
Edit: Ich benutze Ubuntu 16.04 LTS
yes 4 | tr '\n' ' ' | fold -w 200 | head -c1G
Antworten:
Dies ist aufgrund des Titels der Frage teilweise eine humoristische Antwort.
Wenn Sie nach "dem schnellsten Weg zu ..." suchen , ist die Antwort fast immer ein spezielles Werkzeug. Diese "Antworten" zeigen ein solches Tool, nur damit Sie experimentieren können.
Dies ist keine ernsthafte Antwort, da Sie sich nicht mit speziellen Tools für Aufgaben befassen sollten, die Sie nur einmal oder sehr selten ausführen. Sie werden am Ende mehr Zeit damit verbringen, nach Werkzeugen zu suchen und mehr darüber zu lernen, als Dinge zu tun. Muscheln und Hilfsprogramme mögen
bash
undawk
sind nicht die schnellsten, aber Sie können in der Regel einen Einzeiler schreiben , um den Auftrag zu erledigen, und dabei nur Sekunden verwenden. Bessere Skriptsprachen wieperl
können ebenfalls verwendet werden, obwohl die Lernkurve fürperl
steil ist, und ich zögere, sie für solche Zwecke zu empfehlen, da ich von schrecklichen Perl-Projekten traumatisiert bin.python
auf der anderen Seite ist es leicht behindert durch sein eher langsames I / O; Dies ist jedoch nur dann ein Problem, wenn Sie Gigabyte an Daten filtern oder generieren.In jedem Fall sollte das folgende C89-Beispielprogramm (das POSIX.1 nur für eine höhere Taktgenauigkeit verwendet, falls verfügbar) eine Generierungsrate von etwa 100 MB / s erreichen (getestet unter Linux auf einem Laptop mit einem Intel i5-4200U-Prozessor, der die Ausgabe weiterleitet) zu
/dev/null
), mit einem ziemlich guten Pseudozufallszahlengenerator. (Die Ausgabe sollte alle BigCrunch-Tests mit Ausnahme des MatrixRank-Tests bestehen, da der Code xorshift64 * und die Ausschlussmethode verwendet, um ein Verzerren der Ziffern zu vermeiden.)Dezimalstellen.c:
Wir können es viel schneller machen, wenn wir zu einem Zeilenpuffer wechseln, und zwar
fwrite()
einmal, anstatt jede Ziffer einzeln auszugeben. Beachten Sie, dass der Stream weiterhin vollständig gepuffert bleibt, um partielle Schreibvorgänge (ohne Zweierpotenz) zu vermeiden, wenn es sich bei der Ausgabe um ein Blockgerät handelt.Hinweis: Beide Beispiele wurden am 18.11.2016 bearbeitet, um eine gleichmäßige Verteilung der Ziffern zu gewährleisten (Null ist ausgeschlossen; siehe z. B. hier für Vergleiche und Details zu verschiedenen Pseudozufallszahlengeneratoren).
Kompilieren Sie zum Beispiel mit
und optional installieren systemweit
/usr/bin
mitEs werden die Anzahl der Stellen pro Zeile und die Anzahl der Zeilen verwendet. Weil
1000000000 / 100 / 2 = 5000000
(fünf Millionen; Gesamtbytes geteilt durch Spalten geteilt durch 2), können Sie verwendenum die
digits.txt
vom OP gewünschte Gigabyte-Größe zu erzeugen .Beachten Sie, dass das Programm selbst mehr auf Lesbarkeit als auf Effizienz ausgelegt ist. Ich möchte hier nicht die Effizienz des Codes demonstrieren - ich würde sowieso POSIX.1 und Low-Level-I / O anstelle von generischen C-Schnittstellen verwenden -, sondern Ihnen zeigen, welche Art von Balance es mit Aufwand gibt bei der Entwicklung dedizierter Tools im Vergleich zu ihrer Leistung im Vergleich zu Einzeiler- oder Short-Shell- oder awk-Scriptlets.
Bei Verwendung der GNU C-Bibliothek verursacht der Aufruf der
fputc()
Funktion für jede Zeichenausgabe einen sehr geringen Overhead (durch einen indirekten Funktionsaufruf oder durch Bedingungen - dieFILE
Schnittstelle ist tatsächlich ziemlich komplex und vielseitig, wie Sie sehen). Auf diesem bestimmten Intel Core i5-4200U-Laptop/dev/null
dauert die Umleitung der Ausgabe auf die erste (fputc) Version ungefähr 11 Sekunden, während die Version für eine einzelne Zeile nur 1,3 Sekunden dauert.Ich schreibe solche Programme und Generatoren oft nur, weil ich gerne mit riesigen Datensätzen spiele. Ich bin so komisch. Zum Beispiel habe ich einmal ein Programm geschrieben, um alle endlichen positiven IEEE-754-Gleitkommawerte in eine Textdatei zu drucken, mit ausreichender Genauigkeit, um genau den gleichen Wert zu erhalten, wenn sie analysiert werden. Die Datei hatte eine Größe von einigen Gigabyte (vielleicht 4 GB oder so); es gibt nicht so viele endliche positive
float
s, wie man meinen könnte. Ich habe dies verwendet, um Implementierungen zu vergleichen, die solche Daten lesen und analysieren.Für normale Anwendungsfälle wie das OP sind Shell-Skripte und Scriptlets und Einzeiler der bessere Ansatz. Weniger Zeitaufwand für die Ausführung der Gesamtaufgabe. (Außer, wenn sie jeden Tag eine andere Datei benötigen oder wenn es viele Menschen gibt, die eine andere Datei benötigen. In seltenen Fällen kann ein spezielles Tool wie oben den Aufwand rechtfertigen.)
quelle
mmap()
ist dies der einfachste Weg, um die beste E / A-Geschwindigkeit zu erreichen - aber vergleichen Sie dies, bevor Sie Ansprüche geltend machen!write()
, in der Regel schneller alsmmap()
.fwrite()
ist nicht viel langsamer. Ja, das habe ich gemessen (nur nicht für dieses Beispiel);write()
Bei großen Datenblöcken (262144, 524288 oder 1048576 Byte) ist die Leistung tendenziell höher als bei den anderen Methoden. Die Version derfputc()
in GNU C implementierten Bibliothek (die ich auch ausgiebig getestet habe) ist aus mehreren Gründen langsam. Insbesondere muss die Implementierung für jedes hinzugefügte Zeichen entweder bedingte Sprünge oder indirekte Aufrufe ausführen. Dieser geringfügige Mehraufwand summiert sich so oft./dev/null
. Das Scriptlet von Stéphane Chazelas dauert ungefähr 52 Sekunden. Perl-Snippet (einschließlich derhead
Filterung) ca. 58 Sekunden; Ihrshuf
Snippet (mit dem richtigen Timing; Sie messen nur die Shuf-Zeit, vorausgesetzt, die Paste dauert nicht länger) dauert ungefähr 69 Sekunden. Das C ++ 11-Programm von James Hollis dauert jeweils 14 Sekunden. Das obige Programm dauert 10 Sekunden.Diese:
(unter der Annahme einer
head
unterstützten Implementierung-c
) scheint auf meinem System relativ schnell zu sein.tr
Übersetzt den gesamten Byte-Bereich (0 bis 255, 0 bis 0377 in Oktal): Die 25 ersten Bytes als 0, die 25 nächsten als 1 ... 25 9 die restlichen (250 bis 255) zu "x", die wir dann Verwerfen Sie (mittr -d x
), da wir eine gleichmäßige Verteilung wünschen (vorausgesetzt, Sie/dev/urandom
haben selbst eine gleichmäßige Verteilung), und geben Sie daher einigen Ziffern keinen Bias.Das ergibt eine Ziffer für 97% der Bytes von
/dev/urandom
.fold -w 1
macht es eine Ziffer pro Zeile.paste -s
wird mit einer Liste von Trennzeichen aufgerufen, die aus 99 Leerzeichen und einem Zeilenumbruchzeichen besteht, sodass in jeder Zeile 100 durch Leerzeichen getrennte Ziffern stehen.head -c1G
erhält den ersten GiB (2 30 ) davon. Beachten Sie, dass die letzte Zeile abgeschnitten und nicht begrenzt wird. Sie können auf 2 30 -1 kürzen und die fehlende Zeile manuell hinzufügen oder auf 10 9 Bytes kürzen, was 50 Millionen dieser 200-Byte-Zeilen entspricht (dieshead -n 50000000
würde es auch zu einem Standard- / portablen Befehl machen).Diese Timings (erhalten von
zsh
einem Quad-Core-System) geben einen Hinweis darauf, wo die CPU-Zeit verbracht wird:Der erste
tr
ist der Flaschenhals, der die meiste Zeit im Kernel verbracht hat (ich nehme an, für die Zufallszahlengenerierung). Das Timing entspricht in etwa der Rate, mit der ich Bytes/dev/uramdom
abrufen kann (ca. 19MiB / s, und hier produzieren wir 2 Bytes für jeweils 0,97 Bytes von / dev / urandom mit einer Rate von 32MiB / s).fold
scheint eine unangemessene Menge an CPU-Zeit (15s) aufzuwenden, nur um nach jedem Byte ein Zeilenumbruchzeichen einzufügen, aber das wirkt sich nicht auf die Gesamtzeit aus, da es in meinem Fall auf einer anderen CPU funktioniert (durch Hinzufügen der-b
Option wird es geringfügig länger effizient,dd cbs=1 conv=unblock
scheint eine bessere Alternative zu sein).Sie können das
head -c1G
und das Rasieren für einige Sekunden aufheben, indem Sie die Dateigröße (limit filesize 1024m
mitzsh
oderulimit -f "$((1024*1024))"
mit den meisten anderen Shells (einschließlichzsh
)) in einer Subshell begrenzen.Das könnte verbessert werden, wenn wir 2 Ziffern für jedes Byte extrahieren würden, aber wir würden dafür einen anderen Ansatz benötigen. Das Obige ist sehr effizient, da
tr
nur jedes Byte in einem 256-Byte-Array nachgeschlagen wird. Dies kann nicht für 2 Bytes gleichzeitig durchgeführt werden, undhexdump -e '1/1 "%02u"'
die Berechnung der Textdarstellung eines Bytes mithilfe komplexerer Algorithmen wäre teurer als die Zufallszahlengenerierung. Wenn Sie jedoch wie in meinem Fall über CPU-Kerne verfügen, deren Zeit noch übrig ist, gelingt es möglicherweise noch, einige Sekunden zu sparen:Mit:
Ich bekomme (beachte jedoch, dass es hier 1.000.000.000 Bytes im Gegensatz zu 1.073.741.824 sind):
Insgesamt mehr CPU-Zeit, aber besser verteilt auf meine 4 CPU-Kerne, sodass weniger Zeit für die Wanduhr benötigt wird. Der Engpass ist jetzt
hexdump
.Wenn wir
dd
anstelle von zeilenbasiert arbeitenfold
, können wir den Arbeitsaufwand reduzierenhexdump
und die Arbeitsverteilung zwischen den CPUs verbessern:(hier unter der Annahme von GNU
dd
für seiniflag=fullblock
undstatus=none
), was ergibt:Zurück zur Zufallsgenerierung als Engpass.
Wie von @OleTange bereits erwähnt, können Sie mit diesem
openssl
Dienstprogramm einen schnelleren (insbesondere bei Prozessoren mit AES-Befehlen) Pseudozufallsgenerator für Bytes erstellen.auf meinem System spuckt 15 mal so viele Bytes pro Sekunde als
/dev/urandom
. (Ich kann nicht kommentieren, wie es in Bezug auf kryptografisch sichere Zufallsquellen verglichen wird, wenn dies auf Ihren Anwendungsfall zutrifft.)Jetzt gibt es:
zurück zum
hexdump
Flaschenhals.Da ich noch CPUs übrig habe, kann ich drei davon
hexdump
parallel betreiben .(das
<&3
wird für andere Shells alszsh
das close-Kommando stdin on / dev / null benötigt, wenn es im Hintergrund ausgeführt wird).Jetzt bis zu 6,2 Sekunden und meine CPUs fast voll ausgelastet.
quelle
perl
Variante entfernt, die sowieso deutlich langsamer war. Ich kann mit diesem tr | fold | paste-Ansatz keine 2 Stellen pro Byte erhalten.bc
die 0, 1 oder 2 höchstwertigen Ziffern verwenden.Wenn Sie
shuf
verfügbar sind (aktuelle GNU-Coreutils), können Sie dies tun:Auf meiner VM ist dies jetzt etwas langsamer als die Antwort von Stéphane, und zwar um einen Faktor von 3: 4.
quelle
shuf
auf meinem Firmen-PC hat nicht-r
,fmt
hat nicht-g
zupaste
/printf
trick - danke. Ihre Antwort ist jetzt anscheinend schneller.Wenn Sie keine Zufälligkeit mit sehr hoher Qualität benötigen und eine nahezu gleichmäßige Verteilung ausreichend ist, können Sie sehr schnell vorgehen, insbesondere auf einer modernen CPU mit effizienten SIMD-Ganzzahlvektoren wie x86 mit SSE2 oder AVX2.
Dies ist wie die Antwort von @ NominalAnimal, da wir beide die gleiche Idee hatten, aber manuell für x86 vektorisiert haben. (Und mit Zufallszahlen von schlechterer Qualität, aber wahrscheinlich immer noch gut genug für viele Anwendungsfälle.) Dies ist ungefähr 15- bis 30-mal schneller als der Code von @ Nominal, bei einer ASCII-Ausgabe von ~ 13 GB / s auf einem 2,5-GHz-Intel-Haswell CPU mit AVX2. Das ist immer noch weniger als die theoretische maximale Hauptspeicherbandbreite (Dual-Channel-DDR3-1600 ist ungefähr 25,6 GB / s), aber ich habe das Schreiben in / dev / null geplant, so dass nur ein Puffer neu geschrieben wird, der im Cache heiß bleibt. Skylake sollte denselben Code deutlich schneller ausführen als Haswell (siehe unten in dieser Antwort).
Vorausgesetzt, Sie haben tatsächlich irgendwo einen E / A-Engpass auf der Festplatte oder leiten diesen weiter, bedeutet eine schnelle Implementierung, dass Ihre CPU nicht einmal höher takten muss als im Leerlauf. Es verbraucht viel weniger Gesamtenergie, um das Ergebnis zu erzielen. (Batterielebensdauer / Hitze / globale Erwärmung.)
Dies ist so schnell, dass Sie es wahrscheinlich nicht auf die Festplatte schreiben möchten. Generieren Sie sie einfach nach Bedarf neu (aus demselben Startwert, wenn Sie dieselben Daten erneut benötigen ). Selbst wenn Sie es einem Multithread-Prozess zuführen möchten, der alle CPUs verwenden kann, wird es beim Ausführen dieses Befehls zum Weiterleiten der Daten im L3-Cache (und im L2-Cache auf dem Kern, der es geschrieben hat) heiß belassen und daher sehr häufig verwendet wenig CPU-Zeit. (Beachten Sie jedoch, dass das Piping im
/dev/null
Vergleich zum Schreiben viel Aufwand verursacht . Bei einem Skylake i7-6700k, das an einwc -c
anderes Programm weitergeleitet wird, das nur seine Eingabe liest und verwirft, ist es ungefähr 8x langsamer als das Schreiben an/dev/null
und verbraucht nur 70% von a CPU: Aber das sind immer noch 4,0 GB / s bei einer 3,9-GHz-CPU.Das erneute Generieren ist schneller als das erneute Lesen selbst von einer schnellen, mit PCIe verbundenen SSD, aber IDK, wenn es energieeffizienter ist (der Vektor-Integer-Multiplikator ist ziemlich beschäftigt und wahrscheinlich, zusammen mit anderen AVX2-Geräten, ziemlich leistungshungrig) 256b Vektor-ALUs). OTOH, ich weiß nicht, wie viel CPU-Zeit das Lesen von der Festplatte für etwas kostet, bei dem alle Kerne, die diese Eingabe verarbeiten, maximal waren. Ich würde vermuten, dass ein Kontextwechsel, der in 128k-Blöcken neu generiert wird, mit dem Ausführen von Dateisystem- / Pagecache-Code und dem Zuweisen von Seiten zum Lesen von Daten von der Festplatte konkurrieren kann. Wenn es im Pagecache bereits heiß ist, ist es natürlich nur im Grunde genommen memcpy. OTOH, wir schreiben schon so schnell wie memcpy! (was die Hauptspeicherbandbreite zwischen Lesen und Schreiben aufteilen muss). (Beachten Sie auch, dass das Schreiben in den Speicher, dass '
rep movsb
(optimiertes memcpy und memset im Mikrocode, das RFO vermeidet, seit Andy Glew es in P6 (Pentium Pro) implementiert hat ).Bisher ist dies nur ein Proof of Concept und das Newline-Handling ist nur annähernd korrekt. Es ist falsch um die Enden eines Potenz-2-Puffers. Mit mehr Entwicklungszeit. Ich bin zuversichtlich, dass ich einen effizienteren Weg finden könnte, um Zeilenumbrüche einzufügen, der auch genau richtig ist, mit mindestens so geringem Overhead (verglichen mit der Ausgabe nur von Leerzeichen). Ich denke, das sind ungefähr 10 bis 20%. Ich bin nur daran interessiert zu wissen, wie schnell wir diesen Lauf machen können, und nicht daran, eine polierte Version davon zu haben. Deshalb werde ich diesen Teil als Übung für den Leser mit Kommentaren belassen, in denen einige Ideen beschrieben werden.
Auf einem Haswell i5 mit 2,5 GHz maximalem Turbo und DDR3-1600 MHz RAM wurde die Erzeugung von 100 GiB zwar zeitlich festgelegt, aber verkleinert. (Zeitlich festgelegt auf cygwin64 unter Win10 mit gcc5.4
-O3 -march=native
, weggelassen,-funroll-loops
da es mir schon schwer genug fiel, auf diesem geliehenen Laptop anständige zeitliche Abläufe zu erzielen . Hätte nur Linux über USB booten sollen).Schreiben nach / dev / null, sofern nicht anders angegeben.
wc -c
mit 128 KB Puffergröße: 0,32 s bei einer CPU mit 2,38 GHz (maximaler Dual-Core-Turbo). (unskalierte Zeiten: real = 32.466s user = 11.468s sys = 41.092s, einschließlich dieser undwc
). Allerdings wurde nur die Hälfte der Daten tatsächlich kopiert, da mein albernes Programm davon ausgeht, dass write den vollen Puffer ausführt, obwohl dies nicht der Fall ist und cygwin write () nur 64k pro Aufruf in eine Pipe ausführt.Mit SSE2 ist dies ungefähr 15-mal schneller als der skalare Code von @Nominal Animal. Mit AVX2 ist es ungefähr 30-mal schneller. Ich habe nicht versucht , eine Version von Code der Nominal , die gerade verwendet
write()
stattfwrite()
, sondern vermutlich für große Puffer stdio meist aus dem Weg bleibt. Wenn die Daten kopiert werden, führt dies zu einer starken Verlangsamung.1 GB Daten auf einem Core2Duo E6600 (Merom 2,4 GHz, 32 KB privater L1, 4 MB gemeinsam genutzter L2-Caches), DDR2-533 MHz in 64-Bit-Linux 4.2 (Ubuntu 15.10). Diese Dimension wurde noch nicht untersucht, obwohl für write () eine Puffergröße von 128 KB verwendet wurde.
Schreiben nach / dev / null, sofern nicht anders angegeben.
wc -c
: 0,593 s (nicht skaliert: real = 59,266 s Benutzer = 20,148 s sys = 1 m 6,548 s, einschließlich der CPU-Zeit von wc). Die gleiche Anzahl von write () - Systemaufrufen wie bei cygwin, jedoch werden alle Daten per Piping übertragen, da Linux alle 128.000 write () -Aufrufe an eine Pipe verarbeitet.fwrite()
Version (gcc5.2-O3 -march=native
), ausgeführt mit./decdig 100 $((1024*1024*1024/200)) > /dev/null
: 3,19s +/- 0,1%, mit 1,40 Anweisungen pro Zyklus. -Funroll-Loops machten vielleicht einen winzigen Unterschied.clang-3.8 -O3 -march=native
: 3,42 s +/- 0,1%fwrite
anwc -c
: real = 3.980s user = 3.176s sys = 2.080sclang++-3.8 -O3 -march=native
): 22.885s +/- 0.07%, mit 0.84 Anweisungen pro Zyklus. (g ++ 5.2 war etwas langsamer: 22,98s). Das Schreiben von jeweils nur einer Zeile hat wahrscheinlich erheblich geschadet.tr < /dev/urandom | ...
: real = 41.430s user = 26.832s sys = 40.120s.tr
Ich habe die meiste Zeit den gesamten CPU-Kern auf sich gestellt und fast die gesamte Zeit im Kernel-Treiber verbracht, um zufällige Bytes zu generieren und sie in eine Pipe zu kopieren. Der andere Kern dieser Dual-Core-Maschine war der Rest der Pipeline.time LC_ALL=C head -c512M </dev/urandom >/dev/null
: dh nur so viel Zufall ohne Pipe lesen: real = 35.018s user = 0.036s sys = 34.940s.LANG=en_CA.UTF-8
real = 4m32.634s user = 4m3.288s sys = 0m29.364.LC_ALL=C LANG=C
: real = 4m18.637s user = 3m50.324s sys = 0m29.356s. Immer noch sehr langsam.dig3 = v%10
Schritt ist auf dieser HW ungefähr ausgeglichen): 0,166 s (1,82 Anweisungen pro Zyklus) . Dies ist im Grunde die Untergrenze für das, was wir mit einem perfekt effizienten Newline-Handling erreichen können.v%10
, 0,222 Sekunden +/- 0,4%, 2,12 Anweisungen pro Zyklus. (Kompiliert mit gcc5.2-march=native -O3 -funroll-loops
. Unroll-Schleifen helfen bei diesem Code auf dieser Hardware. Verwenden Sie ihn nicht blind, besonders bei großen Programmen.)Wie es gemacht wird
Ein schnelles PRNG ist offensichtlich unerlässlich. xorshift128 + kann vektorisiert werden, sodass Sie zwei oder vier 64-Bit-Generatoren parallel in Elementen eines SIMD-Vektors haben. Jeder Schritt erzeugt einen vollständigen Vektor von Zufallsbytes. ( 256b AVX2 Implementierung hier mit Intel Intrinsics ). Ich habe es wegen Nominals Wahl von xorshift * ausgewählt, da die 64-Bit-Vektor-Ganzzahl-Multiplikation nur in SSE2 / AVX2 mit Techniken mit erweiterter Genauigkeit möglich ist .
Bei einem Vektor aus zufälligen Bytes können wir jedes 16-Bit-Element in mehrere Dezimalstellen aufteilen. Wir erzeugen mehrere Vektoren von 16-Bit-Elementen, bei denen es sich jeweils um eine ASCII-Ziffer + einen ASCII-Raum handelt . Wir speichern das direkt in unserem Ausgabepuffer.
Meine ursprüngliche Version hat nur verwendet
x / 6554
, um eine zufällige Ziffer von jedem uint16_t-Element eines Vektors zu erhalten. Es ist immer zwischen 0 und 9, einschließlich. Es ist voreingenommen von9
, weil(2^16 -1 ) / 6554
es nur 9.99923 ist. (6554 = ceil ((2 ^ 16-1) / 10), wodurch sichergestellt wird, dass der Quotient immer <10 ist.)x/6554
kann mit einer Multiplikation mit einer "magischen" Konstante ( dem Festkomma-Kehrwert ) und einer Rechtsverschiebung des Ergebnisses der hohen Hälfte berechnet werden . Dies ist der beste Fall für die Division durch eine Konstante; Einige Divisoren nehmen mehr Operationen vor, und signierte Divisionen erfordern zusätzliche Arbeit.x % 10
hat eine ähnliche Tendenz und ist nicht so billig zu berechnen. (gcc ASM Ausgang entsprichtx - 10*(x/10)
, also eine zusätzliche Multiplikation und Subtraktion auf der Oberseite der Teilung eine modulare multiplikative Inverse verwendet.) Auch das niedrigste Bit der xorshift128 + ist nicht so hohe Qualität , so Dividieren Entropie aus High - Bits nehmen besser ( für Qualität sowie Geschwindigkeit) als Modulo, um Entropie von niedrigen Bits zu nehmen.Wir können jedoch mehr von der Entropie in jedem uint16_t verwenden, indem wir uns die niedrigen Dezimalstellen ansehen, wie z. B. die
digit()
Funktion von @ Nominal . Um die maximale Leistung zu erzielen, habe ich mich entschieden, die niedrigen 3 Dezimalstellen zu verwenden undx/6554
eine PMULLW und PSUBW (und wahrscheinlich einige MOVDQA) zu speichern, im Vergleich zu der Option mit der höheren Qualität, bei der die 4 niedrigen Dezimalstellen verwendet werden. x / 6554 wird geringfügig von den niedrigen 3 Dezimalstellen beeinflusst, sodass eine gewisse Korrelation zwischen den Stellen desselben Elements besteht (8- oder 16-stelliger Abstand in der ASCII-Ausgabe, abhängig von der Vektorbreite).Ich denke, dass gcc durch 100 und durch 1000 dividiert und nicht durch eine längere Kette, die nacheinander durch 10 dividiert wird, sodass die Länge der nicht durch Schleifen übertragenen Abhängigkeitskette, die 4 Ergebnisse aus jeder PRNG-Ausgabe erzeugt, wahrscheinlich nicht wesentlich verkürzt wird. port0 (Vektormultiplikation und -verschiebung) ist der Engpass aufgrund der modularen multiplikativen Inversen und der Verschiebungen in xorshift +, daher ist es definitiv nützlich, eine Vektormultiplikation zu speichern.
xorshift + ist so schnell, dass selbst die Verwendung von nur ~ 3,3 Bit Zufälligkeit von 16 (dh 20% Wirkungsgrad) nicht viel langsamer ist als das Zerlegen in mehrere Dezimalstellen. Wir nähern uns nur der gleichmäßigen Verteilung, da diese Antwort auf Geschwindigkeit ausgerichtet ist, solange die Qualität nicht zu schlecht ist.
Jede Art von bedingtem Verhalten, das eine variable Anzahl von Elementen beibehält, würde viel mehr Arbeit erfordern. (Könnte aber mit SIMD-Links-Packing-Techniken möglicherweise noch effizienter durchgeführt werden . Dies wird jedoch bei kleinen Elementgrößen weniger effizient. Riesen-Shuffle-Mask-Lookup-Tabellen sind nicht realisierbar und es gibt keine AVX2-Lane-Crossing-Shuffle mit weniger als 32-Bit.) Bit-Elemente: Eine 128-Bit-PSHUFB-Version kann mit BMI2 PEXT / PDEP zwar wie bei AVX2 mit größeren Elementen im laufenden Betrieb eine Maske generieren , dies ist jedoch schwierig, da eine 64-Bit-Ganzzahl nur 8 Byte enthält Zu dieser Antwort gibt es einen Code, der möglicherweise für höhere Elementzahlen geeignet ist.)
Wenn die Latenz des RNG ein Engpass ist, können wir noch schneller vorgehen, indem wir zwei Vektoren von Generatoren parallel schalten und abwechselnd den von uns verwendeten verwenden. Der Compiler kann immer noch problemlos alles in Registern in einer entrollten Schleife halten, wodurch die beiden Abhängigkeitsketten parallel ausgeführt werden können.
In der aktuellen Version, in der die PRNG-Ausgabe reduziert wird, besteht tatsächlich ein Engpass beim Durchsatz von Port 0, nicht bei der PRNG-Latenz, sodass dies nicht erforderlich ist.
Der Code: AVX2-Version
Vollversion mit weiteren Kommentaren zum Godbolt-Compiler-Explorer .
Nicht sehr aufgeräumt, sorry ich muss einschlafen und will das hier posten.
Um die SSE2 Version zu erhalten,
s/_mm256/_mm
,s/256/128/
,s/v16u/v8u/
, und ändernvector_size(32)
bis 16. Auch den Newline Schritt ändern von 4 * 16-4 * 8. (Wie gesagt, Code ist chaotisch und nicht für das Kompilieren von zwei Versionen geeignet. Eigentlich wollte ich keine AVX2-Version erstellen, aber dann wollte ich unbedingt eine Haswell-CPU testen, auf die ich Zugriff hatte.)Kompilieren Sie mit gcc, clang oder ICC (oder hoffentlich mit jedem anderen Compiler, der den GNU C-Dialekt von C99 und die Intelsics von Intel versteht). GNU C-Vektorerweiterungen sind äußerst praktisch, damit der Compiler die magischen Zahlen für Division / Modulo mit modularen multiplikativen Inversen generiert, und gelegentliche
__attribute__
s sind nützlich.Dies könnte portabel geschrieben werden, aber es würde mehr Code erfordern.
Leistungsmerkmale:
Der überlappende Speicher zum Einfügen von Zeilenumbrüchen ist mit erheblichem Aufwand verbunden, um zu entscheiden, wo er platziert werden soll (Verzweigungsfehler und Frontend-Engpässe bei Core2). Der Speicher selbst hat jedoch keine Auswirkungen auf die Leistung. Wenn Sie nur diese Speicheranweisung im Compiler asm auskommentieren (wobei alle Verzweigungen gleich bleiben), blieb die Leistung auf Core2 vollständig unverändert, und wiederholte Durchläufe gaben +/- weniger als 1% dieselbe Zeit. Daraus schließe ich, dass der Speicherpuffer / Cache das in Ordnung bringt.
Die Verwendung eines rotierenden Fensters
ascii_digitspace
mit einem Element, das einen Zeilenvorschub enthält, ist möglicherweise sogar noch schneller, wenn Sie das Fenster so weit ausrollen, dass alle Zähler / Verzweigungen verschwinden.Das Schreiben in / dev / null ist im Grunde genommen ein No-Op, daher bleibt der Puffer im L2-Cache wahrscheinlich heiß (256 KB pro Kern bei Haswell). Die perfekte Beschleunigung von 128b-Vektoren auf 256b-Vektoren wird erwartet: Es gibt keine zusätzlichen Anweisungen, und alles (einschließlich der Speicher) geschieht mit der doppelten Breite. Der Zweig zum Einfügen von Zeilenumbrüchen wird jedoch doppelt so häufig verwendet. Leider habe ich bei meinem Haswell Cygwin-Setup keine Zeit dafür gehabt, dass dieser Teil ausgefallen ist
#ifdef
.2,5 GHz * 32 B / 13,7 GB / s = 5,84 Zyklen pro AVX2-Speicher auf Haswell. Das ist ziemlich gut, könnte aber schneller sein. Vielleicht gibt es in den Cygwin-Systemaufrufen etwas Overhead, als ich dachte. Ich habe nicht versucht, diese in der asm-Ausgabe des Compilers zu kommentieren (was sicherstellen würde, dass nichts wegoptimiert wird.)
Der L1-Cache kann einen 32B-Speicher pro Takt unterstützen, und L2 weist keine wesentlich geringere Bandbreite auf (jedoch eine höhere Latenz).
Als ich mir IACA vor einigen Versionen ansah (ohne Verzweigung nach Zeilenumbrüchen, aber nur einen ASCII-Vektor pro RNG-Vektor), sagte es so etwas wie einen 32B-Vektorspeicher pro 4 oder 5 Takte voraus.
Ich hatte gehofft, durch das Extrahieren von mehr Daten aus jedem RNG-Ergebnis eine Beschleunigung zu erzielen, indem ich mir den Asm selbst ansah und die Anleitungen von Agner Fog und andere Optimierungsressourcen berücksichtigte, für die ich Links im SO x86-Tag-Wiki hinzugefügt habe .)
Auf Skylake wäre dies wahrscheinlich bedeutend schneller , da die Multiplikation und Verschiebung von Vektor-Ganzzahlen auf doppelt so vielen Ports (p0 / p1) ausgeführt werden kann wie bei Haswell (nur p0). Sowohl die Xorshift- als auch die Ziffernextraktion verwenden viele Verschiebungen und Multiplikationen. ( Update: Skylake führt es mit 3.02 IPC aus, was 3,77 Zyklen pro 32-Byte-AVX2-Speicher ergibt, zeitgesteuert mit 0.030s pro 1-GB-Iteration, und schreibt
/dev/null
auf Linux 4.15 auf i7-6700k mit 3.9GHz.Es ist kein 64-Bit-Modus erforderlich, um einwandfrei zu funktionieren . Die SSE2-Version ist beim Kompilieren genauso schnell
-m32
, da sie nicht sehr viele Vektorregister benötigt und die gesamte 64-Bit-Mathematik in Vektoren und nicht in Allzweckregistern ausgeführt wird.Im 32-Bit-Modus ist es auf Core2 sogar etwas schneller, da die Makrofusion von Compare / Branch nur im 32-Bit-Modus funktioniert. Daher gibt es weniger Uops für den nicht ordnungsgemäßen Core (18.3s (1.85 Instructions Per Clock) vs 16,9 s (2,0 IPC)). Die kleinere Codegröße ohne REX-Präfix hilft auch den Core2-Decodern.
Außerdem werden einige Reg-Reg-Vektorbewegungen durch Ladevorgänge ersetzt, da nicht mehr alle Konstanten in Vektorregs festgelegt sind. Da der Ladedurchsatz aus dem L1-Cache kein Engpass ist, hilft dies tatsächlich. (z. B. Multiplikation mit einem konstanten Vektor von
set1(10)
:movdqa xmm0, xmm10
/pmullw xmm0, xmm1
wird zumovdqa xmm0, [constant]
/pmullw xmm0, xmm1
.) Da für reg-reg MOVDQA ein ALU-Port erforderlich ist, konkurriert es mit der tatsächlich ausgeführten Arbeit, aber ein MOVDQA-Ladevorgang konkurriert nur um die Front-End-Dekodierungsbandbreite. (Wenn eine 4-Byte-Adresse in vielen Befehlen enthalten ist, wird ein Großteil des Gewinns durch das Speichern von REX-Präfixen aufgehoben.Es würde mich nicht wundern, wenn beim Speichern von ALU MOVDQA-Ups die eigentlichen Gewinne erzielt werden, da das Frontend mit dem Durchschnitt von 2,0 IPC ziemlich gut mithalten sollte.
Alle diese Unterschiede verschwinden in Haswell, wo das Ganze vom decodierten UOP-Cache ausgeführt werden sollte, wenn nicht vom Loopback-Puffer. ALU + Branch Macro-Fusion funktioniert seit Nehalem in beiden Modi.
quelle
Hier ist eine Lösung, von der ich hoffe, dass sie einfach zu verstehen ist:
od
Erstellt einen einheitlichen Stream von hexadezimalen Ziffern aus/dev/random
.tr
Befreit sich von Buchstaben und behält nur0-9
Ziffernfold
Stellt sicher, dass 100 Stellen pro Zeile vorhanden sindawk
fügt Leerzeichen in Zeilen einhead
verkürzt die Eingabe auf 1 Gigabytequelle
Sie können den
jot
Befehl dazu verwenden:quelle
fmt
hat keine Zielbreitenoption . Wie auch immer, es wird genau sein, da alle Ziffern genau eine Spalte einnehmen!fmt
Versionfmt (GNU coreutils) 8.25
(Ubuntu 16.04)536870912
Dies ähnelt der Methode von Stéphane Chazelas, allerdings lese ich 64 Bit auf einmal, um die Leistung zu verbessern. Die Verteilung ist immer noch einheitlich, aber jetzt erhalten Sie 19 Ziffern für jeweils 8 Bytes anstelle von nur 8 im besten Fall wie zuvor
Auf 32-Bit-Plattformen werden statt 19 jedes Mal 9 Ziffern gelesen.
quelle
perl
nicht mit Quad-Unterstützung kompiliert ist.next if $n >= 1000000000; $s = sprintf("%09u", $n);
, um nur 9 Ziffern zu erhalten$n = unpack("Q")
wenn Quad nicht unterstützt wird.BEGIN{$/=\4; $,=" "} $n = unpack("L");
auch<16e18
und durch 16 teilen, erhalten Sie 18 Stellen mit 86,7% für 1,95 dpB. Mit 32bit<4e9 /4
erhält man 9 Stellen 93,1% für 2,10 dpB. Aber 5 Bytes (als Hex (H10))<1e12
ergeben 12 Ziffern 90,9% für 2,18 dpB, oder das Hex in zwei Hälften teilen und jede Hälfte<1e6
ergibt 6 Ziffern 95,4% für 2,29 dpB; Dies nähert sich der Grenze von log_10 (256) = 2,41.Ich bin mit Nominal Animal einverstanden, eine kompilierte Programmiersprache zu verwenden, wenn Sie Geschwindigkeit benötigen. Sie müssen jedoch keinen eigenen RNG-Code in C schreiben. C ++ 11 bietet den exzellenten Mersenne Twister als Teil seiner Standardbibliothek.
Der obige Code ist einigermaßen einfach und dauert ungefähr eine Minute, wenn ich die Ausgabe in eine Datei leite. Wir können viel schneller vorgehen, indem wir einen String erstellen, der groß genug für 100 Ziffern ist, und die Ziffern hineinhacken. Auf diese Weise können wir jede Zeile und nicht jede Ziffer aufrufen.
Dieser Code benötigt meine Maschine ungefähr sechs Sekunden. Denken Sie daran, dass es sich um eine Standardausgabe handelt, und leiten Sie sie an eine Datei weiter.
Ich habe ein paar Haftungsausschlüsse. Zunächst schreibe ich dies auf einem Windows-PC. Ich denke, dass die Bibliotheken unter Linux alle vorhanden sind, aber wenn ich mich irre, sei darauf hingewiesen.
Außerdem werden genau eine halbe Milliarde durch Leerzeichen getrennte Ziffern ausgegeben, was technisch gesehen ein Gigabyte ist, aber vielleicht nicht genau das, was Sie wollten. Es gibt 5 Millionen Zeilen mit 100 Stellen pro Zeile aus. Wenn der Unterschied wichtig ist, können Sie die Anzahl der Zeilen erhöhen. Auf meiner Windows-Box scheint die Datei etwas größer als 10 ^ 9 Bytes zu sein, was meiner Meinung nach mit zusätzlichen Zeilenumbrüchen zu tun hat.
quelle
/dev/null
die weitaus schneller als das Schreiben in eine echte Datei wärewrite()
Systemaufruf ist ein Memcpy in den Pagecache, der nur blockiert, wenn der Kernel dies beschließt, anstatt mehr Pufferplatz zuzuweisen. Dieses Programm sollte nur dann einen Engpass bei Festplatten-E / A verursachen, wenn der Speicher knapp ist oder wenn Sie O_DIRECT zum Umgehen des Pagecaches verwendet haben. Wenn Siewrite()
Teile haben, die kleiner als der Cache sind, werden Ihre Daten hoffentlich nur einmal im Hauptspeicher abgelegt, und der neu geschriebene Puffer bleibt im L2- oder L3-Cache aktiv.Dies hängt von Ihrer Definition von "zufällig" ab. Wenn Sie kryptografisch zufällig meinen, müssen Sie nur eine gute Bibliothek besorgen und die Kugel beißen, und warten, bis sie ausgeführt wird.
Wenn Sie nur etwas benötigen, das ziemlich zufällig aussieht, haben Sie hier eine einfache Möglichkeit:
Die Ausführung auf einem langsamen Computer kann eine Stunde dauern. schnell genug und zufällig genug für die meisten Zwecke.
quelle
/dev/urandom
ist wahrscheinlich besser alsgzip
, sowohl in der Geschwindigkeit als auch in der Zufälligkeit.Get a file that is several Gb long
Sie benötigen eine Datei ** mit mindestens 8 GB, um eine 1-GB-Datei zu erhaltenquelle
cat file | tr
wenn du nur kannsttr <file
. IIRC können Sie sogar<file tr
. Ich dachte, Sie sprechen nur über dieses Shell-Skript, das klobig und langsam aussieht, wiedu | awk
nach jeder Zeile, um die Größe zu überprüfen, und öffnen die Datei erneut, um jede Zeile anzuhängen, anstatt sie außerhalb der Schleife umzuleiten.cat /dev/urandom | busy-cmd
ist einer der seltenen Fälle, in denen es sinnvoll sein kann, die zufällige Generierung und den ausgelasteten Cmd zwischen Prozessoren aufzuteilen. Nicht so sehr für tr, aber es macht zum Beispiel einen Unterschied für Sam'sod
.