Algoritmo para determinar el rendimiento de aceleración/desaceleración en un cambio de código versus los datos históricos?

Question

Yo trabajo en un gran equipo de programación, y puedo ejecutar un conjunto de pruebas de rendimiento en cada cambio que se realiza en nuestro programa, que básicamente medir el tiempo que se necesita para ejecutar la prueba. Para cada cambio en el código, podemos ejecutar estas pruebas, y hemos de calcular si el cambio provocado que la prueba se ejecute más lentamente haciendo un two-sample t test (en contra de los resultados de la anterior cambio de código). Esto funciona decentemente, pero el problema es que sólo tenemos un pequeño número de muestras de puntos de datos, generalmente un 5 por prueba, por cambio de código. Hay alrededor de 400 mediciones individuales que nos rendimiento de la pista, así que podemos ver un poco de ruido en nuestros resultados (es decir, la prueba de t rendirá un pequeño valor de p para las pruebas de las que no son en realidad más rápido o más lento debido a que el cambio de código).

A pesar de que tenemos un pequeño número de puntos de muestreo en cada cambio de código, tenemos una gran historia de resultados. Quiero utilizar estos datos históricos para ayudarnos, pero no estoy seguro de cómo me puede. Un problema que me preocupa es que cualquier cambio de código puede causar que las pruebas de correr más rápido o más lento, por lo que sólo ciegamente la agregación de los datos históricos producirá un resultado pobre. Existen pruebas estadísticas que me ayude con esto?

Por un poco más de info: la Mayoría del tiempo cambios en el código no tiene ningún impacto en el rendimiento, y aquellos de entre ellos que hacen que las pruebas de rendimiento para correr más rápido o más lento hacerlo únicamente en un puñado de los más de 400 pruebas. Lo que significa que para cualquier prueba, podría ser de cientos de cambios en el código antes de un cambio realmente hace que la prueba se ejecute más rápido o más lento.

Para aclarar, quiero averiguar cuando un cambio de código en realidad causa de que la prueba se ejecute más rápido o más lento. ¿Qué opciones tengo?

Answer 1

Aquí hay algo que no es realmente una respuesta a su pregunta, pero pueden ser útiles para tu problema:

Una de las dificultades que mencionar es que usted está haciendo ~400 pruebas t, y así va a terminar con un montón de falsos pequeño p-valores. Una cosa útil para su uso aquí es `false discovery rate' (FDR), el análisis, que trata de determinar qué fracción de la pequeña p-valores son consistentes con el valor null. Si yo estuviera trabajando en su problema, estoy bastante seguro de que haría uso de algunos FDR método.

FDR de control es un gran tema (http://en.wikipedia.org/wiki/False_discovery_rate) así que no voy a tratar de describir completamente, pero aquí hay algunos enlaces para empezar si usted está interesado:

• El papel que introdujo FDR de control: http://umassmed.edu/uploadedFiles/QHS/Controlling%20the%20False%20Discovery%20Rate%20manuscript.pdf

• Una encuesta reciente libro: http://www-stat.stanford.edu/~ckirby/brad/papers/2010LSIexcerpt.pdf

Answer 2

Aquí es algo que no es exactamente una respuesta a la pregunta original, pero podría ser valioso y también puede actuar como una respuesta a la pregunta detrás de la pregunta que es algo para el efecto de: "¿cómo puedo hacer que la mayor parte de mi programación para acelerar la velocidad de mi código?"

Apuesto a que usted puede modificar una sección, y volver a ejecutar varias veces, mucho más rápido de lo que usted puede re-escribir las partes de la misma. Si ese es el caso, entonces la inserción aleatoria al azar de la longitud de la pausa, y la grabación de ambos sección, la longitud de la pausa inserta, y el impacto global en tiempo de ejecución se podría determinar cómo un retraso de una parte del código se propaga al resto de la misma.

Es saber cuál de las partes tiene el mayor impacto para la velocidad general de tu objetivo? Es el 'estocástica de la intervención de un posible enfoque a algo como esto?

La mejor de las suertes.

Answer 3

Primero quieres saber si ha habido un cambio estadísticamente significativo en el total de tiempo de prueba. En segundo lugar, si ha habido un cambio, que las pruebas han cambiado?

Esto es lo que yo haría: Dentro de cada código de estado calcular la media para cada variable de tiempo. A continuación, para cada variable de tiempo de calcular la desviación estándar de sus medios. Esta medida de variabilidad es la forma de incorporar la información de toda la historia de la prueba.

El próximo uso $t$-pruebas para comprobar los cambios desde el anterior código de estado (la hipótesis nula es que la media de veces que en el estado actual de la igualdad el estado anterior significa).

La prueba principal es simplemente si ha habido un cambio en el total de tiempo, así que no eres el examen de un conjunto de hipótesis y de un simple $t$-prueba es suficiente. Si ha habido un cambio total en el tiempo, entonces yo le compute $t$-estadísticas de las pruebas por separado para ver que pruebas son responsables por el cambio.

Un áspero ejemplo escrito en 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)