À quelle fréquence le seq est-il utilisé dans le code de production Haskell?

23

J'ai une certaine expérience de l'écriture de petits outils dans Haskell et je le trouve très intuitif à utiliser, en particulier pour écrire des filtres (utilisant interact) qui traitent leur entrée standard et la dirigent vers la sortie standard.

Récemment, j'ai essayé d'utiliser un tel filtre sur un fichier qui était environ 10 fois plus gros que d'habitude et j'ai eu une Stack space overflowerreur.

Après avoir fait quelques lectures (par exemple ici et ici ), j'ai identifié deux lignes directrices pour économiser de l'espace de pile (Haskellers expérimentés, veuillez me corriger si j'écris quelque chose qui n'est pas correct):

  1. Évitez les appels de fonction récursifs qui ne sont pas récursifs (c'est valable pour tous les langages fonctionnels qui prennent en charge l'optimisation des appels de queue).
  2. Introduisez seqpour forcer une évaluation précoce des sous-expressions afin que les expressions ne deviennent pas trop grandes avant d'être réduites (ceci est spécifique à Haskell, ou au moins aux langues utilisant l'évaluation paresseuse).

Après avoir introduit cinq ou six seqappels dans mon code, mon outil fonctionne à nouveau sans problème (également sur les données plus volumineuses). Cependant, je trouve que le code d'origine était un peu plus lisible.

Comme je ne suis pas un programmeur Haskell expérimenté, je voulais demander si l'introduction seqde cette manière est une pratique courante et à quelle fréquence on verra normalement seqdans le code de production Haskell. Ou existe-t-il des techniques qui permettent d'éviter d'utiliser seqtrop souvent tout en utilisant peu d'espace de pile?

Giorgio
la source
1
Des optimisations comme celle que vous avez décrite vont presque toujours rendre le code un peu moins élégant.
Robert Harvey
@Robert Harvey: Existe-t-il des techniques alternatives pour limiter l'utilisation de la pile? Je veux dire, j'imagine que je dois réécrire mes fonctions différemment, mais je n'ai aucune idée s'il existe des techniques bien établies. Ma première tentative a été d'utiliser des fonctions récursives de queue, ce qui m'a aidé mais ne m'a pas permis de résoudre complètement mon problème.
Giorgio

Réponses:

17

Malheureusement, il y a des cas où l'on doit utiliser seqpour obtenir un programme efficace / bien fonctionner pour de grandes données. Donc, dans de nombreux cas, vous ne pouvez pas vous en passer dans le code de production. Vous pouvez trouver plus d'informations dans Real World Haskell, Chapitre 25. Profilage et optimisation .

Cependant, il existe des possibilités pour éviter d'utiliser seqdirectement. Cela peut rendre le code plus propre et plus robuste. Quelques idées:

  1. Utilisez plutôt des conduits , des tuyaux ou des itérésinteract . IO paresseux est connu pour avoir des problèmes avec la gestion des ressources (pas seulement la mémoire) et les itérés sont conçus exactement pour surmonter cela. (Je suggérerais d'éviter les E / S paresseux, quelle que soit la taille de vos données - voir Le problème des E / S paresseuses .)
  2. Au lieu d'utiliser seqdirectement (ou de concevoir vos propres) combinateurs tels que foldl ' ou foldr' ou des versions strictes de bibliothèques (telles que Data.Map.Strict ou Control.Monad.State.Strict ) qui sont conçues pour des calculs stricts.
  3. Utilisez l' extension BangPatterns . Il permet de remplacer seqpar une correspondance stricte des motifs. La déclaration de champs constructeurs stricts pourrait également être utile dans certains cas.
  4. Il est également possible d'utiliser des stratégies pour forcer l'évaluation. La bibliothèque de stratégies est principalement destinée aux calculs parallèles, mais possède également des méthodes pour forcer une valeur sur WHNF ( rseq) ou NF complet ( rdeepseq). Il existe de nombreuses méthodes utilitaires pour travailler avec des collections, combiner des stratégies, etc.
Petr Pudlák
la source
+1: Merci pour les conseils et liens utiles. Le point 3 semble assez intéressant (et la solution la plus simple à utiliser pour moi en ce moment). En ce qui concerne la suggestion 1, je ne vois pas comment éviter les E / S paresseux peut améliorer les choses: pour autant que je sache, les E / S paresseux devraient être mieux pour un filtre qui est censé traiter un flux de données (éventuellement très long).
Giorgio
2
@Giorgio J'ai ajouté un lien vers Haskell Wiki sur les problèmes avec Lazy IO. Avec IO paresseux, vous pouvez avoir du mal à gérer les ressources. Par exemple, si vous ne lisez pas entièrement l'entrée (comme en raison d'une évaluation paresseuse), le descripteur de fichier reste ouvert . Et si vous allez fermer le descripteur de fichier manuellement, il arrive souvent qu'en raison d'une lecture paresseuse de l'évaluation, il soit reporté et que vous fermiez le descripteur avant de lire l'intégralité de l'entrée. Et, il est souvent assez difficile d'éviter les problèmes de mémoire avec les E / S paresseux.
Petr Pudlák
J'ai récemment rencontré ce problème et mon programme manquait de descripteurs de fichiers. J'ai donc remplacé IO paresseux par IO strict en utilisant strict ByteString.
Giorgio