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 ] ( 3345 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 11039 )
Calendario
