Cela s'est produit lors d'une discussion avec mon ami à propos de la récursion. Pourquoi ne pas construire
une méthode Javascript JSON.stringify comme exercice de programmation récursive ? Ça a l'air d'être un super
idée.

J'ai rapidement rédigé la première version. Et ça a été horriblement performant ! Le
le temps requis était environ 4 fois supérieur à celui du standard JSON.stringify.

La première ébauche

function json_stringify(obj) {
  if (typeof obj == "number" || typeof obj == "boolean") {
    return String(obj);
  }

  if (typeof obj == "string") {
    return `"${obj}"`;
  }

  if (Array.isArray(obj)) {
    return "["   obj.map(json_stringify).join(",")   "]";
  }

  if (typeof obj === "object") {
    const properties_str = Object.entries(obj)
      .map(([key, val]) => {
        return `"${key}":${json_stringify(val)}`;
      })
      .join(",");
    return "{"   properties_str   "}";
  }
}

En exécutant ce qui suit, nous pouvons voir que notre json_stringify fonctionne comme
attendu.

const { assert } = require("console");
const test_obj = {
  name: "John Doe",
  age: 23,
  hobbies: ["football", "comet study"]
};

assert(json_stringify(test_obj) === JSON.stringify(test_obj))

Pour tester plus de scénarios et plusieurs exécutions pour avoir une idée moyenne de la façon dont notre
le script s'exécute, nous avons créé un script de test simple !

Un script de test simple

function validity_test(fn1, fn2, test_values) {
  for (const test_value of test_values) {
    assert(fn1(test_value) == fn2(test_value));
  }
}

