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.
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.
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.
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.
This isn’t anything to do with PDF, of course; it’s just representing the baked result of a text rendering process. Your device could do that rendering itself just fine; it’d just take a while (much longer than it takes to change font family/font size and see the result in your favourite eBook reader.)
It’d be interesting to see an ePub-like standard that kept the text as semantic text, and rendered “at runtime”, but not “in realtime”; rather using a set of render preferences you set up before-hand to render the book once when you first download/sync it. Sort of like how runtimes like .NET dynamically recompile downloaded bytecode to native code to “specialize” the code for the device they’re running on. With such an approach, you could rely on a render-model that actually spens time doing good, constraint-based rendering of the text to avoid rivers/widows/orphans/excessive hyphens/etc.
You could get pretty far in cutting down the perceived time of this render by just splitting each work into chapters and rendering a chapter at a time. You would be able to start reading once the first chapter finished rendering. Which, for most normal types of books, on the sort of CPU an eBook-reader has, would “only” take ~10 seconds.