与 JSONstringify 竞争 - 通过构建自定义的 JSONstringify

这是在与我的朋友讨论递归时提出的。为什么不建造
javascript json.stringify 方法作为递归编程练习？看起来很棒
主意。

我很快就起草了第一个版本。而且表现很糟糕！
所需时间约为标准的 4 倍 json.stringify.

第一稿

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

通过运行以下命令，我们可以看到我们的 json_stringify 的工作原理如下
预计.

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

测试更多场景，并进行多次运行，以了解我们的
如何 脚本运行，我们做了一个简单的测试脚本！

一个简单的测试脚本

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

运行这个我们得到如下的计时。

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 1241241 ms
testing 1000000 times
    std lib json.stringify() took 3823 ms
    custom json_stringify() took 12275 ms

它可能在不同的系统上运行有所不同，但所用时间的比率
通过 std json.strngify 到我们自定义的 json_stringify 应该是关于
1:3 - 1:4

在一个有趣的案例中，情况也可能有所不同。继续阅读以了解更多信息
那个！

提高绩效

首先可以修复的是地图功能的使用。它创造了
旧数组中的新数组。在我们的对象例子中，它正在创建一个数组
包含对象条目的数组中的 json 字符串化对象属性。

数组元素的字符串化也发生类似的事情。

我们必须循环遍历数组中的元素或对象的条目！但是
我们可以跳过创建另一个数组来连接 json 字符串化部分。

这是更新版本（为简洁起见，仅显示更改的部分）

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

这是现在测试脚本的输出

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

现在看起来好多了。我们的自定义 json_stringify 仅花费 3 毫秒
比 json.stringify 字符串化深度嵌套对象 10,000 次。
虽然这并不完美，但这是可以接受的延迟。

还挤多了？？

当前的延迟可能是由于所有字符串创建和连接造成的
这正在发生。每次我们运行 elements_str += sep + json_stringify(element)
我们正在连接 3 个字符串。

连接字符串的成本很高，因为它需要

Peppertype.ai

高质量AI内容生成软件，它通过使用机器学习来理解用户的需求。

下载

1. 创建一个新的字符串缓冲区来容纳整个组合字符串
2. 将各个字符串复制到新创建的缓冲区

通过我们自己使用 buffer 并直接将数据写入其中可能会给我们
性能改进。因为我们可以创建一个大缓冲区（比如 80 个字符）
然后创建新的缓冲区以容纳 80 个字符，当它用完时。

我们不会完全避免数据的重新分配/复制，但我们会
减少这些操作。

另一个可能的延迟是递归过程本身！具体来说
函数调用会占用时间。考虑我们的函数调用 json_stringify(val)
它只有一个参数。

了解函数调用

步骤是

1. 将返回地址压入堆栈
2. 将参数引用推入堆栈
3. 在被调用的函数中
   1. 从堆栈中弹出参数引用
   2. 从堆栈中弹出返回地址
   3. 将返回值（字符串化部分）压入堆栈
4. 在调用函数中
   1. 从堆栈中弹出函数返回的值

所有这些操作都是为了确保函数调用发生，这会增加 cpu
费用.

如果我们创建一个非递归的 json_stringify 算法来完成所有这些操作
上面列出的函数调用（乘以此类调用的次数）将是
减少到没有。

这可以是未来的尝试。

nodejs版本差异

最后要注意的一件事。考虑测试脚本的以下输出

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

我们自定义的 json_stringify 是否比 nodejs 标准表现更好
json.stringify???

嗯，是的！但这是旧版本的 nodejs (v18.20.3)。事实证明，为了
这个版本（也可能更低）我们定制的 json_stringify 可以工作
比标准库更快！

本文的所有测试（除了最后一个）均已通过
完成 节点 v22.6.0

json.stringify 的性能从 v18 提升到了 v22。这太棒了

还需要注意的是，我们的脚本在 nodejs v22 中表现更好。
所以，这意味着 nodejs 也提高了运行时的整体性能。
底层v8引擎本身可能发生了更新。

嗯，这对我来说是一次愉快的经历。我希望这是为了
你也是。在所有这些享受中，我们学到了一两件事！

继续构建，继续测试！