Software Performance Engineering

There are countless high-performance library implementations available for various domains and hardware platforms, yet Domain-Specific Languages (DSLs) and compilers remain rare. A well-designed DSL can express a far broader range of programs within a domain compared to even the most comprehensive library while also enabling domain-specific, global optimizations that go beyond hand-optimized kernels. The scarcity of high-performance DSLs stems from the complexity of building DSL compilers, which are typically large, intricate systems developed by experts.

In this talk, I will introduce BuildIt, a C++ framework designed for the rapid prototyping of high-performance DSLs. BuildIt uses a multi-stage programming approach to combine the flexibility of libraries with the performance and specialization of code generation. With BuildIt, domain experts can transform existing libraries into efficient, specialized compilers simply by modifying types of the variables. Moreover, it allows them to implement analyses and transformations without needing to write traditional compiler code. Currently, BuildIt supports code generation for multi-core CPUs and GPUs, with FPGA support coming soon. I will also showcase four DSLs created with BuildIt to highlight its power and ease of use: a reimplementation of the GraphIt graph computing language, the BREeze DSL for regular expressions, StreamIt a DSL for stream computing including PyTorch, and NetBlocks, a DSL for custom network protocol development. More information on BuildIt can be found at https://buildit.so/.

The growth of network-structured data across domains like neuroscience and cybersecurity demands scalable graph analytics, but complex tasks like subgraph isomorphism remain accessible only to high-performance computing (HPC) specialists. Arachne is an open-source framework that democratizes high-performance graph analytics through a Python interface while abstracting parallelism complexities. It enables advanced graph algorithms to run efficiently from laptops to supercomputers. Arachne has been adopted by Harvard researchers for the MoMo connectome visualization tool, allowing neuroscientists to draw neural motifs that are translated into attributed subgraphs and searched using our novel HiPerMotif algorithm. Key innovations include HiPerMotif, which achieves up to 66× speedups over parallel approaches.Testing on large-scale datasets including FlyWire and the H01 human brain connectome demonstrates Arachne’s performance: completing complex subgraph searches in 38 seconds versus NetworkX’s 16,000+ seconds. This unified platform balances high-performance computation with accessibility, enabling researchers to extract insights from billion-scale graphs and advancing pattern matching across data-driven sciences.This research is supported in part by NSF grants CCF-2109988, OAC-2402560, and CCF-2453324.

RDF is a modern variant of relational databases, with a universal schema (all data is modelled as triples) and universal identifiers (think of URLs). The query language is SPARQL, which is essentially SQL on RDF data. There are hundreds of fully-featured systems for RDF/SPARQL, from companies, open source projects, and academia. RDF and SPARQL are 100% standardized, yet the performance of these systems varies by many orders of magnitude, often contrary to the claims by the respective creators. In my talk, I will shed some light on this mystery. In a nutshell: computer scientists cannot code, open source developers slept in their algorithms class, and companies eventually stop doing research.

Locks are frequently used in concurrent systems to simplify code and ensure safe access to contended parts of memory. However, they are also known to cause bottlenecks in concurrent code, leading practitioners and theoreticians to sometimes opt for more intricate lock-free implementations. In this talk, I’ll show that, despite the seeming contradiction, it is possible to design practically and theoretically efficient lock-free locks; I’ll present a practical lock-free lock algorithm and our library which allows easily replacing regular locks with lock-free ones. Time permitting, I’ll discuss related open problems.

This talk describes how I spent six months embedded in an industrial-strength software team working as a consulting performance engineer. The system was big (>107 lines of code written by several hundred developers), aged (grown over several decades), important ($300M annual revenue) and slow – if our team couldn’t speed it up, this cash cow and its revenue would be catastrophically lost in a matter of months. I’ll describe some of the problems that we faced, and challenge teachers of performance engineering to prepare their students to work in such a role. I’ll also address how performance engineers can enhance their own performance by using LLMs. (This talk describes joint work with Duffy Boyle, P. Krishnan and John Meiners.)

