CAREER: Foundations, Algorithms, and Tools for Browser Invalidation

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

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.