Arrays vs. Ring Buffers: A Performance Comparison in Rust

The VecDeque collection in Rust implements a double-ended queue with O(1) operations to push and pop on either end. (Other language libraries have similar data structures, such as ArrayDeque in Java.) It also provides O(1) random access to individual elements.

These ring buffers are implemented behind-the-scenes with an array and two index variables: a start and an end. For the sake of simplicity, imagine that the deque is initialized with a starting capacity of 10. Both the start and end variables could then be initialized to point at index 5. Any push to the front decreases the starting index, and any push to the back increases the ending index.

When accessing an individual element, the index is added to the starting index to determine the final array position to employ. If this sum exceeds the size of the array, it "wraps around" to the lower part of the array.

What is not obvious is the degree to which this extra addition to find the index represents a performance penalty. Documentation for the Rust Collections library states that whenever Vec and VecDeque have the same asymptotic time bounds for an operation, that the Vec will generally be faster, but no further details are provided. 

I became interested in this question because of how the constant-time double-ended push and pop operations for a VecDeque incur no asymptotic time penalty for direct random access. If the penalty is, in fact, insignificant, then maybe there is no need to use a regular Vec at all. So to satisfy my curiosity, I constructed an experiment. 

In this experiment, we create a Vec with a specified number of elements. (I used 100000 to produce the data below.) We then randomly shuffle these elements. At this point, the experiment begins. We copy these values into another Vec and then a VecDeque, and then sort them using the selection sort algorithm. While this is not a very good sorting algorithm in general, for this purpose it is ideal, as it requires a lot of random accesses that are widely spaced across the sequence being sorted. By using the same sequence of shuffled values for each data structure, the test should also be fair.

Here are the results. For each algorithm, we performed 30 trials with 100000 elements. Each trial featured a different permutation of those values.

Data Structure	Mean completion time (ms)	Standard Deviation
Vec	3238.4	205.1558
VecDeque	4813.2	213.019

It is pretty clear, then, that for random access the Vec is consistently faster than the VecDeque. In exchange for constant-time front-end pushes and pops, the VecDeque takes about 50% longer to complete each random access. It seems to me to be well worth the cost when that functionality is pertinent, but when it is not the plain Vec is strongly preferable.

Please feel free to download and experiment with my source code if you are interested.

Rust at Apple

I recently saw the following job advertisement at Apple, posted January 29, 2020. (I assume the link will eventually go away once the job is filled, but the text of the ad is what is pertinent here.)

We are seeking an experienced software engineer with a passion for computer networking and security. Be part of a small, highly skilled team building network infrastructure services at Apple. 

The Apple Cloud Traffic team provides a secure networking layer to underpin consumer-facing applications. Based on a custom implementation of IPsec, it must handle the encryption of every packet passing between servers within and across vast data centres, with minimal overhead. Custom-built secure RPC protocols manage the keying, authentication and authorization of all traffic flows. 

The performance and security of the systems we build are critical. We interface directly to low-level Linux kernel interfaces, using asynchronous I/O and threads to distribute workload. Following a very successful first foray into Rust we are migrating an established codebase from C to Rust, and building new functionality primarily in Rust.

 Here are a few aspects I would like to highlight:

• They are migrating an established codebase from C to Rust. This suggests that the well-known problems in C of insecure memory accesses and undefined behavior are impairing the stability of the system, and that the safety guarantees of Rust are expected to eliminate those problems. Code migration is a lot of work!
• They are making significant use of multithreading, another strong point of Rust. The compiler's ability to prevent race conditions in RAM will be a big advantage here.
• Overhead needs to be minimal. The high performance that Rust facilitates will be helpful here.
• The system is making direct system calls to the kernel. Again, the ability of Rust to compete with C in the low-level systems space is emphasized.

I expect we will see more and more similar advertisements as the benefits of Rust continue to become better known.

The rise of Rust

The Rust programming language has been increasing in popularity of late. I learned to program in Rust in order to teach my Spring 2017 operating systems course using the language, inspired by the work of David Evans at the University of Virginia. I was so pleased with the experience that I taught the course in Rust a second time in Spring 2019. I have also started using Rust in software development in my research program.

