Discussion :

[Neitsa]

Bonjour à tous,

Désolé si la question est un peu off-topic au niveau de l'algorithme, mais ca n'est pas en rapport avec un langage spécifique et ca se rapproche de la "queueing theory".

Aujourd'hui avec des collègues nous discutions de l'implémentation de l'endianness et des piles (stacks) au niveau des processeurs.

Si l'endianness (qu'elle soit big, little ou middle) à ses pros et ses contras sans toutefois qu'un choix soit largement préférable à un autre se dégage, nous nous posions la question quant au choix des ingénieurs pour l'implémentation de piles au niveau des CPUs.

Il apparait que la grande majorité des processeurs utilisent le type LIFO (Last In, First Out) et non FIFO (First In, First Out), mais les questions que je me pose sont :

Pourquoi le choix du type LIFO s'impose sur la majorité des processeurs ?

Quel sont les avantages du type LIFO par rapport au type FIFO (et ce, uniquement dans le cadre de l'implémentation d'un processeur) ? [outre le banal "1er arriver premier sorti, ou Dernier arrivé premier sorti"]

Est-ce que la récursion est un facteur déterminant dans le choix du type de pile (la récursion étant peut être plus aisée avec les piles LIFO) ?

Finalement, si le type de pile LIFO est si répandu, quel avantage à utiliser le FIFO ? (et ce dans un cadre plus général, aussi bien au niveau des processeurs, que dans l'utilisation de piles pour utiliser des données avec un langage (ie. <stack> du C++, ou toute implémentation de pile dévolue à un langage)

Je vous serais reconnaissant si vous aviez des pistes de réflexion à ce sujet, c'est une question qui m'intéresse.

Merci à vous.

[2Eurocents]

Un processeur utilise aussi bien des piles (LIFO) que des files (FIFO). En effet, les instructions à traiter, par exemple, sont "enfilées" dans un pipeline, qui est donc un FIFO.

Une autre remarque : pour ce qui est de l'implémentation, une file (FIFO) est plus complexe à gérer qu'une pile (LIFO).

En effet, une pile n'a que peu de paramètres :
- une base (qui peut ne pas exister si la pile est logée dans une zone "conventionnelle").
- un pointeur (c'est la seule donnée réellement nécessaire à la gestion de pile)
- un sommet (qui peut aussi ne pas exister ... c'est la fin de la zone de pile ... aller au delà provoque un débordement).

Une file doit disposer de paramètres supplémentaires, au moins parce que deux pointeurs sont nécessaires. Un pour pointer les éléments à sortir de la pile (les premiers entrés) et un pour pointer l'emplacement auquel ajouter les nouveaux éléments (à l'autre boût).

En outre, une pile part de sa base et croit/décroit dans l'intervalle entre la base et le sommet.

A contrario, une file à ses deux pointeurs qui se courrent après, mais qui risquent de buter sur une limite (une sorte de sommet, aussi), auquel cas il faut gérer la zone de file comme un anneau et repartir au départ ... cela peut s'avérer complexe.


En outre, tous ceux qui ont pratiqué certains langages comme le FORTH, ou qui ont manipulé les calculatrices HP à notation polonaise inversée, savent intuitivement que la structure de pile est extraordinairement efficace dans la mise en place de traitements.

Je n'ose imaginer un parcours récursif, dans un arbre, en utilisant une file de noeuds, et pas une pile, pour remonter aux embranchements après avoir lu la totalité des feuilles .

Voici quelques éléments d'appréciations, mais la discussion est vaste.


Finalement, le choix entre les structures FIFO et LIFO dépend de ce que tu as à faire comme traitement.

Purement séquentiel -> FIFO
Arborescent, récursif, backtrack possible -> LIFO

[d-jo]

Bonjour,

La question n'est-elle pas tout simplement celle de la réentrance du code et de la sauvegarde du contexte ?
Je ne vois personnellement pas de solution plus efficace qu'une pile LIFO pour répondre à ces problèmes.

Avec un pile tu peux mettre en place des mécanismes qui permettent d'assurer l'intégrité des données quels que soit le scénario de changement de contexte.

Si tous tes modules de codes sont écrits de la façon suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 
Empiler la valeur des registres que je vais utiliser 
 
Réserver une place dans la pile pour mes variables 
 
Traitement 
 
Libérer mes variables 
 
Dépiler le contexte

Ils peuvent s'enchaîner dans n'importe quel ordre et à n'importe quel moment et même s'appeler eux mêmes. Tu n'as pas besoin de prévoir tous les cas. A tous les coups ça marche.

A+
Joris

[Jean-Marc.Bourguet]

Il apparait que la grande majorité des processeurs utilisent le type LIFO (Last In, First Out) et non FIFO (First In, First Out), mais les questions que je me pose sont :

Tu connais une exception? Il faut se poser la question "a quoi servent ces instructions?" Les processeurs que je connais qui ont des instructions de manipulation de pile explicites (je veux dire des choses comme push et pop) se servent eux-meme de la pile pour gerer les appels aux routines. Tu admettras qu'u'on quitte les routes dans l'ordre inverse dans lequel on y en rentrer, donc une pile est tout a fait adaptee. Les processeurs qui ont des modes d'adressage a {pre,post}{in,de}crementation gerent aussi bien les piles que les files.

Est-ce que la récursion est un facteur déterminant dans le choix du type de pile

Le fait que l'utilisation d'une pile pour gerer les appels de routines facilite l'implementation de la recursion est plutot un effet de bord. On a abandonne les convention d'appel modifiant le code essentiellement parce que ce genre de convention empeche le partage de code entre plusieurs processus.

Finalement, si le type de pile LIFO est si répandu, quel avantage à utiliser le FIFO ?

Je sens de la confusion. On n'a generalement pas a choisir entre une pile ou une file, mais l'algo demande l'un ou l'autre. On peut d'ailleurs considerer les deux comme etant des cas particuliers des files a priorite (dans les parcours de graphe, l'utilisation d'une pile donne un parcours en profondeur, d'une file un parcours en largeur et d'une file a priorite quelque chose d'autre qui peut etre plus adapte).