Реализация мемоизации в JavaScript / forpes.ru

Главная
Реализация мемоизации в JavaScript

Реализация мемоизации в JavaScript +10

06.03.2023 03:35

EdgarAbgaryan 15 4500 Источник

Про статью

Мне очень хотелось сделать что‑то интерактивное. Поэтому по ходу чтения очень желательно переходить в сервис codesandbox.io и делать задания, прежде чем читать дальше. Соответсвенно, предполагается, что читаться это будет с компьютера, а не с телефона.

Статья планировалась быть доступной и полезной для всех. Особенно для начинающих. Но некоторые темы могут потребовать много усилий от разработчиков с небольшим опытом. Я постарался сократить теоретическую часть и лирические отступления, чтобы получился более практический материал. Верю, что кому надо и сам загуглит недостающую для понимания ему теорию более подробно. Надеюсь, что после прочтения у вас будет уверенное и всестороннее понимание мемоизации и сложится представление о таких темах как: замыкание, функции высшего порядка, чистые функции, каррирование, TDD, рекурсия и property‑based тестирование. А главное — понимание как и где это применять.

Про велосипеды

Фраза «делать свой велосипед» обычно употребляется для негативного окраса чего‑то. Но именно этим мы будем заниматься здесь. Потому что это эффективный метод для того, чтобы разобраться в какой‑то теме. Попробовав самостоятельно реализовать что‑то, мы лучше разберемся в инструментах, которые обычно делают часть работы за нас. После этого мы сможем извлекать больше пользы из привычных инструментов. Например, знания о внутреннем устройстве определённых систем позволит вам дебажить проблему гораздо быстрее хотя бы потому, что вы будете знать, что могло пойти не так. После того, как попытаешься реализовать что‑то сам, некоторые вещи оказываются проще и перестают быть магией. А некоторые казавшиеся простыми библиотеки, оказываются настолько пропитанными нюансами, что ты становишься благодарен создателю пакета за его труд.

Мемоизация

Мемоизация является частным случаем кэширования. К кэшу может относиться любое сохранение данных для будущего переиспользования, в то время как мемоизация относится к кешированию результата вызова функции. В общем, это просто способ оптимизации кода наших программ.

Как уже упоминалось, в интернете полно готовых реализаций. Вот неполный список, который вы можете использовать: лодашевская функция memoize, p‑memoize, async, memoizee (мой любимчик), moize, fast‑memoize, ES7 декоратор @memoize из decko.

Даже если вы явно не используете мемоизацию, то скорее всего это делают некоторые библиотеки, которыми вы пользуетесь на постоянной основе. Например в мире react»а это могут быть библиотеки reselect, react‑query, apollo‑client, хук useMemo и компонент высшего порядка memo и многое другое.

Протокол взаимодействия с этой статьёй

В CodeSandbox находится стартовый шаблон, в котором вы будете писать свою реализацию функции мемоизации. В нём есть два файла: withMemo.js и withMemo.test.js

Продвижение по статье предполагает несколько итераций следующих шагов:

Я предлагаю что‑то реализовать или как‑то улучшить нашу функцию.
Затем я даю тесты, которые нужно добавить в withMemo.test.js для проверки нового функционала.
Вы дописываете что‑то на своё усмотрение в withMemo.js так, чтобы новые тесты прошли успешно, а старые не сломались.
Я показываю возможное решение от себя и, если надо, добавляю пояснения.

Такой подход написания кода (делать несколько итерация написания тестов, а затем обновления кода, чтобы тесты успешно проходились) называется Test Driven Development (TDD).

Поехали

Функция без аргументов

Сначала попытаемся мемоизировать функции, подобные следующей:
```
// Вчитываться в тело функции необязательно
function generateDigitsOfPi() {
    const DIGITS_COUNT = 10_001;
    let q = 1n;
    let r = 180n;
    let t = 60n;
    let i = 2n;
    let str = '';
    for (let j = 0; j < DIGITS_COUNT; j++) {
        let digit = ((i * 27n - 12n) * q + r * 5n) / (t * 5n);
        str += digit
        let u = i * 3n;
        u = (u + 1n) * 3n * (u + 2n);
        r = u * 10n * (q * (i * 5n - 2n) + r - t * digit);
        q *= 10n * i * (i++ * 2n - 1n);
        t *= u;
    }

    const arr = str.split('');
    arr.splice(1, 0, '.');
    return arr.join('');
}
```
Эта функция вернёт число Пи в виде строки с точностью в 10 000 цифр после запятой. Такая функция - хороший кандидат для мемоизации, потому что её исполнение требует достаточно много ресурсов процессора. А после мемоизации вычисления не будут произовдиться на каждый вызов функции. Только на первый.
Добавьте эти тесты в файле withMemo.test.js
```
it(
    "should call original function only ones and " +
      "always return original result (no args)",
    () => {
      const result = Math.random();
      const fn = jest.fn(() => result);
      const memoizedFn = withMemo(fn);

      expect(fn).toHaveBeenCalledTimes(0);
      expect(memoizedFn()).toBe(result);
      expect(fn).toHaveBeenCalledTimes(1);
      expect(memoizedFn()).toBe(result);
      expect(fn).toHaveBeenCalledTimes(1);
    }
  );
```
Заметили, что я в переменную result положил случайное значение, вместо чего-то конкретного? Это одна из практик property-based тестирования. Довольно хорошо она объясняется в этом видео. Такие тесты чуть сложнее писать, зато они покрывают более общие случаи. А специальные библиотеки будут прогонять один и тот же тест несколько раз сами, генерируя разные входные данные и обязательно проверяя крайние значения (например пустые строки или массивы) о которых сами вы могли бы забыть.
Напишите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошли.

Чтобы запустить тесты, перейдите во вкладку Tests

Иногда codesandbox не перезапускает тесты после внесения изменений. Просто обновите страницу, чтобы исправить это.
Решение может выглядеть так:
Решение
```
// принимает в виде аргумента некотору функцию originFn
export const withMemo = (originFn) => {
  let cache;

	// возвращает новую функцию, которая является 
  // мемоизированной версией оригинальной функции
  return () => {
		// если кэша нет, то с помощю оригинальной функции заполняем его
    if (cache === undefined) {
      cache = originFn();
    }

		// в конце всегда возвращаем значение из кэша
    return cache;
  };
};
```
Как видите, ничего сложного нет. Обратим внимание на некоторые концепции.

Во-первых, withMemo является Функцией высшего порядка. Это значит, что функция либо принимает другую функцию в виде аргумента, либо создаёт и возвращает новую функцию. Функция withMemo делает и то и другое.

Во-вторых, в этом примере есть замыкание. Оно заключается в переменной cache. Смысл в том, что после вызова функции withMemo создаётся эта переменная cache, но она не удаляется после того, как withMemo отработает. А не удаляется она потому, что withMemo вернула новую функцию, которая внутри себя работает с этой переменной (то есть имеет ссылку на неё). Но при этом разработчик сам не имеет ссылки на эту переменную cache, чтобы напрямую с ней работать.

Понятие замыкания тесно связано с областью видимости переменных. Области видимости вложены друг в друга и образуют древовидную структуру. В этом полезно разобраться.

А если undefined

В моей реализации предыдущего шага допускается, что оригинальная функция не должна возвращать значение undefined. Если в кэше лежит это значение, то кэш всё равно будет считаться пустым. Такой подход имеет место быть и с ним не будет проблем в подавляющем большинстве случаев. Но давайте всё же исправим этот крайний случай.
Добавьте эти тесты в файле withMemo.test.js
```
it("'undefined' is valid value", () => {
    const result = undefined;
    const fn = jest.fn(() => result);
    const memoizedFn = withMemo(fn);

    expect(fn).toHaveBeenCalledTimes(0);
    expect(memoizedFn()).toBe(result);
    expect(fn).toHaveBeenCalledTimes(1);
    expect(memoizedFn()).toBe(result);
    expect(fn).toHaveBeenCalledTimes(1);
  });
```
Кстати, при правильном использовании библиотеки fast-check, она бы сама указала нам на то, что withMemo неправильно работает в этом крайнем случае. Не стоит всегда рассчитывать только на свою внимательность .
Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись
Возможное решение
Решение
```
export const withMemo = (originFn) => {
  const cache = {
    value: undefined, 
    isCached: false, // отдельная логическая переменная
  };

  return () => {
    if (!cache.isCached) {
      cache.value = originFn();
      cache.isCached = true;
    }
    return cache.value;
  };
};
```
diff: https://github.com/KnightSlayer/with-memo/commit/e6d6be554f0143efceb139cc135f7e2efbb8d692
Я просто завёл отдельную логическую переменную для явного указания, является ли значение закэшированным или нет.

