Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#1 Le 04/07/2014, à 08:56

White Angels

[RESOLU] Comment recupérer les sources d'un logiciel ?

Bonjour à tous,

en cours de C nous avons eu à programmer un algo de tri (quicksort) en utilisant la programmation multi-processeur.
Pour comparez nos programmes on exécutais un tri avec la commande "sort" du shell et avec notre programme (bon on faisait un truc simple uniquement sur des entiers) et notre programme arrivais loin devant sort en termes de performances.

J'ai regardé sur le net, j'ai trouvé ceci : https://stackoverflow.com/questions/115 … e-commands qui m'indique ou télécharger les sources.
Seulement j'ai l’impression que c'est le code sources des fonctions C car le qsort était déjà parallélisé.

Du coup j'aimerais savoir je peux télécharger le programme "sort" qu'on tape dans le shell, juste pour voir si je suis capable de le rendre parallèle.

Dernière modification par White Angels (Le 04/07/2014, à 11:05)


OS : Ubuntu 14.04 Trusty Tahr  || Nombre de convertis aux libres : 2 (peut-être une troisième)

Hors ligne

#2 Le 04/07/2014, à 09:21

claudius01

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

Bonjour,

White Angels a écrit :

Du coup j'aimerais savoir [oû] je peux télécharger le programme "sort" qu'on tape dans le shell...

Sauf erreur de ma part, ce programme sort est dans le package coreutils:
http://www.gnu.org/software/ -> http://www.gnu.org/software/coreutils/ -> sort.c dans un des paquets


Cordialement, A+
--
Claudius

Dernière modification par claudius01 (Le 04/07/2014, à 09:22)

Hors ligne

#3 Le 04/07/2014, à 10:39

ssdg

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

J'ai fait un man sort et j'ai trouvé le lien en bas. J'imagine que ça ne marchera pas avec tout les programmes, mais si ton attention se tourne vers un autre programme, tu pourra trouver la réponse plus rapidement par ce moyen.


s'il n'y a pas de solution, c'est qu'il n'y a pas de problème... ou pas.

Hors ligne

#4 Le 04/07/2014, à 11:05

White Angels

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

@claudius01 : tu avais raison il est bien dans le core-utils.

C'est bizarre, sort est bien multi-thread pourtant bien moins rapide que notre programme !


OS : Ubuntu 14.04 Trusty Tahr  || Nombre de convertis aux libres : 2 (peut-être une troisième)

Hors ligne

#5 Le 04/07/2014, à 11:16

Brunod

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

Est-ce que ton programme fait tout ceci aussi ?

SORT(1)                                                               User Commands                                                               SORT(1)



NAME
       sort - sort lines of text files

SYNOPSIS
       sort [OPTION]... [FILE]...
       sort [OPTION]... --files0-from=F

