Grant: Discovery Grants Program - Individual

Most tasks in data engineering are still limited to a few hundred megabytes per second, at best. Yet our computers can read and write data much faster: recent disks exceed 14 GB/s. My long-term goal is to show that despite the stagnant clock frequencies, we can process data ever faster on commodity cores. In the near term, we can multiply the single-core performance of many common problems, with more gains to come in the future. Importantly, these are efficiency gains: we go faster while using proportionally less power and reducing the latency. I focus on the design of new algorithms that are particularly suited to industry-relevant problems. My short-term objectives are organized in four axes: (1) We will break new speed records in Internet-format processing starting with JSON. To surpass our own results, we will parse files differently, using a technique that we call On Demand: it combines lazy evaluation with advanced programming techniques to achieve unbeatable performance on single-core processors while preserving much of the expressivity of conventional approaches. We are also working on adapting our work from JSON to other formats such as CSV and zone files. Zone files are often large files made of DNS records that are often used both as an exchange format and as a database format. For example, they contain many IP addresses (IPv4 and IPv6), specialized string tokens and time stamps that must be parsed at high speed. We are building the fastest zone-file parser in the world. (2) Unicode strings are ubiquitous. Our recent work has shown that we can multiply the processing speed of these strings by revisiting existing algorithms. We want to establish a new baseline performance for common string processing tasks including Unicode transcoding, search/replace, normalization, collation, and sorting. We expect that breakthrough results are possible by the deliberate design of SIMD-based algorithms. (3) When creating Web applications, developers generally rely on the WHATWG standards (URLs, WebSockets, Fetch, Streams). The Node.js JavaScript runtime environment, used by Slack, Skype and Microsoft Teams, implements these standards. The performance of software implementing these standards is often limited by the processor. We are going to multiply the performance of some implementations (e.g., URLs) within systems like Node.js to learn how we can be more efficient. (4) Indexes are a critical software strategy to improve performance. Our EWAH and Roaring bitmap indexes are industry standards (used by git, YouTube, etc.). Though we have made significant work in improving their practical performance, we believe that much remains to be done: we expect to be able to double the performance in some cases by designing algorithms specific to the next generation of SIMD instructions (AVX-512, SVE2).