What is meta? ×
Meta Stack Exchange is where users like you discuss bugs, features, and support issues that affect the software powering all 133 Stack Exchange communities.

The suggested edit view just showed me two drastically different views of content based on whether I was looking at the rendered mode or the markdown mode:

First, the rendered diff view, showing a lot of code changed:

rendered mode

Second, the markdown diff view, showing nearly nothing changed:

enter image description here

I believe this is a bug. The rendered-diff is difficult and doesn't need to be perfect -- but this one was way wrong. :)

share|improve this question
2  
[+1 confirm] That's pretty painful. Some part of the diff code must be sick and/or needs a beating. –  Toomai Mar 30 '12 at 3:36
4  
This is kinda by design at the moment, but I can see why you wouldn't be happy with it :) I'll look at improving it. –  balpha Mar 30 '12 at 8:48

1 Answer 1

up vote 27 down vote accepted

tl;dr: Fixed in the next build.

The problem here is that we have to be a bit defensive when diffing huge posts, in particular, huge codeblocks.

Our diff engine is based on this implementation of Eugene Myers' O(ND) difference algorithm. The N in this case stands for the length of the text; the D stands for the number of edits. In the usual case, this results in great diff performance.

Assuming you just fix a typo (so maybe D=2), the performance is linear in the text length. In other words, fixing a typo in a 2000-word text results in a diff that text takes 40 times as long as the diff for fixing a typo in a 50-word text. That's fine.

If, on the other hand, you change not just a typo, but the whole text, this means D=N and hence O(N²) performance – so between a 50-word post and a 2000-word post, the difference is suddenly 1600-fold.

A few weeks ago, this became painfully obvious in this suggested edit. The Markdown diff here is no problem (just insert spaces en masse, but leave the rest as-is), but the diff of the rendered version compares two pretty much unrelated walls-of-code (since a code span is entirely different from a code block). Creating that diff took 35-40 seconds, which is obviously not tolerable.

Chances of this issue appearing are much higher for code blocks than for normal text, because a) they have a higher tendency to be huge, and b) when tokenizing code blocks for diffing, the tokens are usually smaller (and thus come in greater numbers) than for normal text, since codeblocks need higher accuracy (e.g. for whitespace).

Unfortunately, you will of course never know the value of D until you actually run the diff, so in order to make sure that the diff runs in reasonable time1, we have to be defensive here and assume the worst case, which is D=N.

So we added a two-step diffing process for long posts. If the number of diff tokens is above a certain threshold, we first put them into groups (essentialy grouping them by their position in the DOM), and only compare the groups as a whole. Only then are the contents of two differing neighboring groups compared. So if you fix one typo in a 50-paragraph text, 49 of the paragraphs are identical and don't have to be compared word-for-word.

This is where your case comes in: Making a minor change in a huge codeblock. We don't want to diff the two versions of the codeblock word-for-word, since they may be entirely different, in which case you can get yourself a coffee before the diffing is done. On the other hand, we also don't want to make it seem that the entire code block has changed, which is what it looked like to you, although it really hasn't.

So I've added yet another step: Before bailing out ("too huge to diff; just assume the entire thing has changed") we try yet another step: A line-by-line diff. We don't touch unchanged lines, and only compare differing lines word-for-word.

In certain cases, that may still cause a change in a huge codeblock to have a less-finegrained diff than the same change in a smaller codeblock, but in most cases (in particular, the one you found), we can now create a reasonable diff of a large code block without running the risk of melting our server CPUs.

1 This would obviously be a DOS vector. Had someone posted that "suggested edit of doom" to Reddit before we fixed this, our servers would very certainly have come to a screeching halt.

share|improve this answer
9  
+1 I love that you're willing to post what is essentially a full blog post to explain what happened and what your thought process was. Thanks! –  eykanal Apr 9 '12 at 17:09
    
I found another similar instance just now: stackoverflow.com/suggested-edits/257445 -- a language tag, a blank line, prepended to 66 identical lines. Any chance the algorithm can be tweaked a bit to more politely show these? Thanks! –  sarnold May 6 '12 at 0:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .