Saving history in a graphics editor?

Question

GIMP

Hello. So I asked myself a question - how to correctly save the history in a graphical editor (like Gimp) for use in UNDO / REDO. I myself see three options:
1. Save the list of actions.
For example, I drew a line of such and such a color in such coordinates, applied the Blur filter, rotated the image. In the case of using UNDO, all actions are passed from the first to the necessary.
Benefit : Takes up very little memory space. When you save a project, you can easily restore the entire history. If you wish, you can even store the full tree (for example, you did action A, B, C, D, E, returned to C, did F, G. The final path turned out to be ABCFG, but you can also save the DE branch in the version control system)
Disadvantage: When using Undo or loading a previously saved image, the entire path is traversed, and this can take a significant amount of time, and if with normal simple editing such a pass can take some 100-200 ms, which is not critical, then when using heavy filters it can slow down to tens of seconds .
2. Save the full dump of the project in a bitmap.
Each action we save the entire picture in memory as a finished drawing.
Advantage : Works very fast. We did undo / redo and just showed from memory the drawing that we had (already rendered). Even a heavy filter, whatever.
Flaw: Takes up a lot of memory space. Let's say we have a 1k*1k drawing. In each pixel, we store 32 bits of information (8 bits per r, g, b and 8 bits per alpha channel), that is, 4 bytes, that is, such a bitmap will ideally take us 4 meters, and a history of 64 actions - 64 *4 = 256 MB in memory. And if we assume that we have a graphic editor that supports layers and let there be at least five of them ... Similarly, it is difficult to store projects with a history.
Gimp
In Gimp, by circumstantial evidence, I determined that the second approach is being used. Signs are:
1. History is limited
2. Heavy filters on undo-redo return the status quo very quickly.
3. Combined approach
Of course there is an alternative. We store the history in the first way, and we store the last, for example, 8 actions in the second way, because seldom is such a distant undo used. Only actions can be saved to the screw, which is why a project with many changes will take a long time to open, but it is acceptable to weigh. Or else add the latest bitmap date.
Advantages of both approaches
The disadvantage is that the application logic becomes much heavier. In fact, it is necessary to implement two mechanisms of history.
Topic for discussion
What do you say? Maybe there is another approach. If not, which approach would you prefer (ideally and under very tight deadlines)? Why?

Answer 1

In my opinion, it would be logical to supplement the third method with some keyframes (similar to video), essentially a bitmap, which would be saved after heavy filters and stored not in the RAM, but on the screw (in a temporary folder). Those. as you described, the last few actions in the RAM in the form of a bitmap. History back in the form of a list of actions from keyframes (heavy filters). Yes, and it would be logical to store such key frames not in raw form, but at least in the same png. This will allow you not to slow down so much when rolling back to a distant history and save space on the screw by compressing png.
In general, the idea with keyframes could be completely applied instead of the third option. Those. small actions are stored exactly as actions, and heavier ones are stored as keyframes in the form of a bitmap in the RAM. If a heavier action is relegated to the past, then pack it into a png and drop it onto the screw.
And… regarding layers… in our case, undo is usually applied to a specific action on a specific layer, and not to all layers at the same time. Of course there are live filters, but that's another story. I mean, the number of layers does not increase the number of bitmap proportionally.

Answer 2

It is interesting to store something like the last few iterations, and for the rest to make patches like diff as a background process.

Answer 3

Is it possible in some cases to build a sequence reverse to the first?
In a sense, there are reversible changes, and there are irreversible ones. It is logical to store the key frame after the irreversible ones, and build up from the main state to the nearest reversible one in the reverse order, using the history on the existing frame, going from the end, not from the beginning.

Answer 4

What if we use geometric distribution? Save not the whole keyframes, but only the pictures from the change area, and then overlay them on top of each other?
That is, each brushstroke is the preservation of the bitmap within the grid cells where it passed, and not the entire picture.