Bersaing dengan JSON.stringify - dengan membina yang tersuai

Ini muncul semasa perbincangan dengan rakan saya tentang Rekursi. Mengapa tidak membina
kaedah Javascript JSON.stringify sebagai latihan pengaturcaraan rekursif? Nampak sangat
idea.

Saya dengan cepat merangka versi pertama. Dan ia beraksi dengan dahsyat!
masa yang diperlukan adalah kira-kira 4 kali ganda daripada standard JSON.stringify.

Draf pertama

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

Dengan menjalankan perkara berikut, kami dapat melihat bahawa json_stringify kami berfungsi sebagai
dijangka.

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

Untuk menguji lebih banyak senario dan berbilang larian untuk mendapatkan idea purata tentang cara
kami skrip berjalan, kami membuat skrip ujian mudah!

Skrip ujian mudah

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

Menjalankan ini, kami mendapat pemasaan seperti berikut.

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

Ia mungkin berjalan secara berbeza pada sistem yang berbeza tetapi nisbah masa yang diambil
oleh std JSON.strngify kepada json_stringify tersuai kami hendaklah kira-kira
1:3 - 1:4

Ia mungkin berbeza juga dalam kes yang menarik. Baca terus untuk mengetahui lebih lanjut tentang
itu!

Meningkatkan prestasi

Perkara pertama yang boleh diperbaiki ialah penggunaan fungsi peta. Ia mencipta
tatasusunan baru dari yang lama. Dalam kes objek kami, ia mencipta tatasusunan
JSON merentangi sifat objek daripada tatasusunan yang mengandungi entri objek.

Perkara yang sama juga berlaku dengan rentetan elemen tatasusunan juga.

Kita perlu melingkari elemen dalam tatasusunan, atau entri objek! Tetapi
kita boleh melangkau membuat tatasusunan lain hanya untuk menyertai bahagian bertali JSON.

Berikut ialah versi yang dikemas kini (hanya bahagian yang diubah ditunjukkan untuk ringkasnya)

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

Dan inilah output skrip ujian sekarang

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

Ini kelihatan lebih baik sekarang. json_stringify tersuai kami mengambil masa hanya 3 ms
lebih daripada JSON.stringify untuk merangkai objek bersarang dalam 10,000 kali.
Walaupun ini tidak sempurna, ia adalah kelewatan yang boleh diterima.

Memicit lagi??

Kelewatan semasa mungkin disebabkan oleh semua penciptaan rentetan dan penyambungan
itu sedang berlaku. Setiap kali kami menjalankan elements_str += sep + json_stringify(elemen)
kami menggabungkan 3 tali.

Rentetan penggabungan adalah mahal kerana ia memerlukan

1. membuat penimbal rentetan baharu agar sesuai dengan keseluruhan rentetan gabungan
2. salin rentetan individu ke penimbal yang baru dibuat

Dengan menggunakan Penampan sendiri dan menulis data terus di sana mungkin memberi kita
peningkatan prestasi. Memandangkan kita boleh mencipta penimbal yang besar (katakan 80 aksara)
dan kemudian buat penimbal baharu untuk memuatkan 80 aksara lagi apabila ia kehabisan.

Kami tidak akan mengelak pengagihan semula / penyalinan data sama sekali, tetapi kami akan
mengurangkan operasi tersebut.

Satu lagi kelewatan yang mungkin adalah proses rekursif itu sendiri! Khususnya
panggilan fungsi yang memakan masa. Pertimbangkan panggilan fungsi kami json_stringify(val)
yang hanya mempunyai satu parameter.

Memahami panggilan Fungsi

Langkahnya ialah

1. Tolak alamat pemulangan ke tindanan
2. tolak rujukan hujah ke timbunan
3. Dalam fungsi yang dipanggil
   1. Pancarkan rujukan parameter daripada tindanan
   2. Pancarkan alamat pemulangan daripada timbunan
   3. tolak nilai pulangan (bahagian bertali) pada tindanan
4. Dalam fungsi panggilan
   1. Pati keluar nilai yang dikembalikan oleh fungsi daripada tindanan

Semua operasi ini berlaku untuk memastikan panggilan fungsi berlaku dan ini menambah CPU
kos.

Jika kami mencipta algoritma bukan rekursif json_stringify semua operasi ini
yang disenaraikan di atas untuk panggilan fungsi (kali bilangan panggilan tersebut) ialah
dikurangkan kepada tiada.

Ini boleh menjadi percubaan masa hadapan.

Perbezaan versi NodeJs

Satu perkara terakhir yang perlu diperhatikan di sini. Pertimbangkan output skrip ujian
berikut

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

Adakah json_stringify tersuai kami hanya berprestasi lebih baik daripada standard NodeJs
JSON.stringify???

Baiklah ya! Tetapi ini adalah versi lama NodeJs (v18.20.3). Ternyata, untuk
versi ini (dan lebih rendah juga mungkin) json_stringify buatan kami berfungsi
lebih pantas daripada perpustakaan standard!

Semua ujian untuk artikel ini (kecuali yang terakhir ini) telah dilakukan dengan
Nod v22.6.0

Prestasi JSON.stringify telah meningkat daripada v18 kepada v22. Ini sangat hebat

Perlu juga ambil perhatian bahawa, skrip kami berprestasi lebih baik dalam NodeJs v22.
Jadi, ini bermakna, NodeJs telah meningkatkan prestasi keseluruhan masa jalan juga.
Kemungkinan kemas kini telah berlaku pada enjin V8 yang mendasari itu sendiri.

Nah, ini merupakan pengalaman yang menyeronokkan untuk saya. Dan saya harap ia akan menjadi untuk
awak juga. Dan di tengah-tengah semua keseronokan ini, kami belajar satu atau dua perkara!

Teruskan membina, teruskan menguji!

Atas ialah kandungan terperinci Bersaing dengan JSON.stringify - dengan membina yang tersuai. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!