Introduction à l'I/O complexité

Tout le monde se secoue ! 

J’ai commencé (il y a 21 minutes) la rédaction d’un article au doux nom de « Introduction à l’I/O complexité » et j’ai pour objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limites pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l’adresse suivante :

Merci !

Salut,

Je prends ma casquette « Staff » pour t’encourager ! Le sujet que tu traites dans ce tutoriel est, je trouve, souvent laissé au second plan, alors qu’il a une forte utilité pratique. Cela me ferait plaisir qu’il soit publié sur Zeste de Savoir.

Je ne suis pas spécialiste, donc je ne peux malheureusement pas te conseiller plus avant. Tout ce que je peux dire, c’est que ça fait écho à une de mes expériences récentes. Pour accélérer significativement un programme plus lent que l’attendu, il avait suffit d’inverser l’ordre de parcours des lignes et des colonnes dans les matrices.

Bon courage !

Hey !

Mais ce tutoriel est super ! Alors ok, il faut repasser sur les fautes mais j’aime beaucoup !

Bonjour,

Je suis content que ça semble vous intéresser et adapter à ce medium. J’avais peur que ce sujet soit un peu trop avancé parce ce qu’il est loin d’être canonique et davantage destiné à un public de doctorants.

J’ai corrigé de nombreuses fautes présentes dans le texte, j’espère qu’il est plus lisible maintenant :x J’étais "lost in translation" puisqu’il s’agit, en partie, d’une traduction d’un travail que j’ai précédemment effectué. Néanmoins, il est possible que des erreurs demeurent.

PS: J’ai eu du mal à trouver le "guide du contributeur", il devrait peut-être mis plus en avant ou, tout du moins, être mentioné sur le forum "Contenus en cours de rédaction".

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

J’avais oublié de mettre à jour la dernière fois

Merci pour cet article qui est très intéressant. Malheureusement il est difficile à aborder, alors que je suis sûr que les notions ne sont pas si complexes que ça. Je ne prétends que ça devrait bloquer la validation, mais c’est tout ce que je peux offrir pour le moment : des exemples de phrases (du début du texte) qui pourraient être clarifiées.

Dans cet article, nous retracerons rapidement les idées qui ont permis l’émergence de cette famille de modèles de calcul

De quelle famille de modèles parlons-nous ?

Ce sont alors davantage des aspects quantitatifs que qualitatifs.

De quels aspects parlons-nous ?

Le temps d’accès aux ressources est certes un des principaux défauts du modèle RAM, mais ce n’est pas ce qui a motivé ce champ d’étude à l’origine.

Je trouve qu’on a globalement plein de phrases comme ça qui pourraient être plus claires : je ne devrais pas me poser de questions en les lisant. Exemple de questions :

• On me dit au début que RAM est arrivé dans les années 90, alors pourquoi ça motiverait des travaux des années 70 ?
• De quel champ d’étude parle-t-on ici : RAM, EM, les modèles de calculs en général ?

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

J’espère avoir clarifié certains points.

Malheureusement il est difficile à aborder, alors que je suis sûr que les notions ne sont pas si complexes que ça.

Je n’ai pas non plus l’impression que ce sujet soit inabordable malgré qu’il demande quelques bases …

Merci, c’est beaucoup plus clair ! J’ai même pu commencer à comprendre les premiers algorithmes des modèles EM et cache-oblivious, et j’en suis assez fier. Je reste assez loin de pouvoir suivre les démonstrations, par contre.

Quelques nouvelles remarques :

• On pourrait dire quelque part que I/O désigne les entrées/sorties ?
• Master theorem : lien vers https://fr.wikipedia.org/wiki/Master_theorem pour clarifier duquel on parle ?
• typo : indépamment
• (et que permuter les éléments n’est pas cache-oblivious même sous cette propriété). <- dit avant d’introduire la notion de cache-obliviousness

Et j’ai aussi une question. Je comprends l’élégance du modèle cache-oblivious, et je vois pourquoi les algorithmes optimaux changent avec ce nouveau modèle. Mais en pratique, on va quand même utiliser les algorithmes optimaux pour EM, non ? Ou alors il peut y avoir des cas où on veut écrire des programmes qui utilisent des B-trees binaires ou dynamiques ?

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Merci Quentin pour les remarques ! Je suis content que ce sujet plaise enfin à quelqu’un

Je comprends l’élégance du modèle cache-oblivious, et je vois pourquoi les algorithmes optimaux changent avec ce nouveau modèle. Mais en pratique, on va quand même utiliser les algorithmes optimaux pour EM, non ?

La question est difficile. L’avantage du modèle cache-oblivious est qu’il s’affranchit complètement des paramètres, l’algorithme devient donc optimal par rapport à n’importe quelle configuration. Cela permet de supprimer les problèmes qui émergent avec des hiérarchies de caches d’un seul tenant puisqu’on sait que la situation est optimale entre chaque paire.

