[HN Gopher] Serialization-Based Undo
___________________________________________________________________
Serialization-Based Undo
Author : prideout
Score : 70 points
Date : 2021-10-17 18:51 UTC (1 days ago)
(HTM) web link (prideout.net)
(TXT) w3m dump (prideout.net)
| hoseja wrote:
| >but since I'm not a fan of C++ streams, it doesn't use them
| internally
|
| Nobody does, it's one of the worst mistakes of C++.
| formerly_proven wrote:
| Unfortunately many C++ tutorials mention or use iostreams which
| makes it look like it's a good idea to use iostreams.
| catern wrote:
| This is cool, but I don't understand the justification for why a
| more traditional "just store a sequence of events" undo system
| wasn't possible. As the author says in the post on the scripting
| system, the game scripts access virtual interfaces. Those could
| just record the methods called before forwarding them on -
| doesn't matter that the scripts make arbitrary method calls. It
| seems to me that there's nothing inherent to "the level script is
| arbitrary code rather than a list of commands as data" that makes
| that style of undo impossible.
| qsort wrote:
| Well, yes, it does matter, because there's no guarantee that
| you can safely compute and execute the inverse operation.
|
| Same reason debuggers don't have a "step back" button.
|
| Strictly from a computation theory point of view, you could
| obviously store a list of executed opcodes and undo by
| replaying up to the (N-1)th operation, but I think they want to
| avoid the overhead.
| johnday wrote:
| "Forward replay" was actually the mechanism that Tabletop
| Simulator originally used for its undo system.
|
| After around 30 minutes of playing games in the simulator,
| pressing "Undo" would hang the client and likely disconnect
| most people connected to the server.
|
| It's not a great way to implement undo.
| royjacobs wrote:
| It can be quite tricky to get right once you get into ownership
| issues. If you delete an item, undo'ing that should reinstate
| it. So that undo step becomes the owner of the data of the
| item, otherwise it couldn't reinstate it. This can already
| become a bit complicated if you're dealing with memory
| management of this item. Do resources that the item uses get
| deleted immediately, or do you want to keep them around in your
| undo state too? If the resource requires a lot of processing
| then that may be the only option.
|
| This then grows more complex if items have parent-child
| relationships and you also need to start storing all the
| information required to completely reinstate all the children,
| possibly also in the same order they were originally created
| in.
|
| You know, tricky.
| jcelerier wrote:
| > It can be quite tricky to get right once you get into
| ownership issues. If you delete an item, undo'ing that should
| reinstate it. So that undo step becomes the owner of the data
| of the item, otherwise it couldn't reinstate it. This can
| already become a bit complicated if you're dealing with
| memory management of this item. Do resources that the item
| uses get deleted immediately, or do you want to keep them
| around in your undo state too? If the resource requires a lot
| of processing then that may be the only option.
|
| yep, as soon as you have an object graph serialization is the
| only way to stay sane. Anecdotally that's what I do in
| https://ossia.io with Qt's QDataStream and serializing /
| deserializing hundreds of steps is pretty much instant. A
| nice benefit of it is to be able to provide a "restore on
| crash" feature: the undo/redo stacks get saved to disk and
| can be used to go back to the exact state the user left if a
| crash happens
| steeleduncan wrote:
| It is interesting to compare this to Jonathan Blow's talk on the
| rewind system in Braid [1].
|
| This stores complete game states using a compression library to
| keep memory under control, whereas Braid stored a combination of
| keyframes, and diffs from those keyframes, to avoid using a
| compression library.
|
| [1] https://www.youtube.com/watch?v=8dinUbg2h70
| Strilanc wrote:
| This is the design I also usually use for undo/redo. Actually for
| small interactive editors I like to go further and make it so
| that anytime you do anything the program serializes its state and
| loads it back in. This is sometimes too costly but has unexpected
| reliability benefits. It makes sure your serialization code is
| well exercised, it ensures most of your program states are
| linkable/nameable, and also it's sort of like every time you do
| anything you're restarting the program. There's much less
| implicit state that can cause problems. And as a fallback if you
| do get the program into a bad state you can just hit undo and
| you're back into a good state.
| rocqua wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| adrusi wrote:
| If photo editors have an internal representation of all
| operations in the history of the document and the ability
| to recompute them all up the a given point, and they
| DON'T expose this to the user except through the undo
| button, that's a pretty big failure of design.
| UncleEntity wrote:
| I know some of them let you see the undo history and let
| you pop (and maybe reorder items) that aren't at the top
| of the stack.
| simulo wrote:
| Micrografx Picture Publisher allowed that more than
| 20years ago, but it is the only image editor I know of
| that did this
___________________________________________________________________
(page generated 2021-10-18 23:02 UTC)