Will these optimizations to my Ruby implementation of diff improve performance in a Rails app?
- by grg-n-sox
<tl;dr>
In source version control diff patch generation, would it be worth it to use the optimizations listed at the very bottom of this writing (see <optimizations>) in my Ruby implementation of diff for making diff patches?
</tl;dr>
<introduction>
I am programming something I have never done before and there might already be tools out there to do the exact thing I am programming but at this point I am having too much fun to care so I am still going to do it from scratch, even if there is a tool for this.
So anyways, I am working on a Ruby on Rails app and need a certain feature. Basically I want each entry in a table of mine, let's say for example a table of video games, to have a stored chunk of text that represents a review or something of the sort for that table entry. However, I want this text to be both editable by any registered user and also keep track of different submissions in a version control system. The simplest solution I could think of is just implement a solution that keeps track of the text body and the diff patch history of different versions of the text body as objects in Ruby and then serialize it, preferably in human readable form (so I'll most likely use YAML for this) for editing if needed due to corruption by a software bug or a mistake is made by an admin doing some version editing.
So at first I just tried to dive in head first into this feature to find that the problem of generating a diff patch is more difficult that I thought to do efficiently. So I did some research and came across some ideas. Some I have implemented already and some I have not. However, it all pretty much revolves around the longest common subsequence problem, as you would already know if you have already done anything with diff or diff-like features, and optimization the function that solves it.
Currently I have it so it truncates the compared versions of the text body from the beginning and end until non-matching lines are found. Then it solves the problem using a comparison matrix, but instead of incrementing the value stored in a cell when it finds a matching line like in most longest common subsequence algorithms I have seen examples of, I increment when I have a non-matching line so as to calculate edit distance instead of longest common subsequence. Although as far as I can tell between the two approaches, they are essentially two sides of the same coin so either could be used to derive an answer. It then back-traces through the comparison matrix and notes when there was an incrementation and in which adjacent cell (West, Northwest, or North) to determine that line's diff entry and assumes all other lines to be unchanged.
Normally I would leave it at that, but since this is going into a Rails environment and not just some stand-alone Ruby script, I started getting worried about needing to optimize at least enough so if a spammer that somehow knew how I implemented the version control system and knew my worst case scenario entry still wouldn't be able to hit the server that bad. After some searching and reading of research papers and articles through the internet, I've come across several that seem decent but all seem to have pros and cons and I am having a hard time deciding how well in this situation that the pros and cons balance out. So are the ones listed here worth it? I have listed them with known pros and cons.
</introduction>
<optimizations>
Chop the compared sequences into multiple chucks of subsequences by splitting where lines are unchanged, and then truncating each section of unchanged lines at the beginning and end of each section. Then solve the edit distance of each subsequence.
Pro: Changes the time increase as the changed area gets bigger from a quadratic
increase to something more similar to a linear increase.
Con: Figuring out where to split already seems like you have to solve edit distance
except now you don't care how it is changed. Would be fine if this was solvable by
a process closer to solving hamming distance but a single insertion would throw this
off.
Use a cryptographic hash function to both convert all sequence elements into integers and ensure uniqueness. Then solve the edit distance comparing the hash integers instead of the sequence elements themselves.
Pro: The operation of comparing two integers is faster than the operation of comparing
two strings, so a slight performance gain is received after every comparison, which
can be a lot overall.
Con: Using a cryptographic hash function takes time to convert all the sequence
elements and may end up costing more time to do the conversion that you gain back from
the integer comparisons. You could use the built in hash function for a string but
that will not guarantee uniqueness.
Use lazy evaluation to only calculate the three center-most diagonals of the comparison matrix and then only calculate additional diagonals as needed. And then also use this approach to possibly remove the need on some comparisons to compare all three adjacent cells as desribed here.
Pro: Can turn an algorithm that always takes O(n * m) time and make it so only worst
case scenario is that time, best case becomes practically linear, and average case is
somewhere between the two.
Con: It is an algorithm I've only seen implemented in functional programming languages
and I am having a difficult time comprehending how to convert this into Ruby based on
how it is described at the site linked to above.
Make a C module and do the hard work at the native level in C and just make a Ruby wrapper for it so Ruby can make all the calls to it that it needs.
Pro: I have to imagine that evaluating something like this in could be a LOT faster.
Con: I have no idea how Rails handles apps with ruby code that has C extensions and it
hurts the portability of the app.
This is an optimization for after the solving of edit distance, but idea is to store additional combined diffs with the ones produced by each version to make a delta-tree data structure with the most recently made diff as the root node of the tree so getting to any version takes worst case time of O(log n) instead of O(n).
Pro: Would make going back to an old version a lot faster.
Con: It would mean every new commit, the delta-tree would get a new root node that
will cost time to reorganize the delta-tree for an operation that will be carried out
a lot more often than going back a version, not to mention the unlikelihood it will be
an old version.
</optimizations>
So are these things worth the effort?
