Reduce the number of actions in the list when history gets too long

[dantman]

I'm working on an app which edits a pretty complex nested JSON document structure. However the actions aren't entirely lightweight.

They make small changes, but sometimes because of the structure of the document and action means a bit more than trivial computation needs to be done for the action to work. For example:

document = { title: 'Untitled', rows: [ { id: 'row-a', columns: [ { id: 'col-a', content: [] }, { id: 'col-b', content: [] } ] }, ... ] };
action = { type: 'ADD_CONTENT', rowId: 'row-a', colId: 'col-a', content: 'foo' };

As you can see, to run the action the reducer needs to iterate over $.rows and $.rows[1].columns to find the index of the row by id (the actual structure is a bit more complex, can require a few more of these index find loops, and may be for a really large document).

Hence while I prefer storing actions over storing state like in redux-undo. I am a little worried about what will happen if someone makes 200 actions and then presses undo. To my understanding this library works without needing an "undo reducer" to go back once in state by starting with the initial state and running all the actions except the previous one through the reducer. Which in my case would mean that when undo is pressed 199 of my actions, which are not completely lightweight, need to be run to re-compute the previous state.

Understandably I would like to be able to limit the number of history entries. I understand that implementing redux-undo style with a limit would probably be expensive/difficult. But I would like a way to trim the list down. Say, if after an action the list grows to >= 200 items I strip out the first 50 items by computing the state after 50 actions and inserting some sort of 'initial state' action at the start of the list instead of them.

[JannicBeck]

Hi,

first of all I understand your concerns and I also thought about implementing a limit the way you suggested with intermediate states being stored on certain points in the history (aka store the state every 100 actions) and recompute from there.

I decided against this, as Undox is really a trade of between time and space complexity, focusing purely on optimizing for space complexity to store application state in the localStorage or any other database.

That said, I'm open to re evaluating this, since we could also cache these intermediate states inside the undox reducer, which would mean you would only have to run 199 actions once and have intermediate states cached in memory after that. The difference being, that these intermediate states won't be part of the state tree and thus not take up space inside localStorage or other db's.

However I don't think your use case needs any of this at all:

1. Your time complexity is O(rows * columns * actions)

As you mentioned 200 actions from my experience this should not be a problem, unless you are really dealing with HUGE lists. But I recommend just trying it out, and see if you run into performance problems. Otherwise I would not bother to optimize prematurely.

2. In the case you really see performance problems

You might want to re evaluate how your store your state. E.g. your might want to use JavaScript Objects instead of arrays, since they are implemented as Hashes. You could then use rowId and colId as a Hash key

document = {
  title: 'Untitled', 
  rows: {
    row-a: {
      id: 'row-a',
      columns: {
        col-a: { id: 'col-a', content: [ ] },
        col-b: { id: 'col-b', content: [ ] }
      },
    },
    row-b: {
      id: 'row-b',
      columns: {
        col-a: { id: 'col-a', content: [ ] },
        col-b: { id: 'col-b', content: [ ] }
      }
    }

  }
}

So you just need to do two lookups: rows[rowId][colId] instead of nested for loops. Which would result in O(1) * O(1) * O(actions) = O(actions)

Alternatively you could also just store cells in a Hash with rowId+colId as key so you can do a lookup like this: cells[rowId+colId]. Aka something like this:

document = {
  title: 'Untitled', 
  rows: {
    row-a: [cell-aa, cell-ab],
    row-b: [cell-ba, cell-bb]
  },
  cols: {
    col-a: [cell-aa, cell-ba],
    col-b: [cell-ab, cell-bb]
  },
  cells: {
    cell-aa: { id: 'cell-aa', content: [] },
    cell-ab: { id: 'cell-ab', content: [] },
    cell-ba: { id: 'cell-ba', content: [] },
    cell-bb: { id: 'cell-bb', content: [] }
  }
}

Also take a look at https://redux.js.org/recipes/structuring-reducers/normalizing-state-shape
This is basically what I am trying to say here.

[dantman]

For other reasons I have actually refactored my template structure to a top level hash based structure like you describe. So my basic actions aren't as heavy, however I'm still a little worried, they are lighter but that doesn't mean they are completely light. I say hundreds as an example because you probably don't need an undo history longer than that. But I'm working on a builder for authoring forms, there could be thousands or even higher magnitudes of actions dispatched while creating a large one. I have no clue how massive the list of actions will get in production.

And I'm trying to use this in an enterprise web application that's going to be deployed to piles of clients. I'm already trying to convince them undo/ngrx-undoable are worth using, even though they are worried about them being one-man libraries with few downloading users and suggesting I use redux-undo even if it's not as well suited to the application.

I cannot very well say "if it turns out we do have performance issues we didn't anticipate, there is nothing in the library that will let us work around it, we'll have to get this fixed upstream or internally and wait with bugs in the live application until we're done adding the feature".

Oh, side note at the moment I ended up choosing ngrx-undoable instead of undox so its easier to use Redux DevTools. But this bug really applies the same to both libraries.

[JannicBeck]

First of all all redux-undo is a one man library too.
It is a good library to start with and I used it in the beginning as well. But it doesn't suit every use case and I'm not a big fan of bloating libraries with features and options for every single use case. Hence I wrote ngrx-undoable. I use ngrx-undoable in a production application with 300+ actions and non-trivial logic inside reducers. So far I have not experienced any performance problems even on tablets like the amazon fire tablet, which have limited processing power.
While with redux-undo my application slowed down significantly and was becoming unresponsive with even 50+ actions.

Also it shouldn't be much of a deal to switch back to redux-undo either, if one might find out that its a better fit for their application.

I have no clue how massive the list of actions will get in

Well then you better find out before shipping your product. There are more things than just this package, that could end up being a bottleneck.

That said, I will look into adding an optional limit for the history, as this seems to be a reasonable feature. I will also look at implementing memoization into the undo reducer, but the cached states won't be returned (they will not be part of your redux store), since this would go against the gist of this library. Aka storing actions instead of states, so we don't fill databases like localStorage with lists of huge state objects.

[JannicBeck]

This will be implemented in ngrx-undoable