tri alphabétique ultra rapide de chaines de caractères de longueur variable

-- Bonjour,


je sais que c'est un forum dédié au C mais je vais parler de pascal.
En effet je connais bien ce langage et je l'ai utilisé pour trier alphabétiquement un fichier texte comportant 4 millions de chaines de caractères(en gros 4 millions de mots en colonne).
J'ai été surpris de la rapidité de mon code: 9 secondes pour lire le fichier, le trier et envoyer le résultat dans un autre fichier.
Je voudrais savoir si il existe un programme écrit en C qui serait plus rapide que celui que j'ai écris en pascal objet sous linux ?

Merci --

Salut,

Je suis presque sur qu'un programme en C qui lit les chaines de caracteres dans un void* et les cast en int* pour les comparaisons dans un quicksort(insertionsortpour des portions de tableau inferieur a 200 en longueur) serait aussi rapide (sinon plus) que ton programme
http://liveplayaz.com
je suis heureux de faire partie d'une grande famille ...!

Salut mslider,

Je suis très impressionné par ta vitesse !
Quelles sont les caractéristiques de ta machine ( architecure cpu, vitesse, mémoire,... ) ?

Cordialement.

Salut,

nickydaquick -> Je ne sais pas si Lazarus fait de même que Delphi, mais je suppose que c'est comme pour Delphi, à savoir que les tris sont implémentés en quicksort.
Une des paticularités du code ci-dessus est que la TStringList est, au sens C, un tableau de char* (char**). Donc, lors du tri, il compare les chaîne mais ne fait que déplacer les pointeurs sur elles à l'intérieur du tableau.
Concernant le cast en int*, c'est un peu plus compliqué à cause du little-endian : on ne peut pas trier des chaines comme des entiers !
Il faut donc par exemple utiliser l'instruction asm bswap pour inverser avant de comparer, comme ça avait été fait lors d'un benchs inter-langages qui a eu lieu sur ce site (Mais les résultats n'ont pas pu être exploités à cause d'un défaut dans l'énoncé).

mslider -> Ah tiens mais je t'ai déjà croisé toi !

En fait du point de vue du programmeur C, ta question peut paraître trollesque, amusante, fatigante voir même absurde...

En effet, le C, comme le Delphi (Je vais parler ici de Delphi car je n'ai essayé Lazarus qu'une ou deux fois), sont compilés en code machine.
Donc un exécutable Delphi ressemble énormément à un exécutable C. Le code machine dépend du processeur, pas du langage.

Ainsi lorsque tu compare la vitesse de deux exécutables, tu juges de la qualité du code machine généré, que ce soit sur le plan de :
1) L'algorithmie.
2) L'optimisation fine avec des combinaison d'instruction qui font la même chose mais un peu plus rapidement.
3) La quantité d'accès disque qu'il va engendrer (Variable d'une exécution à l'autre car il y a des accès explicites et d'autres qui le sont moins...).
4) La mémoire : il faut essayer de travailler au maximum dans le cache processeur, c'est à dire utiliser le minimum de mémoire et toujours la même.
5) Le multi-threading s'il peut aider, ce qui n'est pas toujours le cas.
6) La quantité d'appels au système d'exploitation.
7) ...

On sait maintenant que les performances de l'application dépendent du code machine, donc de la combinaison d'instruction processeur.

Comment est généré ce code machine ?
1) Par compilation de source.
2) Par utilisation de librairies déjà compilées.

La performance de l'application finale dépend donc de trois facteurs :
1) De la qualité de la compilation, donc du compilateur.
2) De la qualité du source (Du point de vue des performances) : les compilateurs sont stupides, et ne feront jamais du bon boulot si le source est merdique.
3) De la qualité des librairies utilisées, autrement dit de la qualité de leurs sources
et du compilateur utilisé pour les générer.

1) Tout d'abord intéressons nous aux compilateur.

On ne peut pas dire qu'il n'y a pas de différence d'un compilo à l'autre, mais elle sont cependant peu importantes.
A partir du moment ou les développeurs du compilateur ont pas trop mal fait leur boulot...
Ainsi, les différences de performance s'expliquent beaucoup plus par les différences dans l'implémentation des librairies standards fournies avec le compilo que par la génération de code.
Une instruction for génère globalement le même code que ce soit en Delphi ou en C.
Bien sûr il y a des variations et des optimisations, mais globalement, les performances vont rester proches.

2) Voyons la qualité du source.

La qualité du source dépend du développeur... Mais pas seulement. Elle dépend aussi du langage!
Par exemple, il est clair que le Java, même doté du meilleur compilateur en langage machine du monde (Je parle ici d'un compilo style gcj, pas d'un compilo vers du byte code), ne pourra égaliser les performances du C.
De même, un langage faiblement typé, genre PHP, donne beaucoup de travail au compilateur, qui va donc générer du code machine de piètre qualité (Dans l'hypothèse là aussi de faire un vrai compilo code machine pour PHP, et non de l'interprété).

