News for hackers. Stuff that matters.
Re:Get Your Book, Make It Free by Veen on Friday May 17, 2019 @11:33AM (#19940557)
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=19473277

Re:Get Your Book, Make It Free by drfuchs on Friday May 17, 2019 @12:04PM (#19940848)
Thanks 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.
Re:Get Your Book, Make It Free by dmix on Friday May 17, 2019 @02:04PM (#19942040)
I 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...

It’s always fascinating how these older algorithms and research is still highly relevant and it’s implementation being debated over.

Re:Get Your Book, Make It Free by raphlinus on Friday May 17, 2019 @11:40AM (#19940630)
As 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.