optimization - pseudocodigo - lothar collatz

Conjetura de Collatz en Rust: enfoque imperativo v funcional

Question

Quería juguetear con algunas buenas conjeturas de Collatz y decidí que sería divertido hacerlo en un estilo (muy) funcional, así que implementé una función unfoldr , cercana a la que Haskell tiene :

fn unfoldr<F, T>(foo: F, seed: T, mut vec: Vec<T>) -> Vec<T>
    where F: Fn(T) -> Option<(T, T)>
{
    if let Some((x, y)) = foo(seed) {
        vec.push(x);
        unfoldr(foo, y, vec)
    } else {
        vec
    }
}

El resto fue bastante sencillo:

fn collatz_next(n: u64) -> u64 {
    if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}

pub fn collatz_seq_f(n: u64) -> Vec<u64> {
    unfoldr(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, Vec::new())
}

Con collatz_seq_f devolviendo un Vec tor con la secuencia que comienza con un número dado n .

Me preguntaba, sin embargo, si Rust aprueba este estilo, e implementó una simple contraparte imperativa:

pub fn collatz_seq_i(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
    let mut c = n;
    while c != 1 {
        vec.push(c);
        c = collatz_next(c);
    }
    vec
}

Y los comparó con el cargo bench (0.13.0-nightly (2ef3cde 2016-09-04)). Estaba un poco decepcionado de que mi enfoque de unfoldr divertido fuera solo la mitad de rápido que la implementación imperativa:

running 3 tests
test tests::it_works ... ignored
test tests::bench_collatz_functional ... bench:         900 ns/iter (+/- 47)
test tests::bench_collatz_imperative ... bench:         455 ns/iter (+/- 29)

test result: ok. 0 passed; 0 failed; 1 ignored; 2 measured

Sé que la versión unfoldr es más abstracta, pero no esperaba tanta diferencia; ¿Hay algo que pueda cambiar para hacerlo más rápido?

Código completo a continuación:

#![feature(test)]

extern crate test;

fn unfoldr<F, T>(foo: F, seed: T, mut vec: Vec<T>) -> Vec<T>
    where F: Fn(T) -> Option<(T, T)>
{
    if let Some((x, y)) = foo(seed) {
        vec.push(x);
        unfoldr(foo, y, vec)
    } else {
        vec
    }
}

fn collatz_next(n: u64) -> u64 {
    if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}

pub fn collatz_seq_f(n: u64) -> Vec<u64> {
    unfoldr(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, Vec::new())
}

pub fn collatz_seq_i(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
    let mut c = n;
    while c != 1 {
        vec.push(c);
        c = collatz_next(c);
    }
    vec
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[test]
    fn it_works() {
        assert_eq!(110, collatz_seq_f(27).len());
        assert_eq!(110, collatz_seq_i(27, Vec::new()).len());
    }

    #[bench]
    fn bench_collatz_functional(b: &mut Bencher) {
        b.iter(|| collatz_seq_f(27));
    }

    #[bench]
    fn bench_collatz_imperative(b: &mut Bencher) {
        b.iter(|| collatz_seq_i(27, Vec::new()));
    }
}

Answer 1

Esta no es una respuesta, sino una prueba adicional para reducir el origen del golpe de rendimiento. Desenrollé la Sobrecarga escribiendo la función recursiva

pub fn collatz_seq_r(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
    if n == 1 {
        vec
    } else {
        vec.push(n);
        collatz_seq_r(collatz_next(n), vec)
    } 
}

collatz_seq_f un rendimiento casi idéntico al del ejemplo collatz_seq_f . Parece que LLVM no está desenrollando esta llamada recursiva.

Alternativa

Después de pensar cómo haría esto en Rust, lo más probable es que haya implementado un iterador cuyo trabajo consiste en componer continuamente el valor anterior con una función, proporcionando una secuencia no final: n, f(n), f(f(n)), ..., f^k(n), ... Esto se puede hacer así:

