J'ai essayé un script bash, mais la création d'un fichier simple de 1 Mo a pris trop de temps. Je pense que la réponse réside dans l’utilisation de /dev/random
ou /dev/urandom
, mais d’autres publications n’expliquent que l’ajout de toutes sortes de données à un fichier à l’aide de ces éléments, mais j’aimerais n’ajouter que des chiffres.
Alors, y a-t-il une commande que je peux utiliser pour créer un fichier aléatoire de taille 1 Go contenant uniquement des nombres compris entre 0 et 9?
Edit: je veux que la sortie soit quelque chose comme ça
0 1 4 7 ..... 9
8 7 5 8 ..... 8
....
....
8 7 5 3 ..... 3
La plage est comprise entre 0 et 9, ce qui signifie uniquement les chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9. Ils doivent également être séparés par un espace et être égaux à 100 par ligne, jusqu'au n
nombre de lignes. C’est quelque chose qui m’importe peu, je veux que ma taille finale soit de 1 Go.
Edit: J'utilise Ubuntu 16.04 LTS
yes 4 | tr '\n' ' ' | fold -w 200 | head -c1G
Réponses:
C'est en partie une réponse ironique, à cause du titre de la question.
Lorsque vous recherchez "le moyen le plus rapide de ..." , la réponse est presque toujours un outil spécialisé. Cela "réponses" montre un tel outil, juste pour que vous puissiez expérimenter.
Ce n'est pas une réponse sérieuse, car vous ne devriez pas rechercher d'outils spécialisés pour des tâches que vous ne faites qu'une fois ou très rarement. Vous verrez que vous finirez par passer plus de temps à chercher des outils et à en apprendre davantage sur eux que de faire des choses réellement. Les coquilles et les utilitaires n’apprécient pas
bash
etawk
ne sont pas les plus rapides, mais vous pouvez généralement écrire une seule ligne pour accomplir le travail, en ne dépensant que quelques secondes. Onperl
peut également utiliser de meilleurs langages de script , bien que la courbe d'apprentissageperl
soit raide, et j'hésite à le recommander, car j'ai été traumatisée par de terribles projets Perl.python
par contre est légèrement handicapé par ses entrées / sorties plutôt lentes; ce n'est toutefois un problème que lorsque vous filtrez ou générez des giga-octets de données.Dans tous les cas, l’exemple de programme C89 suivant (qui utilise POSIX.1 pour une horloge de précision supérieure uniquement si disponible) devrait atteindre un taux de génération d’environ 100 Mo / s (testé sous Linux sur un ordinateur portable doté d’un processeur Intel i5-4200U, en transférant la à
/dev/null
), en utilisant un assez bon générateur de nombres pseudo-aléatoires. (La sortie doit réussir tous les tests BigCrunch, à l'exception du test MatrixRank, car le code utilise xorshift64 * et la méthode d'exclusion pour éviter de biaiser les chiffres.)chiffres décimaux.c:
Nous pouvons faire beaucoup plus rapidement si nous passons à une mémoire tampon de ligne, et
fwrite()
cela une fois au lieu de produire chaque chiffre à la fois. Notez que nous continuons de garder le flux entièrement mis en mémoire tampon pour éviter les écritures partielles (sans alimentation sur deux) si la sortie est un périphérique en mode bloc.Remarque: les deux exemples ont été édités le 18/11/2016 pour assurer une distribution uniforme des chiffres (zéro est exclu; voir par exemple ici pour une comparaison et des détails sur divers générateurs de nombres pseudo-aléatoires).
Compiler en utilisant par exemple
et éventuellement installer à l'échelle du système à l'
/usr/bin
aideIl faut le nombre de chiffres par ligne et le nombre de lignes. Parce que
1000000000 / 100 / 2 = 5000000
(cinq millions; total d'octets divisé par colonnes divisé par 2), vous pouvez utilisergénérer le gigaoctet
digits.txt
souhaité par l’opérateur.Notez que le programme lui-même est écrit avec plus de lisibilité que d’efficacité. Mon intention ici n'est pas de montrer l'efficacité du code - j'utiliserais de toute façon POSIX.1 et les E / S de bas niveau, plutôt que les interfaces C génériques - mais de vous permettre de voir facilement quel type d'équilibre existe avec les efforts déployés en développant des outils dédiés par rapport à leurs performances, par rapport à des monolithes, des scripts courts shell ou awk
En utilisant la bibliothèque GNU C, l'appel de la
fputc()
fonction pour chaque sortie de caractère entraîne une très petite surcharge (d'un appel de fonction indirect ou conditionnel - l'FILE
interface est en fait assez complexe et polyvalente, vous voyez). Sur cet ordinateur portable Intel Core i5-4200U/dev/null
, la première version (fputc) prend environ 11 secondes pour être redirigée vers la sortie , tandis que la version ligne à la fois ne prend que 1,3 seconde.J'écris souvent de tels programmes et générateurs uniquement parce que j'aime jouer avec d'énormes jeux de données. Je suis bizarre comme ça. Par exemple, j’ai un jour écrit un programme pour imprimer toutes les valeurs à virgule flottante IEEE-754 positives finies dans un fichier texte, avec une précision suffisante pour obtenir la même valeur lors de l’analyse. La taille du fichier était de quelques gigaoctets (peut-être 4G environ); il n'y a pas autant de
float
s positifs finis qu'on pourrait le penser. Je l'ai utilisé pour comparer les implémentations qui lisent et analysent ces données.Pour les cas d'utilisation normale, comme dans le cas du PO, les scripts shell, les scriptlets et les one-liners constituent la meilleure approche. Moins de temps passé pour accomplir la tâche globale. (Sauf s'ils ont besoin d'un fichier différent chaque jour ou à peu près, ou s'il y a beaucoup de personnes qui ont besoin d'un fichier différent, dans lequel - rarement - un outil dédié comme ci-dessus pourrait justifier l'effort consenti.)
la source
mmap()
le moyen le plus simple d’atteindre la meilleure vitesse d’E / S - mais une référence avant de faire des déclarations!write()
, sont généralement plus rapides quemmap()
.fwrite()
n'est pas beaucoup plus lent. Oui, j'ai comparé cela (mais pas pour cet exemple particulier);write()
en gros morceaux (262144, 524288 ou 1048576 octets) a tendance à surperformer les autres méthodes. La version defputc()
mise en œuvre dans la bibliothèque GNU C (que j'ai également analysée de manière approfondie) est lente pour un certain nombre de raisons; en particulier, l'implémentation doit faire des sauts conditionnels ou des appels indirects pour chaque caractère ajouté; cette légère surcharge générée si souvent s'additionne./dev/null
. Le scriptlet de Stéphane Chazelas prend environ 52 secondes; perl snippet (y compris lehead
filtrage) environ 58 secondes; votreshuf
extrait (avec le bon timing; vous ne mesurez que le temps shuf, en supposant que la pâte ne prendra pas plus longtemps) prend environ 69 secondes. Le programme C ++ 11 de James Hollis, une ligne à la fois, prend 14 secondes. Le programme ci-dessus prend 10 secondes.Cette:
(en supposant une
head
mise en œuvre qui prend en charge-c
) semble être assez rapide sur mon système.tr
traduit la plage d'octets entière (0 à 255, 0 à 0377 en octal): les 25 premiers octets sont 0, les 25 suivants en tant que 1 ... puis 25 9 le reste (250 à 255) en "x", puis éliminez (avectr -d x
) car nous voulons une distribution uniforme (en supposant qu’elle/dev/urandom
ait une distribution uniforme elle-même) et ne donnons donc pas un biais à certains chiffres.Cela produit un chiffre pour 97% des octets de
/dev/urandom
.fold -w 1
en fait un chiffre par ligne.paste -s
est appelé avec une liste de séparateurs qui se compose de 99 caractères d'espacement et d'un caractère de nouvelle ligne, afin d'avoir 100 chiffres séparés par des espaces sur chaque ligne.head -c1G
obtiendra le premier GiB (2 30 ) de cela. Notez que la dernière ligne sera tronquée et non délimitée. Vous pouvez tronquer à 2 30 -1 et ajouter manuellement la nouvelle ligne manquante, ou tronquer à 10 9 octets, ce qui représente 50 millions de ces lignes de 200 octets (enhead -n 50000000
ferait également une commande standard / portable).Ces temporisations (obtenues par
zsh
un système à quatre coeurs) donnent une indication de l'endroit où le temps CPU est utilisé:Le premier
tr
est le goulot d'étranglement, la plupart du temps passé dans le noyau (je suppose pour la génération de nombres aléatoires). Le timing correspond approximativement au débit auquel je peux obtenir des octets/dev/uramdom
(environ 19 Mo / s et nous produisons ici 2 octets pour chaque 0,97 octet de / dev / urandom à un débit de 32 Mo / s).fold
semble dépenser une quantité déraisonnable de temps processeur (15s) juste pour insérer un caractère de nouvelle ligne après chaque octet, mais cela n’affecte pas le temps total car il fonctionne sur un processeur différent dans mon cas (ajouter l’-b
option le rend très légèrement plus efficace,dd cbs=1 conv=unblock
semble être une meilleure alternative).Vous pouvez vous en passer
head -c1G
et gagner quelques secondes en définissant une limite de taille de fichier (limit filesize 1024m
aveczsh
ouulimit -f "$((1024*1024))"
avec la plupart des autres shells (y compriszsh
)) à la place dans un sous-shell.Cela pourrait être amélioré si nous extrayions 2 chiffres pour chaque octet, mais nous aurions besoin d'une approche différente pour cela. Ce qui précède est très efficace car il
tr
suffit de rechercher chaque octet dans un tableau de 256 octets. Cela ne peut pas être fait pendant 2 octets à la fois, et utiliser de telles choseshexdump -e '1/1 "%02u"'
pour calculer la représentation textuelle d'un octet en utilisant des algorithmes plus complexes serait plus coûteux que la génération de nombres aléatoires elle-même. Néanmoins, si, comme dans mon cas, vous avez des cœurs de processeur dont le temps est compté, il peut encore arriver à gagner quelques secondes:Avec:
Je reçois (notez cependant qu'il s'agit ici de 1 000 000 000 d'octets, par opposition à 1 073 741 824):
Globalement, plus de temps processeur, mais mieux réparti entre mes 4 cœurs de processeurs, le temps de travail est donc réduit. Le goulot d'étranglement est maintenant
hexdump
.Si nous utilisons
dd
au lieu de la lignefold
, nous pouvons réellement réduire la quantité de travailhexdump
à faire et améliorer l'équilibre du travail entre les processeurs:(en supposant ici que GNU est
dd
soniflag=fullblock
etstatus=none
) ce qui donne:Retour à la génération de nombres aléatoires étant le goulot d'étranglement.
Maintenant, comme l'a souligné @OleTange, si vous avez l'
openssl
utilitaire, vous pouvez l'utiliser pour obtenir un générateur d'octets pseudo-aléatoire plus rapide (en particulier sur les processeurs dotés d'instructions AES).sur mon système génère 15 fois plus d'octets par seconde que
/dev/urandom
. (Je ne peux pas dire comment cela se compare en termes de source aléatoire d'aléas sécurisée par cryptographie si cela s'applique à votre cas d'utilisation).Donne maintenant:
Retour à
hexdump
être le goulot d'étranglement.Comme il me reste encore des processeurs, je peux en exécuter 3
hexdump
en parallèle.(le
<&3
est nécessaire pour les shells autres que leszsh
commandes stdin sur / dev / null des commandes de fermeture lorsqu'il est exécuté en arrière-plan).Maintenant, à 6,2 secondes et mes processeurs presque pleinement utilisés.
la source
perl
variante qui était nettement plus lente de toute façon. Je ne peux pas obtenir 2 chiffres par octet avec cette approche tr | fold | paste.bc
(laissez tomber les 0, 1 ou les 2 chiffres les plus significatifs).Si vous avez à
shuf
disposition (récemment, GNU coreutils en a), vous pouvez le faire:Sur ma machine virtuelle, cela est maintenant un peu plus lent que la réponse de Stéphane d'environ 3: 4.
la source
shuf
sur mon entreprise PC n'a pas-r
,fmt
n'a pas-g
troppaste
/printf
astuce - merci. Votre réponse est maintenant apparemment plus rapide.Si vous n'avez pas besoin d'aléatoire de très haute qualité et que la distribution presque uniforme convient, vous pouvez aller très vite, en particulier sur un processeur moderne doté de vecteurs entiers SIMD efficaces tels que x86 avec SSE2 ou AVX2.
Cela ressemble à la réponse de @ NominalAnimal puisque nous avions tous deux la même idée, mais vectorisés manuellement pour x86. (Et avec des nombres aléatoires de qualité médiocre, mais toujours suffisants pour de nombreux cas d'utilisation.) Cela s'exécute environ 15 ou 30 fois plus rapidement que le code de @ Nominal, à environ 13 Go / s de sortie ASCII sur un Intel Haswell cadencé à 2,5 GHz. CPU avec AVX2. C’est toujours moins que la bande passante maximale théorique de la mémoire principale (la DDR3-1600 à double canal est d’environ 25,6 Go / s), mais j’étais en train d’écrire sur / dev / null; Skylake devrait exécuter ce même code considérablement plus rapidement que Haswell (voir le bas de cette réponse).
En supposant que vous ayez un goulot d’étranglement sur les entrées / sorties sur le disque ou sur une tuyauterie quelque part, une implémentation rapide signifie que votre processeur n’a même pas besoin d’être plus rapide qu’au ralenti. Il utilise beaucoup moins d'énergie totale pour produire le résultat. (Vie de la batterie / chaleur / réchauffement climatique.)
C'est tellement rapide que vous ne voulez probablement pas l'écrire sur le disque. Il suffit de générer de nouveau au besoin (à partir de la même graine si vous voulez à nouveau les mêmes données). Même si vous souhaitez le transmettre à un processus multithread pouvant utiliser tous les processeurs, son exécution pour y diriger les données le laissera chaud dans le cache L3 (et le cache L2 du noyau qui l'a écrit), et peu de temps processeur. (Mais notez que la tuyauterie ajoute beaucoup de frais généraux par rapport à l’écriture
/dev/null
. Sur un Skylake i7-6700k, la tuyauterie verswc -c
ou un autre programme qui lit juste + supprime son entrée, c’est environ 8 fois plus lent que l’écriture/dev/null
, et n’utilise que 70% CPU, mais cela reste 4,0 Go / s sur un processeur 3.9GHz.La régénérer est plus rapide que de le relire même à partir d'un SSD rapide connecté par PCIe, mais un IDK s'il est plus économe en énergie (le multiplicateur de vecteur entier est assez occupé et il est probablement très gourmand en énergie, avec d'autres AVX2 256b ALU vectorielles). OTOH, je ne sais pas combien de temps CPU lire sur un disque enlèverait quelque chose qui dépassait tous les cœurs traitant cette entrée. J'imagine qu'un changement de contexte pour générer de nouveau des morceaux de 128 Ko pourrait être concurrentiel avec le code de système de fichiers / pagecache en cours d'exécution et l'allocation de pages pour la lecture de données à partir du disque. Bien sûr, si il fait déjà chaud dans la pagecache, c’est tout simplement mémorable. OTOH, nous écrivons déjà à peu près aussi vite que memcpy! (qui doit partager la bande passante de la mémoire principale entre la lecture et l’écriture). (Notez également que l'écriture en mémoire que '
rep movsb
(optimisé memcpy et memset dans le microcode, ce qui évite les RFO, puisque Andy Glew l’a implémenté dans P6 (Pentium Pro )).Jusqu'à présent, il ne s'agit que d'une preuve de concept et la gestion de la nouvelle ligne n'est qu'approximativement correcte. C'est faux autour des extrémités d'un tampon de puissance de 2. Avec plus de temps de développement. Je suis convaincu que je pourrais trouver un moyen plus efficace d'insérer des nouvelles lignes tout à fait corrects, avec des frais généraux au moins aussi faibles que cela (par rapport à la sortie d'espaces uniquement). Je pense que c'est quelque chose comme 10 à 20%. Je voudrais seulement savoir à quelle vitesse nous pourrions faire cela, et non pas en avoir une version perfectionnée. Je laisserai donc cette partie comme un exercice pour le lecteur, avec des commentaires décrivant certaines idées.
Sur un Haswell i5 à son turbo maxi de 2,5 GHz, avec une RAM DDR3-1600 MHz , chronométré à 100 GiB mais réduit. (Chronométré sur cygwin64 sur Win10 avec gcc5.4
-O3 -march=native
, omis-funroll-loops
car j'avais assez de mal à obtenir un timing correct sur cet ordinateur portable emprunté. Il aurait fallu démarrer Linux sur une clé USB).écrire dans / dev / null sauf indication contraire.
wc -c
, avec une taille de mémoire tampon de 128 Ko: 0,32 seconde avec un processeur à 2,38 GHz (turbo dual-core max). (Temps non mis à l'échelle: réel = 32.466s utilisateur = 11.468s sys = 41.092s, y compris ceci etwc
). Cependant, seulement la moitié des données ont été copiées, car mon programme idiot suppose que l’écriture remplit la totalité du tampon, même si ce n’est pas le cas et que cygwin write () ne produit que 64k par appel dans un tube.Donc, avec SSE2, il est environ 15 fois plus rapide que le code scalaire de @Nominal Animal. Avec AVX2, c'est environ 30 fois plus rapide. Je n'ai pas essayé une version du code de Nominal qui utilise simplement
write()
au lieu defwrite()
, mais vraisemblablement pour les grands tampons, stdio reste généralement à l'écart. S'il s'agit de copier les données, cela entraînerait beaucoup de ralentissement.Il est temps de produire 1 Go de données sur un Core2Duo E6600 (caches Merom 2,4 GHz, L1 privé 32 koB, caches L2 partagés 4 Mo), DDR2-533 MHz sous Linux 4.2 64 bits (Ubuntu 15.10). Toujours en utilisant une taille de tampon de 128kiB pour write (), je n’ai pas exploré cette dimension.
écrire dans / dev / null sauf indication contraire.
wc -c
: 0.593s (non mis à l'échelle: real = 59.266s utilisateur = 20.148s sys = 1m6.548s, temps de calcul de wc compris). Même nombre d'appels système write () que pour cygwin, mais en réalité, canalisation de toutes les données, car Linux gère tous les 128k d'un write () vers un canal.fwrite()
version de NominalAnimal (gcc5.2-O3 -march=native
), fonctionnant avec./decdig 100 $((1024*1024*1024/200)) > /dev/null
: 3.19s +/- 0.1%, avec 1,40 instruction par cycle. Les boucles de compression ont peut-être fait une petite différence.clang-3.8 -O3 -march=native
: 3.42s ± 0.1%fwrite
àwc -c
: real = utilisateur 3.980 = 3.176s sys = 2.080sclang++-3.8 -O3 -march=native
): 22.885s +/- 0.07%, avec 0.84 instructions par cycle. (g ++ 5,2 était légèrement plus lent: 22,98s). Écrire une ligne à la fois a probablement fait très mal.tr < /dev/urandom | ...
: real = 41.430s user = 26.832s sys = 40.120s.tr
La plupart du temps, la totalité du cœur de la CPU était occupée par lui-même, passant presque tout son temps dans le pilote du noyau à générer des octets aléatoires et à les copier dans un canal. L'autre cœur de cette machine double cœur exécutait le reste du pipeline.time LC_ALL=C head -c512M </dev/urandom >/dev/null
: c'est- à- dire en train de lire autant d'aléas sans tuyauterie: 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. Toujours très lent.dig3 = v%10
étape concerne le seuil de rentabilité sur ce matériel): 0,166 (1,82 instructions par cycle) . C’est fondamentalement la limite inférieure de ce que nous pouvons approcher avec une manipulation de nouvelle ligne parfaitement efficace.v%10
, 0.222 secondes +/- 0,4%, 2.12 instructions par cycle. (Compilé avec gcc5.2, les-march=native -O3 -funroll-loops
boucles de déroulage peuvent aider pour ce code sur ce matériel. Ne l'utilisez pas aveuglément, en particulier pour les gros programmes).Comment c'est fait
Un PRNG rapide est évidemment essentiel. xorshift128 + peut être vectorisé, vous avez donc deux ou quatre générateurs 64 bits en parallèle, dans des éléments d’un vecteur SIMD. Chaque étape produit un vecteur complet d'octets aléatoires. ( Implémentation AVX2 256b ici avec les composants intrinsèques Intel ). Je l'ai choisi par rapport au choix de xorshift * de Nominal, car la multiplication vectorielle entière sur 64 bits n'est possible que dans SSE2 / AVX2 avec des techniques de précision étendue .
Avec un vecteur d'octets aléatoires, nous pouvons découper chaque élément de 16 bits en plusieurs chiffres décimaux. Nous produisons plusieurs vecteurs d'éléments 16 bits qui sont chacun un chiffre ASCII + un espace ASCII . Nous stockons cela directement dans notre tampon de sortie.
Ma version originale
x / 6554
consistait simplement à obtenir un chiffre aléatoire de chaque élément uint16_t d'un vecteur. C'est toujours entre 0 et 9 inclus. C'est biaisé9
, car ce(2^16 -1 ) / 6554
n'est que 9.99923. (6554 = ceil ((2 ^ 16-1) / 10), ce qui garantit que le quotient est toujours <10.)x/6554
peut être calculé en multipliant par une constante "magique" ( la réciproque en virgule fixe ) et un décalage à droite du résultat supérieur. C'est le meilleur cas pour la division par une constante; certains diviseurs prennent plus d'opérations, et la division signée prend un travail supplémentaire.x % 10
a un biais similaire et n'est pas aussi bon marché pour calculer. (la sortie asm de gcc est équivalent àx - 10*(x/10)
, soit une multiplication et de soustraction supplémentaire sur le dessus de la division en utilisant un inverse multiplicatif modulaire.) En outre, le bit le plus bas de xorshift128 + ne sont pas aussi haute qualité , de sorte que la division de prendre l' entropie de bits de poids fort est meilleur ( pour la qualité ainsi que la vitesse) que modulo pour prendre l’entropie des bits bas.Cependant, nous pouvons utiliser plus d'entropie dans chaque uint16_t en regardant les chiffres décimaux bas, comme la
digit()
fonction de @ Nominal . Pour des performances maximales, j'ai décidé de prendre les 3 chiffres décimaux les plus bas etx/6554
, pour enregistrer un PMULLW et un PSUBW (et probablement du MOVDQA) par rapport à l'option de qualité supérieure consistant à prendre les 4 chiffres décimaux les plus bas. x / 6554 est légèrement affecté par les 3 chiffres décimaux, il existe donc une corrélation entre les chiffres du même élément (séparation de 8 ou 16 chiffres dans la sortie ASCII, en fonction de la largeur du vecteur).Je pense que gcc divise par 100 et par 1000, plutôt que par une chaîne plus longue qui se divise successivement par 10, de sorte que cela ne raccourcit probablement pas de manière significative la longueur de la chaîne de dépendance non acheminée par boucle qui produit 4 résultats pour chaque sortie de PRNG. port0 (vecteur multiplier et déplacer) est le goulot d'étranglement en raison des inverses multiplicatifs modulaires et des changements dans xorshift +, il est donc certainement utile de sauvegarder un vecteur multiplier.
xorshift + est si rapide que même utiliser seulement ~ 3,3 bits d’aléatoire sur 16 (soit une efficacité de 20%) n’est pas beaucoup plus lent que de le découper en plusieurs chiffres décimaux. Nous ne faisons qu’approximer la distribution uniforme, car cette réponse est axée sur la rapidité tant que la qualité n’est pas mauvaise.
Tout type de comportement conditionnel qui conserve un nombre variable d'éléments nécessiterait beaucoup plus de travail. (Mais pourrait peut-être encore être fait assez efficacement en utilisant les techniques de gauchissement SIMD . Cependant, cela devient moins efficace pour les éléments de petite taille; les tables de recherche de masques de masques géants ne sont pas viables, et il n'y a pas de mélange de passages de voies AVX2 inférieur à 32 - Une version PSHUFB de 128b pourrait toujours générer un masque à la volée avec BMI2 PEXT / PDEP, comme vous pouvez le faire pour AVX2 avec des éléments plus volumineux , mais cela pose problème, car un entier de 64 bits ne contient que 8 octets. sur cette réponse a un code qui pourrait fonctionner pour un nombre plus élevé d'éléments.)
Si la latence du générateur de ressources aléatoires est un goulot d'étranglement, nous pourrions aller encore plus vite en exécutant deux vecteurs de générateurs en parallèle, en alternant celui que nous utilisons. Le compilateur peut toujours conserver facilement tous les registres dans une boucle déroulée, ce qui permet aux deux chaînes de dépendance de s'exécuter en parallèle.
Dans la version actuelle, en découpant la sortie du PRNG, nous avons en fait un goulot d'étranglement sur le débit du port 0, et non du temps de latence du PRNG. Ce n'est donc pas nécessaire.
Le code: version AVX2
Version complète avec plus de commentaires sur l'explorateur du compilateur Godbolt .
Pas très bien rangé, désolé je dois me coucher et je veux que ça soit posté.
Pour obtenir la version SSE2,
s/_mm256/_mm
,s/256/128/
,s/v16u/v8u/
et le changementvector_size(32)
à 16 changer également l'incrément de 4 * retour à la ligne 16-4 * 8. (Comme je l'ai dit, le code est complexe et mal configuré pour la compilation de deux versions. Je n'avais pas prévu au départ de créer une version AVX2, mais je voulais vraiment tester sur un processeur Haswell auquel j'avais accès.)Compilez avec gcc, clang ou ICC (ou, espérons-le, avec tout autre compilateur comprenant le dialecte GNU C de C99 et les éléments intrinsèques d’Intel). Les extensions de vecteur GNU C sont très pratiques pour permettre au compilateur de générer les nombres magiques pour division / modulo à l’aide d’inverses multiplicatifs modulaires, et les
__attribute__
s occasionnels sont utiles.Cela pourrait être écrit de manière portable, mais cela prendrait plus de code.
Notes de performance:
Le magasin qui se chevauche pour insérer des nouvelles lignes a un temps système important pour décider où le placer (erreurs de prédiction de succursale et goulots d'étranglement frontaux sur Core2), mais le magasin lui-même n'a aucun impact sur les performances. En commentant uniquement cette instruction de stockage dans l'asm du compilateur (en laissant toutes les branches identiques), les performances sur Core2 sont restées inchangées, les exécutions répétées donnant le même temps à +/- moins de 1%. Je conclus donc que le tampon de mémoire tampon / cache s’en occupe parfaitement.
Néanmoins, utiliser une sorte de fenêtre tournante
ascii_digitspace
avec un élément ayant une nouvelle ligne pourrait être encore plus rapide, si nous déroulons suffisamment pour que les compteurs / ramifications disparaissent.L'écriture dans / dev / null est fondamentalement une opération non-opérée, donc le tampon reste probablement chaud dans le cache L2 (256 ko par cœur sur Haswell). On attend une accélération parfaite des vecteurs 128b à 256b: il n’ya pas d’instructions supplémentaires et tout (y compris les magasins) se passe avec une largeur deux fois plus grande. La branche d'insertion de nouvelle ligne est prise deux fois plus souvent, cependant. Malheureusement, je n'ai pas eu le temps de ma configuration Haswell cygwin avec cette partie
#ifdef
.2,5 GHz * 32B / 13,7 Go / s = 5,84 cycles par magasin AVX2 sur Haswell. C'est très bien, mais pourrait être plus rapide. Peut-être qu'il y a des frais généraux dans les appels système cygwin que je ne le pensais. Je n'ai pas essayé de commenter ceux-ci dans la sortie asm du compilateur (ce qui ferait en sorte que rien ne soit optimisé.)
La mémoire cache N1 peut gérer une mémoire de 32B par horloge et L2 n’est pas beaucoup de bande passante inférieure (latence plus élevée, cependant).
Lorsque j'ai consulté IACA il y a quelques versions (sans ramification pour les nouvelles lignes, mais en obtenant seulement un vecteur ASCII par vecteur RNG), il prédit quelque chose comme un magasin de vecteurs 32B par 4 ou 5 horloges.
J'espérais obtenir plus de rapidité en extrayant plus de données de chaque résultat RNG, en regardant moi-même l'asm, en considérant les guides d'Agner Fog et d'autres ressources d'optimisation pour lesquelles j'ai ajouté des liens dans le wiki du tag SO x86 .)
Il est probable que ce serait beaucoup plus rapide sur Skylake , où le vecteur entier se multiplie et que shift peut s'exécuter sur deux fois plus de ports (p0 / p1) que Haswell (p0 uniquement). xorshift et l'extraction des chiffres utilisent beaucoup de décalages et de multiplications. ( Mise à jour: Skylake l’utilise à 3,02 IPC, nous donnant 3,77 cycles par magasin AVX2 sur 32 octets , chronométrés à 0,030 s par itération de 1 Go, en écrivant
/dev/null
sur Linux 4.15 sur i7-6700k à 3,9 GHz.Il ne nécessite pas le mode 64 bits pour bien fonctionner . La version SSE2 est aussi rapide quand elle est compilée
-m32
, car elle n’a pas besoin de beaucoup de registres de vecteurs, et tous les calculs 64 bits sont effectués en vecteurs, et non en registres à usage général.En réalité, il est légèrement plus rapide en mode 32 bits sur Core2, car la macro-fusion de comparaison / branche ne fonctionne qu'en mode 32 bits, de sorte qu'il y a moins d'ops pour le noyau en panne (18.3s (1.85 Instructions Per Clock) vs 16,9 s (2,0 IPC)). La taille de code plus petite de l'absence de préfixe REX aide également les décodeurs de Core2.
De plus, certains déplacements vectoriels reg-reg sont remplacés par des charges, car toutes les constantes ne sont plus corrigées dans les registres vectoriels. Étant donné que le débit de charge du cache N1 n'est pas un goulot d'étranglement, cela aide en réalité. (par exemple, la multiplication par un vecteur constant de
set1(10)
:movdqa xmm0, xmm10
/pmullw xmm0, xmm1
se transforme enmovdqa xmm0, [constant]
/pmullw xmm0, xmm1
.) Comme le MOVDQA régulier nécessite un port ALU, il rivalise avec le travail réel en cours, mais une charge MOVDQA ne concourt que pour la bande passante de décodage frontale. (Le fait d'avoir une adresse de 4 octets dans de nombreuses instructions annule en grande partie l'avantage de la sauvegarde des préfixes REX.Je ne serais pas surpris si ce sont les gains réels qui proviennent de l’ajout de ALU MOVDQA uops, car l’interface devrait plutôt bien suivre la moyenne de 2,0 IPC.
Toutes ces différences disparaissent sur Haswell, où tout devrait fonctionner à partir du cache décodé-uop, sinon du tampon de bouclage. La macro-fusion de branche ALU + fonctionne dans les deux modes depuis Nehalem.
la source
Voici une solution que j'espère simple à comprendre:
od
crée un flux uniforme de chiffres hexadécimaux à partir de/dev/random
.tr
se débarrasse des lettres, ne garde que les0-9
chiffresfold
assure qu'il y a 100 chiffres par ligneawk
insère des espaces à l'intérieur des ligneshead
tronque l'entrée à 1 gigaoctetla source
Vous pouvez utiliser la
jot
commande pour cela:la source
fmt
n'a pas d'option de largeur de but. Quoi qu'il en soit, ce sera exact car tous les chiffres occupent exactement une colonne!fmt
version estfmt (GNU coreutils) 8.25
(Ubuntu 16.04)536870912
Cette méthode est similaire à celle de Stéphane Chazelas, mais je lis simultanément 64 bits pour améliorer les performances. La distribution est toujours uniforme mais vous obtenez maintenant 19 chiffres pour chaque 8 octets au lieu de 8 dans le meilleur des cas comme avant
Sur la plate-forme 32 bits, 9 chiffres seront lus à chaque fois au lieu de 19.
la source
perl
n'est pas compilé avec une prise en charge quadruple.next if $n >= 1000000000; $s = sprintf("%09u", $n);
pour obtenir seulement 9 chiffres$n = unpack("Q")
si quad n'est pas supporté.BEGIN{$/=\4; $,=" "} $n = unpack("L");
aussi<16e18
divisez par 16, vous obtenez 18 chiffres 86,7% pour 1,95 dpB. Avec 32 bits,<4e9 /4
obtient 9 chiffres 93,1% pour 2,10 dpB. Mais 5 octets (sous forme hexadécimale (H10))<1e12
donnent 12 chiffres à 90,9% pour 2,18 dpB, ou diviser l’hexagone en deux et<1e6
donner chaque moitié à 6 chiffres à 95,4% pour 2,29 dpB; cela approche la limite de log_10 (256) = 2,41.Je suis plutôt d'accord avec Nominal Animal pour utiliser un langage de programmation compilé si vous avez besoin de rapidité. Cependant, vous n'avez pas besoin d'écrire votre propre code RNG en C. C ++ 11 offre l'excellent Mersenne Twister dans le cadre de sa bibliothèque standard.
Le code ci-dessus est relativement simple et prend environ une minute lorsque je dirige la sortie vers un fichier. Nous pouvons aller beaucoup plus vite en créant une chaîne pouvant contenir 100 chiffres et en la piratant. Cela nous permet d'appeler chaque ligne plutôt que chaque chiffre.
Ce code prend ma machine environ six secondes. Rappelez-vous qu'il s'agit d'une sortie standard, transmettez-la dans un fichier.
J'ai quelques dénis de responsabilité. Tout d'abord, j'écris ceci sur un PC Windows. Je pense que les bibliothèques sont toutes présentes sous Linux, mais si je me trompe, assurez-vous de le préciser.
En outre, il génère exactement un demi-milliard de chiffres séparés par des espaces, ce qui est techniquement un gigaoctet mais peut-être pas exactement ce que vous vouliez. Il génère 5 millions de lignes, 100 chiffres par ligne. Si la différence est importante, vous pouvez augmenter le nombre de lignes. Sur ma machine Windows, le fichier semble légèrement plus grand que 10 ^ 9 octets, ce qui, je pense, a quelque chose à voir avec des caractères de nouvelle ligne supplémentaires.
la source
/dev/null
laquelle serait beaucoup plus rapide que l'écriture dans un fichier réelwrite()
appel système volumineux est une mémoire dans la pagecache, qui ne se bloque que si le noyau décide de le faire au lieu d’allouer plus d’espace tampon. Ce programme ne doit être goulot d’étranglement sur les E / S de disque que lorsque la mémoire est saturée ou si vous avez utilisé O_DIRECT pour contourner le pagecache. Si vouswrite()
utilisez des morceaux de taille inférieure à la taille du cache, il est à espérer que vos données ne seront stockées qu'une seule fois dans la mémoire principale et que le tampon réécrit sur place reste actif dans le cache L2 ou L3.Cela dépend de votre définition de "aléatoire". Si vous voulez dire par cryptographie aléatoire, il vous suffit d’avoir une bonne bibliothèque et de mordre la balle, attendez qu’elle s’exécute.
Si vous avez juste besoin de quelque chose d'assez aléatoire, voici un moyen simple:
Cela peut prendre une heure pour fonctionner sur une machine lente; assez rapide et assez aléatoire pour la plupart des buts.
la source
/dev/urandom
est susceptible d'être meilleur quegzip
, à la fois en vitesse et en caractère aléatoire.Get a file that is several Gb long
vous aurez besoin d’un fichier ** d’au moins 8 Go pour obtenir un fichier de 1 Gola source
cat file | tr
quand vous pouvez simplementtr <file
. IIRC, vous pouvez même<file tr
. Je pensais que vous parliez simplement de la lenteur de ce script shell, commedu | awk
après chaque ligne pour vérifier la taille, et en rouvrant le fichier pour ajouter chaque ligne au lieu de rediriger en dehors de la boucle.cat /dev/urandom | busy-cmd
est l'un de ces rares cas où cela peut avoir un sens, car il peut diviser la génération aléatoire et la commande occupée entre les processeurs. Pas tellement pour tr mais fait une différence pour Sam,od
par exemple.