Rivaliser avec JSON.stringify - en en créant un personnalisé

Cela est apparu 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 génial
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 standardJSON.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 < num_runs; i++) {
    fn(...args);
  }

  const end_time = Date.now()
  return end_time - start_time
}


function performance_test(counts) {
  console.log("Starting performance test with", test_obj);

  for (const count of counts) {
    console.log("Testing", count, "times");

    const duration_std_json = time(JSON.stringify.bind(JSON), count, test_obj);
    console.log("\tStd lib JSON.stringify() took", duration_std_json, "ms");

    const duration_custom_json = time(json_stringify, count, test_obj);
    console.log("\tCustom json_stringify() took", duration_custom_json, "ms");
  }
}

const test_obj = {} // a deeply nested JS object, ommitted here for brevity 
const test_values = [
  12,
  "string test",
  [12, 34, 1],
  [12, true, 1, false],
  test_obj
];

validity_test(JSON.stringify, json_stringify, test_values);
performance_test([1000, 10_000, 100_000, 1000_000]);

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

Il peut fonctionner différemment sur différents systèmes, mais le rapport entre le temps nécessaire
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
ça!

Améliorer les performances

La première chose qui pourrait être corrigée est l'utilisation de la fonction map. Cela 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 chaîné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 pièces 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

Ça 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, c'est 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

1. créer un nouveau tampon de chaîne pour s'adapter à toute la chaîne combinée
2. copier les chaînes individuelles dans le tampon nouvellement créé

En utilisant nous-mêmes un Buffer et en écrivant les données directement là-bas, 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

1. Poussez l'adresse de retour dans la pile
2. pousser la référence de l'argument vers la pile
3. Dans la fonction appelée
   1. Supprimez la référence du paramètre de la pile
   2. Supprimez l'adresse de retour de la pile
   3. pousser la valeur de retour (la partie stringifiée) sur la pile
4. Dans la fonction appelante
   1. 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 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 !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!