research-article

Fast and parallel webpage layout

Authors:

Leo A. Meyerovich,

Rastislav BodikAuthors Info & Claims

WWW '10: Proceedings of the 19th international conference on World wide web

Pages 711 - 720

https://doi.org/10.1145/1772690.1772763

Published: 26 April 2010 Publication History

Abstract

The web browser is a CPU-intensive program. Especially on mobile devices, webpages load too slowly, expending significant time in processing a document's appearance. Due to power constraints, most hardware-driven speedups will come in the form of parallel architectures. This is also true of mobile devices such as phones and e-books. In this paper, we introduce new algorithms for CSS selector matching, layout solving, and font rendering, which represent key components for a fast layout engine. Evaluation on popular sites shows speedups as high as 80x. We also formulate the layout problem with attribute grammars, enabling us to not only parallelize our algorithm but prove that it computes in O(log) time and without reflow.

References

[1]

Apple, Inc. iPhone Dev Center: Creating an iPhone Application, June 2009.

[2]

G. J. Badros. Extending Interactive Graphical Applications with Constraints. PhD thesis, University of Washington, 2000. Chair-Borning, Alan.

Digital Library

[3]

R. Bordawekar, L. Lim, and O. Shmueli. Parallelization of XPath Queries using Multi-Core Processors: Challenges and Experiences. In EDBT'09: Proceedings of the 12th International Conference on Extending Database Technology, pages 180--191, New York, NY, USA, 2009. ACM.

Digital Library

[4]

B. Bos, H. W. Lie, C. Lilley, and I. Jacobs. Cascading Style sheets, Level 2 CSS2 Specification, 1998.

[5]

S. Dubey. AJAX Performance Measurement Methodology for Internet Explorer 8 Beta 2. CODE Magazine, 5(3):53--55, 2008.

[6]

M. Haghighat. Bug 520942 - Parallelism Opportunities in CSS Selector Matching, October 2009. https://bugzilla.mozilla.org/show bug.cgi?id=520942.

[7]

R. Heckmann and R. Wilhelm. A functional description of tex's formula layout. J. Funct. Program., 7(5):451--485, 1997.

Digital Library

[8]

C. Jones, R. Liu, L. Meyerovich, K. Asanovic, and R. Bodik. Parallelizing the web browser, 2009.

[9]

M. Jourdan. A Survey of Parallel Attribute Evaluation Methods. In Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 234--255. Springer Berlin / Heidelberg, 1991.

Digital Library

[10]

N. Kerris and T. Neumayr. Apple App Store Downloads Top Two Billion. September 2009.

[11]

D. E. Knuth. Semantics of Context-Free Languages. Theory of Computing Systems, 2(2):127--145, June 1968.

[12]

H. W. Lie. Cascading Style Sheets. Doctor of Philosophy, University of Oslo, 2006.

[13]

X. Lin. Active Layout Engine: Algorithms and Applications in Variable Data Printing. Computer-Aided Design, 38(5):444--456, 2006.

Digital Library

[14]

M. Mayer. Google I/O Keynote: Imagination, Immediacy, and Innovation... and a little glimpse under the hood at Google. June 2008.

[15]

L. Meyerovich. A Parallel Web Browser. http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/.

[16]

L. Meyerovich. Rethinking Browser Performance. Login, 34(4):14--20, August 2009.

[17]

J. L. Recker, G. B. Beretta, and I.-J. Lin. Font rendering on a gpu-based raster image processor. Technical Report 181, HP Laboratories, August 2009.

[18]

C. Stockwell. IE8 What is Coming. http://en.oreilly.com/velocity2008/public/schedule/detail/32 90, June 2008.

[19]

S. D. Swierstra, P. R. A. Alcocer, J. Saraiva, D. Swierstra, P. Azero, and J. Saraiva. Designing and Implementing Combinator Languages. In Third Summer School on Advanced Functional Programming, volume 1608 of LNCS, pages 150--206. Springer-Verlag, 1999.

[20]

G. Talbot. Confirm a CSS Bug in IE 7 (infinite loop). http://bytes.com/topic/html-css/answers/615102-confirm-serious-css-bug-ie-7-infinite-loop, March 2007.

[21]

D. Turner. The Design of FreeType2. The FreeType Development Team, 2008. http://www.freetype.org/freetype2/docs/design/.

[22]

H. J. Wang, C. Grier, A. Moshchuk, S. T. King, P. Choudhury, and H. Venter. The Multi-Principal OS Construction of the Gazelle Web Browser. In 18th Usenix Security Symposium, 2009.

