Algorithm for determining performance speedup/slowdown in a code change vs. historical data?

Question

I work on a large programming team, and I run a suite of performance tests on every change that is made in our program, which basically measure time it takes to run the test. For every code change, we run these tests, and we calculate whether the change caused the test to run slower by doing a two-sample t test (against the results from the previous code change). This works decently, but the problem is that we only have a small number of sample data points, generally 5 per test, per code change. There are about 400 individual measurements that we track performance on, so we see some noise in our results (i.e. the t-test will yield a small p value for tests which are not actually any faster/slower due to the code change).

Even though we have a small number of sample points on each code change, we have a very large history of results. I want to use this historical data to help us, but I'm not sure how I can. A problem I'm worried about is that any code change may cause the tests to run faster or slower, so just blindly aggregating historical data will yield a poor result. Are there any statistical tests that will help me with this?

For a little more info: Most of the time code changes do not have any impact on performance, and those of them that do cause performance tests to run faster or slower only do so on a handful of the 400 tests. Which means that for any given test, it could be hundreds of code changes before a change actually makes the test run faster or slower.

To clarify, I want to figure out when a code change actually causes a test to run faster or slower. What options do I have?

Answer 1

Here's something that's not really an answer to your question, but may be helpful for your problem:

One of the difficulties you mention is that you are doing ~400 t-tests, and so will end up with lots of spurious small p-values. One useful thing to use here is `false discovery rate' (FDR) analysis, which tries to determine what fraction of the small p-values are consistent with the null. If I were working on your problem, I'm pretty sure I'd use some FDR method.

FDR control is a big topic (http://en.wikipedia.org/wiki/False_discovery_rate) so I won't try to describe it fully, but here are some links to get you started if you're interested:

• The paper that introduced FDR control: http://umassmed.edu/uploadedFiles/QHS/Controlling%20the%20False%20Discovery%20Rate%20manuscript.pdf

• A recent survey book: http://www-stat.stanford.edu/~ckirby/brad/papers/2010LSIexcerpt.pdf

Answer 2

HEre is something that isn't exactly an answer to the original question, but might be valuable and might also act as an answer to the question behind the question which is something to the effect of: "how do I make the most of my programming to speed up my code?"

I bet you can modify a section, and re-run several times, much more quickly than you can re-write parts of it. If that is the case, then randomly inserting random-length pauses, and recording both section placed, length of pause inserted, and impact to overall runtime you could determine how a delay to one part of the code propagates to the rest of it.

Is knowing which parts have the biggest impacts to overall speed your goal? Is the 'stochastic' intervention a plausible approach to something like this?

Best of luck.

Answer 3

First you want to know if there has been a statistically significant change in total testing time. Second, if there has been a change, which tests have changed?

This is what I would do: Within each code state compute the mean for each time variable. Then for each time variable compute the standard deviation of its means. This measure of variability is how you incorporate information from the entire history of testing.

Next use $t$-tests to check for changes from the previous code state (the null hypothesis is that the mean times in the current state equal the previous state means).

The primary test is simply if there has been a change in overall time, so you're not examining a joint hypothesis and a simple $t$-test is sufficient. If there has been a change in total time, then I would compute $t$-statistics for the separate tests to see which tests are responsible for the change.

A rough example written in R:

# Hypothetical time data over 100 states:
state <- rep(1:100, each = 5)
t1 <- 1 + runif(500)
t2 <- 2 + runif(500)
t3 <- 3 + runif(500)
total_time <- t1 + t2 + t3
d <- data.frame(state, total_time, t1, t2, t3)

# Suppose current state is 100, then we want to compare it to state 99
# while taking into account information on variability based on all historical data.

# Means within historical code states:
d_means <- aggregate(d, by=list(d$state), mean)

# Standard deviation of means up to current state:
d_stdev <- sapply(d_means[d_means$state < 100, ], sd)

# Central limit theorem tells us means are approx. normally distributed.
# So we can use t-tests.

# Test if total testing time has changed in current state:
previous <- subset(d_means, state == 99)
current  <- subset(d_means, state == 100)
t_total_time <- (current$total_time - previous$total_time) / d_stdev[['total_time']]

# Now, for example, if abs(t_total_time) > 1.96, then time change is statistically
# significant at roughly 5% level.

# Check each test to see which ones have statistically significant change from
# previous state:
t_test_1 <- (current$t1 - previous$t1) / d_stdev[['t1']]
t_test_2 <- (current$t2 - previous$t2) / d_stdev[['t2']]
t_test_3 <- (current$t3 - previous$t3) / d_stdev[['t3']]

print(t_total_time)
print(t_test_1)
print(t_test_2)
print(t_test_3)