This talk proposes a collaborative approach to teaching performance engineering. Building on the success of the long-standing Algorithms Reading Group at Stony Brook University, the proposed Performance Engineering (PE) meetings aim to foster a hands-on, interactive learning environment. Participants will collaboratively optimize unoptimized code through real-time coding, successive refinements, and discussions of interesting developments. The bi-weekly hybrid sessions will be open to all, recorded, and scribed, with opportunities for participants to continue optimizations between meetings and submit their code to a dedicated server for performance evaluation. An online leaderboard will track successful submissions, encouraging friendly competition and continuous improvement.

Stencil computations are a fundamental tool in scientific computing, modeling the evolution of physical systems on multidimensional grids over multiple timesteps. They underpin numerous applications including fluid dynamics, image processing, mechanical engineering, cellular automata, electromagnetics, and meteorology. Traditionally, stencil algorithms iterate over every grid cell for each timestep, performing Omega(TN) work for a grid of size N and T timesteps.

In this talk, I will present our recent sub-Theta(TN)-work algorithms for general linear stencil computations under aperiodic and free-space boundary conditions, achieving substantial speedups over state-of-the-art methods. Our aperiodic-grid algorithm employs an FFT-based periodic solver within a recursive divide-and-conquer framework (SPAA’21, TOPC), while our free-space algorithm uses Gaussian approximations and N-body methods (SPAA’22, ACDA’25).

More recently, we have extended our FFT-based approach to handle a broad class of problems involving multiple time-varying linear stencils applied across spatial regions with morphing boundaries, without increasing the work or span by more than a logarithmic factor in T (SPAA’25). We have also developed FFT-accelerated algorithms for a class of nonlinear stencil problems in quantitative finance, specifically for pricing American options under binomial, trinomial, and Black–Scholes–Merton models (PPoPP’24).

Implementations of most of these algorithms run significantly faster than the best existing methods.

This is joint work with current and former Stony Brook University students: Zafar Ahmad, Russell Bentley, Reilly Browne, Rathish Das, Pramod Ganapathi, Aaron Gregory, Yushen Huang, Michael Santomauro, and Yimin Zhu.

RocksDB is a library providing a convenient key-value interface for data storage and sits on top of a local or remote filesystem. It is “ource of truth” for most of the online small-to-medium object storage at Meta. We have been involved in developing some advanced data structures such as relaxed consistency concurrent hash tables (unpublished HyperClockCache) and approximate query filters / static functions (Ribbon filter). We are looking to advance these and related areas, including other mutable concurrent data structures and other static representations of indexing or filtering data.

Computer memory is hierarchical, making locality a fundamental concern in software performance engineering. Locality theories formalize the cost of a cache hierarchy. The formalism is necessary for optimization.

This talk overviews two recent theories of locality: the Relational Theory (Yuan et al., TACO 2019), which proves the equivalence of data movement, data reuse, and working set measures; and Data Movement Distance (Smith et al., ICS 2022), a new metric that quantifies locality by its asymptotic complexity.

Rank-polymorphic array programming systematically abstracts from structural array properties such as shape and rank. As usual, abstraction is great for software engineering, but comes at the price of performance. Specialization to rank- and shape-monomorphic intermediate code is the way out of this dilemma, but is limited in practice by the non-availability of rank and shape information at compile time.

We present a staged approach where the runtime system recompiles polymorphic intermediate code concurrently with the execution of the application itself. The resulting fast(er) code is then dynamically linked into the running application, and the runtime system, henceforth, dispatches program execution to the fast clone. Asymptotically, this yields shape-monomorphic performance for rank-polymorphic code.

We further complement asynchronous adaptive specialization with a persistence layer that stores fast clones in a repository for immediate use in further application runs that happen to use the same ranks and shapes. However, what sounds like a simple engineering solution turns out to exhibit a number of critical issues that we will briefly touch upon.