Добавим один аргумент

Функци, всё же, обычно принимают аргументы. Например функция generateDigitsOfPi вместо того, чтобы захардкодить число знаков после запятой в переменную DIGITS_COUNT, может принимать это значение как аргумент digitsCount.

function generateDigitsOfPi(digitsCount) {
    let q = 1n;
    let r = 180n;
    let t = 60n;
    let i = 2n;
    let str = '';
    for (let j = 0; j < digitsCount; j++) {
        let digit = ((i * 27n - 12n) * q + r * 5n) / (t * 5n);
        str += digit
        let u = i * 3n;
        u = (u + 1n) * 3n * (u + 2n);
        r = u * 10n * (q * (i * 5n - 2n) + r - t * digit);
        q *= 10n * i * (i++ * 2n - 1n);
        t *= u;
    }

    const arr = str.split('')
    arr.splice(1, 0, '.')
    return arr.join('')
}

Добавьте эти тесты в файле withMemo.test.js.

it("should cache depending on argument", () => {
    const factor = Math.random();
    const fn = jest.fn((arg) => arg * factor);
    const memoizedFn = withMemo(fn);

    expect(fn).toHaveBeenCalledTimes(0);

    expect(memoizedFn(1)).toBe(factor);
    expect(fn).toHaveBeenCalledTimes(1);

    expect(memoizedFn(1)).toBe(factor);
    expect(fn).toHaveBeenCalledTimes(1);

    expect(memoizedFn(2)).toBe(2 * factor);
    expect(fn).toHaveBeenCalledTimes(2);

    expect(memoizedFn(2)).toBe(2 * factor);
    expect(fn).toHaveBeenCalledTimes(2);

    expect(memoizedFn(1)).toBe(factor);
    expect(fn).toHaveBeenCalledTimes(2);
  });

Напишите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Решение может выглядеть так

Решение

export const withMemo = (originFn) => {
  // в переменной кэша теперь будет объект, ключами которого будут значения
  // аргументов, а значениями объекта будут результаты вызовов оригиналтной
  // функции при соответсвующем аргументе
  const cache = {};

  return (arg) => {
		// эта запись может быть менее привычна. по сути она похожа на
    // if(!cache[arg])
    // но пройдёт если в кэш записан null, undefined, 0, ''.
    if (!(arg in cache)) {
      cache[arg] = originFn(arg);
    }

    return cache[arg];
  };
};

diff: https://github.com/KnightSlayer/with-memo/commit/f877e175a30a77e3ffa27ea1832573e6f68430c9

Пока ничего сложного ведь?

Стратегии сравнивания аргументов

Эквивалентны ли следующие два объекта? Нужно ли считать такие аргументы одинаковыми?
```
const obj1 = {
	foo: 'bar',
}
const obj2 = {
	foo: 'bar',
}
```
Зависит от обстоятельств. Поэтому давайте добавим новую опцию getKey в нашу функцию withMemo, чтобы функция была универсальной.

Добавьте эти тесты в файле withMemo.test.js

it("should cache depending on arg", () => {
    const num = Math.random();
    // создаём 2 функции
    const fn1 = jest.fn((arg) => ({ ...arg, num }));
    const fn2 = jest.fn((arg) => ({ ...arg, num }));

    // в первой функции мы будем сравнивать аргументы по ссылке
    const memoizedFn1 = withMemo(fn1, {
	  // функция теперь должна опцианально прнимать функцию getKey
      getKey: (arg) => arg, 
    });

    // во второй функции мы будем сравнивать аргументы по содержимому
    const memoizedFn2 = withMemo(fn2, {
      getKey: (arg) => JSON.stringify(arg),
    });
    const argA1 = { a: "a" };
    const argA2 = { a: "a" };

    memoizedFn1(argA1);
    expect(fn1).toHaveBeenCalledTimes(1);
    memoizedFn1(argA2);
    expect(fn1).toHaveBeenCalledTimes(2);

    memoizedFn2(argA1);
    expect(fn2).toHaveBeenCalledTimes(1);
    memoizedFn2(argA2);
    expect(fn2).toHaveBeenCalledTimes(1);
  });

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.
Возможное решение:
Решение
```
export const withMemo = (originFn, { getKey = (arg) => arg } = {}) => {
  // Во-первых cache теперь не просто объект а экземпляр Map'а.
  // Так сделано, чтобы ключом кэша могли быть не только строки.
  // А то раньше для всех объектов ключом была строка "[object Object]"
  const cache = new Map();

  return (arg) => {
    const cacheKey = getKey(arg); // раньше ключом был сам аргумент
																	// теперь то, что вернёт функция getKey

    if (!cache.has(cacheKey)) {
      cache.set(cacheKey, originFn(arg));
    }

    return cache.get(cacheKey);
  };
};
```
Для getKey в разных ситуациях могут быть полезны разные функции
- (arg) ⇒ JSON.stringify(arg)
- (arg) ⇒ stableStringify(arg), где stableStringify является функцией из пакета fast-json-stable-stringify. Суть в том, чтобы объекты из примера ниже сериализовались одинаково. Вне зависимости от порядка объявления полей.
```
import stableStringify from 'fast-json-stable-stringify'

const obj1 = {a: 'a', b: 'b'};
const obj2 = {b: 'b', a: 'a'};

JSON.stringify(obj1) === JSON.stringify(obj2) // false
stableStringify(obj1) === stableStringify(obj2) // true
```
- (arg) ⇒ hash(arg). Где hash - любая хеш-функция на ваш выбор. Это может быть полезно, если, например, мы хотим хранить ключи в виде строки как при JSON.stringify, но аргументы - слишком большие объекты, которые станут слишком длинными строками и будут занимать слишком много памяти. А хеш-функция может сократить строки до фиксированной длины.
- (arg) ⇒ arg. Это значение я выбрал по умолчанию для нашей функции, потому что оно годится для большинства случаев и это самый быстрый способ сравнить два объекта - просто по ссылке.
Хочу обратить внимание на то, как я добавил второй аргумент в withMemo. Давайте внимательней рассмотрим два варианта как это можно было сделать
```
// 1)
const withMemo = (originFn, getKey = (arg) => arg) 
// 2)
const withMemo = (originFn, { getKey = (arg) => arg } = {})
```
При втором варианте нам будет удобней в будущем добавлять новые опцианальные аргументы в функцию. К тому же, аргументы получаются именованными, что удобней при вызове функции.

Вместо Map можно было бы использовать WeakMap. В этом случае память будет очищаться эффективнее. Но тогда мы не сможем хранить в качестве ключа примитивы (например строки). А это не универсально. Хорошим решением будет дать возможность юзеру самому выбрать структуру, в которой будет храниться кэш. Главное, чтобы он реализовал нужную часть интерфейса
```
interface Map<K, V> {
    clear(): void; // пока не использовали
    delete(key: K): boolean; // пока не использовали
    get(key: K): V | undefined;
    has(key: K): boolean;
    set(key: K, value: V): this;
    readonly size: number; // пока не использовали
}
```
Итого может получиться так
```
export const withMemo = (
	originFn, 
	{ 
		getKey = (arg) => arg,
		cache = new Map(),
	} = {}
) => {
  return (arg) => {
    const cacheKey = getKey(arg);
    if (!cache.has(cacheKey)) {
      cache.set(cacheKey, originFn(arg));
    }

    return cache.get(cacheKey);
  };
};
```
diff: https://github.com/KnightSlayer/with-memo/commit/30f1cee7db8a614cad9db9e043398eea2187e419

