Multitâche sans thread 1/5 – Générateur


Programmation réactive

Depuis un moment, nous vous proposons une série d’articles sur le modèle réactif. Nous avons regardé d’où vient ce modèle et l’impact sur la gestion des threads. Mais comment ne pas se noyer dans un code trop complexe ?

Nous avons vu qu’une approche réactive, basée sur le traitement rapide et non bloquant d’événements, permettait des gains notables de performance.

Du point de vue du développeur, il n’est pas toujours facile de rédiger du code basé sur ce paradigme. En effet, comme aucun traitement ne doit être bloquant, il est nécessaire d’enchaîner des call-backs pour le moindre traitement un peu complexe.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function archiveOrders(date, cb) {
  db.connect(
    function(err, conn)
    { if (err) return cb(err);
      conn.query("select * from orders where date < ?", [date],
        function(err, orders)
        { if (err) return cb(err);
            helper.each(orders,
              function(order, next)
              { conn.execute("insert into archivedOrders ...", [order.id, ...],
              function(err)
              { if (err) return cb(err);
                conn.execute("delete from orders where id=?", [order.id],
                function(err)
                { if (err) return cb(err);
                  next();
                });
              });
        },
        function()
        { console.log("orders have been archived");
          cb();
        });
    });
  });
}

Ce type de code peu lisible est souvent appelé : callback hell. Le lien explique que finalement, c’est un problème de qualité de code et qu’il est facile à résoudre avec quelques patterns.

Néanmoins, les langages de développement proposent des évolutions pour éviter ce modèle de développement. L’objectif est de rédiger un traitement en apparence linéaire, mais dont chaque portion de code entre deux appels bloquants est exécutée dans un hard-thread différent.

Il existe cinq approches permettant de faciliter la rédaction de programmes réactifs :

  • Générateur
  • Pattern Continuation
  • Co-routine
  • Pipelines / compositions
  • Await / async

Dans cette série d’articles, nous allons parcourir ces différentes solutions pour différents langages de développement. Commençons par la première approche.

Générateur

Un générateur est une routine spéciale permettant de gérer l’itération d’une boucle. La routine produit des valeurs à chaque étape et mémorise le contexte de la boucle pour pouvoir la reprendre plus tard.

Voici un exemple de générateur en Python :

1
2
3
4
5
# Filtre les chaines débutant avec ##
def filter2sharps(iterator):
  for l in iterator:
    if l.startswith("##"):
      yield l

Ce générateur parcourt un itérateur et n’émet une valeur que si elle commence par un double dièse. L’instruction yield (produire en français) est équivalente à un return, à la différence près qu’elle permet de mémoriser l’état de la boucle.

Un usage de ce générateur peut être celui-ci :

1
2
3
4
5
# Utilise le filtre sur un fichier
source= file( ... )
for line in filter2sharps( source.readlines() ):
  print line
source.close()

Dans cet exemple, la boucle parcourt un fichier et affiche uniquement les lignes compatibles avec le générateur qui joue le rôle de filtre. La boucle du générateur est mise « en pause » après chaque invocation de filter2sharps, lors du yield.

Le compilateur du langage effectue une transformation du code du générateur, comme nous allons le voir. Par exemple, le générateur C# suivant est compilé comme ci-dessous.

using System;
using System.Collections;
class Test {
  // Une fonction
  static IEnumerator GetCounter() {
    for (int c = 0; c < 10; c++) {
      yield return c;
    }
  }
}

Le code produit par le compilateur est proche de ce code :

// Une classe
private class GetCounter : IEnumerator
{
  private int _state = 0;
  public int _current;
  private int c = 0;
  public bool MoveNext() {
    switch (_state) {
      case 0: // Dans la boucle
        if (c < 10) {
          _current = c;
          c++;
          return true;
        }
        _state = -1;
        break;
    }
    return false;
  }
}

static IEnumerator GetCounter() {
    return new GetCounter();
}

On retrouve tous les éléments classiques d’une boucle : l’initialisation, la comparaison, l’incrémentation. Mais le code est transformé en automate à états et en objet pour mémoriser le contexte. L’appelant peut maintenir l’itérateur en vie, ce qui maintient le contexte de la boucle.

La transformation d’un générateur en Python est similaire.

1
2
3
4
5
6
7
8
9
# a generator that yields items
# instead of returning a list
def firstn(n):
  num = 0
  while num &lt; n:
    yield num
    num += 1
 