With the advent of modern hardware, parallelism has been more important than ever, and top-tier conference papers reporting performance results are rarely run sequentially. Parallel algorithms have been extensively studied since the 1970s, so what’s new and still needs to be explored? In this talk, I argue that there are still numerous important directions to investigate. I will briefly overview some of my recent work on graph analytics (SSSP, connectivity, k-core, etc.), data structure design (search trees, priority queues, kd-trees, etc.), and highlight ongoing challenges such as space-efficiency, synchronization costs, and the need for simplicity. If time permits, I will also discuss some future topics that may be of interest to this audience.

We need compilers that support the increasingly heterogeneous landscape of architectures. The end of Moore’s Law and Dennard scaling has given rise to architecture specialization at multiple scales, from heterogeneous chip architectures that include chiplets and accelerators to integrated CPU+GPU nodes and heterogeneous clusters of heterogeneous nodes. This talk will focus on the role of data layout in generating code for all of these scales of heterogeneity.

The proposal for the Dagstuhl SPE seminar states: “We have a choice: SPE can be tedious, expensive, haphazard, and controlled by “high priests”; or it can be fun, cheap, principled, and democratically available to the average programmer.” I call this “choosing where and how to locate SPE.” In this talk, I introduce Fastcode – an open-source community for choosing where and how to locate SPE for the greater good.

Learned indexes can outperform traditional structures in speed and space efficiency by predicting key positions in sorted arrays. However, prediction errors necessitate costly last-mile searches, and model evaluation itself can be expensive, limiting performance gains. We present LiBox, a hierarchical, box-based learned index that eliminates these inefficiencies. LiBox partitions keys into “boxes” such that the target box can be identified with zero error using a simple linear regression function. The remaining in-box search requires only a single AVX-512 instruction, enabling highly predictable and minimal instruction counts per query. By using modest extra space to accommodate irregular key distributions, LiBox supports both read and write queries at near array-access speed. Its structure adapts reorganizations to workload patterns, sustaining high read performance while hiding update costs.

This talk discusses recent work to develop structured playgrounds for learning about software performance engineering. Speedcode is an online programming platform that aims to improve the accessibility of software performance-engineering education. At its core, Speedcode provides a platform that lets users gain hands-on experience in software performance engineering and parallel programming by completing short programming exercises. Speedcode challenges users to develop fast multicore solutions for short programming problems and evaluates their code’s performance and scalability in a quiesced cloud environment.

I will also discuss the development of FastCoder-Factory and Lesson which relate to synthetic data generation and collaborative learning for code-optimization tasks.

The future of software performance engineering must include the specialized hardware that is being developed across the industry and academia. Although performance engineers play a critical role, such hardware places a large burden on the software stack and thus increases the need for compilers and programming models for productivity. I will share my thoughts on designing programming systems that permit portable compilation across disparate hardware. These programming systems must raise the level of abstraction to diverse operations on abstract collections. (I think four such collections cover the lion’s share of large-scale computing.) By raising the level of abstraction and by introducing new compiler techniques, we can make programs portable across different machines and different data structures. To manage complexity, compilers should target hardware-facing abstract machines that separate the software and hardware implementations. Finally, intermediate languages can also help us describe hardware to the compiler, so that we can target it without rewriting large parts of the compiler.

A challenge of writing concurrent message-passing pro- grams is ensuring the absence of partial deadlocks, which can cause severe memory leaks in long-running systems. The Go programming language is particularly susceptible to this problem due to its support of message passing and ease of lightweight concurrency creation.

We propose a novel dynamic technique to detect partial deadlocks by soundly approximating liveness using the garbage collector’s marking phase. The approach allows systems to not only detect, but also automatically redress partial deadlocks and alleviate their impact on memory.