function time(fn, num_runs = 1, ...args) {
  const start_time = Date.now()

  for (let i = 0; i 


En exécutant ceci, nous obtenons les horaires comme suit.


Testing 1000 times
    Std lib JSON.stringify() took 5 ms
    Custom json_stringify() took 20 ms
Testing 10000 times
    Std lib JSON.stringify() took 40 ms
    Custom json_stringify() took 129 ms
Testing 100000 times
    Std lib JSON.stringify() took 388 ms
    Custom json_stringify() took 1241 ms
Testing 1000000 times
    Std lib JSON.stringify() took 3823 ms
    Custom json_stringify() took 12275 ms




Le fonctionnement peut être différent sur différents systèmes, mais le rapport entre le temps nécessaire et 

par std JSON.strngify à celui de notre json_stringify personnalisé devrait être d'environ 
1:3 - 1:4

Cela pourrait aussi être différent dans un cas intéressant. Lisez la suite pour en savoir plus sur 

que!

  
  
  Améliorer les performances


La première chose qui pourrait être corrigée est l'utilisation de la fonction map. Il crée

nouveau tableau de l'ancien. Dans notre cas d'objets, il s'agit de créer un tableau de

Propriétés d'objet stringifiées JSON hors du tableau contenant les entrées d'objet.

Une chose similaire se produit également avec la stringification des éléments du tableau.

Nous devons parcourir les éléments d'un tableau, ou les entrées d'un objet ! Mais

nous pouvons ignorer la création d'un autre tableau juste pour rejoindre les parties stringifiées JSON.

Voici la version mise à jour (uniquement les parties modifiées affichées par souci de concision)


function json_stringify(val) {
  if (typeof val === "number" || typeof val === "boolean") {
    return String(val);
  }

  if (typeof val === "string") {
    return `"${val}"`;
  }

  if (Array.isArray(val)) {
    let elements_str = "["

    let sep = ""
    for (const element of val) {
      elements_str  = sep   json_stringify(element)
      sep = ","
    }
    elements_str  = "]"

    return elements_str
  }

  if (typeof val === "object") {
    let properties_str = "{"

    let sep = ""
    for (const key in val) {
      properties_str  = sep   `"${key}":${json_stringify(val[key])}`
      sep = ","
    }
    properties_str  = "}"

    return properties_str;
  }
}




Et voici maintenant le résultat du script de test


Testing 1000 times
        Std lib JSON.stringify() took 5 ms
        Custom json_stringify() took 6 ms
Testing 10000 times
        Std lib JSON.stringify() took 40 ms
        Custom json_stringify() took 43 ms
Testing 100000 times
        Std lib JSON.stringify() took 393 ms
        Custom json_stringify() took 405 ms
Testing 1000000 times
        Std lib JSON.stringify() took 3888 ms
        Custom json_stringify() took 3966 ms




Cela a l'air beaucoup mieux maintenant. Notre json_stringify personnalisé ne prend que 3 ms

plus que JSON.stringify pour stringifier un objet profondément imbriqué 10 000 fois.

Même si ce n'est pas parfait, il s'agit d'un délai acceptable.

  
  
  Presser davantage ??


Le retard actuel pourrait être dû à toutes les créations et concaténations de chaînes 

ça arrive. Chaque fois que nous exécutons elements_str = sep json_stringify(element)

nous concaténons 3 chaînes.

La concaténation de chaînes est coûteuse car elle nécessite

création d'un nouveau tampon de chaîne pour s'adapter à l'ensemble de la chaîne combinée
copier les chaînes individuelles dans le tampon nouvellement créé
En utilisant nous-mêmes un Buffer et en y écrivant les données directement, cela pourrait nous donner

une amélioration des performances. Puisque nous pouvons créer un grand tampon (disons 80 caractères)

puis créez de nouveaux tampons pour contenir 80 caractères de plus lorsqu'ils sont épuisés.

Nous n'éviterons pas complètement la réaffectation/copie des données, mais nous le ferons

réduire ces opérations.

Un autre retard possible est le processus récursif lui-même ! Plus précisément le

appel de fonction qui prend du temps. Considérez notre appel de fonction json_stringify(val)

qui n'a qu'un seul paramètre.

  
  
  Comprendre les appels de fonction


Les étapes seraient

Pousser l'adresse de retour vers la pile
pousser la référence de l'argument vers la pile
Dans la fonction appelée

Supprimez la référence du paramètre de la pile
Supprimez l'adresse de retour de la pile
pousse la valeur de retour (la partie stringifiée) sur la pile

Dans la fonction appelante

Supprimez la valeur renvoyée par la fonction de la pile

Toutes ces opérations ont lieu pour garantir que les appels de fonction se produisent, ce qui ajoute du CPU

frais.

Si nous créons un algorithme non récursif de json_stringify toutes ces opérations

répertorié ci-dessus pour l'appel de fonction (multiplié par le nombre de ces appels) serait 

réduit à néant.

Cela peut être une tentative future. 

  
  
  Différences de version de NodeJs


Une dernière chose à noter ici. Considérez la sortie suivante du script de test


Testing 1000 times
        Std lib JSON.stringify() took 8 ms
        Custom json_stringify() took 8 ms
Testing 10000 times
        Std lib JSON.stringify() took 64 ms
        Custom json_stringify() took 51 ms
Testing 100000 times
        Std lib JSON.stringify() took 636 ms
        Custom json_stringify() took 467 ms
Testing 1000000 times
        Std lib JSON.stringify() took 6282 ms
        Custom json_stringify() took 4526 ms




Notre json_stringify personnalisé a-t-il simplement mieux fonctionné que le standard NodeJs

JSON.stringify ???

Eh bien oui ! Mais il s'agit d'une ancienne version de NodeJs (v18.20.3). Il s'avère que pour

cette version (et inférieure aussi peut-être) notre json_stringify sur mesure fonctionne

plus rapide que celui de la bibliothèque standard !

Tous les tests de cet article (sauf ce dernier) ont été réalisés avec 
Nœud v22.6.0

Les performances de JSON.stringify sont passées de la v18 à la v22. C'est tellement génial

Il est également important de noter que notre script a mieux fonctionné dans NodeJs v22.

Cela signifie donc que NodeJs a également augmenté les performances globales du runtime.

Il est possible qu'une mise à jour ait eu lieu au niveau du moteur V8 lui-même.

Eh bien, cela a été une expérience agréable pour moi. Et j'espère que ce sera pour

toi aussi. Et au milieu de tout ce plaisir, nous avons appris une chose ou deux !

Continuez à construire, continuez à tester !