Estudio del uso de la sobrecarga de operadores para aritmética de punto fijo en C++ 
La aritmética de punto fijo es un mecanismo muy útil para la implementación de funciones matemáticas en procesadores sin unidad de coma flotante como microcontroladores y procesadores pequeños de 8 o 16 bits. A lo largo de este post se plantea el uso de la sobrecarga de operadores de C++ para facilitar las tareas de programación y mejorar la legibilidad del código cuando se usan tipos de punto fijo.

Introducción

La aritmética de punto fijo permite realizar operaciones con números fraccionarios mediante tipos enteros y operaciones enteras. En anteriores posts de este blog se ha hablado de forma extensa acerca de este tema, por lo que se remite a ellos a la persona interesada. A lo largo de este post usaré siempre valores de punto fijo Q16.16 (32 bits con 16 bits para la parte entera y 16 bits para la parte fraccionaria).

Implementación tradicional mediante macros

Tradicionalmente siempre he implementado la aritmética de punto fijo con un fichero de cabecera en el que defino "fixedpoint_t" como un "int32_t" y unas macros especiales para las operaciones de conversión de entero a punto fijo, de multiplicación y de división (las más "complejas"):

typedef int32_t fixedpoint_ct;

#define  FP_MUL(x, y)  ((int32_t) ((((int64_t) (x)) * ((int64_t) (y))) >> 16))
#define  FP_DIV(x, y)  ((int32_t) ((((int64_t) (x)) << 16) / ((int64_t) (y))))
#define  TO_FP(x)      (((int32_t ) (x)) << 16)

Como se puede apreciar, se trata de una implementación extremadamente sencilla y si lo que queremos es escribir una función que calcule:
$$\left({a \times b}\right) + \left({a \over b}\right)$$
Introduciríamos el siguiente código:

fixedpoint_ct fWithMacros(fixedpoint_ct a, fixedpoint_ct b) {
    return FP_MUL(a, b) + FP_DIV(a, b);
}

Y para los valores $a = 4$ y $b = 3$ la invocaríamos de la siguiente forma:

fixedpoint_ct v = fWithMacros(TO_FP(4), TO_FP(3));

Se trata de una implementación perfectamente válida aunque adolece de falta de claridad en el código: hay que leer con cuidado las operaciones aritméticas para no confundirse. Por otro lado es una implementación que tiene la ventaja de que en todo momento está claro que no estamos trabajando con un tipo "trivial".

Implementación basada en sobrecarga de operadores

Buscando un código más legible que el anterior, lo lógico es recurrir a la sobrecarga de operadores de C++. Definimos una clase "fixedpoint_t" en la que metemos un entero de 32 bits y definimos las cuatro operaciones básicas como "operator" dentro de la propia clase:

class fixedpoint_t {
    public:
        int32_t v;
        fixedpoint_t(int32_t x = 0) : v(x << 16) { };
        inline fixedpoint_t &operator = (const int32_t &x) { this->v = x << 16; return *this; };
        inline fixedpoint_t operator + (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = this->v + x.v; return ret; };
        inline fixedpoint_t operator - (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = this->v - x.v; return ret; };
        inline fixedpoint_t operator * (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = (((int64_t) this->v) * ((int64_t) x.v)) >> 16; return ret; };
        inline fixedpoint_t operator / (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = (((int64_t) this->v) << 16) / ((int64_t) x.v); return ret; };
};

Esta implementación nos permite ahora escribir la misma función de antes de una forma más legible:

fixedpoint_t fWithOperators(fixedpoint_t a, fixedpoint_t b) {
    return (a * b) + (a / b);
}

Y, de la misma manera, también nos permite invocarla de forma más legible:

fixedpoint_t v = fWithOperators(4, 3);

Sin embargo se podría pensar que una implementación así generaría mucho más código que la implementación basada en macros. Hagamos unas pruebas.

Comparativa

Si compilamos con gcc el código de ambas funciones sin opciones de optimización:

g++ -std=c++11 -o fp fp.cc

la diferencia es abismal:

_Z11fWithMacrosii:
    push   %rbp
    mov    %rsp,%rbp
    push   %rbx
    mov    %edi,-0xc(%rbp)
    mov    %esi,-0x10(%rbp)
    mov    -0xc(%rbp),%eax
    movslq %eax,%rdx
    mov    -0x10(%rbp),%eax
    cltq   
    imul   %rdx,%rax
    sar    $0x10,%rax
    mov    %eax,%ecx
    mov    -0xc(%rbp),%eax
    cltq   
    shl    $0x10,%rax
    mov    -0x10(%rbp),%edx
    movslq %edx,%rbx
    cqto   
    idiv   %rbx
    add    %ecx,%eax
    pop    %rbx
    pop    %rbp
    retq   

_Z14fWithOperators12fixedpoint_tS_:
    push   %rbp
    mov    %rsp,%rbp
    sub    $0x40,%rsp
    mov    %edi,-0x30(%rbp)
    mov    %esi,-0x40(%rbp)
    lea    -0x40(%rbp),%rdx
    lea    -0x30(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  4009cc <_ZN12fixedpoint_tdvERKS_>
    mov    %eax,-0x20(%rbp)
    lea    -0x40(%rbp),%rdx
    lea    -0x30(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  40098a <_ZN12fixedpoint_tmlERKS_>
    mov    %eax,-0x10(%rbp)
    lea    -0x20(%rbp),%rdx
    lea    -0x10(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  400952 <_ZN12fixedpoint_tplERKS_>
    leaveq 
    retq   

El compilador ha hecho caso omiso del "inline" de las funciones miembro de la clase "fixedpoint_t" y las ha implementado como funciones aparte en ensamblador. En este caso la implementación usando macros es más eficiente. Activemos ahora el primer nivel de optimización "-O1":

g++ -std=c++11 -O1 -o fp fp.cc

Voilà, ahora apenas notamos la diferencia en el código generado:

_Z11fWithMacrosii:
    movslq %edi,%rax
    movslq %esi,%rsi
    mov    %rax,%rcx
    imul   %rsi,%rcx
    sar    $0x10,%rcx
    shl    $0x10,%rax
    cqto   
    idiv   %rsi
    add    %ecx,%eax
    retq   

_Z14fWithOperators12fixedpoint_tS_:
    movslq %edi,%rdi
    movslq %esi,%rsi
    mov    %rdi,%rax
    shl    $0x10,%rax
    cqto   
    idiv   %rsi
    imul   %rdi,%rsi
    sar    $0x10,%rsi
    add    %esi,%eax
    retq   

La implementación utilizando la clase "fixedpoint_t" con los operadores sobrecargados genera un código igual de eficiente que la implementación basada en macros.

Como conclusión podemos sacar que no es necesario sacrificar legibilidad en aras de la velocidad de ejecución, siempre y cuando usemos correctamente los elementos del lenguaje y compilemos usando las opciones de optimización adecuadas.

El código fuente puede descargarse de la sección soft.

[ añadir comentario ] ( 3305 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente  |   ( 3 / 10982 )

<< <Anterior | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | Siguiente> >>