En pratique, on connaît (ou tout du moins, on a des bonnes idées sur) la configuration sur laquelle on va faire tourner l’algorithme. On peut donc mieux tuner les paramètres et battre les cache-oblivious. Il y a d’ailleurs un article sur le coût de la cache-obliviousness¹ qui essaye de quantifier le gain d’information théorique que l’on a lorsqu’on connaît les paramètres du problème a priori mais il est somme toute faible.

Mais le point principal est tout autre. Les algorithmes cache-oblivious sont des monstruosités à programmer alors que les EM sont nettement plus simples. Pour s’en convaincre, il suffit d’écrire un algorithme qui fusionne un nombre arbitraire de listes triées, on se confronte très vite à un mur. En EM, on est capable de fixer les variables et cela simplifie énormément l’algorithme.

Cette complexité algorithmique aura tendance à se traduire par une lenteur de l’algorithme dans les modèles temporels. Et ce qui intéresse les gens est essentiellement le temps d’exécution. La situation est d’ailleurs très claire avec le "list ranking problem", en complexité temporelle, on a un bête algorithme (il suffit de parcourir la liste) en O(n) (thèse de Wyllie, inventeur du modèle PRAM). Alors que si on tente de le rendre optimal en EM, la complexité temporelle passe à un O(n log n)².

Donc en résumé, ça dépend des situations et on benchmark =)

Ou alors il peut y avoir des cas où on veut écrire des programmes qui utilisent des B-trees binaires ou dynamiques ?

En petite aparté, Les B-trees peuvent être vus comme des généralisations des arbres binaires, l’expression "B-trees binaires" me choque =)

Là où c’est fabuleux, c’est quand les deux mondes (l’I/O et le temporel) se rencontrent. On arrive à un critère d’optimalité très fort. Le meilleur exemple sont les B-trees. On est en $\Theta_{\text{EM}}(\log_{B} N)$ et $\Theta_{\text{RAM}}(\log_{B} N)$. Seulement $\Theta(\log_{B} N) = \Theta(\log N)$ à une constante près. Or, les BST ont la même complexité temporelle mais on se rend compte que les red-black trees sont en réalité en $\Theta(\log 2N)$ et les AVL en $\Theta(\log 1.4N)$, là où les B-trees sont pratiquement en $\Theta(\log_{B} N)$ (si je me souviens bien). Mais, en pratique, les B-trees explosent complètement les performances des BST par le fait qu’ils exploitent le cache et minimisent le nombre de cache-miss.

La différence entre les B-trees statiques ou dynamiques résident dans la disposition en mémoire des éléments. Ceux statiques exploitent le van Embde Boas layout alors que les dynamiques sont plus proches de ceux qu’on aurait tendance à écrire naturellement. Et, en pratique, cette différence est marginale et ceux dynamiques sont mieux puisqu’ils offrent plus de fonctionnalités.

En résumé, il n’y a jamais de réponse absolue. D’un point de vue théorique, on va toujours préférer la solution la plus générale et la plus optimale. Et en pratique, on va devoir mesurer et tester différentes méthodes afin de trouver la meilleure à notre cas particulier.

Merci au Récap' communautaire #7 ! Sans lui, je n’aurai jamais entendu parler d’I/O complexité.

Et merci @Gawaboumga pour ta réponse qui est à la fois très claire et très intéressante. Et merci aussi pour tout le travail fourni suite à mes retours : j’ai beaucoup de chance.

J’essaie maintenant de comprendre la démonstration du théorème principal d’EM. (D’ailleurs, c’est un théorème important parce que les études des autres algorithmes mènent souvent à des permutations, ou il y a autre chose ?)

Maintenant, si nous effectuons un transfert en mémoire interne, nous pouvons apprendre où se situent ces $B$ éléments parmi le cache $M$, soit $\binom{M + B}{M}$. Au final, nous devons connaître la position de chacun des éléments ($N!$).

Je ne comprends pas comment on aboutit à $\binom{M + B}{M}$ et $N!$. Je n’ai pas de questions très utiles, mais je vais essayer quand même :

• $\binom{M + B}{M}$ représente un nombre de transferts ? On en a besoin pour quoi ?
• Concernant $N!$, je ne comprends pas non plus. C’est le nombre de permutations de N ? Pourquoi B n’intervient pas ?

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Je ne comprends pas comment on aboutit à $\binom{M + B}{M}$ et $N!$. Je n’ai pas de questions très utiles, mais je vais essayer quand même :

• $\binom{M + B}{M}$ représente un nombre de transferts ? On en a besoin pour quoi ?
• Concernant $N!$, je ne comprends pas non plus. C’est le nombre de permutations de N ? Pourquoi B n’intervient pas ?

Il est vrai que ça sortait un peu de nulle part. J’espère que c’est plus clair avec les nouvelles explications.

En bref, $\binom{M + B}{M} = \binom{M + B}{B}$ correspond au nombre de manière de placer le paquet de $B$ éléments dans notre cache qui, une fois fusionné, aura une taille $M+B$ et il faudra donc, dans le meilleur cas, évincer une cache line et de facto effectuer un transfert. $N!$ correspond quant à lui à toutes les configurations originelles de nos éléments avec chaque élément qui peut être mis n’importe où au départ. On part d’une configuration aléatoire et on veut arriver à ce que tous les éléments soient triés à la fin.

