Это возникло во время обсуждения с моим другом рекурсии. Почему бы не построить
метод 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 


Запустив это, мы получим следующие тайминги.


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




В разных системах это может работать по-разному, но соотношение затраченного времени 

от стандартного 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 строки.

Объединение строк требует больших затрат, поскольку требует

создание нового строкового буфера, вмещающего всю объединенную строку
копировать отдельные строки во вновь созданный буфер
Использование буфера самостоятельно и запись данных непосредственно в него может дать нам

улучшение производительности. Поскольку мы можем создать большой буфер (скажем, 80 символов)

а затем создайте новые буферы, чтобы вместить еще 80 символов, когда они закончатся.

Мы не будем полностью избегать перераспределения/копирования данных, но будем

сокращение этих операций.

Другая возможная задержка — это сам рекурсивный процесс! В частности, 

вызов функции, который занимает время. Рассмотрим вызов нашей функции json_stringify(val)

который имеет только один параметр.

  
  
  Понимание вызовов функций


Шаги будут такими:

Поместить обратный адрес в стек
поместить ссылку на аргумент в стек
В вызываемой функции

Извлечь ссылку на параметр из стека
Извлечь обратный адрес из стека
поместить возвращаемое значение (строковую часть) в стек

В вызывающей функции

Извлечение значения, возвращаемого функцией, из стека

Все эти операции выполняются для обеспечения выполнения вызовов функций, а это увеличивает нагрузку на процессор

затраты.

Если мы создадим нерекурсивный алгоритм 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 увеличилась с версии 18 до версии 22. Это так здорово

Также важно отметить, что наш скрипт работал лучше в NodeJs v22.

Таким образом, это означает, что NodeJs также увеличил общую производительность среды выполнения.

Возможно, произошло обновление самого базового движка V8.

Что ж, для меня это был приятный опыт. И я надеюсь, что это будет для

ты тоже. И посреди всего этого удовольствия мы кое-чему научились!

Продолжайте создавать, продолжайте тестировать!