Difference on time depending on size is ok, different stack consumption would be bad. The Tcl-based diffs load the document in two versions in memory and build from this tcl lists, for which the longest common subsequences are computed.
It well established that scripted solutions are slow on large input files (see e.g. the comments on http://esw.w3.org/topic/HtmlDiff). The best free alternative seems to be currently daisydiff from Google code (gsoc project in 2007) and maybe the php implementation for mediawiki based on the same algorithm (gsoc project in 2008) http://code.google.com/p/daisydiff/ . If someone has time, interest and skills, it sounds like a nice little project to compare this in detail with the tcl based html diff and maybe port it to Tcl.
-gustaf neumann
