@ rt15
Tu ferais bien de remplacer ton '4' par un sizeof(char *)... ça peut faire des étincelles sur certains systèmes sinon :)
Je copie un code tout simple et comparable au tien pour les perfs. Celui là perd du temps à la lecture car un malloc/ligne (puis en free à la fin...), mais j'ai fait au plus simple pour pouvoir trier aussi ce qui arrive sur stdin.
Je test sur un fichier de 4000000 de lignes de 35 caractères (144000000 octets).
C'est un gcc 4.3, les flags d'optim sont les mêmes pour tous les exécutables (y compris pour la commande sort).
Le fichier de données est dans le cache de l'OS, et le fichier de sortie est /dev/null pour ne pas fausser les tests avec les I/O.
déjà, la commande sort en référence, en lui donnant un buffer suffisant pour qu'ils n'utilise pas de fichier temporaire sur le disque dur
# time nice -n -20 sort -S500M toto -o /dev/null
real 0m45.331s
user 0m44.763s
sys 0m0.488s
ensuite celui de rt15,
# time nice -n -20 ./cs
Debut de lecture : 00:02:33
Fin de lecture : 00:02:34
Nombre de lignes : 4000000
Fin de tri : 00:02:41
Fin ecriture : 00:02:42
real 0m9.009s
user 0m8.409s
sys 0m0.512s
Mon premier programme.
# time nice -n -20 ./sortfile_simple toto /dev/null
real 0m9.127s
user 0m8.737s
sys 0m0.360s
Pas mal pour une lecture bourrine comme ça :) Mais on peut faire bien mieux :)
Quelques pistes d'optim que j'ai utilisé pour un autre programme :
- Lecture
Là, je recopie le fichier dans la mémoire du process, ligne par ligne. C'est bien pour une lecture sur stdin, mais pas terrible sinon. D'autant plus que le fichier est peut-être déjà dans le cache de l'OS. Déjà, faire une lecture en une fois dans un gros buffer améliore bien, mais on peut parfois faire encore mieux.
Si dans le fichier de données, les lignes sont séparées par \0 au lieu de \n, alors plus besoin de faire une copie du fichier. On peut l'ouvrir avec mmap et faire pointer le tableau directement sur le mapping (en faisant attention à la dernière ligne si elle n'est pas terminée quand même).
- Tri
Quicksort se parallélise naturellement. Par contre, je n'ai vraiment pas envie d'écrire ça :). Donc une solution intermédiaire bâtarde:
Si on veut utiliser t threads
- trouver t-1 pivots, par exemple en prenant les 1000 premières lignes, en les triant, et en prenant les pivots espacés régulièrement (ça suppose que les données soient uniformes).
- utiliser juste l'algo de partition du quicksort pour placer ces pivots et construire une partition ...p1.....p2 ..... pt-1 ....
- plus qu'à trier en parallèle chaque sous partie
Ça tient la route pour un petit nombre de threads
Si on utilise tout ça (je copie pas le code ici, ça commence à grossir un peu...) :
Sans thread, fichier toujours terminé par \n, juste une lecture plus propre :
# time nice -n -20 ./sortfile -v toto /dev/null
Reading from 'toto'...
Read 4000000 lines.
Sorting...
Writting output to '/dev/null'...
Stats:
comparisons: 82698297
read time: 0.870s
sort time: 5.761s
write time: 1.528s
Cleaning...
real 0m8.195s
user 0m7.768s
sys 0m0.364s
1s de moins déjà :)
Avec 2 threads :
# time nice -n -20 ./sortfile -vt2 toto /dev/null
Reading from 'toto'...
Read 4000000 lines.
Sorting with 2 threads...
Writting output to '/dev/null'...
Stats:
comparisons: 84705684
read time: 0.885s
sort time: 3.464s
write time: 1.669s
Cleaning...
real 0m6.051s
user 0m8.789s
sys 0m0.384s
Enfin, 2 threads toujours, mais le même fichier avec les \n remplacés par des \0
# time nice -n -20 ./sortfile --zero --mmap -vt2 toto0 /dev/null
Reading from 'toto0'...
Read 4000000 lines.
Sorting with 2 threads...
Writting output to '/dev/null'...
Stats:
comparisons: 84705684
read time: 0.731s
sort time: 3.497s
write time: 1.681s
Cleaning...
real 0m5.930s
user 0m8.957s
sys 0m0.124s
La commande sort peut aller se cacher :)
Le code du programme simple :
#ifndef _GNU_SOURCE
# define _GNU_SOURCE
#endif
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include
#include <getopt.h>
#include <string.h>
static int verbose = 0;
/* The string comparison function */
int (*str_compare)(const char *, const char *) = strcmp;
static char ** read_lines(FILE *in, size_t *length) {
char **lines, **tmp_lines;
size_t nlines = 0;
char *buf = NULL, *buf_cpy;
size_t buflen = 0;
size_t i;
ssize_t r;
if (*length < 1)
*length = 1000;
lines = malloc(*length * sizeof(char *));
if (lines == NULL) {
perror("malloc");
return NULL;
}
while (1) {
r = getline(&buf, &buflen, in);
if (r >= 0) {
// Remove the trailing \n or \r\n
if (r >2 && buf[r - 2] '\r' && buf[r - 1] == '\n') {
buf[r - 2] = '\0';
r -= 2;
}
else if (r >1 && buf[r - 1] '\n') {
buf[r - 1] = '\0';
r--;
}
if (r == 0) {
continue;
}
// Expand the array
if (*length == nlines) {
*length += 1000;
tmp_lines = realloc(lines, *length * sizeof(char *));
if (tmp_lines == NULL) {
perror("realloc");
for (i = 0; i < nlines; i++) {
free(lines[i]);
}
free(lines);
free(buf);
return NULL;
}
lines = tmp_lines;
}
// Copy the line from the getline buffer
buf_cpy = malloc(r + 1);
if (buf_cpy == NULL) {
perror("malloc");
for (i = 0; i < nlines; i++) {
free(lines[i]);
}
free(lines);
free(buf);
return NULL;
}
memcpy(buf_cpy, buf, r + 1);
lines[nlines] = buf_cpy;
nlines++;
}
else {
break;
}
}
*length = nlines;
free(buf);
return lines;
}
static void free_lines(char **lines, size_t len) {
size_t i;
for (i = 0; i < len; i++) {
free(lines[i]);
}
free(lines);
}
static int write_lines(FILE *out, char **lines, size_t len) {
size_t i;
int r;
for (i = 0; i < len; i++) {
r = fprintf(out, "%s\n", lines[i]);
if (r < 0) {
perror("fprintf");
return -1;
}
}
return 0;
}
// Basic comparison with str_compare
static int cmp_lines(const void *p1, const void *p2) {
return str_compare(*(char * const *) p1, *(char * const *) p2);
}
static void usage(const char *name) {
fprintf(stderr, "Usage: %s [OPTION]... input_file output_file\n\n", name);
fprintf(stderr, "Options:\n");
fprintf(stderr, " -h, --help "
"this help message\n");
fprintf(stderr, " -c, --coll "
"use 'strcoll' to order the lines\n");
fprintf(stderr, " -V, --vers "
"use 'strverscmp' to order the lines\n");
fprintf(stderr, " -v, --verbose "
"print progress messages to stderr\n\n");
fprintf(stderr, "Use "-" instead of the input or output file to use "
"respectively stdin or stdout.\n");
fprintf(stderr, "The default comparison function is 'strcmp'.\n");
}
int main(int argc, char *argv[]) {
int exit_status = EXIT_SUCCESS;
int opt;
const char *in_filename, *out_filename;
FILE *in_file, *out_file;
char ** lines;
size_t lines_length = 0;
const char *prog_name = argv[0];
struct option long_options[] = { { "help", 0, NULL, 'h' }, { "verbose", 0,
NULL, 'v' }, { "coll", 0, NULL, 'c' },
{ "vers", 0, NULL, 'V' }, { 0, 0, 0, 0 } };
while ((opt = getopt_long(argc, argv, "hcVv", long_options, NULL)) >= 0) {
switch (opt) {
case 'v':
verbose = 1;
break;
case 'h':
usage(prog_name);
exit(EXIT_SUCCESS);
break;
case 'c':
str_compare = strcoll;
break;
case 'V':
str_compare = strverscmp;
default:
usage(prog_name);
exit(EXIT_FAILURE);
break;
}
}
argv += optind;
argc -= optind;
if (argc != 2) {
usage(prog_name);
exit(EXIT_FAILURE);
}
in_filename = argv[0];
out_filename = argv[1];
if (strcmp(in_filename, "-") != 0) {
in_file = fopen(in_filename, "r");
if (in_file == NULL) {
perror("fopen");
exit(EXIT_FAILURE);
}
}
else {
in_file = stdin;
in_filename = "stdin";
}
if (strcmp(out_filename, "-") != 0) {
out_file = fopen(out_filename, "w");
if (out_file == NULL) {
perror("fopen");
exit(EXIT_FAILURE);
}
}
else {
out_file = stdout;
out_filename = "stdout";
}
if (verbose)
fprintf(stderr, "Reading from '%s'...\n", in_filename);
lines = read_lines(in_file, &lines_length);
if (lines == NULL) {
exit_status = EXIT_FAILURE;
goto close_end;
}
if (verbose) {
fprintf(stderr, " Read %zd lines.\n", lines_length);
}
if (verbose)
fprintf(stderr, "Sorting...\n");
qsort(lines, lines_length, sizeof(char *), cmp_lines);
if (verbose)
fprintf(stderr, "Writting output to '%s'...\n", out_filename);
if (write_lines(out_file, lines, lines_length) < 0) {
exit_status = EXIT_FAILURE;
goto free_end;
}
free_end:
if (verbose)
fprintf(stderr, "Cleaning...\n");
free_lines(lines, lines_length);
close_end:
fclose(in_file);
fclose(out_file);
return exit_status;
}
et le code utilisé pour les derniers essais : http://pastebin.com/f1fceff27
Dobel
[Une fois rien, c'est rien; deux fois rien, ce n'est pas beaucoup, mais pour trois fois rien, on peut déjà s'acheter quelque chose, et pour pas cher]