Hacker News Reader

Comment by jacobolus | Hacker News Reader

Okay, according to this paper

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....

View on HN

There is also a paper that claims linear time for formatting paragraphs using dynamic programming: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3...

I haven't really wrapped my head around the paper yet, but I think it only holds if you take out some of the elements of the original Knuth & Plass algorithm (the box, glue and penalty model.) Nevertheless, linear time seems possible for a total-fit algorithm if you're willing to give up that model.

There is also a Haskell and C++ implementation (with source code) available on the authors web page: http://progtools.comlab.ox.ac.uk/members/oege/publications/s...

Nobody denied that it is slower in theory, but I still claim that you won't be able to measure the difference on an average web page. So time is not an excuse for not implementing this (and this was the original question).

Yeah, I never would have disagreed with that. Which is why I said “Both seem like pretty weak excuses to me.”

By “non-negligible” I meant something like 2–10 times slower (you’d have to test to be sure... I tried searching around but couldn’t find any direct speed comparisons). For typical pages it’s not going to matter, but if you have a page like the HTML5 spec, where it takes a half a second to resize a window now, it’s going to be noticeably slower using a more sophisticated paragraph composer.

Keep in mind, Safari doesn’t even do kerning, because they’re afraid it’d be too slow. (Also a ludicrous excuse for desktop hardware and typical web pages, IMO.)

And the Safari guys also use the same excuse (“it’s too slow”) for not doing real color management with CSS/HTML colors.

I agree with you now :-)

I would like to have two browsers of the same type, one with high(er) quality typography and one as it is now. And then compare the speed. That would be interesting.

Before we make fun of the webkit folks for not doing the proper work because "it's too slow," remember that these are the same folks that we praise for making the fastest dang HTML rendering engine on the planet. (Or near enough.) Their culture of performance has significantly raised the standard of web browsing performance, and that's not something to take lightly.

I imagine it would have to make a fairly significant difference in rendering quality in order to make any speed losses worthwhile. Death by a thousand cuts and all that.

Would it be a problem to send me these papers?

My email is on profile.

edit: I probably have access from academic network, but I am at home for a few days...

Can’t you just click the links?

I do not have access to acm papers from my current location and I will be here for a few days.

Oh, sorry. I think maybe these are ones that have full text available if you arrive via a google search? I don’t think I’m currently logged into anything special.

Funny thing!

When I clicked again just now, I was able to download this paper... I still don't understand what has changed.

Thank you for your time.

EDIT: And thanks to cpach!

For future reference, do

    ssh -D 1080 unixhost.yourinstitution.edu

then set your browser’s SOCKS proxy to localhost:1080.

The second paper can easily be found via Google: http://www.google.com/search?q=eppstein+convex+and+concave+c... http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p546-eppst...

Thanks!

Reply on news.ycombinator.com