Про запросы к API

Как вы могли почувствовать, мемоизация лучше всего будет работать для чистых функций. Вызовы методов сервера вряд ли можно назвать чистыми. Но кого это останавливает? Вызовы методов api часто мемоизируют. Это экономит трафик и слегка снижает нагрузку на сервер. Но запрос к серверу может завалиться по независимым от нас причинам. И это хотелось бы обрабатывать. Например, просто не записывать ничего в кэш при ошибке.

Добавьте эти тесты в файле withMemo.test.js

it("should clear cache on error", async () => {
    const result = Math.random();
    let callIndex = 0;
    const fn = jest.fn(async () => {
      callIndex++;
      if (callIndex === 1) return Promise.reject("Some error");
      return Promise.resolve(result);
    });

    const memoizedFn = withMemo(fn, {
      cacheRejectedPromise: false
    });

    await expect(memoizedFn()).rejects.toEqual("Some error");
    expect(fn).toHaveBeenCalledTimes(1);

    expect(await memoizedFn()).toBe(result);
    expect(fn).toHaveBeenCalledTimes(2);

    expect(await memoizedFn()).toBe(result);
    expect(fn).toHaveBeenCalledTimes(2);
  });

  it("should not clear cache on error", async () => {
    const error = Math.random();
    const fn = jest.fn(async () => Promise.reject(error));

    const memoizedFn = withMemo(fn, {
      cacheRejectedPromise: true
    });

    await expect(memoizedFn()).rejects.toEqual(error);
    expect(fn).toHaveBeenCalledTimes(1);
    await expect(memoizedFn()).rejects.toEqual(error);
    expect(fn).toHaveBeenCalledTimes(1);
  });

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.
Возможное решение:
Решение
```
export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    cache = new Map(),
    cacheRejectedPromise = false, // добавил новую опцию
  } = {}
) => {
  return (arg) => {
    const cacheKey = getKey(arg);

    if (!cache.has(cacheKey)) {
      cache.set(cacheKey, originFn(arg));
    }

    const cachedValue = cache.get(cacheKey);

    // удаляем из кэша значение, если значением будет 
    // отклоненный промис
    if (!cacheRejectedPromise) {
      Promise.resolve(cachedValue).catch(() => {
        cache.delete(cacheKey);
      });
    }

    return cachedValue;
  };
};
```
Хочу обратить внимание на то, что в кэше храниться будет не результат промиса, а сам промис. Вы могли реализовать что-то вроде такого:
```
originFn(arg).then(result => cache.set(cacheKey, result));
// или 
const result = await constoriginFn(arg); // мемоизированная функция всегда возвращает промис :(
cache.set(cacheKey, result));
```
Если это ваш случай, то основной его недостаток в том, что если произойдёт второй вызов до того как зарезолвится промис первого вызова, то от кэша не будет толку. Например, если две части приложения (хедер и сайдбар) одновременно запрашивают getCurrentUser, то на сервер уйдёт 2 одинаковых запроса. Но если хранить в кэше сам промис, то запрос будет один. Второй вызов вместо создания нового промиса, будет ждать завершения промиса первого вызова.

Ещё хочу объяснить эту запись:
```
Promise.resolve(cachedValue)
```
Результатом этого вырожения всегда будет промис. Если cachedValue уже промис, то ничего не поменяется, а иначе cachedValue обернётся в промис. В итоге мы всегда можем работать с этим значением как с промисом и не добавлять лишних условий.

Ещё хочу отметить, что HTTP запросы могут кэшироваться и без такого вмешательства. Умные люди сделали так, чтобы всё хорошо работало для многих случаев и так.

Больше аргументов

Некоторые люди считают, что у функции не должно быть больше одного аргумента. И у них даже есть хорошие аргументы для этого. В реальности же у функций может быть произвольное количество аргументов. Давайте покроем этот случай.

Самый простой способ сравнить все аргументы, это представить, что у нас не много аргументов, а только один аргумент-массив. Тогда задачу можно свести к предыдущей, просто сериализовав все аргументы с помощью JSON.stringify. Примерно так:
```
export const withMemo = (originFn) => {
	const cache = new Map();

  return (...args) => {
    const cacheKey = JSON.stringify(args); // Все аргументы разом сериализуем

    if (!cache.has(cacheKey)) {
      cache.set(cacheKey, originFn(...args));
    }

    return cache.get(cacheKey);
  };
};
```
Недостатком тут будет то, что у нас нет больше возможности выбирать стратегию сравнивания аргументов. А сравнение по ссылке это самое быстрое и менее затратное по памяти.

Я хочу предложить 2 способа обработки множества аргументов. Первая идея в том, что кэш должен быть многоуровневым. Попробую проиллюстрировать
```
const sum = (...args) => args.reduce((acc, num) => acc + num, 0)

// сначала кэш пустой
cache = {}

sum(4, 6) // 10
// кэш начинает заполняться
cache = {
	4: {
		6: 10, // из этой записи следует, что если первый аругумент 4, а второй 6, то результат будет 10
	}
}

sum(4, 8) // 12
cache = {
	4: {
		6: 10,
		8: 12,
	}
}

sum(2, 1) // 3
cache = {
  2: {
    1: 3,
  },
	4: {
		6: 10,
		8: 12,
	}
}

sum(4) // 4
cache = {
  2: {
    1: {
			1: 4,
	  },
  },
	4: {
		6: 10,
		8: 12,
    '': 4,
	}
}
```
Вторая идея более хитрая. Для начала нужно воспользоваться каррированием. Каррирование – это трансформация функций таким образом, чтобы они принимали аргументы не как f(a, b, c), а как f(a)(b)(c). То есть одна функция принимает только 1 аргумент и возвращает новую фуннкцию которая тоже принимает только 1 аргумент. А поскольку наша функция withMemo уже умеет хорошо работать с одним аргументом, то можно сделать её рекурсивной.

Добавьте эти тесты в файле withMemo.test.js.

it("multiple arguments", () => {
    const fn = jest.fn((...args) => args.reduce((acc, num) => acc + num, 0));
    const memoizedFn = withMemo(fn);

    expect(memoizedFn(4, 6)).toBe(10);
    expect(fn).toHaveBeenCalledTimes(1);

    expect(memoizedFn(4, 6)).toBe(10);
    expect(fn).toHaveBeenCalledTimes(1);

    expect(memoizedFn(4, 8)).toBe(12);
    expect(fn).toHaveBeenCalledTimes(2);

    expect(memoizedFn(4)).toBe(4);
    expect(fn).toHaveBeenCalledTimes(3);

    expect(memoizedFn(4, 6)).toBe(10);
    expect(fn).toHaveBeenCalledTimes(3);
  });

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись. Можете воспользоваться одной из предложенных идей или придумать своё решение. Я настоятельно рекомендую попробовать несколько вариантов для максимального усвоения материала.

Примеры решений:

Решения

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getCacheStore = () => new Map(), // тут небольшое изменение
    cacheRejectedPromise = false,
  } = {}
) => {
  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false
  });

  const cache = createSubCache();

  return (...args) => {
    let currentCache = cache;

    for (const arg of args) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
      currentCache.result = originFn(...args);
      currentCache.isCached = true;
    }

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() => {
        currentCache.isCached = false;
        currentCache.result = null;
      });
    }

    return currentCache.result;
  };
};

diff: https://github.com/KnightSlayer/with-memo/commit/30548ae8f47fc40d600493a025d3cfb313a63df0

Вариант решения с каррированием и рекурсией:

