Hacker News Reader

Comment by nimbupani | Hacker News Reader

Bram Stein works for Adobe :) We did look into it but it was not fast enough for the needs of browsers.

The run-time of that particular implementation of the Knuth-Plass algorithm is quadratic in paragraph length, which is too slow for web browsers (which might have to deal with very long paragraphs). However, the algorithm can be implemented to run in O(n) for large n, or O(n log n) with smaller fixed constants. Though you might have some issues with the line breaks made by the browser.

I'm not totally sure, but I think the linear time papers I've read sacrifice some of the aspects of the original Knuth and Plass algorithm. I think some of those are going to be necessary to properly implement the Knuth and Plass algorithm in browser (also, floats are going to be interesting.)

The performance isn't actually that bad, I can perform line breaking in JavaScript on some very large documents, with the only performance bottleneck being DOM node creation (which native implementations won't suffer from.) If necessary the linebreaking could also be done incrementally, with a first first-fit pass and then the Knuth and Plass algorithm.

I could be mistaken, but I'm fairly certain Internet Explorer implements the Knuth and Plass algorithm when using `text-justify: newspaper`. Unfortunately, I can't check because it isn't open source. The output however is pretty much identical to what my JavaScript version generates, so I'm inclined to believe it is the Knuth and Plass algorithm.

Reply on news.ycombinator.com