7 ms·

Why current browsers are not using this, or some improved version of this algorithm?

by stralep 17y ago

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 ago
  Speed 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 ago
    Well, 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 ago
      Tenths 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 ago
        Maybe. 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 ago
        You 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 ago
    It 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 ago
      If 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 ago
        Okay, 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....
patrickg 17y ago
Because a) first fit, best fit or something else is trivial to implement, having a good total fit implementation that works in a lot of circumstances is not trivial (I have re-implemented a simpler version of the algorithm in Ruby including using a hyphenation library). b) you can ask the same question: why does almost no word processor implement this algorithm? And with word processors it is much more important! The answer is simple: Most word processors are doing many things badly so having a total-fit h&j (hyphenation and justification) algorithm would only make the output slightly better but still much inferior to good book typography.
- imurray 17y ago
  why does almost no word processor implement this algorithm? In TeX the line breaking depends on the whole paragraph. I imagine it could be visually quite distracting if the line-wrapping jumped around in a WYSIWYG word processor as you added text to a paragraph. Edit: ah. I see this is noted in the posted article’s To-do section: Figure out how to deal with dynamic paragraphs (i.e. paragraphs being edited) as their ratios will change during editing and thus visibly move around.
  - patrickg 17y ago
    What about a menu (ribbon) item called "apply very nice typography to your document" which recalculates/reformats the paragraphs? Would this be a solution?
    - imurray 17y ago
      Maybe. But there are probably all sorts of annoying details to deal with. For example, the pagination of the document could change, and so that would lead to further editing to fix it. Then how does line-breaking work during that editing phase, or in general after applying the menu item? I don’t actually use a WYSIWYG editor any more, so I’ll leave my speculation there.
    - yan 17y ago
      This is exactly why I prefer authoring documents in LaTeX vs WYSIWYG tools: I can concentrate on semantics and not worry about representation. Writing stuff in Word forces you to be distracted by its appearance on the page and can drive me crazy with micro-adjustments. With LaTeX, I just write the document and the computer does what computers are good at doing.
icco 17y ago
In the end, most of the big browsers are open-source, so I guess you could try submitting a patch, but I agree with most the answers here about performance, laziness, and the fact that users don't care.

Why current browsers are not using this, or some improved version of this algorithm?

by stralep 17y ago

Why current browsers are not using this, or some improved version of this algorithm?

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 ago
Speed 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 ago
  Well, 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 ago
    Tenths 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 ago
      Maybe. 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 ago
        You 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 ago
  It 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 ago
    If 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 ago
      Okay, 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....

patrickg 17y ago

Because a) first fit, best fit or something else is trivial to implement, having a good total fit implementation that works in a lot of circumstances is not trivial (I have re-implemented a simpler version of the algorithm in Ruby including using a hyphenation library). b) you can ask the same question: why does almost no word processor implement this algorithm? And with word processors it is much more important! The answer is simple: Most word processors are doing many things badly so having a total-fit h&j (hyphenation and justification) algorithm would only make the output slightly better but still much inferior to good book typography.

imurray 17y ago
why does almost no word processor implement this algorithm? In TeX the line breaking depends on the whole paragraph. I imagine it could be visually quite distracting if the line-wrapping jumped around in a WYSIWYG word processor as you added text to a paragraph. Edit: ah. I see this is noted in the posted article’s To-do section: Figure out how to deal with dynamic paragraphs (i.e. paragraphs being edited) as their ratios will change during editing and thus visibly move around.
- patrickg 17y ago
  What about a menu (ribbon) item called "apply very nice typography to your document" which recalculates/reformats the paragraphs? Would this be a solution?
  - imurray 17y ago
    Maybe. But there are probably all sorts of annoying details to deal with. For example, the pagination of the document could change, and so that would lead to further editing to fix it. Then how does line-breaking work during that editing phase, or in general after applying the menu item? I don’t actually use a WYSIWYG editor any more, so I’ll leave my speculation there.
  - yan 17y ago
    This is exactly why I prefer authoring documents in LaTeX vs WYSIWYG tools: I can concentrate on semantics and not worry about representation. Writing stuff in Word forces you to be distracted by its appearance on the page and can drive me crazy with micro-adjustments. With LaTeX, I just write the document and the computer does what computers are good at doing.

icco 17y ago

In the end, most of the big browsers are open-source, so I guess you could try submitting a patch, but I agree with most the answers here about performance, laziness, and the fact that users don't care.