// options не раскрываем здесь, чтобы потом передать в рекурсии
export const withMemo = (originFn, options = {}) => {
  const {
    getKey = (arg) => arg,
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
  } = options;

  const cache = {
    subFunctions: getCacheStore(),
    result: null,
    isCached: false
  };

  return (...args) => {
    // Это условин выхода из рекурсии - аргументы закончились
    if (!args.length) {
      if (!cache.isCached) {
        cache.result = originFn();
        cache.isCached = true;
      }

      if (!cacheRejectedPromise) {
        Promise.resolve(cache.result).catch(() => {
          cache.result = null;
          cache.isCached = false;
        });
      }

      return cache.result;
    }

    const [arg, ...otherArgs] = args;
    const cacheKey = getKey(arg);

    if (!cache.subFunctions.has(cacheKey)) {
      cache.subFunctions.set(
        cacheKey,
				// тут рекурсия
        withMemo((...theArgs) => originFn(arg, ...theArgs), options)
      );
    }

    const subFunction = cache.subFunctions.get(cacheKey);

    return subFunction(...otherArgs);
  };
};

Если вы ещё плохо понимаете рекурсию, но хотите разобраться, то предлагаю вам внимательно посмотреть второй вариант решения, а затем попробовать воспроизвести. Если у вас получится написать аналогичную функцию не подглядывая, то можете считать, что вы достигли успеха. Если пришлось немного подглядеть, то просто повторите итерацию)

Время жизни

Мы уже довольно хорошо разобрались с мемоизацией. Очень надеюсь, что у вас уже возникли идеи, как это можно применить в текущем вашем проекте. Но у нас есть ещё много пространства для улучшения.

“В компьютерной науке есть две трудные вещи: недействительность кэша, именование вещей и ошибки на единицу”, — Леон Бамбрик.

Раз мы начали мемоизировать такие нечистые функции как запросы к апи, то надо позаботиться об инвалидации кэша. То есть о его очищении.

В этой статье есть разные продвинутые техники кэширования и его инвалидации. Мы займёмся пока более простыми вещами. А для чего нам вообще инвалидировать кэш? Одна из причин - прошло время и в кэше неактуальные данные. Другая причина - кэш начал занимать слишком много памяти.

Одним из самых простых решений первой проблемы является определение времени жизни кэша. Давайте добавим новую опцию ttl (Time to live) к нашей функции.

Добавьте эти тесты в файле withMemo.test.js

it("ttl", async () => {
    const fn = jest.fn();
    const memoizedFn = withMemo(fn, { ttl: 1000 }); // в милисекундах

    memoizedFn();
    expect(fn).toHaveBeenCalledTimes(1);
    await wait(500);

    memoizedFn();
    expect(fn).toHaveBeenCalledTimes(1);
    await wait(500);

    memoizedFn();
    expect(fn).toHaveBeenCalledTimes(2);
  });

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Вариант решения:

Решение

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
    ttl
  } = {}
) => {
  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false,
    invalidationTimeoutId: null,
  });

  const cache = createSubCache();

  const invalidateByCache = (theCache) => {
    theCache.isCached = false;
    theCache.result = null;
    clearTimeout(theCache.invalidationTimeoutId);
  };

  return (...args) => {
    let currentCache = cache;

    for (const arg of args) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
      currentCache.result = originFn(...args);
      currentCache.isCached = true;

      // ставим таймер, чтобы очистить кэш
      if (ttl != null) {
        currentCache.invalidationTimeoutId = setTimeout(
          () => invalidateByCache(currentCache),
          ttl
        );
      }
    }

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() =>
        invalidateByCache(currentCache)
      );
    }

    return currentCache.result;
  };
};

diff: https://github.com/KnightSlayer/with-memo/commit/70f90c3fa3e8f8f71126a132fc949b1441683eb2

Теперь очистка кэша происходит в 2х местах (по таймауту и при отклонённом промисе). Поэтому эта логика вынесена в отдельную функцию invalidateByCache.

В этом примере я для простоты не реализовал продолжение очистки кэша вверх по дереву. Но это будет полезно сделать. Пример для пояснения:

// допустим у нас есть мемозированная функция для суммы аргументов
memoizedSum(4, 6, 5) // 15
memoizedSum(4, 6, 10) // 20

// после этих вызовов кэш будет выглядеть так
cache == {
 4: {
		6: {
			5: 15,
			10: 20,
		}
	}
}

// после инвалидации кэша для аргументов (4, 6, 5),
// общий кэш будет выглядеть так
cache == {
 4: {
		6: {
			10: 20,
		}
	}
}

// после инвалидации кэша для аргументов (4, 6, 10),
// общий кэш будет выглядеть так
cache == {
 4: {
		6: {
		}
	}
}

// а правильней было бы так
cache == {}

Максимальный размер

Теперь попробуем ограничить максимальное потребление памяти нашей функцией. Ограничивать мы будем, правда, количество записей в кэше, а не количество занятой памяти в байтах (вычисление потребляемой памяти не такая простая задача, как может показаться). Но эти два показателя обычно напрямую коррелируют, так что этого нам хватит. Заведём новую опцию maxSize для нашей функции. После достижения максимального количества записей в кэше, при добавлении новой записи, мы должны удалить одну из предыдущих записей. Нужно выбрать стратегию вытеснения кэша. Например самого давно не используемого или самого редко используемого или просто раньше всех добавленного. Стратегий много и для разных функций и разных ситуаций подходят разные.

Даже стратегия MRU (Most Recently Used - Наиболее недавно использовавшийся) иногда является лучшим выбором.
- Когда файл периодически сканируется по циклической схеме, MRU (Most Recently Used - Наиболее недавно использовавшийся) — наилучший алгоритм вытеснения.
  
  Источник Hong-Tai Chou". David J. Dewitt: http://www.vldb.org/conf/1985/P127.PDF
Я предлагаю реализовать LRU (Least recently used - Вытеснение давно неиспользуемых) стратегию вытеснения кэша, но предоставить возможность конечному пользователю передать свою стратегию. Для любой реализации нам придётся собирать некоторую статистику по вызовам функций. Для общего кейса нам хватит массива таймстемпов хитов (hit - использование кэша). То есть наша функция будет потреблять больше памяти, чтобы хранить эту статистику. Ну и дополнительные вычислительные мощности понадобятся, чтобы выбрать вытесняемую запись по выбранной стратегии. Так что, если будете делать свою функцию мемоизации для настоящего проекта, то не добавляйте эту фичу без надобности. Иначе вашу реализацию уж точно не получится назвать “самой быстрой функцией мемоизации”.

Добавьте эти тесты в файле withMemo.test.js

it("LRU", async () => {
    const fn = jest.fn((...args) => args.join("-"));
    const memoizedFn = withMemo(fn, {
      cacheReplacementPolicy: {
        maxSize: 3
      }
    });

    memoizedFn(1, 2);
    await wait(0);
    memoizedFn(1, 3);
    await wait(0);
    memoizedFn(2, 3);
    await wait(0);
    memoizedFn(1, 2);
    expect(fn).toHaveBeenCalledTimes(3);
    await wait(0);
    memoizedFn(3, 3); // replace cache for (1, 3)
    expect(fn).toHaveBeenCalledTimes(4);
    await wait(0);
    memoizedFn(1, 2);
    expect(fn).toHaveBeenCalledTimes(4);
    await wait(0);
    memoizedFn(2, 3);
    expect(fn).toHaveBeenCalledTimes(4);
    await wait(0);
    memoizedFn(3, 3);
    expect(fn).toHaveBeenCalledTimes(4);
    await wait(0);
    memoizedFn(1, 3); // replace cache for (1, 2)
    expect(fn).toHaveBeenCalledTimes(5);
  });

Перед каждым вызовом функции я поставил await wait(0); чтобы таймстемпы хитов отличались. Иначе у всех хитов было бы одинаковое время и мы бы не смогли выбрать самый давно не используемый кэш. Если вам это не подходит. то можно, например, хранить в хитах не массив таймстемпов, а массив объектов типа {index, timestamp}. index уж точно не будет повторяться.

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Вариант решения

Решение