DESCRIPTION
       Write sorted concatenation of all FILE(s) to standard output.

       Mandatory arguments to long options are mandatory for short options too.  Ordering options:

       -b, --ignore-leading-blanks
              ignore leading blanks

       -d, --dictionary-order
              consider only blanks and alphanumeric characters

       -f, --ignore-case
              fold lower case to upper case characters

       -g, --general-numeric-sort
              compare according to general numerical value

       -i, --ignore-nonprinting
              consider only printable characters

       -M, --month-sort
              compare (unknown) < 'JAN' < ... < 'DEC'

       -h, --human-numeric-sort
              compare human readable numbers (e.g., 2K 1G)

       -n, --numeric-sort
              compare according to string numerical value

       -R, --random-sort
              sort by random hash of keys

       --random-source=FILE
              get random bytes from FILE

       -r, --reverse
              reverse the result of comparisons

       --sort=WORD
              sort according to WORD: general-numeric -g, human-numeric -h, month -M, numeric -n, random -R, version -V

       -V, --version-sort
              natural sort of (version) numbers within text

       Other options:

       --batch-size=NMERGE
              merge at most NMERGE inputs at once; for more use temp files

       -c, --check, --check=diagnose-first
              check for sorted input; do not sort

       -C, --check=quiet, --check=silent
              like -c, but do not report first bad line

       --compress-program=PROG
              compress temporaries with PROG; decompress them with PROG -d

       --debug
              annotate the part of the line used to sort, and warn about questionable usage to stderr

       --files0-from=F
              read input from the files specified by NUL-terminated names in file F; If F is - then read names from standard input

       -k, --key=KEYDEF
              sort via a key; KEYDEF gives location and type

       -m, --merge
              merge already sorted files; do not sort

       -o, --output=FILE
              write result to FILE instead of standard output

       -s, --stable
              stabilize sort by disabling last-resort comparison

       -S, --buffer-size=SIZE
              use SIZE for main memory buffer

       -t, --field-separator=SEP
              use SEP instead of non-blank to blank transition

       -T, --temporary-directory=DIR
              use DIR for temporaries, not $TMPDIR or /tmp; multiple options specify multiple directories

       --parallel=N
              change the number of sorts run concurrently to N

       -u, --unique
              with -c, check for strict ordering; without -c, output only the first of an equal run

       -z, --zero-terminated
              end lines with 0 byte, not newline

       --help display this help and exit

       --version
              output version information and exit

       KEYDEF  is F[.C][OPTS][,F[.C][OPTS]] for start and stop position, where F is a field number and C a character position in the field; both are ori‐
       gin 1, and the stop position defaults to the line's end.  If neither -t nor -b is in effect, characters in a field are counted from the  beginning
       of  the  preceding  whitespace.  OPTS is one or more single-letter ordering options [bdfgiMhnRrV], which override global ordering options for that
       key.  If no key is given, use the entire line as the key.

       SIZE may be followed by the following multiplicative suffixes: % 1% of memory, b 1, K 1024 (default), and so on for M, G, T, P, E, Z, Y.

       With no FILE, or when FILE is -, read standard input.

       *** WARNING *** The locale specified by the environment affects sort order.  Set LC_ALL=C to get the traditional sort order that uses native  byte
       values.

AUTHOR
       Written by Mike Haertel and Paul Eggert.

REPORTING BUGS
       Report sort bugs to bug-coreutils@gnu.org
       GNU coreutils home page: <http://www.gnu.org/software/coreutils/>
       General help using GNU software: <http://www.gnu.org/gethelp/>
       Report sort translation bugs to <http://translationproject.org/team/>

COPYRIGHT
       Copyright © 2013 Free Software Foundation, Inc.  License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
       This is free software: you are free to change and redistribute it.  There is NO WARRANTY, to the extent permitted by law.

SEE ALSO
       uniq(1)

       The full documentation for sort is maintained as a Texinfo manual.  If the info and sort programs are properly installed at your site, the command

              info coreutils 'sort invocation'

       should give you access to the complete manual.



GNU coreutils 8.21                                                      March 2014                                                                SORT(1)

Windows est un système d'exploitation de l'homme par l'ordinateur. Linux, c'est le contraire...
39 pc linux convertis

Hors ligne

#6 Le 04/07/2014, à 11:34

eiger

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

White Angels a écrit :

C'est bizarre, sort est bien multi-thread pourtant bien moins rapide que notre programme !

As-tu vérifié que sort s’exécutait réellement sur plusieurs threads ? D'après le code, la création des threads dépend également d'une heuristique, qui n'a peut-être pas été assez vérifiée sur différents processeurs:

/* Heuristic value for the number of lines for which it is worth creating
   a subthread, during an internal merge sort.  I.e., it is a small number
   of "average" lines for which sorting via two threads is faster than
   sorting via one on an "average" system.  On a dual-core 2.0 GHz i686
   system with 3GB of RAM and 2MB of L2 cache, a file containing 128K
   lines of gensort -a output is sorted slightly faster with --parallel=2
   than with --parallel=1.  By contrast, using --parallel=1 is about 10%
   faster than using --parallel=2 with a 64K-line input.  */
enum { SUBTHREAD_LINES_HEURISTIC = 128 * 1024 };
verify (4 <= SUBTHREAD_LINES_HEURISTIC);

