logo

Latest Updates

Illustration for persistent multiversion adaptive radix trees

Paper@SIGMOD'26

2026-05-31 | Author: Trevor

A paper by Arash (Mohammad) Khalaji, Trevor Brown and Khuzaima Daudjee has been accepted at SIGMOD'26! The paper, titled ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries, presents a persistent, versioned Adaptive Radix Tree for non-volatile memory. It integrates multiversioning into ART to support efficient, linearizable range queries under concurrency, while using in-node logging to improve point query and update performance. In experiments, it matches or exceeds current NVM-based indexes on point operations while providing correct concurrent range queries, which existing indexes do not provide. Look for the paper, code and artifact on the publications page.

More information...
Illustration for dynamic multiversioning in transactional memory

Paper@PPoPP'26

2026-01-31 | Author: Trevor

A paper by Guy Coccimiglio, Trevor Brown and Srivatsan Ravi has been accepted at PPoPP'26! The paper, titled Multiverse: Transactional Memory with Dynamic Multiversioning, introduces a software transactional memory system that lets versioned and unversioned transactions run together. It keeps ordinary transactions competitive with state-of-the-art unversioned STM, while adding fast support for long-running reads over data that is being frequently updated. In those long-read workloads, Multiverse can outperform prior STMs by orders of magnitude. Look for the paper, code and artifact on the publications page.

More information...
Illustration for persistent hybrid transactional memory with fine-grained locking

Paper@SPAA'25

2025-07-28 | Author: Trevor

A paper by Guy Coccimiglio, Trevor Brown and Srivatsan Ravi has been accepted at SPAA'25! The paper, titled Persistent HyTM via Fast Path Fine-Grained Locking, studies how to combine hardware transactional memory with non-volatile memory despite the fact that persistence instructions abort hardware transactions. The solution uses the hardware fast path mainly to read or acquire fine-grained locks, yielding durable linearizable transactions and improved performance over prior persistent STMs and HyTMs, especially on read-dominant workloads. Look for the paper, code and artifact on the publications page.

More information...
Illustration for hardware-accelerated coarse-granular GPU indexing

Paper@ICDE'25

2025-05-19 | Author: Trevor

A paper by Justus Henneberg, Felix Schuhknecht, Rosina Kharal and Trevor Brown has been accepted at ICDE'25! The paper, titled More Bang for Your Buck(et): Fast and Space-efficient Hardware-accelerated Coarse-granular Indexing on GPUs, makes GPU-resident database indexes more practical by using NVIDIA ray tracing cores to index buckets of keys rather than individual keys. The resulting cgRX index reduces memory overhead, improves range lookups, and supports practical updates; in experiments, it gives 1.5x-3x higher throughput per memory footprint than comparable range-lookup baselines. Look for the paper on the publications page.

More information...
Illustration for publish-on-ping memory reclamation reservations

PPoPP'25 distinguished paper

2025-03-01 | Author: Trevor

A paper by Ajay Singh and Trevor Brown has been accepted at PPoPP'25 and received a Distinguished Paper Award! The paper, titled Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for Concurrent Data Structures, tackles the cost of hazard-pointer-style memory reclamation, where traversals repeatedly publish reservations and pay ordering fences before reads. Publish-on-ping lets threads track reservations privately and publish them only when a reclaimer asks, serving as a drop-in replacement for hazard pointers and hazard eras. Across several concurrent data structures, it reports 1.2x-4x speedups over original hazard pointers and up to 3x over hazard eras. Look for the paper, code and ACM DL link on the publications page.

More information...
Image of the cover of the book Shared Memory Synchronization (2nd edition) by Michael L. Scott and Trevor Brown

Book published!

2024-01-30 | Author: Trevor

The second edition of the book Shared Memory Synchronization, which I joined Michael L. Scott in preparing, has just been published! It features many substantial improvements over the original text, such as greatly improved coverage of non-blocking / lock-free algorithms, concurrent memory reclamation, and high level synchronization primitives. Another big change was the inclusion of detailed annotations, in all code throughout the book, of what kinds of memory ordering constraints are required for real implementations of the algorithms to be correct (or at least our best effort attempt at specifying these constraints). As far as I know, this is quite unique for books in this area. Many other changes are detailed in the foreword, which should be accessible free of charge. At the time of writing, the book costs $45 USD for hardcover(!) and $35 USD for e-book.