const cacheReplacementStrategies = {
	// реализация стратегии вытеснения давно неиспользуемых кешей
  lru: (itemsSet) => {
    const asArray = Array.from(itemsSet)
      .sort((a, b) => a.hits.at(-1) - b.hits.at(-1))
		// я решил, что функция должна вернуть Массив кэшей для вытеснения.
	  // иногда, в целях оптимизации, лучше освободить сразу много места (например 10%)
    // чем слишком часто вызывать эту функцию
    return asArray.slice(0, 1);
		// если хотим очистить 10% от всех записей
		// return asArray.slice(0, Math.round(asArray.length * 0.1);
  }
};

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
    ttl,
		// новая опция. может быть объектом со свойствами maxSize и strategy
    cacheReplacementPolicy = null
  } = {}
) => {
  if (cacheReplacementPolicy && !cacheReplacementPolicy.maxSize) {
    throw new Error("maxSize is mandatory for cacheReplacementPolicy");
  }

  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false,
    invalidationTimeoutId: null,
    hits: [], // новое свойства кэша
  });

  const rootCache = createSubCache();

	// нам нужна плоская структура всех кешей (не дерево), чтобы сразу передать
  // все кеши в стратегию валидации и быстро получать размер кеша.  
  // allCacheRecords мог бы быть массивом вместо set'а. 
  // но удаление элемента из середины массива медленная операция, потому 
  // что придётся сдвигать все последующие элементы на единицу. 
  // allCacheRecords необязательная штука. Если её не заводить
  // то перед вызовом стратегии вытеснения кеша надо проходиться по всему
  // дереву кэшей, чтобы собрать все записи.
  // Какой вариант лучше - спорный вопрос
  const allCacheRecords = new Set(); 

  const invalidateByCache = (theCache) => {
    clearTimeout(theCache.invalidationTimeoutId);
    theCache.isCached = false;
    theCache.result = null;
    theCache.invalidationTimeoutId = null;
    // два дополнительных действия при инвалидации кэша
    theCache.hits = [];
    allCacheRecords.delete(theCache);
  };

  return (...args) => {
    let currentCache = rootCache;

    for (const arg of args) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
			// если размер кэша переполнен и указано cacheReplacementPolicy
      // то инвалидируем часть кэша
      if (cacheReplacementPolicy) {
        const {
          maxSize,
          strategy = cacheReplacementStrategies.lru
        } = cacheReplacementPolicy;
        if (allCacheRecords.size >= maxSize) {
          const cachesToReplace = strategy(allCacheRecords);
          cachesToReplace.forEach(invalidateByCache);
        }
      }

      currentCache.result = originFn(...args);
      currentCache.isCached = true;

      if (ttl != null) {
        currentCache.invalidationTimeoutId = setTimeout(
          () => invalidateByCache(currentCache),
          ttl
        );
      }
			// добавили новый кэш в allCacheRecords
      allCacheRecords.add(currentCache);
    }
    // добавляем значение в hit
    currentCache.hits.push(+new Date());

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() =>
        invalidateByCache(currentCache)
      );
    }

    return currentCache.result;
  };
};

diff: https://github.com/KnightSlayer/with-memo/commit/1a5809cb1bd769e3e49cb5fe5abccb4354fbe2ce

Хочу обратить внимание на то, что настоящий размер кэша может быть меньше, чем allCacheRecords.size. Например, если передать в getCacheStore что-то, что вернёт WeakMap то некоторые значения из кэша могут уходить минуя наш invalidateByCache. Поэтому, перед тем как вытеснить какие-та значения из кэша, вы можете захотеть рекурсивно пройтись по дереву и посчитать настоящий размер кэша.

Если вы будете делать что-то подобное, то я бы рекомендовал сделать свойство strategy обязательным, а не использовать lru по умолчанию, если ничего не передали. Так пользователи будут делать более осознанный выбор. Но не надо заставлять коллег писать свои стратегии. Предоставьте набор стратегий, которые они могут импортировать и передать в функцию мемоизации

Ручная инвалидация кэша

Мы научили нашу функцию сбрасывать кэш по ряду разных признаков. Но и этого может не хватить. Иногда хочется императивно инвалидировать кэш для каких-то аргументов или, и вовсе, вообще весь кэш сбросить (например, когда юзер разлогинился).

Добавьте эти тесты в файле withMemo.test.js

it("invalidateCache", () => {
    const fn = jest.fn();
    const memoizedFn = withMemo(fn);

    memoizedFn(1, 2);
    memoizedFn(1, 3);
    memoizedFn.invalidateCache();
    expect(fn).toHaveBeenCalledTimes(2);
    memoizedFn(1, 3);
    expect(fn).toHaveBeenCalledTimes(3);
    memoizedFn(1, 2);
    expect(fn).toHaveBeenCalledTimes(4);
  });

  it("invalidateCacheByArgs", () => {
    const fn = jest.fn();
    const memoizedFn = withMemo(fn);

    memoizedFn(1, 2);
    memoizedFn(1, 3);
    memoizedFn.invalidateCacheByArgs(1, 2);
    expect(fn).toHaveBeenCalledTimes(2);
    memoizedFn(1, 3);
    expect(fn).toHaveBeenCalledTimes(2);
    memoizedFn(1, 2);
    expect(fn).toHaveBeenCalledTimes(3);
  });

Хочу напомнить, что функции в JS являются объектами. То есть в них, как и во все объекты, можно по ключу записать значение obj.key = value. Поэтому memoizedFn.invalidateCacheByArgs(1, 2); абсолютно валидная конструкция.

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Вариант решения:

Решение

const cacheReplacementStrategies = {
  lru: (itemsSet) => {
    const asArray = Array.from(itemsSet)
      .sort((a, b) => a.hits.at(-1) - b.hits.at(-1))
    return asArray.slice(0, 1);
  }
};

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
    ttl,
    cacheReplacementPolicy = null
  } = {}
) => {
  if (cacheReplacementPolicy && !cacheReplacementPolicy.maxSize) {
    throw new Error("maxSize is mandatory ");
  }

  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false,
    invalidationTimeoutId: null,
    hits: []
  });

  const rootCache = createSubCache();
  const allCacheRecords = new Set();

  const invalidateByCache = (theCache) => {
    clearTimeout(theCache.invalidationTimeoutId);
    theCache.isCached = false;
    theCache.result = null;
    theCache.invalidationTimeoutId = null;
    theCache.hits = [];
    allCacheRecords.delete(theCache);
  };

	// теперь мы не возвращаем сразу мемоизированную версию функции, а
  // записываем её в переменну, чтобы потом добавить новых свойств
  const memoizedFn = (...args) => {
    let currentCache = rootCache;

    for (const arg of args) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
      if (cacheReplacementPolicy) {
        const {
          maxSize,
          strategy = cacheReplacementStrategies.lru
        } = cacheReplacementPolicy;
        if (allCacheRecords.size >= maxSize) {
          const cachesToReplace = strategy(allCacheRecords);
          cachesToReplace.forEach(invalidateByCache);
        }
      }
      currentCache.result = originFn(...args);
      currentCache.isCached = true;

      if (ttl != null) {
        currentCache.invalidationTimeoutId = setTimeout(
          () => invalidateByCache(currentCache),
          ttl
        );
      }
      allCacheRecords.add(currentCache);
    }
    currentCache.hits.push(+new Date());

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() =>
        invalidateByCache(currentCache)
      );
    }

    return currentCache.result;
  };

  // добавляем наши две функции для императивной очистки кэша
  memoizedFn.invalidateCache = () => {
		if (ttl != null) {
      allCacheRecords.forEach(
				cacheData => clearTimeout(cacheData.invalidationTimeoutId)
			)
    }
    allCacheRecords.clear();
    Object.assign(rootCache, createSubCache());
  };

  memoizedFn.invalidateCacheByArgs = (...args) => {
    let currentCache = rootCache;

    for (const arg of args) {
      const cacheKey = getKey(arg);

      currentCache = currentCache.subCaches.get(cacheKey);
      if (!currentCache) return;
    }

    invalidateByCache(currentCache);
  };

	// возвращаем мемоизированную версию оригинальной функции
  return memoizedFn;
};

