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 )