performance - tener - ¿Por qué mi código se ejecuta más lentamente cuando elimino las comprobaciones de límites?

longitud title seo

Question

Estoy escribiendo una biblioteca de álgebra lineal en Rust.

Tengo una función para obtener una referencia a una celda matricial en una fila y columna dadas. Esta función comienza con un par de aserciones de que la fila y la columna están dentro de los límites:

#[inline(always)]
pub fn get(&self, row: usize, col: usize) -> &T {
    assert!(col < self.num_cols.as_nat());
    assert!(row < self.num_rows.as_nat());
    unsafe {
        self.get_unchecked(row, col)
    }
}

En bucles ajustados, pensé que podría ser más rápido omitir la verificación de límites, así que proporciono un método get_unchecked :

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

Lo extraño es que, cuando uso estos métodos para implementar la multiplicación de matrices (a través de los iteradores de fila y columna), mis puntos de referencia muestran que en realidad es un 33% más rápido cuando verifico los límites. ¿Por qué está pasando esto?

He intentado esto en dos computadoras diferentes, una con Linux y la otra con OSX, y ambas muestran el efecto.

El código completo está en github . El archivo relevante es lib.rs Las funciones de interés son:

• get a la línea 68
• get_unchecked en la línea 81
• next en la línea 551
• mul en la línea 796
• matrix_mul (punto de referencia) en la línea 1038

Tenga en cuenta que estoy usando números de nivel de tipo para parametrizar mis matrices (con la opción de tamaños dinámicos también a través de tipos con etiquetas ficticias), por lo que el punto de referencia está multiplicando dos matrices de 100x100.

ACTUALIZAR:

He simplificado significativamente el código, eliminando cosas que no se usan directamente en el punto de referencia y eliminando parámetros genéricos. También escribí una implementación de multiplicación sin usar iteradores, y esa versión no causa el mismo efecto . Vea here para esta versión del código. La clonación de la sucursal de minimal-performance y el cargo bench funcionamiento evaluarán las dos implementaciones diferentes de la multiplicación (tenga en cuenta que las afirmaciones están comentadas para comenzar en esa sucursal).

También es de destacar que si cambio las funciones get* para devolver copias de los datos en lugar de referencias ( f64 lugar de &f64 ), el efecto desaparece (pero el código es ligeramente más lento en todos los aspectos).

Answer 1

No es una respuesta completa porque no he probado mis afirmaciones, pero esto podría explicarlo. De cualquier manera, la única manera de saber con certeza es generar el LLVM IR y la salida del ensamblador. Si necesita un manual para LLVM IR, puede encontrarlo aquí: http://llvm.org/docs/LangRef.html .

De todos modos, basta de eso. Digamos que tienes este código:

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

El compilador aquí cambia esto en una carga indirecta, que probablemente se optimizará en un ciclo cerrado. Es interesante observar que cada carga tiene la posibilidad de fallar: si sus datos no están disponibles, se activará un límite.

En el caso de la verificación de límites combinada con el ciclo cerrado, LLVM hace un pequeño truco. Debido a que la carga está en un bucle estrecho (una multiplicación de matriz) y porque el resultado de la verificación de límites depende de los límites del bucle, eliminará la verificación de límites del bucle y lo colocará alrededor del bucle. En otras palabras, el bucle seguirá siendo exactamente el mismo, pero con una verificación de límites extra.

En otras palabras, el código es exactamente el mismo, con algunas diferencias menores.

Entonces, ¿qué cambió? Dos cosas:

1. Si tenemos la verificación de límites adicionales, ya no hay posibilidad de una carga fuera de límites. Esto podría desencadenar una optimización que antes no era posible. Sin embargo, teniendo en cuenta cómo se suelen implementar estas comprobaciones, no creo que esto sea así.

2. Otra cosa a considerar es que la palabra "inseguro" puede desencadenar algún comportamiento, como una condición adicional, datos de pin o deshabilitar el GC, etc. No estoy seguro de este comportamiento exacto en Rust; La única forma de conocer estos detalles es mirar el LLVM IR.