Digital Library

Cited By

Singhal VSakka LSundararajah KNewton RKulkarni M(2024)Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree TraversalsACM Transactions on Architecture and Code Optimization10.1145/365260521:2(1-25)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3652605
Song SLee BChandra SBlincoe KTonella P(2023)Metamong: Detecting Render-Update Bugs in Web Browsers through FuzzingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616336(1075-1087)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616336
Yang XLiu WLin HLi ZQian FWang XLiu YXu T(2023)Visual-Aware Testing and Debugging for Web Performance OptimizationProceedings of the ACM Web Conference 202310.1145/3543507.3583323(2948-2959)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583323
Show More Cited By

Index Terms

Fast and parallel webpage layout

Recommendations

Modular verification of web page layout

Automated verification can ensure that a web page satisfies accessibility, usability, and design properties regardless of the end user's device, preferences, and assistive technologies. However, state-of-the-art verification tools for layout properties ...
A Reduction of Grid-Bag Layout to Auckland Layout
ASWEC '10: Proceedings of the 2010 21st Australian Software Engineering Conference

Many major programming platforms support layout managers in Grid-bag style, where GUI elements can be placed on a rectangular grid. In Grid-bag layout mangers, cells of the underlying grid can be merged in order to create more complex layouts. In this ...
ALMcss: a javascript implementation of the CSS template layout module
DocEng '12: Proceedings of the 2012 ACM symposium on Document engineering

Traditionally, web standards in general and Cascading Style Sheets (CSS) in particular take a long time from when they are defined by the W3C until they are implemented by browser vendors. This has been a limitation not only for authors, who had to wait ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '10: Proceedings of the 19th international conference on World wide web

April 2010

1407 pages

ISBN:9781605587998

DOI:10.1145/1772690

General Chairs:
Michael Rappa
North Carolina State University, USA
,
Paul Jones
University of North Carolina at Chapel Hill, USA
,
Program Chairs:
Juliana Freire
University of Utah, USA
,
Soumen Chakrabarti
Indian Institute of Technology, India

Copyright © 2010 International World Wide Web Conference Committee (IW3C2).

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 April 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '10

WWW '10: The 19th International World Wide Web Conference

April 26 - 30, 2010

North Carolina, Raleigh, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
1,165
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Singhal VSakka LSundararajah KNewton RKulkarni M(2024)Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree TraversalsACM Transactions on Architecture and Code Optimization10.1145/365260521:2(1-25)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3652605
Song SLee BChandra SBlincoe KTonella P(2023)Metamong: Detecting Render-Update Bugs in Web Browsers through FuzzingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616336(1075-1087)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616336
Yang XLiu WLin HLi ZQian FWang XLiu YXu T(2023)Visual-Aware Testing and Debugging for Web Performance OptimizationProceedings of the ACM Web Conference 202310.1145/3543507.3583323(2948-2959)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583323
Song SHur JKim SRogers PLee BDwyer MDamian DZeller A(2022)R2Z2Proceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510044(1818-1829)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510044
Pourghassemi BBonecutter JLi ZChandramowlishwaran A(2021)adPerfProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34473815:1(1-26)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.1145/3447381
Wang YLiu JZhang DQiu XLee JPetrank E(2021)Reasoning about recursive tree traversalsProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441617(47-61)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441617
Oulasvirta ADayama NShiripour MJohn MKarrenbauer A(2020)Combinatorial Optimization of Graphical User Interface DesignsProceedings of the IEEE10.1109/JPROC.2020.2969687108:3(434-464)Online publication date: Mar-2020
https://doi.org/10.1109/JPROC.2020.2969687
Shi AHadzi-Tanovic MZhang LMarinov DLegunsen O(2019)Reflection-aware static regression test selectionProceedings of the ACM on Programming Languages10.1145/33606133:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360613
Sharif HSrivastava PHuzaifa MKotsifakou MJoshi KSarita YZhao NAdve VMisailovic SAdve S(2019)ApproxHPVM: a portable compiler IR for accuracy-aware optimizationsProceedings of the ACM on Programming Languages10.1145/33606123:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360612
Sergey INagaraj VJohannsen JKumar ATrunov AHao K(2019)Safer smart contract programming with ScillaProceedings of the ACM on Programming Languages10.1145/33606113:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360611
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

EPUB

View this article in ePub.

Figures

Tables

Media

View Table of Conten