diff: https://github.com/KnightSlayer/with-memo/commit/cac2b38ba6952a9a558a5e23727d3deb1474ed5c

Контекст

Если вы хотите мемоизировать функцию, которая зависит от контекста (от this), то вероятнее всего вы делаете что-то неправильно. Но

a. Всякие бывают случаи.

b. Для наших образовательных целей это не так и важно.

Так что давайте научим нашу функцию адекватно работать в зависимости от контекста. Для этого добавим в нашу функцию опцию getContextKey по аналогии с getKey. Если эта опция передана, то считаем контекст просто ещё одним аргументом функции и сводим задачу к предыдущей.

Добавьте эти тесты в файле withMemo.test.js

it("context", () => {
    class Point {
      constructor(x, y) {
        this.x = x;
        this.y = y;
      }
      
      doubleX() {
        return this.x * 2
      }
    }
    const fn = jest.fn(Point.prototype.doubleX);
    Point.prototype.doubleX = withMemo(fn, {
      getContextKey: (context) => context.x
    });

    const p1 = new Point(3, 100);
    const p2 = new Point(5, 50);

    expect(p1.doubleX()).toBe(6);
    expect(fn).toHaveBeenCalledTimes(1);
    expect(p1.doubleX()).toBe(6);
    expect(fn).toHaveBeenCalledTimes(1);
    expect(p2.doubleX()).toBe(10);
    expect(fn).toHaveBeenCalledTimes(2);
    p2.x = 3;
    expect(p2.doubleX()).toBe(6);
    expect(fn).toHaveBeenCalledTimes(2);
    p2.x = 33;
    expect(p2.doubleX()).toBe(66);
    expect(fn).toHaveBeenCalledTimes(3);
  });

  it("invalidate with context", () => {
    const fn = jest.fn();
    const memoizedFn = withMemo(fn, {
      getContextKey: (context) => context
    });
    class Dummy {}
    Dummy.prototype.memoizedFn = memoizedFn;

    const obj1 = new Dummy();
    const obj2 = new Dummy();

    obj1.memoizedFn(2);
    obj1.memoizedFn(3);
    obj1.memoizedFn(3);
    expect(fn).toHaveBeenCalledTimes(2);
    obj2.memoizedFn(2);
    obj2.memoizedFn(3);
    expect(fn).toHaveBeenCalledTimes(4);
    obj1.memoizedFn.invalidateCacheByContextAndArgs(obj1, 3);
    obj2.memoizedFn(3);
    expect(fn).toHaveBeenCalledTimes(4);
    obj1.memoizedFn(2);
    expect(fn).toHaveBeenCalledTimes(4);
    obj1.memoizedFn(3);
    expect(fn).toHaveBeenCalledTimes(5);
  });

Как вы должны были заметить, предлагается добавить отдельный метод invalidateCacheByContextAndArgs. Мы не можем использовать invalidateCacheByArgs не изменив синтаксис и получив информацию о контексте.

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Вариант решения:

Решение

const cacheReplacementStrategies = {
  lru: (itemsSet) => {
    const asArray = Array.from(itemsSet)
      .sort((a, b) => a.hits.at(-1) - b.hits.at(-1))

    return asArray.slice(0, 1);
  }
};

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getContextKey = null, // новая опция
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
    ttl,
    cacheReplacementPolicy = null
  } = {}
) => {
  if (cacheReplacementPolicy && !cacheReplacementPolicy.maxSize) {
    throw new Error("maxSize is mandatory ");
  }

  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false,
    invalidationTimeoutId: null,
    hits: []
  });

  const rootCache = createSubCache();
  const allCacheRecords = new Set();

  const invalidateByCache = (theCache) => {
    clearTimeout(theCache.invalidationTimeoutId);
    theCache.isCached = false;
    theCache.result = null;
    theCache.invalidationTimeoutId = null;
    theCache.hits = [];
    allCacheRecords.delete(theCache);
  };

	// чтобы получать контекст в момент вызова нужно заменить 
  // стрелочную функцию на обычную
  const memoizedFn = function (...args) {
    let currentCache = rootCache;

		// если передали getContextKey, то в корне кэша лежат
    // значения для контекста
    if (getContextKey) {
      const cacheKey = getContextKey(this);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    for (const arg of args) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
      if (cacheReplacementPolicy) {
        const {
          maxSize,
          strategy = cacheReplacementStrategies.lru
        } = cacheReplacementPolicy;
        if (allCacheRecords.size >= maxSize) {
          const cachesToReplace = strategy(allCacheRecords);
          cachesToReplace.forEach(invalidateByCache);
        }
      }
      currentCache.result = originFn.call(this, ...args);
      currentCache.isCached = true;

      if (ttl != null) {
        currentCache.invalidationTimeoutId = setTimeout(
          () => invalidateByCache(currentCache),
          ttl
        );
      }
      allCacheRecords.add(currentCache);
    }
    currentCache.hits.push(+new Date());

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() =>
        invalidateByCache(currentCache)
      );
    }

    return currentCache.result;
  };

  memoizedFn.invalidateCache = () => {
		if (ttl != null) {
      allCacheRecords.forEach(
				cacheData => clearTimeout(cacheData.invalidationTimeoutId)
			)
    }
    allCacheRecords.clear();
    Object.assign(rootCache, createSubCache());
  };

  memoizedFn.invalidateCacheByArgs = (...args) => {
    if (getContextKey) throw new Error("Use invalidateCacheByContextAndArgs instead");

    let currentCache = rootCache;

    for (const arg of args) {
      const cacheKey = getKey(arg);

      currentCache = currentCache.subCaches.get(cacheKey);
      if (!currentCache) return;
    }

    invalidateByCache(currentCache);
  };

	// новая функция
  memoizedFn.invalidateCacheByContextAndArgs = (context, ...args) => {
    if (!getContextKey) throw new Error("Use invalidateCacheByArgs instead");

    let currentCache = rootCache;
    const contextKey = getContextKey(context);
    currentCache = currentCache.subCaches.get(contextKey);
		if (!currentCache) return;

    for (const arg of args) {
      const cacheKey = getKey(arg);

      currentCache = currentCache.subCaches.get(cacheKey);
      if (!currentCache) return;
    }

    invalidateByCache(currentCache);
  };

  return memoizedFn;
};

diff: https://github.com/KnightSlayer/with-memo/commit/a5abe90f04dfef1b8e0c4faf248bba1377171c1f

Вызывать invalidateCacheByContextAndArgs когда не передан getContextKey не имеет смысла. Поэтому, когда такое происходит, лучше выбросить ошибку с подсказкой. То же самое и с invalidateCacheByArgs, когда getContextKey передан.

Трансформация аргументов

Последнее обновление, которое я предлагаю реализовать, это опция transformArgs. Допустим у нас есть коммутативная функция (результат которой не зависит от порядка аргументов). Например функция сложения. Мы бы хотели, чтобы если уже вычислено значение для sum(4, 9), то для sum(9, 4) взялось значение из кэша. Для этого, перед тем как начать работать с аргументами мы могли бы отсортировать их. transformArgs будет позволять пропускать некоторые аргументы или как-то их преобразовывать.

Добавьте эти тесты в файле withMemo.test.js

it("transformArgs", () => {
    const fn = jest.fn((a, b) => a + b);

    const memoizedFn = withMemo(fn, {
      transformArgs: (...args) => args.sort()
    });

    expect(memoizedFn(4, 9)).toBe(13);
    expect(memoizedFn(9, 4)).toBe(13);
    expect(fn).toHaveBeenCalledTimes(1);
    expect(memoizedFn(4, 4)).toBe(8);
    expect(fn).toHaveBeenCalledTimes(2);
  });

Обновите тело функции withMemo в файле withMemo.js, так, чтобы тесты успешно прошлись.

Вариант решения:

Решение

const cacheReplacementStrategies = {
  lru: (itemsSet) => {
    const asArray = Array.from(itemsSet)
      .sort((a, b) => a.hits.at(-1) - b.hits.at(-1))

    return asArray.slice(0, 1);
  }
};