There are a few things I have come across recently that, I think, demonstrate the appeal of programming in Rust. The following quotes come from a Reddit thread posing the question: "Why does Rust seem to inspire people?"

It took me literally a day and a half from "I'm going to try writing my first Rust program" to "here's a working multithreaded network program with string processing that can pump out 100GB+ a day of throughput with no memory leaks or buffer overflow errors." That's nuts. I couldn't have done that in a GC'd language or C++, or at least not as quickly. The way move semantics, the borrow checker, thread spawning, and channels/atomics work is very well thought out.

I can vouch for this experience personally. In fact, writing a multithreaded web server is one of the key assignments I employ in my operating systems course. The ownership guarantees embedded in Rust's static type system make this possible.

I’m a college professor in software engineering, so I’m saturated in young people excited about tech. For the last few years, it’s been fascinating to see how excitement for Rust has gained momentum.

In our major, you tend to learn C freshman year alongside Python, Ruby, and Java. Lots of folks love C for being system-level and fast. But, pointers and malloc are brutal to learn. I witness it every year. Even if you enjoy C, everyone had a story about staying up all night debugging a segfault. I recently met with a mental health counselor who sees a lot of students in my major. Segfaults came up. Yeah. Anecdotally, C’s memory management hurts peoples’ mental health.

Then, when they take my security course and learn about buffer overflows and other memory corruption issues they start to question the wisdom of such permissive language like C and C++. It’s a phase we all go through. We all question the establishment in college.

Then when students learn about Rust, they hear about how memory allocation is safe and zero-cost abstraction. They get excited and start evangelizing to their peers. The excitement is noticeably more than other tech, which I always thought was interesting. We don’t cover it in any class (yet...), so they pick it up in their spare time.  

I’m honestly surprised that a lot of my students like Rust. (Thrilled that they are!) Its a tough language to learn. It’s got some different concepts (e.g borrowing, lifetimes) that are a big paradigm shift for them. For me, I rolled my eyes about it for like three years and just recently started learning Rust and I’m impressed.

It really is time to question the establishment. The experience of programming in Rust demonstrates that you can write bare-metal code in a language with a type system that guarantees the absence of buffer overflows and memory corruption without compromising on performance. At this point, it is arguably an ethical imperative to show our students that there is a better way.

The sad reality of our world is that everything is broken - as someone who has done security research, I can tell you that every word in that article is true, and more.

The reason why everything is broken is because there are two kinds of programming languages: the slow ones (Python, Java, Go) and the ones that lead to horrific security vulnerabilities (C, C++). We need our computers to go fast, so we use C and C++, and so everything is glitchy and broken.

Now imagine a language that breaks that mold. That is fast as C/C++ and can fully replace them, but without the security vulnerabilities. The holy grail that would lets us write code that is secure, reliable and fast all at the same time.

That's Rust.

I seriously cannot overstate how big of a deal this is. Nothing like this has ever existed before. Most thought creating such a language impossible!

This reinforces what the professor had to say, from the viewpoint of a computer security researcher. Rust is a tool that suffices to make legions of computer security problems just go away.

Five days trying to figure out a segfault. (Personal project in highschool) Gave up. Half a year later, checked it out again. Blindingly obvious after ten minutes. Even experience doesn't beat the three seconds it takes to read the rust compiler's output. Heavenly.

This quote comes from a manifestly talented and experienced developer. It is interesting to think about the useful experience this person could have developed in solving problems other than finding segmentation faults if, in his career, the compiler had been a reliable ally in avoiding these problems.

Rust is far from perfect, and sometimes feels a bit pedantic, but coding in Rust I never ever put my hands in the air and think "damn, I hate this language so much, it's so stupid", which I routinely do when using other mainstream languages.

Rust is the first language I am actually pleased to work with, and it's been years now. Tooling is great, community works well, popularity is good enough. And the language feels like it was coherently and carefully designed for humans (as opposed to: oh, you have a bug, you must be stupid or something for doing wrong things). And it is a programming language suitable even for low level systems/kernel/embedded programming, just as much for web dev, which is simply amazing.

