Konkurrieren Sie mit JSON.stringify – indem Sie ein benutzerdefiniertes erstellen

Dies kam während einer Diskussion mit meinem Freund über Rekursion zur Sprache. Warum nicht
bauen? eine Javascript JSON.stringify-Methode als rekursive Programmierübung? Scheint großartig zu sein
Idee.

Ich habe schnell die erste Version entworfen. Und es hat schrecklich funktioniert! Das
Der Zeitaufwand betrug etwa das Vierfache des Standards JSON.stringify.

Der erste Entwurf

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 + "}";
  }
}

Indem wir Folgendes ausführen, können wir sehen, dass unser json_stringify wie folgt funktioniert
erwartet.

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))

Um mehr Szenarien und mehrere Durchläufe zu testen, um eine durchschnittliche Vorstellung davon zu bekommen, wie unser
Nachdem das Skript ausgeführt wurde, haben wir ein einfaches Testskript erstellt!

Ein einfaches Testskript

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]);

Wenn wir das ausführen, erhalten wir die Zeitangaben wie folgt.

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

Es kann auf verschiedenen Systemen unterschiedlich laufen, aber das Verhältnis der benötigten Zeit
von std JSON.strngify zu unserem benutzerdefinierten json_stringify sollte ungefähr
sein 1:3 - 1:4

In einem interessanten Fall könnte es auch anders sein. Lesen Sie weiter, um mehr über
zu erfahren das!

Verbesserung der Leistung

Das erste, was behoben werden könnte, ist die Verwendung der Kartenfunktion. Es schafft
neues Array vom alten. In unserem Fall von Objekten wird ein Array von
erstellt JSON stringifizierte Objekteigenschaften aus dem Array, das Objekteinträge enthält.

Ähnliches passiert auch mit der Stringifizierung der Array-Elemente.

Wir müssen die Elemente in einem Array oder die Einträge eines Objekts durchlaufen! Aber
Wir können die Erstellung eines weiteren Arrays überspringen, nur um die JSON-String-Teile zu verbinden.

Hier ist die aktualisierte Version (der Kürze halber werden nur die geänderten Teile angezeigt)

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;
  }
}

Und hier ist jetzt die Ausgabe des Testskripts

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

Das sieht jetzt viel besser aus. Unser benutzerdefiniertes json_stringify benötigt nur 3 ms
mehr als JSON.stringify, um ein tief verschachteltes Objekt 10.000 Mal zu stringisieren.
Obwohl dies nicht perfekt ist, ist es eine akzeptable Verzögerung.

Mehr rausquetschen??

Die aktuelle Verzögerung könnte auf die gesamte Erstellung und Verkettung von Zeichenfolgen zurückzuführen sein
das passiert. Jedes Mal, wenn wir elements_str += sep + json_stringify(element)
ausführen Wir verketten 3 Zeichenfolgen.

Das Verketten von Zeichenfolgen ist kostspielig, weil es

erfordert

1. Erstellen eines neuen String-Puffers, der in den gesamten kombinierten String passt
2. Einzelne Zeichenfolgen in den neu erstellten Puffer kopieren

Wenn wir selbst einen Puffer verwenden und die Daten direkt dorthin schreiben, erhalten wir möglicherweise
eine Leistungssteigerung. Da wir einen großen Puffer erstellen können (sagen wir 80 Zeichen)
und erstellen Sie dann neue Puffer, um 80 Zeichen mehr aufzunehmen, wenn sie aufgebraucht sind.

Wir werden die Neuzuweisung/das Kopieren von Daten nicht ganz vermeiden, aber wir werden es tun
Reduzierung dieser Vorgänge.

Eine weitere mögliche Verzögerung ist der rekursive Prozess selbst! Insbesondere die
Funktionsaufruf, der Zeit kostet. Betrachten Sie unseren Funktionsaufruf json_stringify(val)
das nur einen Parameter hat.

Funktionsaufrufe verstehen

Die Schritte wären

1. Schieben Sie die Rücksprungadresse auf den Stapel
2. Schieben Sie die Argumentreferenz auf den Stapel
3. In der aufgerufenen Funktion
   1. Entfernen Sie die Parameterreferenz vom Stapel
   2. Entfernen Sie die Absenderadresse vom Stapel
   3. Schiebe den Rückgabewert (den stringifizierten Teil) auf den Stapel
4. In der aufrufenden Funktion
   1. Entfernen Sie den von der Funktion zurückgegebenen Wert vom Stapel

Alle diese Vorgänge werden durchgeführt, um sicherzustellen, dass Funktionsaufrufe ausgeführt werden, und dies erhöht die CPU
Kosten.

Wenn wir einen nicht rekursiven Algorithmus von json_string erstellen, werden alle diese Operationen ausgeführt
Die oben aufgeführten Werte für Funktionsaufrufe (mal die Anzahl solcher Aufrufe) wären
auf Null reduziert.

Dies kann ein zukünftiger Versuch sein.

NodeJs-Versionsunterschiede

Eine letzte Sache, die hier zu beachten ist. Betrachten Sie die folgende Ausgabe des Testskripts

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

Hat unser benutzerdefiniertes json_stringify einfach eine bessere Leistung als der NodeJs-Standard?
JSON.stringify???

Na ja! Dies ist jedoch eine ältere Version von NodeJs (v18.20.3). Es stellt sich heraus, für
In dieser Version (und vielleicht auch in einer niedrigeren Version) funktioniert unser maßgeschneidertes json_stringify
schneller als die Standardbibliothek!

Alle Tests für diesen Artikel (außer diesem letzten) wurden mit
durchgeführt Knoten v22.6.0

Die Leistung von JSON.stringify ist von v18 auf v22 gestiegen. Das ist so toll

Es ist auch wichtig zu beachten, dass unser Skript in NodeJs v22 eine bessere Leistung erbracht hat.
Das bedeutet also, dass NodeJs auch die Gesamtleistung der Laufzeit erhöht hat.
Möglicherweise wurde der zugrunde liegende V8-Motor selbst aktualisiert.

Nun, das war eine erfreuliche Erfahrung für mich. Und ich hoffe, dass es so sein wird
Du auch. Und inmitten all dieser Freude haben wir das eine oder andere gelernt!

Weiterbauen, weiter testen!

Das obige ist der detaillierte Inhalt vonKonkurrieren Sie mit JSON.stringify – indem Sie ein benutzerdefiniertes erstellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!