3 ms·

Essentially the idea here is not to muck about with diffs or event / command based sourcing. Just store each internal state you might want to recover, in full.

by rocqua 5y ago

Essentially the idea here is not to muck about with diffs or event / command based sourcing. Just store each internal state you might want to recover, in full. Except use compression to store the states you want to recover. In this article, the compression is done based on the 'initial state'. I imagine there is flexibility on maybe 'checkpointing' some states once the difference becomes to big. Maybe do the compression not with a prefix of the 'initial' state but with a prefix of the entire undo history. All this requires is halfway efficient serialization / deserialization implementation, and access to Zstandard (I guess other compression algorithms also work). I think the key trick here is that, if you can serialize to bytes, you can just use compression methods as a replacement for storing diffs or other complicated methods for de-duplicating data. This could be a really powerful method to really easily keep a state history without high performance cost. From the developer p.o.v. its like you have each previous state at your fingertips. Whilst in reality the compression ensures it is stored efficiently.

devit 5y ago
This only works if the commands update only a few bytes. This would not work, for instance, in an image editor with an "adjust brightness/contrast" command since that changes the whole image. It's also inefficient since you need to examine the whole state to generate the diffs, so in general it's not a great solution.
- saurik 5y ago
  What isn't the alternative you are comparing against, though? Keeping a command history from the start of time and re-executing all of it to undo one step? You can't just "undo" a brightness/contrast change as that operation isn't perfectly "reversible" (if this isn't obvious, drag the contrast so low that the entire image turns grey and now try to "undo" that given only what you did and a fully-grey buffer). If you keep checkpoints so you can replay smaller segments, that's effectively the same thing as what this is suggesting (with respect to what has to be implemented and the overall scale of storage required), but with a checkpoint for every step (which is a constant divisor).
  - devit 5y ago
    Reexecuting it all is the simplest strategy if you don't need to undo often or the performance is acceptable anyway. But in general, every command would generate an "undo record" with information to undo it. In case of the brightness/contrast change you can do that by undoing in the naive way and then storing the difference between the "naively undone" image and the origignal version, compressed, in the undo record. In general the undo record will only be large if you lose a lot of information, and then there won't be as much information left to lose and thus the next undo records won't be able to be so large, so overall the total size of the compressed current image and undo record will amortize and be in the range of the size of the original image plus the command description. For example, once you turn the image fully grey, then all per-pixel transformations will be either be reversible or the undo record will compress to the effect on one pixel since it's the same for all the image. This doesn't hold however if you also have operations that create information (e.g. something that draws a pseudorandom image with you then adjust contrast on, resulting in a pseudorandom undo record that you can't compress with standard techniques): in that case I think reexecuting the command history is the only space-efficient solution that doesn't require coding for the specific application.
    - saurik 5y ago
      This "undo record" sounds like (essentially) the same thing as storing the (compressed) diff from the current state to the prior state which you were arguing against. If you have an operation that is changing a lot and isn't reversible, either you are reexecuting from the beginning of time (which particularly for image editing would be ridiculous: even a single operation on the image is often annoyingly slow, much less suddenly doing tons as you rapidly make changes and then undo back through them) or you are storing checkpoints at some frequency in the form of diffs on the full serialized state (which seems to be what you are returning to re-suggest anyway).
  - dragontamer 5y ago
    > Keeping a command history from the start of time and re-executing all of it to undo one step? Someone needs to play around with NLE video editors. Because yes, that's what they basically do. The video editing steps are all items on the "timeline". When you hit the "render" button, the computer goes into overdrive: spinning up a bunch of threads (maybe even GPU-kernels) and actually calculates everything. What you see in the preview-screen doesn't always match the final render. The preview-screen is just a quickie-calculation, much like how 3d programs (ex: Blender) have a realtime renderer (see Eevee) vs the offline, more accurate renderer (see Cycles). --------- From an NLE perspective: the GUI is basically a glorified editor of commands.

by rocqua 5y ago

devit 5y ago

This only works if the commands update only a few bytes. This would not work, for instance, in an image editor with an "adjust brightness/contrast" command since that changes the whole image. It's also inefficient since you need to examine the whole state to generate the diffs, so in general it's not a great solution.

saurik 5y ago
What isn't the alternative you are comparing against, though? Keeping a command history from the start of time and re-executing all of it to undo one step? You can't just "undo" a brightness/contrast change as that operation isn't perfectly "reversible" (if this isn't obvious, drag the contrast so low that the entire image turns grey and now try to "undo" that given only what you did and a fully-grey buffer). If you keep checkpoints so you can replay smaller segments, that's effectively the same thing as what this is suggesting (with respect to what has to be implemented and the overall scale of storage required), but with a checkpoint for every step (which is a constant divisor).
- devit 5y ago
  Reexecuting it all is the simplest strategy if you don't need to undo often or the performance is acceptable anyway. But in general, every command would generate an "undo record" with information to undo it. In case of the brightness/contrast change you can do that by undoing in the naive way and then storing the difference between the "naively undone" image and the origignal version, compressed, in the undo record. In general the undo record will only be large if you lose a lot of information, and then there won't be as much information left to lose and thus the next undo records won't be able to be so large, so overall the total size of the compressed current image and undo record will amortize and be in the range of the size of the original image plus the command description. For example, once you turn the image fully grey, then all per-pixel transformations will be either be reversible or the undo record will compress to the effect on one pixel since it's the same for all the image. This doesn't hold however if you also have operations that create information (e.g. something that draws a pseudorandom image with you then adjust contrast on, resulting in a pseudorandom undo record that you can't compress with standard techniques): in that case I think reexecuting the command history is the only space-efficient solution that doesn't require coding for the specific application.
  - saurik 5y ago
    This "undo record" sounds like (essentially) the same thing as storing the (compressed) diff from the current state to the prior state which you were arguing against. If you have an operation that is changing a lot and isn't reversible, either you are reexecuting from the beginning of time (which particularly for image editing would be ridiculous: even a single operation on the image is often annoyingly slow, much less suddenly doing tons as you rapidly make changes and then undo back through them) or you are storing checkpoints at some frequency in the form of diffs on the full serialized state (which seems to be what you are returning to re-suggest anyway).
- dragontamer 5y ago
  > Keeping a command history from the start of time and re-executing all of it to undo one step? Someone needs to play around with NLE video editors. Because yes, that's what they basically do. The video editing steps are all items on the "timeline". When you hit the "render" button, the computer goes into overdrive: spinning up a bunch of threads (maybe even GPU-kernels) and actually calculates everything. What you see in the preview-screen doesn't always match the final render. The preview-screen is just a quickie-calculation, much like how 3d programs (ex: Blender) have a realtime renderer (see Eevee) vs the offline, more accurate renderer (see Cycles). --------- From an NLE perspective: the GUI is basically a glorified editor of commands.