3 ms·
There was an interesting conversation about the performance of line breaking algorithms recently. David Fuchs — who worked with Knuth on the line breaking algor
by Veen 7y ago
There was an interesting conversation about the performance of line breaking algorithms recently. David Fuchs — who worked with Knuth on the line breaking algorithms in Tex — commented that the algorithm in Tex isn't especially performance intensive. It's not included in browsers because high-quality line breaking doesn't play well with floats.
https://news.ycombinator.com/item?id=19785968 https://news.ycombinator.com/item?id=19785968
https://news.ycombinator.com/item?id=19473277 https://news.ycombinator.com/item?id=19473277
- raphlinus 7y agoAs another datapoint, Knuth-Plass style line breaking is implemented on Android TextView and turned on by default, as of Marshmallow I think. There is a bit of a performance cost, but I personally never came across anybody who turned it off to gain more speed.
- drfuchs 7y agoThanks for the shout-out, but all the credit for the line-breaking in TeX goes to Knuth and Plass; I was just in the nearby vicinity, and like to make authoritative pronouncements. The linked comments do represent my accurate measurements of running the unadulterated TeX code from Knuth's hand on modern hardware.
- dmix 7y agoI found this great overview of the algorithm which similarly addresses what your comment mentions about it being quadratic is a ‘commonly known fact’ by programmers but is not really true: https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md https://github.com/jaroslov/knuth-plass-thoughts/blob/master... It’s always fascinating how these older algorithms and research is still highly relevant and it’s implementation being debated over.