CAREER: Foundations, Algorithms, and Tools for Browser Invalidation

职业：浏览器失效的基础、算法和工具

• 批准号: 2340192
• 负责人: Pavel Panchekha
• 金额: $ 51.28万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-15 至 2029-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2340192&HistoricalAwards=false
• 关键词: CAREER; Foundations; Algorithms; Tools; Browser

This project aims to make web applications faster and less buggy by improving how web browsers implement an important algorithm called "invalidation." Web browsers are applications that view web pages; popular ones include Google Chrome, Microsoft Edge, Apple Safari, Samsung Internet, and Mozilla Firefox. They use a variety of algorithms to run web applications quickly. One of the most important that applies to a web browser component called its rendering engine, is invalidation. Invalidation means reusing previously-computed results when they could not have changed in the meanwhile. While simple in concept, invalidation is difficult in practice because tracking what can and can not change is extremely difficult. Bugs incorrectly reuse old results or incorrectly recompute unchanged results, and that causes web applications to look wrong, stutter, or freeze. In this project, the investigator presents new programming techniques that automatically track what can and can not change, removing the hardest part of invalidation. If successful, web browsers could adopt these techniques and run web applications faster with fewer bugs. That would ultimately serve the national prosperity by improving software developers' productivity and making more software accessible over the web. The new techniques and tools will be widely disseminated. Research will be integrated into education and training for students, developers and users of web browsers. Technically, browser invalidation algorithms are a set of cache invalidation algorithms for data with tree-structured dependencies. These algorithms are essential to reducing browser rendering latency. Today, these algorithms are written manually and susceptible to both under- and over-invalidation bugs. The projects explores a new monadic abstraction for tracking tree-structured dependencies between data values and automatically propagating invalidation messages ("dirty bits") through this dependency graph. A programming interface based on Resource Allocation Is Initialization (RAII) techniques and abstract invalidation allows integrating this abstraction into existing rendering engines. To test whether invalidation bugs are in fact eliminated, the investigator plans to build a black-box invalidation testing tool for web browsers, which will automatically search for invalidation bugs, which should confirm a dramatic reduction in bugs using the invalidation abstraction. To reduce runtime overhead, a compile-time policy framework will allow incrementally annotating protected data so that the dependency-tracking abstraction compiles down to code competitive with today's manual invalidation algorithms. Finally, a tracing system that combines performance counters such as RDTSC with the dependency graph allows attributing computation time to individual HTML elements and Cascading style sheets (CSS) properties and highlighting that performance data in the browser developer tools. In combination, these thrusts aim to make web browsers faster and less buggy while improving web application developers' ability to adapt their applications to web browser invalidation for greater performance.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目旨在通过改善Web浏览器实现一种称为“无效”的重要算法来使Web应用程序更快，更少的货物。 Web浏览器是查看网页的应用程序；流行的包括Google Chrome，Microsoft Edge，Apple Safari，Samsung Internet和Mozilla Firefox。他们使用各种算法快速运行Web应用程序。适用于称为其渲染引擎的Web浏览器组件的最重要的是无效。无效意味着在与此同时不变时重复使用先前计算的结果。尽管概念很简单，但实际上很难无效，因为跟踪可以和无法改变的事情非常困难。错误错误地重复使用旧结果或错误地重新计算未改变的结果，这会导致Web应用程序看起来错误，口吃或冻结。在这个项目中，研究人员介绍了新的编程技术，这些技术会自动跟踪可以和无法改变的内容，从而消除了无效的最难部分。如果成功，Web浏览器可以采用这些技术，并更快地运行Web应用程序，而错误较少。最终，通过提高软件开发人员的生产率并使更多的软件可以通过网络访问，这最终将为国家繁荣提供服务。新技术和工具将被广泛传播。研究将纳入针对Web浏览器的学生，开发人员和用户的教育和培训。从技术上讲，浏览器无效算法是具有树结构依赖关系的数据的一组缓存无效算法。这些算法对于减少浏览器渲染延迟至关重要。如今，这些算法是手动编写的，并且容易受到不足和过度侵入的错误的影响。这些项目探索了一个新的Monadic抽象，用于在数据值之间跟踪树结构化的依赖关系，并通过此依赖关系图自动传播无效消息（“ Dirty Bits”）。基于资源分配的编程界面是初始化（RAII）技术和抽象无效，允许将此抽象集成到现有的渲染引擎中。为了测试实际上是否被消除了无效错误，研究人员计划为Web浏览器构建黑框无效测试工具，该工具将自动搜索无效错误，该错误应通过使用无效抽象来确认错误的错误减少。为了减少运行时开销，编译时策略框架将允许逐步注释受保护的数据，从而使依赖性跟踪抽象汇编以与当今的手动无效算法进行编码竞争。最后，将诸如RDTSC之类的性能计数器与依赖关系图相结合的跟踪系统允许将计算时间归因于单个HTML元素和级联样式表（CSS）属性（CSS）属性，并在浏览器开发人员工具中突出显示该性能数据。结合起来，这些推力旨在使Web浏览器更快，更小的车辆，同时改善Web应用程序开发人员将其应用程序调整到Web浏览器无效的能力以提高性能。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的评估来通过评估来支持的，审查了更广泛的影响。