7 ms·

If you don't know the constant, how can you say that it is non-negligible? I doubt that one can measure the difference in speed rendering an average webpage wit

If you don't know the constant, how can you say that it is non-negligible? I doubt that one can measure the difference in speed rendering an average webpage with either algorithm. And your remark about real time: Even the old (and slow!) TeX can do linkebreaking for several hundred pages of text in a second. Including writing pdf. So you are probably right about real-time h&j even for quite large documents.

jacobolus 17y ago
Okay, according to this paper http://delivery.acm.org/10.1145/1610000/1600217/p99-hurst.pdf?key1=1600217&key2=1309156621&coll=GUIDE&dl=GUIDE&CFID=76735931&CFTOKEN=29858694 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.pdf?key1=146656&key2=0419156621&coll=GUIDE&dl=GUIDE&CFID=76736091&CFTOKEN=34983403 http://delivery.acm.org/10.1145/150000/146656/p546-eppstein....
- patrickg 17y ago
  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).
  - jacobolus 17y ago
    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.
    - patrickg 17y ago
      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.
    - doty 17y ago
      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.
- stralep 17y ago
  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...
  - jacobolus 17y ago
    Can’t you just click the links?
    - stralep 17y ago
      I do not have access to acm papers from my current location and I will be here for a few days.
      - jacobolus 17y ago
        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.
        stralep 17y ago
        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!
      - imurray 17y ago
        For future reference, do ssh -D 1080 unixhost.yourinstitution.edu then set your browser’s SOCKS proxy to localhost:1080.
  - cpach 17y ago
    The second paper can easily be found via Google: http://www.google.com/search?q=eppstein+convex+and+concave+cost+functions+filetype%3Apdf http://www.google.com/search?q=eppstein+convex+and+concave+c... http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p546-eppstein.pdf http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p546-eppst...
- bramstein 17y ago
  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.3229 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/scp99 http://progtools.comlab.ox.ac.uk/members/oege/publications/s...

jacobolus 17y ago

Okay, according to this paper http://delivery.acm.org/10.1145/1610000/1600217/p99-hurst.pdf?key1=1600217&key2=1309156621&coll=GUIDE&dl=GUIDE&CFID=76735931&CFTOKEN=29858694 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.pdf?key1=146656&key2=0419156621&coll=GUIDE&dl=GUIDE&CFID=76736091&CFTOKEN=34983403 http://delivery.acm.org/10.1145/150000/146656/p546-eppstein....

patrickg 17y ago
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).
- jacobolus 17y ago
  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.
  - patrickg 17y ago
    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.
  - doty 17y ago
    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.
stralep 17y ago
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...
- jacobolus 17y ago
  Can’t you just click the links?
  - stralep 17y ago
    I do not have access to acm papers from my current location and I will be here for a few days.
    - jacobolus 17y ago
      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.
      - stralep 17y ago
        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!
    - imurray 17y ago
      For future reference, do ssh -D 1080 unixhost.yourinstitution.edu then set your browser’s SOCKS proxy to localhost:1080.
- cpach 17y ago
  The second paper can easily be found via Google: http://www.google.com/search?q=eppstein+convex+and+concave+cost+functions+filetype%3Apdf http://www.google.com/search?q=eppstein+convex+and+concave+c... http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p546-eppstein.pdf http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p546-eppst...
bramstein 17y ago
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.3229 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/scp99 http://progtools.comlab.ox.ac.uk/members/oege/publications/s...