Изучаем и реализуем алгоритм работы правильного observer паттерна для react компонентов +14



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


Итак в прошлой статье для того чтобы компоненты реакта автоматически подписывались на данные которые они рендерят и при изменении вызывался перерендер только нужных компонентов мы пришли к такой модификации observer паттерна


let CurrentObservables = null;
class Observable {
  listeners = new Set();
  constructor(value){
    this.value = value
  }
  get(){
    if(CurrentObservables) CurrentObservables.add(this);
    return this.value;
  }
  set(newValue){
    if(newValue !== this.value){
      this.notify();
    }
  }
  subscribe(listener){
    this.listeners.add(listener)
  }
  unsubscribe(listener){
    this.listeners.delete(listener)
  }
  notify(){
    for(const listener of this.listeners){
       listener();
    }
  }
}
function connect(target){
  return class extends (target instanceof React.Component ? target : React.Component) {
     stores = new Set();
     listener = ()=> this.setState({})
     render(){
        this.stores.forEach(store=>store.unsubscribe(this.listener));
        this.stores.clear();
        const prevObservables = CurrentObservables;
        CurrentObservables = this.stores;
        cosnt rendered = target instanceof React.Component ? super.render() : target(this.props);
        this.stores = CurrentObservables;
        CurrentObservables = prevObservables;
        this.stores.forEach(store=>store.subscribe(this.listener));
        return rendered;
     }
     componentWillUnmount(){
      this.stores.forEach(store=>store.unsubscribe(this.listener));
     }
  }
}

Давайте немного отрефакторим — вынесем логику установки глобального массива внутрь самого обзервера. Это можно представить как например ячейки таблицы в гугл-докс — есть ячейка которая просто хранит значение а есть ячейка которая хранит не только значение (которое будет закешировано) а и формулу(функцию) для ее пересчета. И заодно кроме формулы функции-пересчета мы добавим еще параметр функции для выполнения сайд-эффектов, как например вызов setState({}) на компоненте, когда у нас изменится значение. В итоге получим вот такой вот класс Cell


let CurrentObserver = null
class Cell {
  reactions = new Set();
  dependencies = new Set();
  tracked = false;
  constructor(value,  fn = null, reactionFn = null) {
    this.value = value;
    this.fn = fn;
    this.reactionFn = reactionFn
  }
  get() {
    if (this.fn && !this.tracked) this.run();
    if (CurrentObserver) {
      this.reactions.add(CurrentObserver);
      CurrentObserver.dependencies.add(this);
    }
    return this.value;
  }
  set(newValue) {
    if (newValue !== this.value) {
      this.value = newValue;
      for (const reaction of this.reactions) {
        reaction.run();
      }
      return true;
    } else {
      return false;
    }
  }
  run() {
    if(!this.fn) return;
    const currentObserver = CurrentObserver;
    CurrentObserver = this;
    const oldDependencies = this.dependencies;
    this.dependencies = new Set(); 
    const newValue = this.fn();
    CurrentObserver = currentObserver;
    for(const dep of oldDependencies){ 
      if(!this.dependencies.has(dep)){
        dep.reactions.delete(this);
      }
    }
    const changed = this.set(newValue);
    if (changed && this.tracked && this.reactionFn){
      const currentObserver = CurrentObserver;
      CurrentObserver = null;
      this.reactionFn();
      CurrentObserver = currentObserver;
    }
    this.tracked = true;
  }
  unsubscribe(){
    for(const dep of this.dependencies){
      dep.reactions.delete(this);
    }
    this.tracked = false;
  }
}

function connect(target){
  return class extends (target instanceof React.Component ? target : React.Component) {
    constructor(...args){
      super(...args);
      this._cell = new Cell(null, ()=>{
        return target instanceof React.Component ? super.render() : target(this.props);
      }, ()=>{
        this.forceUpdate(); //здесь вместо setState({}) используется forceUpdate() потому что у компонента может и не быть своего состояния
      });
    }
    render(){
      return this._cell.get();
    }
    componentWillUnmount(){
      this._cell.unsubscribe();
    }
  }
} 