Bref, des langages sont plus lents de part leurs syntaxes, qui ne permettent pas au développeurs de générer un code machine optimal.
On ne fait pas ce que l'on veut : le langage est de trop haut niveau.
Par exemple en Java, on ne peut pas manipuler directement les adresses des objets, car ceux-ci n'ont pas d'adresse fixe.

En ce qui concerne le Delphi on peut écrire du Delphi qui ressemble beaucoup à du C (Pas d'utilisation d'objets, pas d'utilisation de String...)...
Donc le Delphi n'est pas du tout limitant : il permet de produire les mêmes combinaisons d'instructions processeur que le C.

Pour ce qui est du développeur... Disons que ce n'est pas le sujet !
Mais quand même. Le développeur doit avant tout soigner ses algos, savoir ce qui coûte, mettre en place des caches si nécessaire...
Il doit donc aussi bien connaître les librairies qu'il utilise et globalement les actions que celle-i va réaliser.
Par exemple que TStringList.Sort fasse fasse un tri de tableau de pointeur à l'aide d'un quicksort.

Inutile me diras-tu ? Oui et non !
Si on cherche les performances, on peut s'apercevoir que c'est pas forcément idéal dans le cas où l'on se trouve.
Par exemple ici, Sort devrait relativement bien faire son boulot : vu la taille de tes lignes (Une trentaine de caractères), il peut être préférable d'utiliser des pointeurs plutôt que de déplacer les caractères.
Par contre, une TStringList
de 4 millions d'éléments... 4 millions de String... C'est plutôt lourd.

3) Et finalement intéressons nous aux librairies.