sum_of_first_n = sum(firstn(1000000))

Est généré ainsi :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class firstn(object):
  def __init__(self, n):
    self.n = n
    self.num, self.nums = 0, []
  def __iter__(self):
    return self
  # Python 3 compatibility
  def __next__(self):
    return self.next()
  def next(self):
    if self.num &lt; self.n:
      cur, self.num = self.num, self.num+1
      return cur
    else:
      raise StopIteration()

Javascript 1.7 propose maintenant des générateurs. Pour cela, les functions doivent être suffixées d’une étoile.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Javascript
// Generateur infini
function* fibonacci() {
  let [prev, curr] = [0, 1];
  for (;;) {
    [prev, curr] = [curr, prev + curr];
    yield curr;
  }
}
for (n of fibonacci()) {
  // truncate the sequence at 1000
  if (n &lt; 1000) break;
  print(n);
}

Un générateur Javascript est également utilisé par des frameworks pour proposer des co-routines (décrit dans un prochain article).

Pour la programmation réactive

Pour la programmation réactive, nous pouvons les utiliser comme une brique de base pour implémenter un scheduler.

Par exemple, dans l’extrait suivant (l’intégralié du source est présent ici), les appels théoriquement bloquants vers les API fichiers sont remplacés par des invocations asynchrones. Grâce à l’utilisation de yield return, ces appels asynchrones semblent parfaitement séquentiels.

1
2
3
4
5
6
7
8
9
10
11
12
13
static IEnumerable CopyFileAsync(string origin, string destination)
{
    Console.WriteLine(String.Format("{0} - Read", origin));
    var readtask = ReadFileAsync(origin);
    yield return readtask;
 
    Console.WriteLine(String.Format("{0} - Write", origin));
    var file_content = readtask.Value;
    yield return WriteFileAsync(destination, file_content);
 
    Console.WriteLine(String.Format("{0} -  Work finished", origin));
    yield break;
}

Dans l’éxécution ci-dessous, nous appellons ce code 3 fois. Vous pouvez constater que les appels sont entrelacés même si le code parait écrit de façon séquentielle.

Exécution entrelacée
Un simple scheduleur maison permet alors d’entrelacer différents générateurs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void Main(string[] args)
{
  // Create pseudo threads
  var contexts = new List()
  {
    AsyncTask.Run(() =&gt; CopyFileAsync("Resources/file1.txt", "Resources/file1_copy.txt")),
    AsyncTask.Run(() =&gt; CopyFileAsync("Resources/file2.txt", "Resources/file2_copy.txt")),
    AsyncTask.Run(() =&gt; CopyFileAsync("Resources/file3.txt", "Resources/file3_copy.txt")),
  };
 
  // Sheduler - Un seul thread pour plusieurs traitements en //
  while (contexts.Any(at =&gt; at.Done == false))
  {
    foreach (var elt_task in contexts)
    {
      if (elt_task.CanMoveNext())
      {
        elt_task.MoveNext();
      }
    }
  }
}

Il faut alors proposer des méthodes ayant l’apparence de méthodes bloquantes, mais qui sont en réalité non-bloquantes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static AsyncStep&lt;byte[]&gt; ReadFileAsync(string origine)
{
  var asyncTask = new AsyncStep&lt;byte[]&gt;() { State = AsyncState.Await };
 
  var file = File.OpenRead(origine);
  var data = new byte[file.Length];
 
  asyncTask.Value = data;
  file.BeginRead(data, 0, (int) file.Length, (a) =&gt;
  {
    file.Close();
    // Update state
    asyncTask.State = AsyncState.Continue;
  }, null);
 
  return asyncTask;
}

Notre collègue Florent Jaby propose une approche similaire en Javascript pour node.js.

Pour conclure

Le tableau suivant résume les avantages et inconvénients de cette approche.

Générateur
Usages Dans une boucle
Limitations Retourne un Itérateur Local à une fonction
Points forts Généré

Un générateur est un automate à états généré lors de la compilation d’une boucle. Il s’agit d’un producteur d’éléments qui se met en pause a chaque itération, en attente de l’invocation suivante.

Dans le prochain article de la série, nous traiterons de l’approche « continuation ».

Philippe PRADOS, Fabien Arcellier et l’équipe « Réactive »