Welcome to Trevor Brown's home page
I'm currently a postdoctoral researcher at the Technion University in Haifa, Israel.
Before that, I was a PhD student at the University of Toronto.
Although I was in the theory group at U of T, I would say that my work is slightly closer to systems work than theory.
I care greatly about rigor, whether in theoretical or experimental work.
My research currently revolves around concurrent data structures, especially lock-free ones.
I am also interested in transactional memory, non-volatile memory, and techniques for coping with non-uniform memory architectures.
Supervisor at the Technion: Hagit Attiya
Supervisor at U of T: Faith Ellen
Contact: me [at] tbrown [dot] pro
Curriculum Vitae: [PDF]
- (2017) Cost of concurrency in hybrid transactional memory.
Trevor Brown and Srivatsan Ravi.
To appear at DISC'17.
A preliminary version also appeared at TRANSACT'17.
- (2017) Reuse, don't recycle: transforming algorithms that throw away descriptors.
Maya Arbel-Raviv and Trevor Brown.
To appear at DISC'17.
Also appeared as a poster and short paper at PPoPP'17.
- (2017) A template for implementing fast lock-free trees using HTM.
- (2017) Techniques for constructing efficient lock-free data structures.
University of Toronto, PhD thesis.
- (2016) PHyTM: persistent hybrid transactional memory.
Hillel Avni and Trevor Brown.
A preliminary version also appeared at TRANSACT'16.
- (2016) Concurrent data structures.
Faith Ellen and Trevor Brown.
Faith's invited talk and short publication, which I co-authored.
- (2016) Investigating the performance of hardware transactions on a multi-socket machine.
Trevor Brown, Alex Kogan, Yossi Lev and Victor Luchangco.
A preliminary version also appeared at TRANSACT'16.
- (2015) Faster Data Structures in Transactional Memory using Three Paths.
Brief Announcement at DISC'15.
- (2015) Reclaiming memory for lock-free data structures: there has to be a better way.
- (2014) B-slack trees: space efficient B-trees.
- (2014) A general technique for non-blocking trees.
Trevor Brown, Faith Ellen and Eric Ruppert.
Also appeared as a brief announcement at DISC'13.
- (2013) Pragmatic primitives for non-blocking data structures.
Trevor Brown, Faith Ellen and Eric Ruppert.
- (2012) Range queries in non-blocking k-ary search trees.
Trevor Brown and Hillel Avni.
- (2011) Non-blocking k-ary search trees.
Trevor Brown and Joanna Helga.
[The talk: Video,
A significantly expanded version also appeared as York University Technical Report CSE-2011-04.
(2017) Good data structure experiments are R.A.R.E. (Invited talk at the 1st Workshop on the Theory and Practice of Concurrency)
(2017) Good data structure experiments are R.A.R.E. (at Oath/Yahoo! labs)
Non-blocking Tree Data Structures
My colleagues and I have developed a number of highly efficient non-blocking (lock-free) tree data structures, and implemented them in Java.
More are in the works.
- [Chromatic tree]
This is a relaxed version of a red-black tree that has less strict balancing criteria.
Weakening the structural properties makes this tree much more contention friendly than a traditional red-black tree.
Even though its balancing is less strict than a red-black tree's, the height of the tree is O(c+log n),
where c is the number of insertions and deletions currently in progress.
- [Relaxed AVL tree]
This is a relaxed version of an AVL tree that has less strict balancing criteria, so it is more contention friendly.
The height of the tree is O(c+log n), where c is the number of insertions and deletions currently in progress.
For those interested to know what else is out there, as of September 2013, the only other efficient, provably correct non-blocking trees in the literature are a concurrent hash trie that supports fairly fast cloning (Prokopec et. al), and a B+tree that does not have successor or predecessor pointers (Braginsky and Petrank).
- [k-ary search tree with range queries]
This is a leaf-oriented search tree in which every internal node has k children, and leaves contain between 0 and k keys.
The data structure supports non-blocking range queries that are extremely fast when the ranges being queried are small (for instance, containing 500 keys).
- [3-ary search tree (3ST),
- [Binary search tree]
This is an implementation of the non-blocking binary search tree introduced by Faith Ellen, Eric Ruppert, Panagiota Fatouru and Franck van Breugel at PODC'10.
This was the first implementation of a non-blocking binary search tree.
Reproducing experiments or performing your own
Writing a test harness to correctly perform experiments in Java is difficult.
So, I've provided a full featured test harness that can reproduce all of the experiments in my paper "A general technique for non-blocking trees."
It's also easy to add your own data structures to it, and compare them to the (many) data structures included with the test harness.
If you want to do experiments that measure throughput (operations/second) of a number of data structures, over several different workloads (operation mixes) and key ranges, then this can get you running very quickly.
A word about experimental methodology.
The test harness is available for download here. It includes scripts for Linux / Solaris to reproduce the experiments in the paper. It also includes a very detailed README.txt file that explains how to use it, which algorithms are included, and how to add your own algorithms.
- Experiments of this sort in Java should be performed with a number of timed trials, each running for a reasonable length of time, such as five seconds.
This length of time should be long enough that running substantially longer trials (e.g., 10x longer) does not change your results.
The amount of memory allocated to the JVM should be chosen such that memory will be exhausted, and garbage collection performed, several times per trial.
If garbage collection is never triggered, then a crucial piece of your data structure's performance is being ignored, and one cannot gauge how your algorithm will perform on a real system.
However, if memory pressure is too severe, you will be measuring the performance of a stressed garbage collector, and not your algorithm.
Try to choose the smallest memory limit that does not grossly inflate the standard deviation of your throughput measurements over all trials for an experiment.
I typically find 3GB to be reasonable for five second trials on 128 thread servers.
I also recommend setting a minimum and maximum heap size, since Java is very eager in resizing the heap.
- Each trial should start with trees that are prefilled to their expected size in the steady state, so that you are measuring steady state performance, and not inconsistent performance as the size of the tree is changing.
If your experiment consists of random operations in the proportions i% insertions, d% deletions, and s% searches on keys drawn uniformly randomly from a key range of size r, then the expected size of the tree in the steady state will be ri/(i+d).
For example, in an experiment where 20% of operations are insertions, 10% are deletions, and 70% are searches, the expected size of the tree in the steady state is (2/3)r.
See Section 5 of the paper for more details on why this is the case.
The test harness will prefill trees to the appropriate size (using many threads) if you specify the "-prefill" flag.
- When you work in Java, compilation happens on the fly, during the first few seconds of your experiments.
For this reason, you should throw away the first few trials of each experiment.
It should be obvious how many need to be discarded when you look at the measured throughput of each trial.
This is important because some algorithms take longer than others to compile, and an algorithm that takes longer may be stuck in its slow, interpreted state for much longer than another. This can skew throughput measurements in favour of the algorithm that compiles faster.
- Remember to use a 64-bit JVM on a 64-bit machine, and to use the -d64 and -server JVM flags.
These flags can drastically change performance measurements.
- Experiments should run in separate invocations of the JVM, since they will not be statistically independent if they run in the same VM. I've seen this change results dramatically.
For more information on this and other best practices for Java experiments, see the paper "Statistically rigorous java performance evaluation" by Georges et al.
- TA for CSC263 Winter 2014: data structures [under Sam Toueg]
- TA for CSC2221 Fall 2013: introduction to distributed computing [graduate course; under Sam Toueg]
- TA for CSC263 Winter 2013: data structures [under Sam Toueg]
- TA for CSC369 Fall 2012: operating systems [under Angela Demke-Brown]
- TA for CSC263 Winter 2012: data structures [under Sam Toueg]
- TA for CSC263 (and 265) Fall 2011: (enhanced) data structures [under Faith Ellen, Toni Pitassi]
Repetitive Strain Injuries
I have been suffering from a severe repetitive strain injury (RSI) for quite a while, now. Since August of 2012, I've been unable to use a computer in any serious capacity via a keyboard and mouse. This might seem like highly personal information for me to be sharing on my public website, but this issue is insidious, poorly understood, and common among computer scientists and other heavy computer users. What's worse is that it seems like once you have chronic tendinitis, carpal tunnel syndrome or any other RSI, you can never truly be free of it. The various roads to recovery are peppered with terrible pitfalls and, despite your best efforts (and obedience of doctors' orders), it is all too easy to worsen your condition instead of improving it. Moreover, doing nothing might lead to sub optimal healing or, at worst, atrophy and degeneration.
Since October 2012, this issue has shot to the top of my personal interests, and I am quite invested in discovering how to make a full recovery. I've since been to numerous doctors and specialists (GPs, physiotherapists, a physiatrist, an acupuncturist), read dozens of medical papers, and pursued many avenues that promise recovery. Unfortunately, it seems like no one truly understands my condition. Visit half a dozen doctors, and you will hear half a dozen distinct, and often contradictory, opinions. This doesn't mean that you should try to tackle this without the help of medical professionals. However, if you rely solely on their knowledge, you may wind up struggling for a long time with a condition that is at the fringe of medical knowledge. I intend to devote a fair amount of space on this site (and maybe branch off into another site) to providing a nice, clean distillation of what I've learned from these many sources, along with attempted explanations of the evidence that led me to my conclusions. If you are struggling with something similar, I would welcome your input, and your reactions to my thoughts. I would also like to hear your story, so that I can turn my page into a collection of recorded experiences, to further the state of knowledge of these conditions. With time, careful contemplation, and a bit of luck, I hope we can make a full recovery together, and lead future sufferers to similar success.
From a technical standpoint, in order to be able to pursue my work, I've had to change the way I use computers dramatically. While I was trying to figure this out, I investigated many alternative computer interface options. Unfortunately, while most technologies I found had the potential to satisfy a very casual computer user, some of them were extremely expensive, others would just cause my injuries to migrate to different parts of my limbs, and the rest were not really "industrial-strength." I didn't want to spend $600-1,000 just to see whether a single piece of hardware would work out, and using the inexpensive or freely available technologies would make me far too slow to efficiently write and edit research papers, or even navigate my computer without serious frustration. In the end, I wound up developing some of my own solutions, which are exceedingly simple, inexpensive, and quite effective. I intend to publish a number of these things on my site, including the software I wrote, video and descriptions of the hardware I cobbled together, and a description of how to reproduce my LaTeX editing set up. My hope is that someone can take what I've done for LaTeX editing, and do it for programming in Java or C++ (since that is one area where my set up currently falls flat on its face).
I know this is an Internet cliché, but expect further updates soon!
Update (Dec. 16, 2013)
After 14 months of pain, I've now been essentially symptom free for almost two months, and have been working at full capacity throughout that time (approx. 30k key presses & clicks per day). I think I now understand the pathology of my particular flavour of RSI, and how to fix it. As a teaser, I'll say that circulation (blood flow) is the largest factor. I'd like to write more about this soon, but, in the mean time, if you are struggling with a RSI that prevents you from using a computer as you would like, and you would like to hear about my recovery technique, please drop me an e-mail. I could use the motivation to dedicate time to writing about it.
Here's a graph that shows how the activity level I've been able to maintain has changed each month over the last two years.
Month zero is January 2012.
I think it provides fairly good evidence that I've finally arrived at a good mental model of how this RSI works, and how to fix it.
Update (Jan. 24, 2014)
I'm still feeling great. I think I've had two small relapses, each lasting a day. My work level is as high as ever, and sometimes higher.
The real reason I'm updating right now is that some people have expressed interest in what I've learned, and what my proposed solutions are.
So, I finally sat down, collected my notes from various sources, and wrote up a fairly comprehensive first draft.
On a side-note, I wrote this huge page in one sitting, using my hands. *gasp*
Update (May 15, 2014)
After four more months, I'm happy to report that my hand usage is still going strong.
I'm basically back to what I love (playing Starcraft II every night and typing the days away), but there are a few caveats.
First, I've had a handful of small relapses that have taken me out of commission for a day each.
This usually happens when I've worked an unusually large amount over 3-4 days, and then had a long gaming session, and been too lazy to soak my hands in hot water before bed.
This is still remarkably little trouble considering that I used to be taken out of commission for five days at a time, much more frequently, and by a MUCH lower level of work.
Second, if I don't soak my hands in hot water before playing games, I injure myself pretty quickly.
So, it seems like hot water is going to be a part of my daily routine for the forseeable future.
I suspect the ultimate solution might be significant daily cardiovascular exercise to improve circulation, but I have yet to try that.
(A stomach ulcer makes it uncomfortable to run and jump around for more than a few minutes, so I'm hesitant.)
The third and final caveat is that I believe I will get injured if I lift heavy objects using my wrists (more than 10lb per wrist) for any prolonged period of time (more than a few seconds).
I suppose this is just because I'd generally avoided using my hands to handle any objects heavier than a few hundred grams up until the last few months.
I'm slowly starting to let myself lift larger objects.
It seems to be okay to manipulate large objects as long as the time is very short and the muscle positions are very strong and stable (to avoid pulling and injuring muscles or tendons).
For instance, to get some extra wrist strengthening action in whenever I'm moving around on a couch or bed, I intentionally lift my own body weight (~165lb) using my clenched fists (with straight wrists, fists pointing down).
However, repetitive actions like washing dishes (especially scrubbing pans) can still sometimes irritate my wrists for a few hours.
I'm guessing that this will go away if I resume exercising my wrists with things like regular dish washing, but I've been holding back because of its repetitiveness.
Packing to move to a new apartment in the next two weeks is going to be a serious test of my progress.
Here's a graph that shows how my progress has continued.
The way I aggregated the statistics into months is a little bit different from the way I did above, so some data points might look slightly different.
Update (Feb 18, 2015)
Well, it has been another 9 months.
My hand usage is stronger than ever, but I'm still periodically having mild wrist pain.
More and more, as time goes on, I'm thinking that the ultimate solution will be improving circulation.
Nevertheless, I think it's safe to say that I've returned to productivity.
Every night I soak my wrists and forearms in 109F water for 9 minutes, and that's enough to keep my problems at bay.
If I stop doing that for two or three nights, then I'm in constant pain (whether or not I perform any repetitive activity).
So, until I sort out the larger circulation issue, I'm just going to keep soaking every night.
Here's another graph that shows how my progress has continued.
Update (Mar 15, 2017)
So, it has been about two years since my last update.
I'm still soaking my wrists every night for 11 minutes in a bucket of 110F water, and it's still working well.
I'm not so sure that my problem is circulation, any more, although I think it's a factor.
I'm starting to think that I might have some sort of inflammatory/arthritic condition, since it seems useful occasionally to apply cold, instead of hot.
I think there is some value in learning to recognize when your body wants cold and when it wants heat.
Once every couple of weeks, I have a slipup, and end up losing productivity for a day or two, but overall, I'm able to maintain a very high level of productivity.
In two weeks, I'm flying to Israel for the next 6 months.
I wonder how/if things will change in the hot hot heat.
Here's a graph that shows my continued progress.
I also have some stuff (Python code) pertaining to the CSC2501 course at the U of T
I'll eventually add more things to this site as I think of them and find the time.