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浏览器是查看网页的应用程序;流行的浏览器包括Google Chrome、微软Edge、Apple Safari、Samsung Internet和Mozilla Firefox。它们使用各种算法来快速运行Web应用程序。其中一个最重要的适用于Web浏览器组件称为其渲染引擎，是无效。无效意味着重用以前计算的结果，当它们不能同时改变时。虽然概念简单，但无效在实践中很难，因为跟踪什么可以改变，什么不能改变是极其困难的。错误地重用旧结果或错误地重新计算未更改的结果，导致Web应用程序看起来错误，卡顿或冻结。在这个项目中，研究人员提出了新的编程技术，自动跟踪什么可以和不能改变，消除无效的最困难的部分。如果成功，Web浏览器可以采用这些技术，更快地运行Web应用程序，减少错误。这最终将通过提高软件开发人员的生产力和使更多的软件可以通过网络访问来服务于国家的繁荣。新技术和新工具将得到广泛传播。研究将纳入对学生、开发人员和网络浏览器用户的教育和培训。从技术上讲，浏览器失效算法是一组针对具有树结构依赖的数据的缓存失效算法。这些算法对于减少浏览器渲染延迟至关重要。今天，这些算法是手动编写的，容易受到无效和无效错误的影响。该项目探索了一种新的一元抽象，用于跟踪数据值之间的树结构依赖关系，并通过此依赖关系图自动传播无效消息（“脏位”）。基于资源分配指令集（RAII）技术和抽象无效的编程接口允许将该抽象集成到现有的渲染引擎中。为了测试无效错误是否真的被消除了，研究人员计划为Web浏览器构建一个黑盒无效测试工具，它将自动搜索无效错误，这应该会证实使用无效抽象的错误会大大减少。为了减少运行时开销，编译时策略框架将允许递增地注释受保护的数据，以便依赖性跟踪抽象编译到与当今的手动无效算法竞争的代码。最后，将RDTSC等性能计数器与依赖关系图相结合的跟踪系统允许将计算时间归因于单个HTML元素和层叠样式表（CSS）属性，并在浏览器开发工具中突出显示性能数据。结合起来，这些目标旨在使Web浏览器更快，更少的错误，同时提高Web应用程序开发人员的能力，使他们的应用程序适应Web浏览器失效，以获得更好的性能。这个奖项反映了NSF的法定使命，并已被认为是值得支持的评估使用基金会的智力价值和更广泛的影响审查标准。