More information...
Timeline plot showing time intervals spent freeing batches in epoch based reclamation

Paper@PPoPP'24

2023-11-10 | Author: Trevor

A paper by my students Daewoo Kim and Ajay Singh titled "Are Your Epochs Too Epic? Batch Free Can Be Harmful" has been accepted at PPoPP'24. It demonstrates that a deferred remote freeing mechanism in popular memory allocators like jemalloc can have a strong negative interaction with the batch freeing approach taken by virtually all safe memory reclamation algorithms. As a proof of concept, we propose amortizing the freeing of objects over many operations, rather than freeing large batches, and show this results in large speedups in many state of the art safe memory reclamation algorithms. We also resurrect an old idea: token ring epoch based reclamation, and show that, with an improved understanding of what happens in the allocator, this extremely simple variant of EBR can be highly practical (outperforming the state of the art).

More information...
vEB tree node layout

Paper@PPoPP'24

2023-11-10 | Author: Trevor

A paper by my student Mohammad Khalaji, Professor Khuzaima Daudjee from the University of Waterloo, and Professor Vitaly Aksenov from City University London titled "Practical Hardware Transactional vEB Trees" has been accepted at PPoPP'24. It presents a fast van Emde Boas (vEB) tree implemented using transactional lock elision overtop of Intel's restricted transactional memory. Van Emde Boas trees offer set/map operations with runtimes that are doubly logarithmic in the universe size. We start with a naive implementation, and present a sequence of optimizations that result in a high performance data structure suited for (relatively) small or densely packed universes.

More information...
Image of back pointers, a key mechanism in the paper.

Paper@SSS'23

2023-07-24 | Author: Trevor

A paper by my student Gaetano Coccimiglio, myself and Professor Srivatsan Ravi titled "The fence complexity of persistent sets" has been accepted at SSS'23. It introduces some simple lower bounds in persistent sets, as well as a new algorithmic technique that can be used to implement non-blocking data structures with flush-free read-only operations.

More information...
Code snippet using conditional reads for a stack

Paper@IPDPS'23

2022-12-17 | Author: Trevor

A paper by my PhD student Ajay Singh, myself, and Michael Spear, has been accepted at IPDPS'23! The paper, "Efficient Hardware Primitives for Immediate Memory Reclamation in Optimistic Data Structures," introduces Conditional Access, a proposal for new hardware instructions that enable deleted nodes to be immediate freed in a large class of concurrent data structures. This is in contrast to the traditional memory reclamation approaches that delay reclamation to avoid use-after-free bugs, creating several performance problems in the process.

More information...
Large performance differences between popular benchmarks

Paper@OPODIS'22

2022-12-13 | Author: Trevor

A paper by my PhD student Rosina Kharal is appearing at OPODIS'22. The paper, "Performance Anomalies in Concurrent Data Structure Microbenchmarks" compares performance results across several popular data structure benchmarks. When running ostensibly the same workload in each benchmark, the three benchmarks often give substantially different performance results. We drill down to find the underlying causes of these differences, which range from simple bugs, to idiosyncracies of random number generators. Rosina gave the talk at OPODIS.

More information...
PREP-UC pseudocode snippet

SPAA'22 candidate for best paper

2022-07-11 | Author: Trevor

A paper by my PhD student Gaetano (Guy) Coccimiglio, myself, and Srivatsan Ravi, was a candidate for best paper (top 4) at SPAA this year. The paper, "PREP-UC: A practical replicated persistent universal construction," gives an algorithm for automatically transforming a sequential algorithm into a persistent (on Intel Optane DCPMMs), NUMA aware, deadlock-free, concurrent algorithm. Guy gave the talk at SPAA.

More information...
PPoPP'22 best artifact

PPoPP'22 best artifact!

2022-04-06 | Author: Trevor