We implement the approach in the tool Golf, as an extension to the garbage collector of the Go runtime system and evaluate its effectiveness in a series of experiments. Preliminary results show that the approach is effective at detecting 94% and 50% of partial deadlocks in a series of microbenchmarks and the test suites of a large-scale industrial codebase, respectively. Furthermore, we deployed Golf on a real service used by Uber, and over a period of 24 hours, effectively detected 252 partial deadlocks caused by three programming errors.

In a randomized work-stealing scheduler, parallel speedup depends on the spawn overhead, which workers pay to allow tasks to execute in parallel, and the steal overhead, which thieves pay to start executing new work. It’s important to minimize the spawn overhead, because the spawn overhead incurred by the parallel code must first be offset by parallel scalability before any speedup can be observed.

In pursuit of zero spawn overhead, this work considers a strategy that eliminates the use of deques entirely, obviating the need for a worker to perform explicit bookkeeping or set up a deque to enable parallelism. To that end, we propose DLite, a compiler and runtime ABI (Application Binary Interface) that incurs near-zero spawn overhead, empirically measured to be about 6% compared to a regular function invocation. DLite decreases the spawn overhead to almost nil, at the expense of a high steal cost. Specifically, DLite employs a backtracking strategy: When a steal attempt occurs, the victim provides its current stack and base pointers to the thief, and the thief then reconstructs the necessary state to realize the parallel execution.

We have implemented Cilk-DLite, which extends the OpenCilk platform to implement DLite. When the application has ample parallelism, Cilk-DLite exhibits similar scalability to OpenCilk with much lower spawn overhead. When the application lacks parallelism, the high steal cost in Cilk-DLite can impede scalability due to slower work distribution. We deep dive into one benchmark to analyze the performance impact of the high steal cost.

Today, most application developers write code without much regard for how quickly it will run. Moreover, once the code is written, it is rare for it to be reengineered to run faster. Historically, gains in performance from miniaturization, codified in Moore’s Law, relieved programmers from the burden of making software run fast. But with the end of Moore’s Law, interest is resurging in software performance engineering: making software run fast or otherwise consume few resources such as time, storage, file IO’s, network bandwidth, energy, etc. In the future, to develop innovative products and applications, programmers will need to engage in performance engineering, which is an integrative field requiring an understanding of algorithms, software, and computer architecture. Unfortunately, performance engineering is not widely taught, and most people consider it an unstructured collection of ad hoc tricks. Now is the time to establish software performance engineering as a science-based discipline in its own right alongside traditional areas of computer science.

We introduce the Weighted Red-Blue Pebble Game, an extension of the classic red-blue pebble game with weighted operation costs. This weighted formulation enables constant-factor analysis of highly resource-constrained systems with bounded fast memory, unlimited slow memory, and strict energy and power constraints.

We apply our model to computational kernels in ultra-low-power brain-computer interfaces (BCIs) implanted near the brain. We express these kernels as computational directed acyclic graphs (CDAGs), enabling modular composition of operation schedules with data movement. We derive theoretically optimal schedules for a broad class of tree-structured CDAGs and apply them to on-chip memory design with circuit-level validations for power and area.

Our algorithms result in an average 63% memory area reduction and 43% static power reduction for BCI workloads–critical improvements for ensuring safe, thermally constrained operation in implantable devices. Beyond BCIs, our results underscore the broader utility of weighted pebble games in optimizing memory and I/O across resource-constrained computing environments.

HPCToolkit is a tool for performance analysis of programs on systems ranging from desktops to GPU-accelerated supercomputers. Hardware support for instruction-level performance measurement in AMD, Intel, and NVIDIA GPUs was developed at the urging of the HPCToolkit project team. When measuring a GPU-accelerated application, HPCToolkit employs novel wait-free queues to communicate performance measurements between tool threads and application threads. To accelerate attribution of an execution’s performance measurements, HPCToolkit analyzes the execution’s CPU and GPU binaries to recover mappings between machine instructions and source code. To analyze terabytes of performance measurements gathered during executions at exascale, HPCToolkit employs distributed-memory parallelism, multithreading, sparse data structures, and out-of-core streaming algorithms. To support interactive exploration of profiles up to terabytes in size, HPCToolkit’s hpcviewer GUI uses out-of-core methods to visualize performance data. Recently, HPCToolkit was extended with support for top-down CPU performance analysis. This talk will describe key aspects of HPCToolkit, successes analyzing applications, and some challenges ahead.