Il faudrait donc vérifier que tu as au moins 128k lignes à trier.

Hors ligne

#7 Le 04/07/2014, à 11:52

White Angels

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

J'ai poussé les testes jusqu'a 100k lignes, et plus j'augmentais en nombre de lignes plus j'étais performant par rapport à sort.
Pourtant, d'après sont commentaire, quand tu as moins de 64k lignes tu es plus performant avec un seul thread !

PS : Non mon programme étais pas aussi poussé, il triais que les entiers et faisait en tout et pour tout 700 lignes de code contre 5k lignes pour le sort.


OS : Ubuntu 14.04 Trusty Tahr  || Nombre de convertis aux libres : 2 (peut-être une troisième)

Hors ligne

#8 Le 04/07/2014, à 12:06

Brunod

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

as-tu vu l'option  --parallel=N
              change the number of sorts run concurrently to N ?


Windows est un système d'exploitation de l'homme par l'ordinateur. Linux, c'est le contraire...
39 pc linux convertis

Hors ligne

#9 Le 04/07/2014, à 12:27

claudius01

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

White Angels a écrit :

... il [le programme] triait que les entiers...

Je n'ai pas vérifié que si sort trouve uniquement des entiers à trier (une 1st passe de lecture serait alors nécessaire), il se replie sur le bon opérateur de comparaison numérique. A défaut, sort va utiliser le strcmp sur des chaînes qu'elles soient numériques ou alphabétiques.
Donc, attention à ne pas comparer (c'est le cas de le dire ;-) des choses incomparables.

Il faudrait un résultat de comparaison sur un fichier tel que le fichier source de sort.c par exemple et constitué effectivement de ~4500 lignes.

Dernière modification par claudius01 (Le 04/07/2014, à 14:51)

Hors ligne

#10 Le 04/07/2014, à 13:03

eiger

Re : [RESOLU] Comment recupérer les sources d'un logiciel ?

Petit test rapide sur des fichiers composés d'entiers pseudo-aléatoires avec un fichier de 100k lignes et un fichier de 200k lignes. Aucune option particulière passée à sort.

Avec 100k:

strace a écrit :

10104 read(3, "13521\n7993\n28644\n857\n23445\n10029"..., 565248) = 565248
10104 read(3, "504\n25138\n26330\n17771\n18510\n2051"..., 4096) = 1272
10104 read(3, "", 4096)                 = 0
10104 lseek(3, 0, SEEK_CUR)             = 566520
10104 close(3)                          = 0
10104 munmap(0x7f79c10d3000, 4096)      = 0
10104 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 1), ...}) = 0
10104 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f79c10d3000
10104 write(1, "0\n", 2)                = 2
10104 write(1, "0\n", 2)                = 2
10104 write(1, "0\n", 2)                = 2
10104 write(1, "0\n", 2)                = 2

Avec 200k:

strace a écrit :

10106 read(3, "29490\n2750\n30566\n3396\n8439\n670\n9"..., 1130496) = 1130496
10106 read(3, "40\n29639\n20515\n18957\n18955\n25097"..., 4096) = 1391
10106 read(3, "", 4096)                 = 0
10106 lseek(3, 0, SEEK_CUR)             = 1131887
10106 close(3)                          = 0
10106 munmap(0x7f036e5e6000, 4096)      = 0
10106 mmap(NULL, 8392704, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0x7f036dde6000
10106 mprotect(0x7f036dde6000, 4096, PROT_NONE) = 0
10106 clone(child_stack=0x7f036e5e5ff0, flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, parent_tidptr=0x7f036e5e69d0, tls=0x7f036e5e6700, child_tidptr=0x7f036e5e69d0) = 10107
10107 set_robust_list(0x7f036e5e69e0, 0x18) = 0
10107 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 1), ...}) = 0
10107 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f036dde5000
10107 write(1, "0\n", 2)                = 2
10107 write(1, "0\n", 2)                = 2
10107 write(1, "0\n", 2)                = 2
10106 futex(0x1e94398, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>

Avec 200k, un thread est créé. Avec 100k ce n'est pas le cas.

Hors ligne