4 ms·
The claimed reasons are (a) it would take work to implement, and (b) it would be slower than the current method. Both seem like pretty weak excuses to me. The
by jacobolus 17y ago
The claimed reasons are (a) it would take work to implement, and (b) it would be slower than the current method.
Both seem like pretty weak excuses to me.
The main real reason is likely that most users don’t care, and so they can get away with it.
- lambda 17y agoSpeed is a pretty important reason, and users not caring is also a pretty important reason. Users do care about speed, and don't care about absolutely ideal line breaking; so why trade off something they do care about for something they don't?
- jacobolus 17y agoWell, it was an important reason in 1990, maybe, or even 1995. But we’ve had a couple of orders of magnitude improvement in computing speed since then. There’s no reason to favor some marginal speed advantage (tenths or hundredths of a second) to better layout.
- lambda 17y agoTenths of a second can be pretty damn significant. Every tenth of a second extra load time leads to approximately a 1% drop in sales, according to research done by Amazon. One of the big points of competition between browsers these days is in speed. Part of the reason people switch from IE to one of the more modern browsers is because they are just that much snappier.
- jacobolus 17y agoMaybe. Though the only time there’s going to be a noticeable slowdown is when you’re dealing with huge amounts of text. Like an amount that will take 20 minutes or an hour to read. At that point, an extra 10th of a second to render, in return for a much more pleasant reading experience seems like a no-brainer trade-off. On a typical Amazon page the difference is going to be unnoticeable.
- eru 17y agoYou can just do the fast algo. first, and do the more sophisticated one, when your browser is idle. (The text will jump around a bit, but it does so anyway while loading.)
- patrickg 17y ago(b) is not correct. The time complexity of the total fit algorithm (as described in Knuth&Plass' paper) is almost the same as the simple (first-/best-fit) method. They use a technique called dynamic programming to divide the problem into pieces where the perfect line break of a sub paragraph is valid for optimal breaking of the whole paragraph.
- jacobolus 17y agoIt is definitely slower. The computational complexity of the Knuth-Plass algorithm might be of similar (or maybe even the same) order as just fitting as much as possible on each line, but it definitely at least has a different constant out front. I’m not exactly sure what the speed difference is, but it’s non-negligible.... though on modern hardware either way is absurdly fast, and there’s no reason the Knuth method couldn’t be done in real-time even for quite large documents.
- patrickg 17y agoIf you don't know the constant, how can you say that it is non-negligible? I doubt that one can measure the difference in speed rendering an average webpage with either algorithm. And your remark about real time: Even the old (and slow!) TeX can do linkebreaking for several hundred pages of text in a second. Including writing pdf. So you are probably right about real-time h&j even for quite large documents.
- jacobolus 17y agoOkay, according to this paper http://delivery.acm.org/10.1145/1610000/1600217/p99-hurst.pdf?key1=1600217&key2=1309156621&coll=GUIDE&dl=GUIDE&CFID=76735931&CFTOKEN=29858694 http://delivery.acm.org/10.1145/1610000/1600217/p99-hurst.pd... Knuth-Plass takes O(kn) where n is the number of words and k the number of words per line. That’s definitely slower than the naive line-by-line method. But the better algorithm can be supposedly improved with the method in this paper (I haven’t read it and don’t have time just now, so I’m not sure how much slower it would then be than the naive way). http://delivery.acm.org/10.1145/150000/146656/p546-eppstein.pdf?key1=146656&key2=0419156621&coll=GUIDE&dl=GUIDE&CFID=76736091&CFTOKEN=34983403 http://delivery.acm.org/10.1145/150000/146656/p546-eppstein....