Scientific models are today limited by compute resources, forcing approximations driven by feasibility rather than theory. They consequently miss important physical processes and decision-relevant regional details. Advances in AI-driven supercomputing – specialized tensor accelerators, AI compiler stacks, and novel distributed systems – offer unprecedented computational power. Yet, scientific applications such as ocean models, often written in Fortran, C++, or Julia and built for traditional HPC, remain largely incompatible with these technologies. This gap hampers performance portability and isolates scientific computing from rapid cloud-based innovation for AI workloads. In this work, we bridge that gap by transpiling existing programs using the MLIR compiler infrastructure. This process enables advanced optimizations, deployment on AI hardware, and automatic differentiation. In particular, we demonstrate execution of a state of the art Julia-based ocean model (Oceananigans), with >277 custom single-node CUDA kernels on thousands of distributed GPUs and Google TPUs. Our results demonstrate that cloud-based hardware and software designed for AI workloads can significantly accelerate simulations, opening a path for scientific programs to benefit from cutting-edge computational advances.

Linear probing-based hash tables offer high data locality and are considered among the fastest in real-world applications. However, they come with an inherent tradeoff between space efficiency and speed, i.e. when the hash table approaches full capacity, its performance tends to decline considerably due to an effect known as primary clustering. As a result they are only used at low load factors.

Tombstones (markers for deleted elements) can help mitigate the effect of primary clustering in linear probing hash tables. However, tombstones require periodic redistribution, which, in turn, requires a complete halt of regular operations. This makes linear probing not suitable in practical applications where periodic halts are unacceptable.

In this talk, we present a solution to forestall primary clustering in linear probing hash tables, ensuring high data locality and consistent performance even at high load factors. Our approach redistributes tombstones within small windows, deamortizing the cost of mitigating primary clustering and eliminating the need for periodic halts. We provide theoretical guarantees that our deamortization method is asymptotically optimal in efficiency and cost. We also design an efficient implementation within dominant linear-probing hash tables and show performance improvements.

We introduce Zombie hashing in two variants: ordered (compact) and unordered (vectorized) linear probing hash tables. Both variants achieve consistent, high throughput and lowest variance in operation latency compared to other state-of-the-art hash tables across numerous churn cycles, while maintaining 95% space efficiency without downtime. Our results show that Zombie hashing overcomes the limitations of linear probing while preserving high data locality.

The size of a data structure (i.e., the number of elements in it) is a widely used property of a data set. However, for concurrent programs, obtaining a correct size efficiently is non-trivial. In fact, the literature does not offer a mechanism to obtain a correct (linearizable) size of a concurrent data set without resorting to inefficient solutions, such as taking a full snapshot of the data structure to count the elements, or acquiring one global lock in all update and size operations. I will talk about a methodology for adding a concurrent linearizable size operation to sets and dictionaries with a relatively low performance overhead.

Rank-Polymorphism relates to the ability of specifying algorithms that operate on arrays of statically undetermined dimensionality and shape. As it turns out, this capability is instrumental for enabling various performance-related aspects such as parallelism and locality to be captured in array shapes rather than explicit loop nests. At the example of SaC (www.sac-home.org), we demonstrate how this can be achieved, delivering competitive performance from very concise, easily verifiable, rank-polymorphic specifications.

