Реализация мемоизации в JavaScript06.03.2023 09:47

Про статью

Мне очень хотелось сделать что-то интерактивное. Поэтому по ходу чтения очень желательно переходить в сервис 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

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

  1. Я предлагаю что-то реализовать или как-то улучшить нашу функцию.

  2. Затем я даю тесты, которые нужно добавить в withMemo.test.js для проверки нового функционала.

  3. Вы дописываете что-то на своё усмотрение в withMemo.js так, чтобы новые тесты прошли успешно, а старые не сломались.

  4. Я показываю возможное решение от себя и, если надо, то добавляю пояснения.

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

Поехали

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

  1. Сначала попытаемся мемоизировать функции подобные следующей: 

    // Вчитываться в тело функции необязательно
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 цифр после запятой. Такая функция хороший кандидат для мемоизации, потому что её исполнение требует достаточно много ресурсов процессора. А после мемоизации вычисления не будут делаться на каждый вызов функции. Только на первый.

  2. Добавьте эти тесты в файле 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 тестирования. Довольно хорошо она объясняется в этом видео. Такие тесты чуть сложнее писать, зато они покрывают более общие случаи. А специальные библиотеки будут прогонять один и тот же тест несколько раз сами, генерируя разные входные данные и обязательно проверяя крайние значения (например пустые строки или массивы) о которых сами вы могли бы забыть.

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

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

    967b86fbc60a640bea8f37681d5512c9.png

    Иногда codesandbox не перезапускает тесты после внесения изменений. Просто обновите страницу, чтобы исправить это.

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

    Решение
    // принимает в виде аргумента некотору функцию originFn
export const withMemo = (originFn) => {
  let cache;

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

		// в конце всегда возвращаем значение из кэша
    return cache;
  };
};

    Как видите, ничего сложного нет. Обратим внимание на некоторые концепции.

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

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

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

А если undefined

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

  2. Добавьте эти тесты в файле 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 неправильно работает в этом крайнем случае. Не стоит всегда рассчитывать только на свою внимательность .

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

  4. Возможное решение

    Решение
    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

    Я просто завёл отдельную логическую переменную для явного указания, является ли значение закэшированным или нет.

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

  1. Функци, всё же, обычно принимают аргументы. Например функция 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('')
}

  2. Добавьте эти тесты в файле 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);
  });

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

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

    Решение
    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

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

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

  1. Эквивалентны ли следующие два объекта? Нужно ли считать такие аргументы одинаковыми? 

    const obj1 = {
	foo: 'bar',
}
const obj2 = {
	foo: 'bar',
}

    Зависит от обстоятельств. Поэтому давайте добавим новую опцию getKey в нашу функцию withMemo, чтобы функция была универсальной.

  2. Добавьте эти тесты в файле 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);
  });

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

  4. Возможное решение:

    Решение
    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 {
    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

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

  2. Добавьте эти тесты в файле 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);
  });

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

  4. Возможное решение:

    Решение
    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 запросы могут кэшироваться и без такого вмешательства. Умные люди сделали так, чтобы всё хорошо работало для многих случаев и так.

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

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

    Самый простой способ сравнить все аргументы, это представить, что у нас не много аргументов, а только один аргумент-массив. Тогда задачу можно свести к предыдущей, просто сериализовав все аргументы с помощью 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 уже умеет хорошо работать с одним аргументом, то можно сделать её рекурсивной.

  2. Добавьте эти тесты в файле 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);
  });

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

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

    Решения
    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);
  };
};

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

Время жизни

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

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

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

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

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

  2. Добавьте эти тесты в файле 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);
  });

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

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

    Решение
    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 == {}

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

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

    Даже стратегия MRU (Most Recently Used — Наиболее недавно использовавшийся) иногда является лучшим выбором.

    Я предлагаю реализовать LRU (Least recently used — Вытеснение давно неиспользуемых) стратегию вытеснения кэша, но предоставить возможность конечному пользователю передать свою стратегию. Для любой реализации нам придётся собирать некоторую статистику по вызовам функций. Для общего кейса нам хватит массива таймстемпов хитов (hit — использование кэша). То есть наша функция будет потреблять больше памяти, чтобы хранить эту статистику. Ну и дополнительные вычислительные мощности понадобятся, чтобы выбрать вытесняемую запись по выбранной стратегии. Так что, если будете делать свою функцию мемоизации для настоящего проекта, то не добавляйте эту фичу без надобности. Иначе вашу реализацию уж точно не получится назвать «самой быстрой функцией мемоизации».

  2. Добавьте эти тесты в файле 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 уж точно не будет повторяться.

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

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

    Решение
    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 по умолчанию, если ничего не передали. Так пользователи будут делать более осознанный выбор. Но не надо заставлять коллег писать свои стратегии. Предоставьте набор стратегий, которые они могут импортировать и передать в функцию мемоизации

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

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

  2. Добавьте эти тесты в файле 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); абсолютно валидная конструкция.

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

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

    Решение
    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

Контекст

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

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

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

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

  2. Добавьте эти тесты в файле 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 не изменив синтаксис и получив информацию о контексте.

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

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

    Решение
    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, 
    
            
    © Habrahabr.ru