Désolé, mais je comprends toujours pas. En fait, même si je prends un exemple, je ne comprends pas l’algorithme utilisé dans la démonstration.

Par exemple, je prends N=10, M=6 et B=2, et je dis que le disque contient (9, 8) (7, 6) (5, 4) (3, 2) et (1, 0). Et je veux trier dans l’ordre croissant (une permutation comme un autre). Je transfère trois lignes pour remplir le cache, par exemple (9, 8), (5, 4) et (1, 0). Alors mon cache devient (0, 1) (4, 5) et (8, 9) parce que le tri dans le cache est gratuit ? Ensuite je fais un autre transfert, genre (7, 6), et j’arrive à dire que c’est entre (4, 5) et (8, 9) ?

C’est l’idée ou pas du tout ?

Il y a deux aspects:

1) L’algorithme montre une borne théorique de manière existentielle. Il existe un algorithme qui prend une permutation et la transforme en une autre en cette complexité mais il ne décrit pas comment y arriver. De la même manière qu’il est possible de montrer qu’un système d’équations différentielles possède une solution sans pour autant fournir une solution analytique. C’est quelque chose qu’on retrouve par exemple dans deux autres démonstrations:

• Imaginons que nous souhaitions trier une collection et que nous soyons capables de demander à un oracle si "x < y", sa seule réponse est "oui/non". À chaque étape, on va pouvoir effectuer deux embranchements (un pour oui et un pour non), on a donc une progression de type 2^k états possibles au bout de k choix. De l’autre côté, on doit être capable d’arriver à n’importe quelle configuration possible des N éléments. La question est combien faut-il de "k" (d’étapes) au minimum afin d’arriver à toutes ces configurations. La réponse est log_2{N!} -> N log N. C’est là une des démonstrations sur la complexité des tris (dans un modèle à comparaison). Mais ça ne définit pas un algorithme en particulier, les gens sont arrivés après avec les merge sort, quick sort, tournament sort, … et ont prouvé que la complexité de ces dits algorithmes correspondaient à la borne théorique et étaient donc "optimaux".
• Un autre problème est le "element distinctness problem", déterminer si tous les éléments sont différents. Il faut observer qu’on peut associer à chaque instance du problème un point dans l’espace à $\mathbb{Z}^N$ et qu’on souhaite qu’au final il existe N! feuilles menant à oui (ou non) à ce problème. On peut couper le polytope par des (hyper)plans et on se rend compte qu’il faut de nouveau N log N étapes pour déterminer la solution. L’algorithme consiste d’ailleurs à trier les éléments et à regarder s’il existe deux adjacents ayant la même valeur. Mais quid si nous n’avons que l’égalité et non l’inégalité ? L’algorithme naïf devient en N^2 et est-ce qu’il en existe un en N log N ?

2) Si on veut trier (9, 8), (7, 6), (5, 4), (3, 2) et (1, 0) dans l’ordre croissant et avec la configuration N=10, M=6 et B=2. On peut par exemple employer "merge-sort". On met (9, 8), (7, 6) en cache, on produit (6, 7), (8, 9) en mémoire. On fait le même avec la suite, (2, 3), (4, 5). Et on se retrouve avec (6, 7), (8, 9), (2, 3), (4, 5) et (0, 1) au bout du premier parcours.

On recommence en fusionnant les listes de taille 2. On met (2, 3) et (6, 7) en mémoire, on itère sur les deux listes en même temps et on va chercher le bloc suivant lorsqu’on arrive au bout d’un des blocs (ça risque d’être compliqué de swap avec seulement 3 places). On a (2, 3), (4, 5), (6, 7), (8, 9) et (0, 1). Et on termine par les tailles 4 et on a fini.

D’accord, merci, ça aide bien, et je comprends mieux la démonstration !

Même si je ne peux pas attester qu’il n’y a pas d’erreur, est-ce qu’on pourrait publier ce super article ? Ce serait du gâchis de le laisser derrière un login-wall.

Il y a juste une passe à faire sur les fautes de forme.

UP de l’espace ? Je dois encore apporter des modifications ou c’est bon, M. aabu ?

Bonsoir,

L’affaire est un peu embarrassante.

Pour ne rien te cacher, j’ai pris en validation le tuto avec l’objectif de trouver un validateur ad hoc… que nous n’avons pas trouvé.

J’aurai bien pris en charge moi-même, faute de meilleure solution, mais je n’ai pas le temps en ce moment.

J’ai appelé à l’aide mes collègues de la validation, et personne n’a de temps pour l’instant…

Je suis très embêté de faire attendre ton tuto sans raison valable, surtout qu’il a l’air très bien à première vue.

Bonjour,

La bêta du contenu « Introduction à l’I/O complexité » a été désactivée.