CAREER: Foundations, Algorithms, and Tools for Browser Invalidation

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

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.