export const withMemo = (
  originFn,
  {
    getKey = (arg) => arg,
    getContextKey = null,
    getCacheStore = () => new Map(),
    cacheRejectedPromise = false,
    ttl,
    cacheReplacementPolicy = null,
    transformArgs = (args) => args // новая опция. по умолчанию ничего не меняем
  } = {}
) => {
  if (cacheReplacementPolicy && !cacheReplacementPolicy.maxSize) {
    throw new Error("maxSize is mandatory ");
  }

  const createSubCache = () => ({
    subCaches: getCacheStore(),
    result: null,
    isCached: false,
    invalidationTimeoutId: null,
    hits: []
  });

  const rootCache = createSubCache();
  const allCacheRecords = new Set();

  const invalidateByCache = (theCache) => {
    clearTimeout(theCache.invalidationTimeoutId);
    theCache.isCached = false;
    theCache.result = null;
    theCache.invalidationTimeoutId = null;
    theCache.hits = [];
    allCacheRecords.delete(theCache);
  };

  const memoizedFn = function (...args) {
    let currentCache = rootCache;

    if (getContextKey) {
      const cacheKey = getContextKey(this);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    // применяем тут и в функциях invalidateCacheByArgs и invalidateCacheByContextAndArgs
    for (const arg of transformArgs(...args)) {
      const cacheKey = getKey(arg);
      if (!currentCache.subCaches.has(cacheKey)) {
        currentCache.subCaches.set(cacheKey, createSubCache());
      }

      currentCache = currentCache.subCaches.get(cacheKey);
    }

    if (!currentCache.isCached) {
      if (cacheReplacementPolicy) {
        const {
          maxSize,
          strategy = cacheReplacementStrategies.lru
        } = cacheReplacementPolicy;
        if (allCacheRecords.size >= maxSize) {
          const cachesToReplace = strategy(allCacheRecords);
          cachesToReplace.forEach(invalidateByCache);
        }
      }
      currentCache.result = originFn.call(this, ...args);
      currentCache.isCached = true;

      if (ttl != null) {
        currentCache.invalidationTimeoutId = setTimeout(
          () => invalidateByCache(currentCache),
          ttl
        );
      }
      allCacheRecords.add(currentCache);
    }
    currentCache.hits.push(+new Date());

    if (!cacheRejectedPromise) {
      Promise.resolve(currentCache.result).catch(() =>
        invalidateByCache(currentCache)
      );
    }

    return currentCache.result;
  };

  memoizedFn.invalidateCache = () => {
    if (ttl != null) {
      allCacheRecords.forEach(
        cacheData => clearTimeout(cacheData.invalidationTimeoutId)
      )
    }
    allCacheRecords.clear();
    Object.assign(rootCache, createSubCache());
  };

  memoizedFn.invalidateCacheByArgs = (...args) => {
    if (getContextKey)
      throw new Error("Use invalidateCacheByContextAndArgs instead");

    let currentCache = rootCache;

    for (const arg of transformArgs(...args)) {
      const cacheKey = getKey(arg);

      currentCache = currentCache.subCaches.get(cacheKey);
      if (!currentCache) return;
    }

    invalidateByCache(currentCache);
  };

  memoizedFn.invalidateCacheByContextAndArgs = (context, ...args) => {
    if (!getContextKey) throw new Error("Use invalidateCacheByArgs instead");

    let currentCache = rootCache;
    const cotextKey = getContextKey(context);
    currentCache = currentCache.subCaches.get(cotextKey);
		if (!currentCache) return;

    for (const arg of transformArgs(...args)) {
      const cacheKey = getKey(arg);

      currentCache = currentCache.subCaches.get(cacheKey);
      if (!currentCache) return;
    }

    invalidateByCache(currentCache);
  };

  return memoizedFn;
};

diff: https://github.com/KnightSlayer/with-memo/commit/21b74b4b4ccad634c5b3dc28cd93c0ab9e72c149

На этом всё с основной частью, но есть ещё пару вещей, о которых есть желание поговорить.

Пример CRUD сервиса с мемоизацией

Хочется предложить вариант использования нашей функции, который можно быстро внедрить в большинство проектов и который сразу принесёт пользу.

Допустим у нас есть REST API для сущности User и нужно реализовать обычные CRUD функции для неё. Как это может выглядеть вместе с функцией withMemo которую мы вместе реализовали:

const createMemoizedCrudService = (endpoint) => {
  const get = withMemo(
		(id) => fetch(`${endpoint}/${id}`),
		{ ttl: 5 * 60 * 1000, } // 5 минут
	)

  const getAll = withMemo(
		(paginationAndFiltersParams) => fetch(`${endpoint}?${ + new URLSearchParams(paginationAndFiltersParams)}`), 
		{ ttl: 1 * 60 * 1000, } // 1 минута
	})

  const create = (id, newEntity) => {
    getAll.invalidateCache();

    return fetch(`${endpoint}`, {
      method: 'POST',
      body: JSON.stringify(newEntity),
    })
  }

  const update = (id, updatedEntity) => {
    getAll.invalidateCache();
    get.invalidateCacheByArgs(id);

    return fetch(`${endpoint}/${id}`, {
      method: 'PUT',
      body: JSON.stringify(updatedEntity),
    })
  }

  const bulkUpdate = (filters, updatedValues) => {
    getAll.invalidateCache();
    get.invalidateCache();

    return fetch(`${endpoint}/bulk`, {
      method: 'PUT',
      body: JSON.stringify({ filters, updatedValues }),
    })
  }

  const remove = (id) => {
    getAll.invalidateCache();
    get.invalidateCacheByArgs(id);

    return fetch(`${endpoint}/${id}`, {
      method: 'DELETE',
    })
  }

  return {
    get,
    getAll,
    create,
    update,
    bulkUpdate,
    remove,
  }
}

И вот так использовать

const usersCrudService = createMemoizedCrudService('/api/users')

usersCrudService.get(1) // запрос
usersCrudService.get(1) // запроса нет, берём результат из кеша
usersCrudService.get(2) // запрос
usersCrudService.getAll() // запрос
usersCrudService.getAll() // кэш
usersCrudService.update(1, {name: 'Victor'})
usersCrudService.get(1) // запрос, так как update сбросил кэш
usersCrudService.get(2) // кэш
usersCrudService.getAll() // запрос

// через 5 минут
usersCrudService.get(2) // запрос, потому что кэш удалился по таймауту


// другие сервисы
const companiesCrudService = createMemoizedCrudService('/api/companies')
const phonesCrudService = createMemoizedCrudService('/api/phones')

Буду рад видеть ваши идеи и способы применения в комментариях

Про покрытие тестами

Если вам кажется, что тесты, которые мы написали, хорошо покрывают работу нашей функции, то это не так) Главная проблема получившейся функции withMemo в том, что у неё много опций и от этого внутри много if»ов. В идеале нужно написать тесты с сочетанием всех опций, чтобы быть уверенным, что всё работает как ожидается. А это приводит к комбинаторному взрыву количества вариантов.

Тут мне вспоминается видео с канала Fun Fun Function на ютубе, выпуски с которого я кода‑то не пропускал. Видео называлось Settings are evil и достаточно эмоционально и детально рассказывало об этой проблеме.

Если вы скопируете код нашей withMemo как есть, то имеет смысл сделать обёртку над ней, в которой вы зафиксируете все опции и для которой напишете свои тесты для покрытия именно вами выбранного сочетания настроек.

Ограничения

Надо понимать, что для мемоизации идеально подходят только чистые функции. И то не все, а которые вызываются часто и потребляют много ресурсов процессора. А если функция не чистая, то мы всегда рискуем получать устаревшее значение из кэша.