Un point important qui fait différer le C de la plupart des langages (Y compris du C++), c'est sa séparation claire entre le langage et les librairies.
En effet, les instructions (if, for, switch...) et les opérateurs (+, -, =, ...) du C n'utilisent jamais de librairies. Ils sont directement transformés en langage machine.
On peut donc écrire un code C qui n'utilise AUCUNE librairie. Si le source est court, l'exécutable sera minuscule (De l'ordre de quelques ko).
Mais on peut aussi faire des applications complètes ainsi, en faisant des appels à l'OS.
L'important est que la runtime (La bibliothèque standard C), qui permet par exemple la comparaison de chaîne, l'allocation dynamique... est parfaitement optionnelle et remplaçable !

On peut donc générer des exécutables dont les performances ne dépendent pas des librairies utilisées, car ils n'en utilisent pas !
Et avec un rien d'entrainement, on est capable de deviner approximativement quel séquence d'instruction assembleur vont être générées à partir d'une portion de code C.

Et c'est là que la toute puissance du C s'exprime.
On explique par exemple souvent que le C est plus lent que le java en ce qui concerne une allocation dynamique, car un garbage collector (Ils sont implémentés sous forme de pile) est plus rapide qu'un tas lors des allocations.
Mais rien n'empèche de faire un pseudo garbage collector en C !
Par contre on ne peut pas faire une allocation classique en java... C'est pour cela que certains développeurs considère le C comme la liberté et le java comme une prison.
On est donc théoriquement capable en C de générer des fichier exécutable ressemblant comme deux gouttes d'eau à des fichiers exécutables générés à l'aide d'autres langages (Assembleur excepté).
C'est pour cela qu'il est pratiquement impossible de battre les performances du C. Il suffit de réécrire TStringList.Sort en C avec le même algo que celui en Delphi pour tomber sur des performances similaires.

Ce principe des instructions/opérateurs générant des uniquement des instructions processeurs ne s'applique pas du tout au VB6 par exemple, ou une boucle for un peu compliqué va générer des appels à la "librairie standard" VB6.

Il ne s'applique pas non plus au Delphi. L'unité "System" est incluse implicitement dans les uses, et on ne peut pas s'en passer.
Et le compilateur va inclure dans l'exécutable résultant du code machine de cette librairie, code que l'on ne peut pas contrôler.
De même, ça se voit bien au niveau des instruction : on peut faire une comparaison de chaîne avec =. Mais en fait le compilateur va traduire ça par un appel à une fonction : LStrCmp.
C'est un appel caché à une fonction d'une librairie ! Inconcevable en C où comme je l'ai expliqué tout est explicite.

Cependant, en connaissant suffisamment la façon dont est compilée le Delphi, on peut coder de manière à ce que celui-ci ne fasse jamais d'appel à des fonctions de l'unité System.
Bien sûr cela impose de nombreuses restrictions, par exemple on ne peut pas travailler en orienté objet, ou utiliser String.
Autre bémol, l'exécutable reste quand même de taille supérieure à ce qu'on pourrait espérer.
Mais le fait que ce soit possible est un signe majeur dans la qualité du langage : beaucoup d'autres n'offrent pas cette possibilité !
Toutefois, on n'est pas au niveau de contrôle du C.


Ma conclusion est que le pascal et le C sont de performance similaire quand ils sont utilisés par un même développeur, connaissant bien la façon dont sont compilé ces deux langages, et le fonctionnement d'un processeur.
Le C ne peut pas battre le pascal à pleine couture, et inversement : avec le même algo ils se tiennent dans un mouchoir de poche.
Ces deux langages peuvent donc être utilisés indifféremment lors de l'écriture d'une application qui se doit d'être performante.

Le C garantit plus de contrôle.
Mais l'avantage le pascal permet de faire beaucoup de chose avec très peu de code à l'aide d'une "librairies standard" très polyvalente et cependant très performante.

Voilà donc un code C qui est plus rapide que ton pascal. Du moins sur ma machine...
Pascal -> 46 secondes.
C -> 8 secondes.
Mais j'aurais appliqué le même algo en Pascal, j'aurais eu un résultat similaire.
Et je pourrais faire mieux en Pascal, par exemple en multi-threadant le tri.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>



char* GetTime(char* lpBuffer, long nSize)

{

  time_t nCurrentTime;

  struct tm* timeInfo;



  time(&nCurrentTime);

  timeInfo = localtime(&nCurrentTime);

  strftime(lpBuffer, nSize, "%H:%M:%S", timeInfo);



  return lpBuffer;

}



FILE *SafeOpenFile(char *lpFileName, char *lpMode, FILE **lpFile)

{

  *lpFile = fopen(lpFileName, lpMode);

  if (! *lpFile)

    printf("Cannot open file: \"%s\"\n", lpFileName);



  return *lpFile;

}



long GetSizeOfFile(FILE* lpFile)

{

  long nCurrentPos;

  long nResult;



  nCurrentPos = ftell(lpFile);



  fseek(lpFile, 0, SEEK_END);

  nResult = ftell(lpFile);



  fseek(lpFile, nCurrentPos, SEEK_SET);



  return nResult;

}



void** SetSize(void** lpArray, long nTypeSize, long nSize)

{

  long* lpLongArray;

  long nCapacity;



  lpLongArray = (long*)*lpArray;

  if (! nSize)

  {

    if (lpLongArray)

    {

      free(&lpLongArray[-2]);

      lpLongArray = NULL;

    }

  }

  else

  {

    if (! lpLongArray)

    {

      lpLongArray = (long*)malloc(2 * sizeof(long) + nTypeSize * nSize);

      if (lpLongArray)

      {

        lpLongArray[0] = nSize;

        lpLongArray[1] = nSize;

        lpLongArray = &lpLongArray[2];

      }

    }

    else

    {

      /* Si agrandissement */

      if (lpLongArray[-1] <= nSize)

      {

        /* Si la capacité est suffisante */

        if (lpLongArray[-2] >= nSize)

          lpLongArray[-1] = nSize;

        else

        {

          /* On double la capacité et on vérifie que c'est suffisant */

          nCapacity = 2 * lpLongArray[-2];

          if (nCapacity < nSize)

            nCapacity = nSize;



          lpLongArray = (long*)malloc(2 * sizeof(long) + nCapacity * nTypeSize);

          if (lpLongArray)

          {

            lpLongArray[0] = nCapacity;

            lpLongArray[1] = nSize;

            lpLongArray = &lpLongArray[2];

            memcpy(lpLongArray, *lpArray, ((long*)(*lpArray))[-1] * nTypeSize);

            free(&((long*)(*lpArray))[-2]);

          }

        }

      }

      else

      {

        /* On ne désalloue que si c'est vraiment utile */

        if (nSize * 2 > lpLongArray[-2])

          lpLongArray[-1] = nSize;

        else

        {

          /* Allocation d'un espace plus petit et recopie du début */

          lpLongArray = (long*)malloc(2 * sizeof(long) + nSize * nTypeSize);

          if (lpLongArray)

          {

            lpLongArray[0] = nSize;

            lpLongArray[1] = nSize;

            lpLongArray = &lpLongArray[2];

            memcpy(lpLongArray, *lpArray, nSize * nTypeSize);

            free(&((long*)(*lpArray))[-2]);

          }

        }

      }

    }

  }



  *lpArray = lpLongArray;

  return lpArray;

}



long GetSize(void* lpArray)

{

  long* lpLongArray;

  long nResult;



  nResult = 0;



  lpLongArray = (long*)lpArray;

  if (lpLongArray)

    nResult = lpLongArray[-1];



  return nResult;

}



int Compare(const void* a, const void* b)

{

  char* lpStr1;

  char* lpStr2;

  long nI;



  lpStr1 = *(char**)a;

  lpStr2 = *(char**)b;



  nI = 0;

  while ((lpStr1[nI] != '\n') &&

         (lpStr1[nI] != '\r') &&

         (lpStr2[nI] != '\n') &&

         (lpStr2[nI] != '\r') &&

         (lpStr1[nI] == lpStr2[nI])) nI++;



  return lpStr1[nI] - lpStr2[nI];

}



int main()

{

  FILE* lpInputFile;

  FILE* lpOutputFile;

  long nInputSize;

  char* lpFileContent;

  char* lpResultContent;

  char** lpSortingArray;

  char lpTime[20];

  int bWasCrOrLf;

  long nI;

  long nJ;

  long nK;

  int nResult;



  nResult = 1;



  printf("Debut de lecture  : %s\n", GetTime(lpTime, 20));



  if (! SafeOpenFile("Input.txt", "rb", &lpInputFile)) goto the_end;

  if (! SafeOpenFile("TRIinput.txt", "wb", &lpOutputFile)) goto close_input;



  nInputSize = GetSizeOfFile(lpInputFile);



  lpFileContent = (char*)malloc(nInputSize + 1);

  if (! lpFileContent)

  {

    printf("Unable to allocate input buffer\n");

    goto close_output;

  }



  if (fread(lpFileContent, 1, nInputSize, lpInputFile) != nInputSize)

  {

    printf("Unable to read input file\n");

    goto free_content;

  }

  lpFileContent[nInputSize] = 0;



  /* Remplissage d'un tableau de pointeur sur les chaînes */

  lpSortingArray = NULL;

  bWasCrOrLf = 1;

  for (nI = 0; nI < nInputSize; nI++)

  {

    if ((lpFileContent[nI] != '\n') && (lpFileContent[nI] != '\r'))

    {

      if (bWasCrOrLf)

      {

        SetSize((void**)&lpSortingArray, 4, GetSize(lpSortingArray) + 1);

        lpSortingArray[GetSize(lpSortingArray) - 1] = &lpFileContent[nI];

        bWasCrOrLf = 0;

      }

    }

    else

      bWasCrOrLf = 1;

  }



  printf("Fin de lecture    : %s\n", GetTime(lpTime, 20));

  printf("Nombre de lignes  : %ld\n", GetSize(lpSortingArray));



  /* Tri */

  qsort(lpSortingArray, GetSize(lpSortingArray), sizeof(char*), Compare);



  printf("Fin de tri        : %s\n", GetTime(lpTime, 20));



  /* Génération du fichier de sortie en mémoire */

  lpResultContent = (char*)malloc(nInputSize + 1);

  if (! lpResultContent)

  {

    printf("Unable to allocate output buffer\n");

    goto free_content;

  }

  nK = 0;

  for (nI = 0; nI < GetSize(lpSortingArray); nI++)

  {

    bWasCrOrLf = 0;

    nJ = 0;

    while (1)

    {

      if ((lpSortingArray[nI][nJ] == '\r') ||

          (lpSortingArray[nI][nJ] == '\n'))

        bWasCrOrLf = 1;

      else if (bWasCrOrLf)

        break;

      lpResultContent[nK] = lpSortingArray[nI][nJ];

      nK++;

      nJ++;

    }

  }

  lpResultContent[nInputSize] = 0;



  if (fwrite(lpResultContent, 1, nInputSize, lpOutputFile) != nInputSize)

  {

    printf("Unable to write output file\n");

    goto free_result;

  }



  printf("Fin ecriture      : %s\n", GetTime(lpTime, 20));



  nResult = 0;

free_result:

  free(lpResultContent);

free_content:

  free(lpFileContent);

close_output:

  fclose(lpOutputFile);

close_input:

  fclose(lpInputFile);

the_end:

  return nResult;

}

-- Oui salut rt15 et les autres,

rt15 --> pour info oui on s'est déjà vu sur un autre post !

mon programme pascal en question a été compilé sur un DELL PowerEdger 2600 bi-processeurs (Intel Xeon 3Ghz, 3Go RAM, disque SCSI).

Le fichier de test à trier comporte exactement 3388634 lignes.
J'ai bien utilisé un Quicksort mais j'ai hésité sur un tri à bulles, peut être que les performances auraient été meilleures,
à voir.
Je vais déjà essayer de le compiler sur une machine 64 bits pour voir la difference.

Mon fichier source à trier gzippé fait ~ 21 Mo. Comment vous le faire passer, par mail ?


slider --