Rasgos de tipo:el rendimiento importa

Rasgos de tipo:el rendimiento importa

Si observa detenidamente, verá que los rasgos de tipo tienen un gran potencial de optimización. Los rasgos de tipo admiten en el primer paso para analizar el código en tiempo de compilación y en el segundo paso, para optimizar el código en función de ese análisis. ¿Cómo es eso posible? Dependiendo del tipo de variable, se elegirá una variante más rápida de un algoritmo.

Trabajar en toda el área de memoria

La idea es bastante sencilla y se utiliza en las implementaciones actuales de la Biblioteca de plantillas estándar (STL). Si los elementos de un contenedor son lo suficientemente simples, el algoritmo de STL como std::copy, std::fill o std::equal se aplicará directamente al área de memoria. En lugar de usar std::copy para copiar los elementos uno por uno, todo se hace en un gran paso. Internamente, se utilizan funciones de C como memcmp, memset, memcpy o memmove. La pequeña diferencia entre memcpy y memmove es que memmove puede manejar áreas de memoria superpuestas.

Las implementaciones del algoritmo std::copy, std::fill o std::equal utilizan una estrategia simple. std::copy es como un envoltorio. Este contenedor verifica si el elemento es lo suficientemente simple. Si es así, el contenedor delegará el trabajo a la función de copia optimizada. De lo contrario, se utilizará el algoritmo de copia general. Este copia cada elemento después del otro. Para tomar la decisión correcta, si los elementos son lo suficientemente simples, se utilizarán las funciones de la biblioteca type-traits.

El gráfico muestra esta estrategia una vez más:

Esa era la teoría, pero aquí está la práctica. ¿Qué estrategia utiliza std::fill?

std::fill

std::fill asigna un valor a cada elemento del rango. La lista muestra una implementación simple.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// fill.cpp
 
#include <cstring>
#include <chrono>
#include <iostream>
#include <type_traits>

namespace my{

 template <typename I, typename T, bool b>
 void fill_impl(I first, I last, const T& val, const std::integral_constant<bool, b>&){
 while(first != last){
 *first = val;
 ++first;
 }
 }

 template <typename T>
 void fill_impl(T* first, T* last, const T& val, const std::true_type&){
 std::memset(first, val, last-first);
 }

 template <class I, class T>
 inline void fill(I first, I last, const T& val){
 // typedef std::integral_constant<bool,std::has_trivial_copy_assign<T>::value && (sizeof(T) == 1)> boolType;
 typedef std::integral_constant<bool,std::is_trivially_copy_assignable<T>::value && (sizeof(T) == 1)> boolType;
 fill_impl(first, last, val, boolType());
 }
}

const int arraySize = 100000000;
char charArray1[arraySize]= {0,};
char charArray2[arraySize]= {0,};

int main(){

 std::cout << std::endl;

 auto begin= std::chrono::system_clock::now();
 my::fill(charArray1, charArray1 + arraySize,1);
 auto last= std::chrono::system_clock::now() - begin;
 std::cout << "charArray1: " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;

 begin= std::chrono::system_clock::now();
 my::fill(charArray2, charArray2 + arraySize, static_cast<char>(1));
 last= std::chrono::system_clock::now() - begin;
 std::cout << "charArray2: " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;

 std::cout << std::endl;

}

my::fill toma en la línea 27 la decisión de qué implementación de my::fill_impl se aplica. Para usar la variante optimizada, los elementos deben tener un operador de asignación de copia generado por el compilador std::is_trivially_copy_assignable y deben tener 1 byte de tamaño:sizeof(T) ==1. La función std::is_trivially_copy_assignable es parte del tipo -rasgos. Explico en la publicación Comprobar tipos la magia detrás de las funciones de rasgos de tipo.

Mi GCC 4.8 llama en lugar de la función std::is_trivially_copy_assignable std::has_trivial_copy_assign. Si solicita con la palabra clave predeterminada del compilador el operador de asignación de copia, el operador será trivial.

struct TrivCopyAssign{
 TrivCopyAssign& operator=(const TrivCopyAssign& other)= default;
};

Volvamos al ejemplo del código. Si la expresión boolType() en la línea 27 es verdadera, se usará la versión optimizada de my::fill_impl en las líneas 18 - 21. Esta variante llena en oposición a la variante genérica my::fill_impl (línea 10 -16) el área de memoria completa, que consta de 100 millones de entradas, con el valor 1. sizeof(char) es 1.

¿Qué pasa con el rendimiento del programa? Compilé el programa sin optimización. La ejecución de la variante optimizada es unas 3 veces más rápida en Windows; unas 20 veces más rápido en Linux.

Microsoft Visual 15

CCG 4.8

La decisión de qué variante de un algoritmo debe usarse a veces no es tan fácil.

std::igual

El implementador de std::equal tenía un humor especial porque llamó a su criterio de decisión __simple. El código se copia de la implementación de GCC 4.8 STL.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
template<typename _II1, typename _II2>
inline bool __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2){
 typedef typename iterator_traits<_II1>::value_type _ValueType1;
 typedef typename iterator_traits<_II2>::value_type _ValueType2;
 const bool __simple = ((__is_integer<_ValueType1>::__value
 || __is_pointer<_ValueType1>::__value )
 && __is_pointer<_II1>::__value
 && __is_pointer<_II2>::__value
 &&__are_same<_ValueType1, _ValueType2>::__value
 );
 return std::__equal<__simple>::equal(__first1, __last1, __first2);
}

Tengo una percepción diferente de __simple. Para usar la variante optimizada de std::equal, los elementos del contenedor deben cumplir con algunas garantías. Los elementos del contenedor tienen que ser del mismo tipo (línea 9) y tienen que ser una integral o un puntero (líneas 5 y 6). Además, los iteradores tienen que ser punteros (líneas 7 y 8).

¿Qué sigue?

No lo lograron en el estándar C++98. Pero los tenemos en C++11:tablas hash. El nombre oficial es un contenedor asociativo desordenado. Extraoficialmente, a menudo se les llama diccionarios. Prometen una característica de importación:rendimiento. Porque su tiempo de acceso es constante en el caso óptimo.

¿Por qué necesitamos el contenedor asociativo desordenado? ¿Qué los diferencia de los contenedores asociados ordenados de C++98 (std::map, std::set, std::multimap y std::multiset)? Esa es la historia del próximo post.