Нужно держать в голове, что в любом случае функция мемоизации не бесплатна. Хранение результатов прошлых вызовов функции для переиспользования в будущем влечёт большие накладные расходы памяти. Выигрыш в скорости вычислений может не перевешивать увеличение в потребляемой памяти, если оригинальная функция и так быстрая (например не стоит мемоизировать функцию сложения) или если оригинальная функция вызывается достаточно редко. Большинство функций могут принимать неограниченный набор аргументов, а значит, что при мемоизации потребление памяти тоже может расти бесконечно. Если есть ограничения в употребляемой памяти, то нужно использовать какие‑то политики вытеснения старого кэша.

Мемоизация это всегда компромисс между потребляемой памятью и скоростью функции.

Мемоизация рекурсивных функций

Если сначала написать рекурсивную функцию, а потом передать её в withMemo как в этом примере

const factorial = (x) => {
  if (x === 0) {
    return 1;
  }
  else {
    return x * factorial(x - 1);
  }
}

const memoizedFactorial = withMemo(factorial)

то для внутренних рекурсивных вызовов будут применяться оригинальная функция, а не мемоизированная её версия.

memoizedFactorial(50)
memoizedFactorial(49) // не воспользуется кэшом и сделает все 49 рекурсивных вызовов
memoizedFactorial(51) // не воспользуется кэшом и сделает все 51 рекурсивных вызовов
memoizedFactorial(50) // возмёт результат из кеша

Но это легко исправить. Достаточно переписать объявление функции следующим образом

const memoizedFactorial = withMemo(
	(x) => {
	  if (x === 0) {
	    return 1;
	  }
	  else {
	    return x * memoizedFactorial(x - 1);
	  }
	}
)

memoizedFactorial(50)
memoizedFactorial(49) // возмёт результат из кеша
memoizedFactorial(51) // сделает 1 рекурсивный вызов и всё
memoizedFactorial(50) // возмёт результат из кеша

Библиотека

Я не смог удержаться от того, чтобы не сделать npm пакет с этим кодом. Тем более, что вся работа уже почти сделана. Только надо переписать всё что есть на TypeScript»е, добавить несколько стратегий вытеснения кэша, чуть оптимизировать и пару тестов добавить. Это, кстати, мой первый пакет в npm.

Пока переписывал, сделал несколько изменений в конечной реализации. Я добавил продолжение очистки кэша вверх по дереву, о которой упоминал в секции «Время жизни». Выпилил allCacheRecors и заменил на число cacheSize и функцию getAllCacheRecors(). Если интересны детали реализация, то вот исходники https://github.com/KnightSlayer/with‑memo

На этом всё. Спасибо всем за внимание. Кто смог пройти весь путь строго по протоколу — молодцы! Вы — лучшие!

Комментарии (15)

vsecoder
00.00.0000 00:00
#25295436
Интересная статья, отложу и почитаю
1. kislo
  00.00.0000 00:00
  #25295778
  +6
  Тоже так постоянно думаю, уже около ста статей в отложенных накопилось

yarkov
00.00.0000 00:00
#25295452
Неплохо. Спасибо за статью.

lorus
00.00.0000 00:00
#25295662
А если рекурсия? То есть функция запросит мемоизированное значение прямо или опосредованно? Вполне себе вариант в сложных случаях отложенных вычислений
1. EdgarAbgaryan Автор
  00.00.0000 00:00
  #25295756
  Этот вопрос возник до прочтения секции "Мемоизация рекурсивных функций" или после? Если сделать как в примере в этой секции, то не меомоизированной версии функции не будет. Будет только мемоизированая версия и вызываться всегда будет только она
  1. lorus
    00.00.0000 00:00
    #25295780
    К своему стыду, упустил этот раздел.
    Но, после прочтения, вопрос всё-же остался.
    Что если рекурсивное обращение произошло до того, как результат попал в кеш?
    
    EdgarAbgaryan Автор
    00.00.0000 00:00
    #25295816
    Я не уверен, что понимаю вопрос. Поверхностно всё просто, результат есть в кэше - берём оттуда, функцию не вызываем. Нет кеша - вызываем функцию и записываем в кэш. Даже при отложенных вычислениях мы Сразу кладём в кэш промис
    
    Попробуй написать маленький пример рекурсивной функции и поставь в нём console.log'и. Если так всё равное не разберёшься. То скинь пример своей функции сюда - попробую помочь
    
    lorus
    00.00.0000 00:00
    #25295856
    Утрирую:
    
    const getValue1 = withMemo(() => getValue2() - 1); const getValue2 = withMemo(() => getValue1() + 1); getValue1(); // Бесконечная рекурсия.
    
    В случае с промисами будет не бесконечная рекурсия с ошибкой, а бесконечное ожидание, что ещё хуже.
    Я о том, вообще-то, что для разрешения таких ситуаций тоже можно придумывать различные стратегии.
    
    aamonster
    00.00.0000 00:00
    #25295924
    +1
    Не-не-не, задача вычислимости – слишком сложная, чтобы в неё ввязываться. К тому же, допустим, у вас будет не ваш пример, а вычисление функции Аккермана. В ней нет бесконечной рекурсии, но от этого не сильно легче.
    
    lorus
    00.00.0000 00:00
    #25295916
    Ещё проще, чтобы стала понятна проблема:
    
    const getValue = withMemo(() => getValue());
    
    Вычисленное значение попадает в кеш, очевидно, только после того, как завершится вычисление. Но рекурсивный вызов происходит во время вычисления. То есть значения в кеше ещё нет. Значит вызов произойдёт снова, и снова, и снова...
    
    EdgarAbgaryan Автор
    00.00.0000 00:00
    #25295934
    Оба примера в принципе нерабочие. Мемоизация тут не при чём. Такое ощущение, что ты пишешь "можно коряво написать рекурсию и никогда из неё не выйти". Да, можно. Если в твоих примерах убрать withMemo, то будет просто сломанная рекурсия
    
    lorus
    00.00.0000 00:00
    #25295974
    Это утрированные примеры, да. Тем не менее, вполне себе реально получить ситуацию.
    А стратегия выходя из неё может проистекать из условий задачи. Например, можно ведь возвращаеть значение по умолчанию, пока результат вычисляется:
    
    const getValue = withMemo( async () => ({ done: true, value: await someVeryLongOperation() }), { defaultValue: { done: false, value: undefined } }, );
1. Alexandroppolus
  00.00.0000 00:00
  #25298010
  +1
  Для рекурсии можно сделать такую нашлепку поверх withMemo:
  
  const recMemo = (f) => { let memFunc; const func = (...a) => memFunc(...a); memFunc = withMemo(f(func)); return memFunc; }; // пример использования // функция Фибоначчи в длинной арифметике const memFib = recMemo( (func) => (x) => x < 2n ? x : func(x - 1n) + func(x - 2n) ); memFib(200n); // 280571172992510140037611932413038677189525n
  
  Этот вариант позволяет создать функцию "на лету" и сразу передать куда-нибудь, не сохраняя в переменную.

underherzen
00.00.0000 00:00
#25295776
очень интересная статья, интересно было бы продолжить эту тему в контексте подобия react-query
1. noodles
  00.00.0000 00:00
  #25314362
  очень интересная статья, интересно было бы продолжить эту тему в контексте подобия react-query
  
  Если не делать запросы из разметки (view-слоя) как написано
  
  если две части приложения (хедер и сайдбар) одновременно запрашивают getCurrentUser, то на сервер уйдёт 2 одинаковых запроса
  
  то судя по всему react-query и не нужен вовсе.

Реализация мемоизации в JavaScript +10

Про статью

Про велосипеды

Мемоизация

Протокол взаимодействия с этой статьёй

Поехали

Функция без аргументов

А если undefined

Добавим один аргумент

Стратегии сравнивания аргументов

Про запросы к API

Больше аргументов

Время жизни

Максимальный размер

Ручная инвалидация кэша

Контекст

Трансформация аргументов

Пример CRUD сервиса с мемоизацией

Про покрытие тестами

Ограничения

Мемоизация рекурсивных функций

Библиотека

Комментарии (15)

EdgarAbgaryan Автор

EdgarAbgaryan Автор

EdgarAbgaryan Автор