I love the core features: ownership/borrowing, thread-safety, good type system, and miss them soo much when I can't use them in other languages. It's a very powerful force, reinforcing the appreciation of Rust.

So, everything I do in Rust ... feels joyful. I feel like you can achieve anything, and it is not even that difficult. At least the language empowers me, instead of getting in the way, like other ones.

A couple of comments:

• I boldfaced an important line above, which references the common notion that memory bugs are signs of bad programming. The Rust environment eliminates this needless hazing. 
• The second line I boldfaced reflects my own experience, but I want to include an important caution: it takes quite a bit of practice with Rust to get to the point where it is not difficult to use. The language is well-known for its steep learning curve. I would like to encourage anyone starting out with Rust to persevere until you get to that point.

The article Why Rust is the Future of Robotics also has interesting insights, most particularly the following information about embedded development:

For embedded systems, specific tools have also been developed:

• Peripheral control — There is this thing called svd2rust that can automatically generate a Rust API to access every peripherals on a micro-controller, directly from it’s SVD description. Rust is smart and it can enforce at compile time that you use peripherals as they should be. You cannot compile if you try writing to a read-only register, or read to a write-only registers. You cannot write invalid bit patterns to a register too. The SVD can define a range of valid values and Rust won’t let you go out of range.
• Ressource collision prevention— In the next version, they will introduce singletons to let Rust know when some code wants to use a peripheral already in use, for example a timer. This is a common source of problems in embedded systems were resources are limited and several devices might want to use them. It is a classic with Arduino Uno boards that only have few timers. So when you use the Servo library, you cannot use PWM on the pin 9 and 10. But the code will compile, push to the board and fail badly by producing very strange behaviours extremely hard to debug. This made many, many, Arduino users confused. With singletons, Rust can tell you at compile time if the timer is already in use, preventing users massive headaches without any runtime overhead.

That is, it turns out the ownership concept can be employed to avoid many specific hardware-utilization errors at compile time. Here is a similar comment from a Hacker News thread:

As for the borrow checker, I actually did find it useful in bare metal. But more for handling hardware resources. Different measurements require different sets of power supplies to be activated, and exclusive control over different I/Os, etc. The ownership model made it easier to ensure statically that we sequence the measurements in a way such that the different measurement routines can never reconfigure resources that are in use by a different routine.

In effect, the borrow checker is proving to be a highly configurable theorem prover for software verification!

The ownership concept also aids in code optimization. Amit Patel describes how, thanks to knowing the owner of an array, Rust code for an array copy uses 50% fewer memory accesses than the equivalent C++ code.

For those die-hard C programmers convinced that nothing can beat it, I recommend reading Learning Rust the Dangerous Way. The author's methodology is fascinating. He took a benchmark C program from the Programming Language Shootout and translated it into Rust.

An important aspect of Rust is that code can be marked unsafe, indicating that the compiler's safety guarantees won't be enforced on that block of code. This transfers the safety burden from the compiler to the programmer. It acknowledges that there are situations where the programmer really knows better than the compiler. What is great about this is that by eliminating safety checks on the smallest possible block of code, the bulk of the program still retains safety guarantees, making it easier to reason about its correctness.

This author, then, takes the C source code for the n-body problem and transliterates it into an equivalent Rust program, the entirety of which is in an unsafe block. He then gradually refines each unsafe block into safe Rust code. At the end, the only unsafe code remaining is the calls to the CPU vectorization instructions. As of this writing, the fastest program in the shootout for this problem is Rust #7, by a different author but taking the same basic approach.

The significance of this achievement is to end the belief that unsafe code is generally necessary for high performance. For the most part, except for small, specialized routines, it is not, and most (if not all) of any given program can genuinely be checked at compiler time to be safe.

Although there are not necessarily a huge number of jobs available in Rust as of yet, I suspect this is about to change very quickly. Here's one example. A student of mine was recently hired at Google, and his group was ecstatic that he learned Rust in my operating systems course. While the group does not yet have Rust in production, they are looking for an opportunity.