A paper by Trevor Brown, William Sigouin and Dan Alistarh received the best artifact award at PPoPP 2022! The paper, titled PathCAS: an efficient middle ground for concurrent search data structures, describes a new synchronization primitive called PathCAS that can be used to easily and efficiently implement concurrent data structures. At a high level, you can think of it as somewhat similar to a combination of atomic snapshots of the search path and multiword compare-and-swap for updates. Data structures built from PathCAS rival the state of the art in handcrafted data structures, and are very simple.

More information...
Two papers accepted at PPoPP'22

Two papers@PPoPP'22

2021-11-26 | Author: Trevor

Congratulations to Anubhav Srivastava and William Sigouin! Their hard work has resulted in two papers being accepted at PPoPP'22! "PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures" by Trevor Brown, William Sigouin and Dan Alistarh, and "Elimination (a,b)-trees with fast, durable updates" by Anubhav Srivastava and Trevor Brown. Artifacts were submitted for both. Look forward to their appearance soon!

More information...
Paper accepted at PPoPP 2021

PPoPP'21 best artifact!

2020-11-16 | Author: Trevor

A paper by Ajay Singh, Trevor Brown and Ali Mashtizadeh was accepted for publication at PPoPP'21! It received the best artifact award, and was in the top 4 candidates for best paper! The paper, titled NBR: neutralization based reclamation, describes how POSIX signals can be used to safely, easily and efficiently reclaim memory for concurrent data structures whose operations follow a simple template. NBR is up to 2.5x faster than the competition and uses very little memory (constant per thread).

More information...
2D heatmap / histogram

New tutorial: histogram pitalls

2020-06-13 | Author: Trevor

An exploration of an insidious problem with histograms that can lead to completely incorrect experimental conclusions.

More information...
PPoPP'20 best paper award plaque

Best paper award: PPoPP'20

2020-02-26 | Author: Trevor

A paper by Trevor Brown, Aleksandar Prokopec and Dan Alistarh just won best paper at PPoPP'20! The paper, titled "Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time," introduces a next generation search tree for fast in-memory indexing. Check it out on the publications page...

More information...
Bash prompt showing clean debugging output

New tutorial: renaming tokens in debugging output

2019-11-28 | Author: Trevor

Sometimes, in my debugging output, I like to rename long tokens into shorter names that are easier to read / recognize quickly. For example, if I'm printing memory addresses distributed over several OS pages, and I want to analyze how objects fall into cache lines and pages, I like to give the different pages short names like A, B, C, instead of "page 19985124131," since the precise location of the page doesn't usually matter to me. This tutorial demonstrates an easy way to do this renaming, and also shows how to print nicely coloured(!) debugging output in bash.

More information...
SPTDC'19 logo

Second highest rated SPTDC talk

2019-07-29 | Author: Trevor

The results of attendee evaluations are in! Trevor's invited lecture at SPTDC'19 was the second highest rated lecture, with a mean score of 4.68 out of 5. The highest rated lecture was by Michael Scott with an astounding 4.93 rating. The average rating over all invited lectures was 4.24. You can watch Trevor's talk at the link below!

More information...
Cluster rack unit

Rift: new 8-node Intel cluster

2019-07-23 | Author: Trevor

We just received word today that our lab has been allocated an eight-node compute cluster that is being recovered from the retired ORCA cluster at SHARCNET (Compute Canada). Our new "rift" cluster is currently being configured. This will be a huge help for small scale multicore and distributed system experiments, continuous integration, and marmoset performance testing for Trevor's graduate course CS 798 - Multicore Programming.

More information...
Zyra rack unit

Zyra: new high-end experimental server

2019-07-18 | Author: Trevor

Our new 144 thread server, Zyra, has arrived at the University, and is currently being racked and configured! This will join our 192 thread server, Jax, to alleviate time sharing bottlenecks whenever we prepare multiple papers for tight conference deadlines.

More information...
SPTDC'19 logo

Invited talk by Trevor at SPTDC'19

2019-06-05 | Author: Trevor

On July 12th, Trevor will give a three hour invited lecture at the 2nd Summer School on the Practice and Theory of Distributed Computing, in St. Petersburg, Russia. The title of the talk is "Practical Aspects of Multicore Programming." More than 150 students are expected to attend the school. Other speakers include Maurice Herlihy, Lesley Lamport, Michael Scott.

More information...