struct Compose<T, F> {
    value: T,
    func: F
}

impl<T, F> Iterator for Compose<T, F> 
    where T: Copy,
          F: Fn(T) -> T {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        let res = self.value;                    // f^k(n)
        self.value = (self.func)(self.value);    // f^{k+1}(n)
        Some(res)
    }
}

impl<T, F> Compose<T, F> {
    fn new(seed: T, func: F) -> Compose<T, F> {
        Compose { 
            value: seed,
            func: func
        }
    }
}

Así que aquí puedo llamar a Compose::new(seed_value, function) para obtener un iterador de composición. Generar la secuencia a Collatz se convierte en:

pub fn collatz_seq_iter(n: u64) -> Vec<u64> {
    Compose::new(n, collatz_next)
             .take_while(|&n| n != 1)
             .collect::<Vec<_>>()
}

Con esto obtengo los puntos de referencia:

test tests::bench_collatz_functional ... bench:         867 ns/iter (+/- 28)
test tests::bench_collatz_imperative ... bench:         374 ns/iter (+/- 9)
test tests::bench_collatz_iterators  ... bench:         473 ns/iter (+/- 9)
test tests::bench_collatz_recursive  ... bench:         838 ns/iter (+/- 29)

Pero lo interesante aquí es que si decides que solo te importa el tamaño, la llamada: Compose::new(n, collatz_next).take_while(|&n| n != 1).count() as u64 casi exactamente el mismo rendimiento que eliminar la línea vec.push(c) en el enfoque imperativo:

test tests::bench_collatz_imperative ... bench:         162 ns/iter (+/- 6)
test tests::bench_collatz_iterators  ... bench:         163 ns/iter (+/- 4)

Answer 2

Esto va a contener algunos detalles de implementación de por qué unfoldr es un poco lento.

Propuse una variante diferente, y @breeden me ayudó a verificar que es una mejora que hace que coincida con la variante imperativa de rendimiento. Mantiene la recursión, pero ya no podemos llamarla funcional. [^ 1]

fn unfoldr2<F, T>(foo: F, seed: T, vec: &mut Vec<T>)
    where F: Fn(T) -> Option<(T, T)>
{
    if let Some((x, y)) = foo(seed) {
        vec.push(x);
        unfoldr2(foo, y, vec)
    }
}

fn collatz_next(n: u64) -> u64 {
    if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}

pub fn collatz_seq_f(n: u64) -> Vec<u64> {
    let mut v = Vec::new();
    unfoldr2(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, &mut v);
    v
}

La diferencia aquí ilustrará qué "salió mal" con la primera versión. En unfoldr , hay un valor vec que se transmite, y en unfoldr2 solo hay una referencia mutable a un vector en su lugar.

El valor vec tiene un efecto en unfoldr y descubriste que limitaba el compilador: desenrollar. Desenrollar es lo que sucede si una función entra en pánico. Si se desenrolla mediante la función unfoldr , todas las variables locales se deben descartar, y eso significa vec . Se inserta algún código especial para tratar con esto (llamado "plataforma de aterrizaje") y llamadas de función que pueden entrar en pánico al insertar una instrucción para desviarse a la plataforma de aterrizaje en pánico.

Entonces en unfoldr :

1. Hay una variable local que tiene un destructor, vec
2. Hay una llamada a la función que puede entrar en pánico (pánico de vec.push en el desbordamiento de la capacidad)
3. Hay una plataforma de aterrizaje que deja caer el vec y se reanuda

Además, hay un código para mover el valor de Vec. (Se copia a la pila para que esté disponible para el código del panel de aterrizaje).

unfoldr2 no obtiene ninguna optimización mágica de recursión en solo un bucle, pero todavía tiene menos código porque no tiene necesidad de manejar el desenrollado o mover el Vec.

[^ 1]: ¿Podemos salvar la funcionalidad imaginando el vec.push (x) como una interfaz para una secuencia / generador / salida del marcador, o simplemente como una devolución de llamada?