As talented programmers begin to insist on using Rust for the sake of its safety guarantees, I predict that companies will respond to this pressure by starting more and more projects in Rust. I expect it to be a top-10 programming language by the end of this newly inaugurated decade. I highly encourage anyone interested in these possibilities to take the time to learn to program in Rust. I think this language is one of the most important technological advances in computing from the past decade, and now is the time to embrace progress moving forward!

Thoughts on the process of hiring faculty

Over the last several years, I have participated in five search committees seeking to hire tenure-track Assistant Professors. In this essay, I'd like to help potential job applicants gain some understanding of the dynamic of hiring. I also hope that others who are themselves seeking to hire might gain some insight from someone else who has been there.

Two of these searches were Computer Science searches, one was Spanish, one was Physics, and one was Mathematics. (All five searches were successful.) At Hendrix College, most search committees consist of the following people:

• All continuing full-time faculty from the department.
• One faculty member who is in the same area as the hiring department (Natural Science, Social Science, Humanities) but from a different department.
• One faculty member who is outside the area of the hiring department.
• Two undergraduate students.

Since our department houses both Computer Science and Mathematics programs, I participated as a department member in all three of those searches. (For the Computer Science searches, I was the committee chair.) I was in-the-area-but-outside-the-department on the Physics search, and outside-the-area on the Spanish search.

As a liberal arts college, our primary criterion is demonstrated potential for excellence in teaching. Criteria can vary significantly among departments, but potential for excellence in scholarship is also important. Perhaps just as important is the concept of "fit"; that is, the ideal candidate should somehow complement the other faculty in the hiring department, and by doing so strengthen the department as a whole. Furthermore, the ideal candidate should also be a good match for Hendrix College. At a school as small as Hendrix, it is important that any candidate should demonstrate the potential for productive relationships with faculty in different disciplines in addition to the home department.

So, how do I go about evaluating a candidate?

At the application stage, I start by reading the cover letter. I need to see evidence that the candidate has researched both Hendrix College and the target department.  Building upon that evidence, the cover letter should tell me a convincing story about how the candidate will succeed as a faculty member at Hendrix College. Failing this, it is possible that I will not read the rest of the application, especially if I have a lot of them to read. 

Next, I'll read the candidate's CV. Here, I am looking for the following:

• Evidence of teaching experience, especially courses previously taught.
• Research record. Here, I am trying to see how well the demonstrated research agenda will work at Hendrix.
• Any other interesting tidbits.

Then, I will carefully study the teaching statement, again looking for potential of excellence. I want to see evidence that the candidate has reflected on their experience in the classroom and improved their teaching based on that experience.

I read the research statement next. I try to find evidence that the research agenda has the potential to productively involve undergraduate students. I really like research statements that explicitly describe how undergraduate students could get involved.

For both the teaching and research statements, I am also assessing the quality of the candidate's writing. If either statement is poorly written, it implies serious problems down the line. First, the candidate will be unlikely to help students improve their own writing. Second, poor writing is usually symptomatic of incoherent thinking.

Finally, I read the letters of recommendation. I like to see specific examples demonstrating the candidate's potential for excellence in teaching. A description of a visit to a class is much more impressive than the typical "I saw the person give a research presentation, and it was so lucid and clear that I am sure this person will be an excellent teacher." In regards to research, I like to see examples that showcase the candidate's problem-solving abilities and creativity.

For candidates who we select for videoconference interviews, we typically allow 25-30 minutes. The specific questions we ask are a means to a goal, which is to use our brief time with the candidate to see if we can visualize that person as a productive colleague. I look for evidence of deep knowledge of the subject matter that we would like the person to teach. I also evaluate the candidate's ability to clearly and concisely explain concepts and ideas. I try to ask questions that bring about extemporaneous answers from the candidate.

I also want the candidate to have 3-4 questions ready for us. Those questions should provide evidence that the candidate has thought seriously about the specific position at Hendrix.