Теперь выясним режимы обновления нашей обcерверов. В примере выше у нас пока все обcерверы активные — после того как первый раз вызвался .get он подписался на свои dependencies и будет вызываться каждый раз когда какая-то зависимость изменит свое значение. Этот режим удобен для компонентов которые должны обновляться каждый раз когда изменились данные на которые они подписаны но есть так называемые "кешируемые" или "мемоизированные" функции для которых такое поведение нежелательно. Например есть обзервер const fullName = new Cell(()=>firstName.get() + lastName.get()) который должен вычислять полное имя когда изменится либо имя либо фамилия. Но что если после того как он вычислится к fullName в приложении при каких-то условиях обращаться не придется? Мы получим лишнее вычисление и чтобы этого избежать можно сделать так чтобы компонент вычислялся не сразу а только когда к не нему обратятся — при вызове .get().


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


Давайте рассмотрим такую ситуацию — есть четыре ячейки — firstName, lastName, fullName (которая вычисляет полное имя) и label (которая выводит либо имя если оно длинное иначе полное имя)


const firstName = new Cell("fff");
const lastName = new Cell("lll"); 
const fullName = new Cell("", ()=>firstName.get() + " " + lastName.get());
const label = new Cell("", ()=>firstName.get().length <= 3 ?  fullName.get() : firstName.get()))

Здесь самый простой вариант ромбовидных зависимостей — от firstName зависит fullName, от fullName зависит label но label также зависит и от firstName и получается как бы цикл.
Надо уточнить что в процессе нас интересует перевычисление только значения ячейки label (например нужно отрендерить в компоненте) поэтому если значение fullName для label вдруг вычислять не требуется то его вычислять и не стоит.


И вот первый баг — при измении firstName — в нашей реализацией Cell когда мы вы цикле вызываем подписчиков у нас компонент label будет вычисляться дважды — первый раз firstName вызовет label потому что он непосредственно него подписан, а второй раз label вычисляется когда fullName изменит свое значение. Первое вычисление label не нужно потому что содержит временные данные — новое имя и старое fullName. Соотвественно нам нужно избавиться от ненужных вычислений и сделать мы это можем только вызвав подписчиков в правильном порядке — сначала fullName а потом label.


Как мы это можем сделать? Если подумать то есть парочка вариантов.