Scientific workflows that require HPC resources are critical in many areas of scientific exploration. Because these workflows tend to be data intensive, severe bottlenecks emerge in storage systems and I/O networks. Although there has been much prior work on coordination of workflows, scheduling algorithms, and HPC storage systems, there are no comprehensive workflow performance diagnosis suites that can automatically identify and alleviate bottlenecks. We present DataFlowDrs, a new comprehensive suite of tools for performance optimization of HPC workflows that especially focuses on data flow and storage. Our suite introduces (a) lightweight high-resolution tools for measurement and profiling of executions; (b) novel methods for automatically predicting data flow bottlenecks after only a 3-5 runs using automatically generated interpretable models of data flow; (c) effective performance analysis and bottleneck detection that can automatically rank order bottlenecks for different combinations of task parallelism and storage resources; (d) actionable performance optimization in the form of new schedules and resource assignments.

Graph analytics are reputed for posing significant challenges to the memory system, which is primarily due to “random” memory access patterns. In this talk, we revisit performance models and characterisation of the memory system issues. We discuss two solutions to the problem: vectorisation and data compaction and evaluate how they alleviate the bottleneck presented by the memory system.

Amdahl’s Law – that serial sections ultimately limit parallel speedup – is often obscured by modern profilers. In fork-join parallelism, standard tools misrepresent execution costs, allowing serial bottlenecks to hide in plain sight. We introduce Parallelism-corrected profiling, a straightforward method to adjust profiler outputs according to their “wall time” contribution. We apply this method to LLM inference on CPU, finding several bottlenecks that resulted in an easy 1.4x speedup.

This talk will cover everything you need to know about how to design efficient parallel applications that operate on dynamic graphs! It will focus on three key aspects:(1) How do you design the containers (ie, data structures) that encapsulate the dynamic graph? (2) What is the right framework (ie, interface) for interacting with a dynamic graph? (3) How do you fairly benchmark the performance of your parallel application for dynamic graphs?

To answer these questions, this talk will discuss two main results. First, I will present a new container for dynamic graphs called F-Graph. F-Graph is a multicore batch-parallel dynamic-graph system that is optimized for spatial locality. It is built on top of a batch-parallel packed-memory array, yielding fast performance for a variety of graph applications. Next, I will present BYO, a unified framework for large-scale graph containers designed to facilitate benchmarking. BYO provides a simple and abstract container API, along with a clean interface. The evaluation uses BYO to evaluate 27 different graph containers on 10 different graph algorithms using 10 large graph datasets. The resulting data illuminates the issues and tradeoffs involved in designing parallel applications for dynamic graphs. Overall, the talk hopes to provide insight into both the theory and practice of efficient parallel computation for dynamic graphs.

Below are very brief notes of the discussions:

• $\mathrm{■}$

  Name? Highlights of Performance Engineering (HOPE) or Highlights of Performance Engineering on Software (HOPES)?

• $\mathrm{■}$

  When/Where? Possible plan: 2027 PPoPP/HPCA/CGO/CC/.. Co-located conferences on multiple relevant areas; good location (Salt Lake City); flexible timeline. It doesn't need to be always at PPoPP, though. Maybe we can reconsider the venue every year based on time/location/…

• $\mathrm{■}$

  How to submit?

  • –

    Submissions will be based on “highlights”, which are papers published elsewhere but highly relevant to SPE. Accepted papers will be invited to give talks.

  • –

    We can make it submission+invitation based. The PC (or an even smaller committee) may recommend papers, but submissions are open to the public.

  • –

    Papers will be evaluated by a 2-4 pages abstract. Full papers should be provided. Accepted papers will be invited to give talks; more papers may be accepted as posters. The quality of the write-up is important in the review process as it is an indicator of the talk quality.

  • –

    A submission can contain multiple papers or a series of work. In this case the abstract should provide a nice overview of them.

  • –

    Accepted manuscripts can be published as abstract/workshop short papers on ACM DL.

• $\mathrm{■}$

  Other discussions

  • –

    Tracks? Expected number of submissions/acceptance rate? Balance topics?

  • –

    Possible funding for student traveling? (would make it more attractive to get more submissions)

  • –

    For invited papers, should we always accept or they still compete with other papers normally?