For the on-campus interview, I am looking for the same things, although in more depth. It is again an exercise in visualizing the candidate as a productive colleague. I would recommend that candidates not be too uptight about this; just be yourself! If the application your produced is consistent with what you are like in person, there is nothing to worry about.

The candidate's public presentation is extremely important (as Dr. McCulloch reminded me in his comment below). It is my opportunity to visualize the candidate in the classroom. It is also an extended introduction to the candidate's thought process and perspective. During the talk, I need to see that the candidate pitches their ideas in a manner that is both accessible to and appealing to students. I really want to see students get excited about the topic that they are presenting. Something that really helps with this is when the candidate is excited about the topic. Such excitement can be contagious.

The talk can make or break the interview. I have seen a lackluster interview with a phenomenal talk that resulted in an offer. I have seen a strong interview with a problematic talk that resulted in us crossing the candidate off the list. Related to this, the candidate should ensure significant depth of knowledge of the topic of the talk. The candidate need not know everything, and being clear about the limits of our knowledge is important in this profession. But at some point a faculty candidate is expected to have acquired expertise, and we should see evidence of this in the talk.

Decision time is often very difficult. At times, I must admit that there is not enough evidence that the candidate will be a productive colleague, at which point there is no need to consider that person further. But more often than not, by the time we bring a candidate on campus there is already very good evidence that this person would be an excellent colleague, and the campus visit often confirms this. (This also applies to the videoconference interviews.) From there, we have to weigh the strengths and weaknesses of the candidates against each other in order to make a decision.

There have been multiple occasions where my impulse is "hire them both!" But as this is usually not practical, a decision must be made. Candidates should not take a negative decision personally. Under other circumstances, and in comparison with other people, we might well have hired them.

Candidates should also realize that they are not going to get any feedback from us in the event of a negative decision. There is no benefit to us for providing feedback, and there are significant risks in doing so. The biggest risk is simply that the feedback might not be properly understood or contextualized by the candidate. Candidates not receiving an offer have to grasp that there was someone else available who was a better fit, and move on to considering their other options.

Every search, while stressful and time-consuming, is an experience I consistently enjoy. It is a great opportunity to meet some very interesting and capable people. I have sometimes had productive professional relationships with people I met during a search process who did not wind up hired as a result of it. I wish all candidates the best of luck in their searches!

An excellent guide to setting up OpenCV on Android

This post will be short and to the point.

I've been trying to get OpenCV going in Android Studio for quite some time. I finally found an article that clearly described how to get it done. Special thanks to Elvis Chidera for his great work on that tutorial!

Now it is time to start on the actually interesting work.

A subtle and interesting race condition

Race conditions are an important and common topic when discussing multithreaded programming. Every instructor benefits by including realistic examples when lecturing on this subject. The best source of realistic examples is, arguably, real examples from real code. In the spirit of recording such an example both for my benefit and for that of anyone reading this, let me describe for you a race condition I fixed today.

The program is an Android app that sends commands to an Arduino board to control a robot. When the user is ready to begin controlling the robot, it starts up a thread to handle the communication. The communication thread maintains a TreeSet data structure (trueFlags) that tracks which sensory conditions are true. On each iteration, it updates the user interface to display these conditions for the user.

In an Android app, to update the user interface from a separate thread requires specifying a block of code for the UI to run when it is ready. In our example, the code looks like this:

    private void updateGUI(final Action currentAction) {
        getActivity().runOnUiThread(new Runnable() {   
            @Override
            public void run() {
                allTrueFlags.setText(trueFlags.toString());

                StringBuilder values = new StringBuilder();
                for (int i : sensorValues) {
                    values.append(i + ", ");
                }
                bytesReceived.setText(values.toString());
                bytesSent.setText(currentAction.toString());
            }
        });
    }

It looks pretty harmless. After all, only the UI data structures are being modified, and only on a thread set aside for that purpose! But it caused our app to crash at seemingly random intervals as the robot wandered around a room.

The trouble was the call to trueFlags.toString(). This TreeSet is constantly being modified in the communication thread. On the rare occasions when these modifications were interrupted to run the UI thread, a ConcurrentModificationException was thrown when trying to construct a string from it. Often, the robot would run for minutes at a time before this occurred!

