9 ms·
What's been wrought using the Piece Table? (2014)
- nerdponx 9y agoWhat was wrong with the original title? It was "What's been wrought using the Piece Table?"
- punnerud 9y agoI had no idea what a Piece Table was and how important it is, so I wanted it also to be reflected in the title.
- castis 9y agoI would hazard a guess that others, like myself, would have simply passed this article by, not knowing what a piece table was. I know now, which I hope is the important part. https://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table
- JadeNB 9y agoIt seems a bit click-baity ("well, what has been wrought using it?"). I suppose that the current one is arguably still a bit so (it could be "How the piece table enabled unlimited undo …"), but it seems better to me.
- yodon 9y agoHmmm... my guess is you're probably not making a whole lot off those ads on your website if "What's been wrought using the Piece Table?" strikes you as click baity.
- always_good 9y agoThey're referring to the format of "click to find out!" when it can be mentioned right there in the title. That nobody is going "oh boy, so what has been wrought using the piece table?" is part of their point.
- punnerud 9y agoClick to find out without the normal read the whole article to find out? You are given a new title when you enter the site. Those two combined give you more then enough information to figure out if you already know it. And if you already knew that Word is using the algorithm, you would probably just skipped or opened the link to verify that is was this algorithm. All this combined, do you mean I should have kept the original title?
- cnp 9y agoThe old one conveys much less information than the new, all things considered
- dang 9y agoWe've changed the title back to that. It was "The Algorithm that enabled unlimited undo and fast save/copy-paste in Word" before. One secret of HN titles is that sometimes the non-original title helps a story make the front page but then reverting it to the original makes it more interesting again.
- kornish 9y agoFor context, this was almost certainly submitted because of a recent submission about data structures for use in text editors. If anyone wants to check out the comments: https://news.ycombinator.com/item?id=15381886 https://news.ycombinator.com/item?id=15381886.
- punnerud 9y agoTrue, but the original post only partially talk about the algorithm at the end (when I almost was on my way to leave the article). The link I posted was mentioned as a cool read in between, but I feel it deserve more credit and readers.
- kornish 9y agoAbsolutely. Thanks for posting!
- thomastjeffery 9y agoIf you are interested, I wrote a quick Piece Table implementation in Haskell there.
- joeax 9y agoI was tasked with writing a undo/redo framework for an existing client app a few years back. It's basically an HMI system (a tool typically used in manufacturing to visually model an industrial system) that used SVG+HTML. I could have used a piece table concept (didn't know it was called that), storing a diff fragment of what was changed (using a library like diff-match-patch). Unfortunately, there was more than a text-representation that needed to be maintained so it didn't work initially. I wound up using a stack-based architecture that pushed operations stored as functions onto a main stack then its reverse operation onto an undo stack. Once I worked out the state management problems it worked out quite well. I've always wondered what other approaches others have done if tasked with a similar problem.
- wila 9y agoHaving written an undo/redo stack for a graphical editing component. That's pretty much what I did. Maintain a redo stack that holds the operations and parameters. An undo then became going back to the original image plus a redo of everything on the stack minus the last operation. Rather simplistic, but it worked well for our purposes and was easy to implement.
- default-kramer 9y agoI do this all the time when I write a game which can easily be described as a sequence of discrete moves. Chess is a good example, and games with physics engines are the opposite. As you said, the Undo operation is just "start with the initial board and apply N-1 moves to get the current state." This plays nicely with immutability too.
- terminalcommand 9y agoStarting with the initial board and applying n-1 moves should be significantly slower than using immutable data structures. I don't have much experience in algorithms but I think O(1) trumps O(N-1) :).
- 9y ago
- frandroid 9y agoHow does a piece table differ from a linked list?
- ithkuil 9y agoMore similar to a rope/cord: https://en.m.wikipedia.org/wiki/Rope_(data_structure) https://en.m.wikipedia.org/wiki/Rope_(data_structure)
- ww520 9y agoLinked list is a generic data structure with the linking information specified and none of the content is specified. Piece Table spells out what kind of content data to maintain, like the offset and length of the data fragments of the original document and the change log document.
- thomastjeffery 9y agoIn a Piece Table, a Piece is a representation of an edit. You can keep these edits in any structure you want, including a linked list. If you are interested, I posted such an implementation (using Haskell) here: https://news.ycombinator.com/item?id=15381886 https://news.ycombinator.com/item?id=15381886
- bitmapbrother 9y agoThe title makes it seem like it was exclusive to Word and developed by Microsoft when in reality it was developed at Xerox and used by their Bravo word processor.
- cpr 9y agoRight, since Charles Simonyi wrote both originally.
- ksk 9y agoIt does seem like that, but the piece table itself is not an algorithm FWICT, and as an abstract concept it can be implemented in various ways (with varying degrees of optimizations). A car is not just a car! Given that people are still attempting to re-invent text editors, it would be interesting to know if anyone has unknowingly come up with similar ideas in their design.
- dang 9y agoThat was the rewritten title (see https://news.ycombinator.com/item?id=15388593 https://news.ycombinator.com/item?id=15388593). We've reverted it to the original now.
- punnerud 9y agoGod point, thanks. Agree with you. I will try to remember that next time an article make the front page.
- bitmapbrother 9y agoMuch better. Thanks.
- rhinoceraptor 9y agoIs fast save the (in)famous Word file format where the in-memory state is written to a file?
- duncan_bayne 9y agoYes. Along with - as I assume you're alluding to - state that you might not intend to share along with the current state of the document.
- kobeya 9y agoSaving internal memory state to a file is such a terrible idea, who would do that! Proceeds to go write a program to manipulate memory-mapped files.
- rhinoceraptor 9y agoThat’s what Emacs (and AFAIK, some other interactive lisp environments) do to speed up boot time.
- duncan_bayne 9y agoIt's a great idea, seriously. As demonstrated by the details in this article. _But_ non-technical users do not understand how it works, which means that they were _very_ surprised to find state other than the obviously visible stuff being saved along with documents, and thus sent accidentally to recipients. If you're going to make use of this sort of clever optimization, you owe it to your users to at least document the consequences, if not the specific implementation. Edited: I think you read more criticism into my post than was intended on my part.
- hangonhn 9y agoWow. The inventor Piece Table is none other than Moore of Boyer Moore string search algorithm: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sea...
- karmakaze 9y agoAlso related to both strings and piece tables is the rope data-structure for concatenations of strings
- projektfu 9y agoJust mentioning that "unlimited undo/redo" meant that it was really fast to undo and redo one step in Word. This system didn't necessarily enable an undo history like we expect from word processors now. In fact, up to Word 5.1a for the Mac and Word for Windows 2.0, Word didn't have undo history. Undo would undo the last action, and then it would undo the undo. I believe undo history was added to Word 6.0.
- cwt137 9y agoIs this in any way related to Operational Transformation?
- yuhong 9y agoThe history of FullWrite is slightly wrong. Wikipedia has a better one: https://en.wikipedia.org/wiki/FullWrite_Professional https://en.wikipedia.org/wiki/FullWrite_Professional (1988 is also around the time of a famous DRAM shortage BTW)
- tudorw 9y agoIf you're interested in this kind of structure it's worth taking a look at 'transclusion' devised by Ted Nelson in the mid 60's https://en.wikipedia.org/wiki/Transclusion https://en.wikipedia.org/wiki/Transclusion reply
- infogulch 9y agoWhat's the difference between this and ropes? They seem conceptually similar.
- terminalcommand 9y agoRopes are inherently a binary tree. From what I can understand you can implement piece tables both as a double linked list and a b-tree. Furthermore in ropes every leaf spans one character, in piece tables, pieces have different lengths. Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable. If you want to implement undo, you only keep references to the former ropes. There is no inserting or adding via looking up the changes in an undo list. I think maybe if you implemented a piece table, where every piece spans one character, used a binary tree and made it immutable, you'd get a ropes data structure. For more information about persistence vs immutability this link might help: https://stackoverflow.com/questions/10034537/persistent-vs-immutable-data-structure https://stackoverflow.com/questions/10034537/persistent-vs-i...
- deathanatos 9y ago> Furthermore in ropes every leaf spans one character, The Boehm paper on ropes[1] (which is about the only academic literature on the subject that I know of) does not do that (and explicitly suggests one should not), nor does any real-world implementation, (e.g., the Boehm implementation, SGI's impl) do that. It would be incredibly inefficient, and for no real gain. A good rope implementation will store an array of characters/bytes in the leaves, up to some threshold. > Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable. There is nothing inherently immutable about ropes, and it is certainly possible to mutate a rope. (For example, appending a single character to a leaf with space is much quicker if the rope as a whole is mutable.) Look at the SGI implementation for an example here; their reference docs[2] contain sufficient details to see that the rope itself is mutable. Now, a rope typically just describes a sequence of characters. It is entirely possible for a leaf node in a specialized rope to reference on-disk content, and other leaves to reference in-memory content. In that regards, it can be like a piece table. Implementing an undo/redo on top of a rope is less straight-forward; whereas a piece table's undo history can essentially share large portions of the linked list (see the lovely diagrams here[3]) I'm not sure the same can be done on a Rope's tree, due to the tree's need to balance and re-balance. That is, without copying the tree, since that kind of defeats a lot of the benefits that a piece table has — not needing to copy the entire "file", even if that's just a bunch of spans. Now, one could make the leaves in a rope ref-counted (so they could be shared) and then copy the Concat nodes for undo/redo levels. Keeping the concat nodes as copies means the copies can balance independently, and since concat nodes are small (~2 pointers for left/right and a depth, IIRC) that isn't too much copying (the bulk of the data, the text, is refcounted in the leaves). But the simplicity of the piece table really starts to shine at this point. [1]: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9... [2]: http://www.sgi.com/tech/stl/Rope.html http://www.sgi.com/tech/stl/Rope.html [3]: http://www.catch22.net/tuts/piece-chains http://www.catch22.net/tuts/piece-chains
- mcguire 9y agoIs there nothing that J Strother Moore hasn't touched?
- rosstex 9y agoFun fact: UC Berkeley's intro course on Data Structures used a Text Editor for the massive project of the semester in Spring 2016. (Source: I wrote the autograder.) Our undo/redo feature was suggested to be implemented as a stack. http://datastructur.es/sp16/materials/proj/proj2/proj2.html http://datastructur.es/sp16/materials/proj/proj2/proj2.html
- bernadus_edwin 9y agoWe call it now as redux
- kristianp 9y agoThere are some other pages about MS Word here too: https://web.archive.org/web/20150822081514/http://1017.songtrellisopml.com:80/ https://web.archive.org/web/20150822081514/http://1017.songt...
- e98cuenc 9y agoA few years ago (2003, time flies) I wrote a piece table with a twist, instead of using a linked list I used a tree. I put a description of the whole algorithm here: http://e98cuenc.free.fr/wordprocessor/piecetable.html http://e98cuenc.free.fr/wordprocessor/piecetable.html A years later it was integrated in AbiWord. There was a major mistake in the profiling. The dots in the graphs were the best of 3 measuraments. At the time I thought that was the fairest to prevent outliers due to concurrent process. It also warms the data in the cache making the best measurement super fast.
- Sammi 9y agoThe writer of the article wrote more details in a reddit discussion on the article three years ago: https://www.reddit.com/r/programming/comments/22fpz0/whats_been_wrought_using_the_piece_table_how/ https://www.reddit.com/r/programming/comments/22fpz0/whats_b... Found it in the wikipedia footnotes :)
- anovikov 9y agoBack in 2000, i was hired to write an app that recovered damaged Word documents, and i had to experience it first hand. Impressed me as well!