Одним из вариантов является способ "dirty-clean" который описан автором mobx в его докладе про устройство mobx (https://www.youtube.com/watch?v=TfxfRkNCnmk) (забавно что автор по факту солгал потому в самом mobx реализуется не этот а более правильный алгоритм но об этом позже).



Вкратце алгоритм состоит из способа распространения вызова функции по графу зависимостей и выявление значение "глубины" каждой зависимости через инкремент-декремент счетчика и потом вызов их в порядке увеличения глубины. Пусть при изменении имени, ячейка firstName не будет сразу вызывать подписчиков в цикле, а установит внутри каждого из слушателей значение 1 и вызовет их чтобы каждый установил значение своих подписчиков на 1 больше чем у него самого. И так рекурсивно. Ячейка fullName получит значения 1 а ячейка label получит значение 2 потому что счетчик увечили сначала ячейка firstName а потом и ячейка fullName. Теперь, после того как рекурсивный вызов закончился, ячейка fistName вызывает обратную процедуру — уменьшение счетчика рекурсивно у своих подписчиков. И теперь момент — после того как вызвался код уменьшения счетчика надо проверить если значение вернулось к нулю то только тогда следует выполнить перевычисление ячейки. Итак, произойдет уменьшение счетчика label с 2 до 1 (но не вычисляется потому что не 0) потом уменьшится счетчик fullName c 1 на 0 и вычислится fullName и только потом вычислится сам label потому что fullName после вычисление вызовет уменьшение счетчика label c 1 до 0.


Таким образом мы получили вычисление label только один раз после того как все зависимые ячейки сами обновятся и будут иметь актуальное значение.


Другим вариантом (который по факту является оптимизированной версией первого) будет идея вызвать подписчиков в порядке увеличения их глубины. Под глубиной ячейки примем максимальное значение глубины своих зависимых ячеек + 1 а ячейка без формулы которая не имеет зависимостей будет иметь глубину 0. Получаем что firstName и lastName будут иметь значение 0, fullName будет иметь значение 1 а label будет иметь значение 2 потому что максимальное значение у подписчиков (fullName и firstName) равно 1, делаем +1 получаем 2.


Теперь когда ячейка fistName обновит свое значение она должна вызвать своих подписчиков в порядке увеличение глубины — сначала fullName а потом label. Массив можно сортировать каждый раз при вызове, а можно оптимизиировать и сделать вставку в отсортированный массив в момент добавления новой зависимости.


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


Таким образом мы получим вызов подписчиков в правильном порядке и избежим лишний вычислений. Почти...


В обоих вариантах есть один очень неприметный баг. Формула ячейки label не просто зависит от firstName и fullName — она зависит от них при определенных условиях. Если значение firstName.get().length <= 3 то мы выводим fullName но если значение больше 3 то мы зависим только от firstName. А теперь подумаем что происходит при когда значение firstName меняется с 4 на 3. Ячейка firstName обновит свое значение и должна вызвать подписчиков в порядке глубины — сначала будет вызов fullName который вычислит свое значение а потом вызов label который вычислит свое значение уже имея актуальное значение fullName. На первый взгляд кажется все правильно. Но если подумать то вычисление fullName на самом деле здесь не нужно — потому что значение fistName будет равно 3 а значит когда последним вызовется label ему не потребуется вызвать fullName.get() потому что ветка if просто не выполнится. Причем, в следующий раз, когда потребуется вызвать fullName его значение будет неактуально потому что между его вызовом может сколько угодно раз обновляться lastName. Вот вам и баг с лишним вычислением. В итоге наш алгоритм с вызовом подписчиков в порядке их глубины не работает в общем случае.


Итак существует тот самый "правильный" алгоритм, который ни при каких условиях и хитросплетенных зависимостях не вызовет двойного вычисления ячейки. Для начала приведу код, который по совместительству является почти полноценной версией mobx (за исключением массива и декораторов) всего в 85 строчках кода


class Cell {
  reactions = new Set();
  dependencies = new Set();
  runned = false;
  constructor(value, fn  = null, reactionFn = null, active = false) { 
    this.value = value;
    this.fn = fn;
    this.reactionFn = reactionFn;
    this.state = fn ? "dirty" : "actual";
  }
  get() {
    if (this.state !== "actual") this.actualize();
    if (CurrentObserver) {
      this.reactions.add(CurrentObserver);
      CurrentObserver.dependencies.add(this);
    }
    return this.value;
  }
  set(newValue) {
    if (newValue !== this.value) {
      this.value = newValue;
      for (const reaction of this.reactions) {
        reaction.mark(true);
      }
      runPendingCells()
      return true;
    } else {
      return false;
    }
  }
  mark(dirty = false) {
    this.state = dirty ? "dirty" : "check";
    for (const reaction of this.reactions) {
      if(reaction.state === "actual") reaction.mark();
    }
    if (this.active) PendingCells.push(this);
  }
  actualize() {
    if (this.state === "check") {
      for (const dep of this.dependencies) {
        if(this.state === "dirty") break;
        dep.actualize();
      }
      if(this.state === "dirty"){
        this.run();
      } else {
        this.state = "actual"
      }
    } else if(this.state === "dirty"){
      this.run();
    } 
  }
  run() {
    if (!this.fn) return;
    const currentObserver = CurrentObserver;
    CurrentObserver = this;
    const oldDependencies = this.dependencies;
    this.dependencies = new Set();
    const newValue = this.fn();
    CurrentObserver = currentObserver;
    for (const dep of oldDependencies) {
      if (!this.dependencies.has(dep)) dep.reactions.delete(this);
    }
    const changed = this.set(newValue);
    this.state = "actual";
    if (changed && this.reactionFn) {
      const currentObserver = CurrentObserver;
      CurrentObserver = null;
      this.reactionFn(!this.runned);
      if(!this.runned) this.runned = true;
      CurrentObserver = currentObserver;
    }
  }
  unsubscribe() {
    for (const dep of this.dependencies) {
      dep.reactions.delete(this);
      if(dep.reactions.size === 0) dep.unsubscribe();
    }
    this.state = "dirty";
  }
}
function runPendingCells() {
  for (const cell of PendingCells) {
    cell.actualize();
  }
}

А теперь описание:
Пусть ячейка будет иметь три состояния — "actual" (которое значит что значение формулы актуально), "dirty" (которое будет значит что как только вызовется get() ячейка должна пересчитаться) и "check". Теперь как только ячейка изменит свое значение она не будет сразу вызывать вычисление подписчиков в каком-либо порядке а пометит своих подписчиков как "dirty". А те в свою очередь тоже пометят своих подписчиков но только значением "check" а те в свою очередь тоже пометят своих подписчиков значением "check", и так далее рекурсивно до конца. То есть только подписчики той ячеки которая изменилась будут иметь значение "dirty" а все остальные до конца дерева — значение "check", а чтобы при рекурсивном вызове мы не зациклились надо вызывать рекурсию только для тех ячеек которые еще не были помечены (имеют значение "actual").


Дальше при достижении конца дерева — то есть той ячейки у которой больше нет подписчиков и она является "активной" надо добавить такую ячейку в неких глобальный массив PendingCells. "Активной" является ячейка которая представляет не какую-то мемоизированную функцию (значение которой может не понадобиться прямо сейчас) а реакция (например компонент реакта) которая должна запускаться каждый раз когда любая из зависимых ячеек меняет свое значение.


В итоге, когда ячейка изменила свое значение и вызвала этот рекурсивный процесс для своих подписчиков, у нас в глобальном массиве PendingCells будут находится некие root-ячейки у которых нет зависимостей но которые прямо или косвенно могут зависеть и соотвественно либо будут пересчитываться (если вдруг все промежуточные ячейки в цепочке поменяют свое значение) либо не будут (если кто-то в этой цепочке при перевычислении не изменит свое значение)


Теперь переходим ко второму этапу. Ячейка которая изменилась и вызвала для своих подписчиков рекурсивный процесс, вызывает некую глобальную функцию flush() которая возьмет ячейки которые накопились в глобальном массиве PendingCells и вызовет у них функцию actualize(). Эта функция будет рекурсивной и будет делать вот что — если значение ячейки является "dirty" она вызовет перевычисление своей формулы (а мы помним что значение "dirty" будут иметь только ячейки которые являются прямыми подписчиками ячейки которая изменилась, а все остальные до конца дерева будут иметь значение "check"). Если же значение равно "check", то ячейка попросит свои зависимые ячейки актуализироваться (вызовет метод actualize()) и после этого снова проверит свое значение и если оно равно "check" то мы меняем значение на "actual" и не вызываем перерасчет, если же оно "dirty" то мы соответственно должны вызвать перевычисление. При этом, проверку на "dirty" нужно после вызова "actualize()" на каждой зависимой ячейке, потому что если ячейка приняла значение "dirty" нет смысла вызывать актуализацию других ячеек и можно сразу прервать цикл и выполнить перерасчет. А то что остальные ячейки не актуализировались, это уже неважно, так как если произойдет обращение к ячейке чтобы получить значение формулы в методе .get(), ячейка должна проверить свое значение и если оно "check" то она должна вызвать этот метод actualize() а если "dirty" то соотвественно выполнить перерасчет. Вот и все, конец алгоритма.


Итак алгоритм на первый взгляд может показаться сложным но он достаточно простой — когда ячейка меняет свое значение у нас всего 2 этапа — первый этап это рекурсивный спуск чтобы пометить как dirty (для первого уровня) и check для всех остальных а второй этап это рекурсивный подъем при котором происходит актуализация значений.


Теперь проясню некоторые неочевидные моменты.


Первое — каким образом происходит избежание того бага с лишним перерасчетом? Это происходит потому что у нас нет жесткого условия вызывать перевычисление зависимых ячеек у ячейки которая изменились. Зависимые ячейки будут помечены как dirty, и все — они вычислятся только когда где-то потребуется узнать их значение. То есть, в примере с багом — ячейка fullName будет просто помечена как "dirty" а потом вычислять ее значение не потребуется так как в label выполнится условие firstName.get().length === 3 и label больше не будет зависеть от fullName.


Второе — почему такое странное действие — внутри метода actualize() — проверить — если значение равно "check" то вызвать actualize() у зависимых ячеек и в процессе этого и также после цикла снова повторно проверить значение и если "dirty" то прервать цикл и вызвать перерасчет а если "check" то сбросить после цикла на "actual" и ничего не делать? Все дело в том что в процессе вызова actualize() у зависимых ячеек некоторые из них могут иметь значение "dirty" и как мы знаем они должны выполнить перерасчет. А при вычислении есть условие — если ячейка поменяла свое значение то она должна пометить своих слушателей как "dirty". И таким образом ячейка которая до этого была "check" может после актуализации своих зависимых ячеек сама изменить значение когда изменится кто-либо из них и соотвественно нужно проверить условие снова. Но только в этом случае если никакие зависимые ячейки не изменили свое значение то значит и самой ячейки смысла вычисляться нет и мы меняем значение с "check" на "actual"


Ну а теперь мы можем проверить действие этого алгоритма на нашем примере с багом. Меняется firstName, ячейки label и fullName помечаются как "dirty" и только label попадает в глобальный массив PendingCells потому что fullName не является "активной" ячейкой как label а просто мемоизирует свое значение и обновится только в момент обращения к ней а не сразу. Дальше label поскольку имеет значение "dirty" сразу выполнит перерасчет но поскольку firstName.get().length === 3 значение fullName нам не потребуется и мы таким образом избежим лишнего перевычисления.


Честно сказать описание алгоритма занимает куда больше места чем его реализация. Этот код на typescript а также пример с реактом и тест на баг с вычислениями находится в репозитории (https://github.com/bgnx/xmob)

Вы можете помочь и перевести немного средств на развитие сайта

Теги:



Комментарии (14):

  1. ETCDema
    /#10667036

    А топологическая сортировка для определения порядка и логирование измененных полей в цикле пересчета для уменьшения количества вычислений не проще будет?

    • mayorovp
      /#10667066

      Нет, не проще. Проблема в том, что при динамическом сборе зависимостей мы не знаем реального набора зависимостей пока выражение не будет посчитано. Правильная топологическая сортировка в таких условиях невозможна.

  2. Riim
    /#10667216

    > Причем, в следующий раз, когда потребуется вызвать fullName его значение будет неактуально потому что между его вызовом может сколько угодно раз обновляться lastName

    неактуальным в смысле неверным? Обновление lastName заставит обновиться и fullName, разве нет?

    • bgnx
      /#10667316

      Ячейка label больше не будет зависеть от fullName а fullName так как от него никто не зависит и он не является «активным» обсервером то тоже отпишется от своих зависимостей и больше не будет вычисляться когда будет обновляться lastName

      • Riim
        /#10667380

        Ячейка label больше не будет зависеть от fullName а fullName так как от ...

        Да, верно. Это довольно легко поправить. В cellx можно подсмотреть как.


        существует тот самых "правильный" алгоритм, который ни при каких условиях и хитросплетенных зависимостях не вызовет двойного вычисления ячейки

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


        let a = new Cell(1);
        let b = new Cell(1, () => {
            console.log(123);
            return a.get();
        });
        
        b.get();
        
        a.set(5);
        a.set(1);
        
        b.get();

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

        • bgnx
          /#10667406

          Это не те лишние вычисления которые связаны с алгоритмом. В статье я рассматривал ситуации избегания лишних вычислений только при изменении одной ячейки. Если же нужно чтобы несколько изменений одной или разных ячеек накапливались и выполнялся в итоге толко один набор перевычислений то это легко добавить. Тут есть два способа. Первый это написать некий враппер подобно декоратору action mobx внутри которого будем выполнять все операции обновления. При вызове этого враппера устанавливаем глобальных флаг и потом ячейка посмотрит на этот флаг будет вычисляться не сразу а добавится в некий временный массив. А в конце вызова этот враппер снимет глобальных флаг и вызовет обновление накопившихся ячеек. Но у этого варианта есть недостаток — нужно постоянно врапить асинхронные операции и так же он будет работать с async-await. А вот вторым вариантом является установка минимального таймера и отложенный пересчет ячеек после того как произойдет синхронная установка новых значений

          • bgnx
            /#10667424

            Кстати я тут описал общий способ реализации этих двух вариантов но для алгоритма которого я описал в статье (рекурсивный спуск и подъем) реализация будет состоять в добавлении всего нескольких строчек. В примере в статье я убрал для наглядности но в варианте который находится в репозитории уже добавлена реализация второго варианта с таймером. И никаких лишних вычислений у нас снова нет)

            • Riim
              /#10667474

              В статье я рассматривал ситуации избегания лишних вычислений только при изменении одной ячейки

              в примере программист меняет только ячейку [a], да и зачем вообще такое ограничение? Вы вообще не рассчитываете, что программист захочет поменять сразу две ячейки? Ну и вы видимо не поняли природу этого лишнего вычисления, action из mobx здесь не причём, здесь [b] помечается как протухшая, а дальше [a] принимает исходное значение, но [b] по прежнему остался протухшим хотя очевидно, что пересчитывать его нет смысла.

              • bgnx
                /#10667516

                Я решил разбирать сложности по очереди. Если лишние вычисления появляются уже при изменении только одной ячейки то что говорить про множественные изменения? Поэтому в статье и описывается три алгоритма уменьшения вычислений при изменении одной ячейки где только последний («спуск-подъем») обеспечивает наименьшее количество вычислений.

                Насчет множественных изменений — нам нужно чтобы при выполнении какого-то обрабочика события мы могли выполнить множественное обновление стора, например поменять много свойств на объекте (или в разных объектах без разницы) но чтобы компонент перерендерился только один раз в конце всех наших действий а не синхронно после каждого изменения поля. action декоратор выполняет это через обертку и флаги, а в репозитории xmob есть пример где все вычисления будут выполняться не синхронно а один раз после таймаута когда все изменения после закончаться.

                Насчет примера с когда значение одной ячейки может после нескольких изменений вернуться в первоначальное значение. Тут я согласен, вычисления быть не должно но это наверное настолько редкая ситуация что я пока не могу придумать реалистичного кейса чтобы после нескольких синхронных изменений значение ячейки вернулось в первоначальное состояние. Но даже если такой редкий кейс найдется, то можно легко модифицировать алгоритм так чтобы не было установки флага «dirty» на зависимых ячейках сразу а происходила проверка изменилась ли ячейка уже в процессе актуализации после таймера

                • Riim
                  /#10667662

                  это наверное настолько редкая ситуация что я пока не могу придумать реалистичного кейса

                  со строками конечно редкая, а вот с числами и особенно с boolean вполне случается.


                  то можно легко модифицировать алгоритм так чтобы не было установки флага «dirty» на зависимых ячейках сразу а происходила проверка изменилась ли ячейка уже в процессе актуализации после таймера

                  вооот!) Это то, что я хотел получить! Правда я думал вы попробуете исправить реализацию в коде, а я придумаю следующий пример ломающий исправление. Ну да ладно, и так норм. Так вот, так не получится :). Во-первых, программист может захотеть прочитать зависимую ячейку до того как сработает таймер, который её "состарит" и она выдаст неактуальное значение, во-вторых, усложняем пример до четырёх ячеек:


                  let a = new Cell(1);
                  let b = new Cell(2);
                  let c = new Cell(() => a.get() + b.get());
                  let d = new Cell(() => c.get());

                  а теперь меняем [a] и [b] так что бы [c] не изменился:


                  a.set(2);
                  b.set(1);

                  дальше запускается "состаривающий" проход, он правильно состаривает [c], тк. [a] и [b] изменились и пересчитать (позже, после этого прохода) всё же нужно (алгоритм же не знает, что получится исходное значение), но как ему понять нужно ли состарить [d] не вычисляя пока [c]? А если здесь всё же вычислять [c], то это уже по сути возвращение к первой схеме реализации РП, в которой этой проблемы изначально нет.


                  Я потратил довольно много времени пытаясь довести вторую реализацию хотя бы до уровня первой, в плане количества подобных фич, в результате получается либо совсем уж фичасто, либо примерно так же, но совсем уж медленно. В результате какой смысл использовать вторую схему если она минимум (в простейшем варианте с бесконечным числом фич) в 5 раз медленнее первой? В 5 Карл!!! Это не на 20% и не на 30%, это на 500% медленнее!

                  • bgnx
                    /#10667806

                    Во-первых, программист может захотеть прочитать зависимую ячейку до того как сработает таймер, который её «состарит» и она выдаст неактуальное значение,

                    Для этого последнего алгоритма «cпуска-подъем» который описывается в статье нет никакой разницы сработает ли вычисление после таймера или когда программист захочет прочитать зависимую ячейку до того как сработает таймер. При вызове метода .get() если значение не равно «actual» будет точно такой же процесс актуализации зависимостей как и при вызове таймера. И соотвественно вернется всегда только актуальные значение.
                    дальше запускается «состаривающий» проход, он правильно состаривает [c], тк. [a] и [b] изменились и пересчитать (позже, после этого прохода) всё же нужно (алгоритм же не знает, что получится исходное значение), но как ему понять нужно ли состарить [d] не вычисляя пока [c]?

                    Если мы имеете ввиду невозможность после двух присваиваний избежать вычисления вообще (потому что ячейка [c] при вычислении все равно не изменит свое значение) то да тут я согласен и даже уверен избежать вычисления [c] в принципе невозможно.
                    Если же вы спрашиваете про ячейку [d] то тут все просто — она после того как вычислится [c] увидет что ее значение не изменилось и сама не будет вычисляться. (точнее это не она увидит а ячейка [c] не установит ей флаг «dirty» потому что сама не изменила значение, которое потом проверится и «check» заменится на «actual», но это сути не меняет)
                    А если здесь всё же вычислять [c], то это уже по сути возвращение к первой схеме реализации РП, в которой этой проблемы изначально нет.

                    Это в какой такой первой схеме реализации РП этой проблемы изначально нет? Нет лишних вычислений только в третьем варианте который описывается в статье (я его называю как «спуск и подъем»)

                    • Riim
                      /#10667868

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

  3. vintage
    /#10667824

    $mol_atom именно так и работает, за одним исключением.


    Если же значение равно "check", то ячейка попросит свои зависимые ячейки актуализироваться (вызовет метод actualize()) и после этого снова проверит свое значение и если оно равно "check" то мы меняем значение на "actual" и не вызываем перерасчет, если же оно "dirty" то мы соответственно должны вызвать перевычисление.

    Проверять на dirty надо не после актуализации всех зависимостей, а после актуализации каждой зависимости и при обнаружении dirty прерывать актуализацию оставшихся зависимостей, так как не факт, что их актуальные значения вообще понадобятся в этот раз. Соответственно формально вместо Set должен использоваться Array, но Set тоже сохраняет порядок добавления, так что тоже годится.

    • bgnx
      /#10667978

      Действительно, что-то я пропустил этот момент, спасибо за замечание