It was not difficult to fix this bug, but it took quite a lot of effort to find it! Hopefully, posting this example will help someone else out there identify a similar bug sometime.  Here is the fixed code that avoids the bug, by moving the string conversion back into the communication thread:

    private void updateGUI(final String trueFlagString, final Action currentAction) {
        getActivity().runOnUiThread(new Runnable() {
            @Override
            public void run() {
                allTrueFlags.setText(trueFlagString);

                StringBuilder values = new StringBuilder();
                for (int i : sensorValues) {
                    values.append(i + ", ");
                }
                bytesReceived.setText(values.toString());
                bytesSent.setText(currentAction.toString());
            }
        });
    }

Probability and Boolean Logic

To understand probability, it is helpful to understand boolean logic. In this post, I will review both and show the connections. This is a first draft of the explanation I have in mind. I welcome suggestions to improve the presentation of these ideas.

A probability is a real number between 0 and 1 inclusive. This number represents uncertain knowledge of an outcome. The sum of the probabilities of all possible outcomes of an event is 1.

A classic example is the event of flipping of a coin. There are two possible outcomes: heads and tails. Without performing any experiments, we would estimate the probability of heads as 0.5 and tails as 0.5.

Boolean logic relies on variables that have two possible values (true/false and 1/0 are the most popular; we'll rely on true/false for the rest of this post). These variables can be combined and manipulated using the and, or, and not operators. The not operator has one argument, and returns true if the argument is false and false if the argument is true. The and operator has two arguments, returning true if they are both true and false otherwise. The or operator has two arguments, returning false if they are both false and true otherwise.

We can extend boolean logic to reason about probabilities. We will give arithmetic definitions of the three boolean operators for use with probabilities:

• x and y -> x * y (multiplication)
• x or y -> x + y (addition)
• not x -> -x (negation)

So if we do two coin tosses, the probability of getting heads twice is:

• heads and heads
• 0.5 * 0.5
• 0.25

The same reasoning applies to getting tails twice, yielding the same probability (0.25). The probability of getting either heads twice or tails twice is:

• heads and heads or tails and tails
• 0.25 + 0.25
• 0.5

Let's extend this line of reasoning to another example: the rolling of a six-sided die. I'll use fractions to describe the probabilities in order to avoid gratuitous repeating decimals. The probability of any particular value showing up is ¹⁄₆. To calculate the probability of a member of a set of values showing up, we can add them up individually, as this is just an or operation. So the probability of a 1 or a 4 is ¹⁄₆   + ¹⁄₆   =  ²⁄₆.

This gets more interesting when we want to compute probabilities such as "anything except a 6". Since that is equivalent to not, we calculate ⁶⁄₆   - ¹⁄₆   =  ⁵⁄₆. An alternative is to sum the probabilities of those values, but using not makes the calculation much simpler.

In general, by using not we can greatly simplify our calculations. Consider calculating the probability of getting 16 or less when rolling three dice. If we view it as "not (17 or 18)", the calculation becomes:

• p(18) = p(6, 6, 6) = p(6) * p(6) * p(6) = ¹⁄₆   * ¹⁄₆  * ¹⁄₆  =  ¹⁄₂₁₆.
• p(17) = p(6, 5, 5) + p(5, 6, 5) + p(5, 5, 6) = ³⁄₂₁₆.
• p(16 or less) = not (p(17) or p(18)) = 1 - (¹⁄₂₁₆  + ³⁄₂₁₆) = 1 - (⁴⁄₂₁₆) = ²¹²⁄₂₁₆ = ⁵³⁄₅₄.

Two important caveats:

1. To represent and as multiplication, the events must be independent of each other. This applies, for example, to coin flipping, because nothing about the first flip has any causative effect on the outcome of the second flip. 
2. To represent or as addition, the events must be mutually exclusive. For example, a die roll cannot be both a 1 and a 4 at the same time.

So, to conclude for now, I personally find it helpful to leverage the convertibility between boolean logic and probability to simplify my calculations and save effort.