Parallélisation du code

Problématique

Le programme repose sur le traitement d'un grand nombre de fichiers XML, qui peuvent mettre du temps à être chargé en mémoire, et le traitement de ce format de données est gourmant en temps CPU.

Comme le temps de traitement de mes fichiers était très long (notamment à cause du fait que je traitais des fichiers énormes qui ne devaient pas être inclus), j'ai décidé de tenter de paralléliser le code afin de réduire le temps d'exécution total du programme.

Comme l'interpréteur Perl est au moins aussi mauvais que le langage qu'il interprète, il ne s'arrange pas pour exploiter de lui-même plusieurs cores ou CPU, comme le ferait par machine BEAM (la VM d'Erlang) par exemple.

Il faut donc le faire explicitement. Dans la plupart des langages, on penserait pour cela à utiliser des threads (aussi appelés processus légers). Et c'est faisable en Perl aussi, mais en me renseignant sur le sujet, je suis tout d'abord tombé sur la création de nouveaux processus, au moyen de fork.

La méthode que j'ai utilisée fait usage de la classe Parallel:ForkManager, qui n'est qu'un wrapper autour de l'appel système fork. Les processus créés utilisent de facto des espaces mémoires différents pour l'écriture (il est fait usage de la technique de copy on write par le système, d'où un faible coût de création des processus) ce qui empêchent de les faire travailler sur une même structure de données. Un premier coût est donc la sérialisation et la désérialisation dans un fichier pour passer les résultats au processus père.

Ceci dit, j'ai pû remarquer expérimentalement que ce coût était négligeable dans notre cas, en comparant les temps d'exécution entre des exécutions qui utilisent un dossier temporaire pour la sérialisation présent sur le disque dur et d'autres où il est situé sur un ramdisk.

Partition de l'ensemble des données

Afin de nourrir les différents processus, il est nécessaire au préalable de partitionner l'ensemble des données à traiter en N parts qu'on essaiera de faire les plus égales possibles.

Pour cela j'ai créé une version particulière du parcours de l'arborescence dans laquelle il existe une fonction qui va se charger construire une liste de répertoires. Il est possible de choisir la profondeur à laquelle descend la procédure pour établir la liste.

Dans le cas de nos données, une profondeur de 1 construit la liste des dossiers qui correspondent aux mois de l'année.

# construit une liste des répertoires contenus dans le dossier passé en paramètre
# avec une profondeur maximale
sub build_subdir_list {
    my ($dir, $list_ref, $max_depth) = @_;
    build_subdir_list_helper($dir, $list_ref, $max_depth - 1, 0);
}

sub build_subdir_list_helper {
    my ($dir, $list_ref, $max_depth, $depth) = @_;
  
    opendir(DIR, $dir) or die "can't open $dir: $!\n";
    my @files = readdir(DIR);
    closedir(DIR);

    foreach my $file (@files) {    
        next if $file =~ /^\.\.?$/;
        
        $file = $dir."/".$file;
        if (-d $file && ($depth < $max_depth)) {
            build_subdir_list_helper($file, $list_ref, $max_depth, $depth + 1);
        }
        else {
            if(-d $file) {
                push(@$list_ref, $file);
            }
        }
    }
}

Le code itère ensuite sur cette liste et crée un processus par dossier. Le composant ForkManager se charge de respecter la contrainte qui lui est passée en paramètre du nombre maximal de processus fils concurrents.

Fusion des résultats

Puisque les fichiers sont traités en parallèle, il faut à un moment donné réunir les différentes données dans une seule liste afin de passer à l'étape de traitement suivante, qui est d'écrire les fichiers générés.

La fusion d'un nombre raisonnable de listes se fait rapidement grâce à la fonction push de Perl. Avec une implémentation sous forme de liste chaînée, c'est effectivement une opération rapide où il suffit de déplacer le pointeur de fin de liste vers la tête de la liste à concaténer.

En revanche, le coût de filtrement des doublons est prohibitif, tout du moins comme je l'avais fait avec l'utilisation de l'opérateur ~~ et une itération sur tous les éléments de toutes les listes résultants pour créer une liste sans doublons.

Car si on peut empêcher l'ajout au sein d'un processus, rien ne dit que l'élément ne sera pas présent dans les résultats de plusieurs processus. Il faut donc nécessairement le reporté à la fin. Mais il s'agit d'une liste d'environ 300 000 chaînes de caractères de tailles diverses.

Constat final

En conclusion, c'est le manque de structures de données thread-safe (et lock free tant qu'à faire) dans le langage et dans sa bibliothèque standard qui rend diffile (pour le programmeur) de paralléliser le code. Cela alourdit donc la logique nécessaire dans la fusion et la rend en pratique impraticable. À tout le moins en utilisant des tableaux, ce qui n'est pas forcément la structure à utiliser en Perl quand on veut se prémunir des doublons avec efficacité.

En C#, on dispose de la Task Parallel Library, qui permet d'adresser ces problématiques de manière très productive.