Programación concurrente (V)

 Artículos de la serie:

1. Introducción básica: clase std::thread y función std::async
2. Paralelización de algoritmos
3. Comprendiendo std::async en más detalle
4. ¿Cómo funciona std::packaged_task?
5. Mecanismo de exclusión mutua (mutex)
6. std::jthread: hilo cooperativamente interrumpible
7. Queue sincronizado
8. Ejercicio resuelto de paralelización

---

Mecanismo de exclusión mutua (mutex)

Consideremos un recurso mutable compartido por dos hilos de ejecución diferentes (por supuesto, su número pudiera ser mayor). Si ambos hilos sólo realizan acciones de lectura sobre el recurso, no corremos riesgo alguno de corromperlo. Sin embargo, si al menos uno de los hilos ejecuta acciones de escritura, modificando el recurso, es obvio que deberemos establecer un orden de acceso entre los hilos, de forma que mientras que uno de ellos esté operando con el recurso, el resto de hilos que intenten acceder a él queden momentáneamente bloqueados. Hablamos aquí, pues, de un mecanismo de exclusión mutua entre hilos.

Programación concurrente (IV)

 Artículos de la serie:

1. Introducción básica: clase std::thread y función std::async
2. Paralelización de algoritmos
3. Comprendiendo std::async en más detalle
4. ¿Cómo funciona std::packaged_task?
5. Mecanismo de exclusión mutua (mutex)
6. std::jthread: hilo cooperativamente interrumpible
7. Queue sincronizado
8. Ejercicio resuelto de paralelización

---

¿Cómo funciona std::packaged_task?

En este artículo centraremos nuestra atención en el modo en que se encuentra implementada la plantilla de clase std::packaged_task<> [1], la cual, como analizamos en el post anterior de la serie, constituye un envoltorio para cualquier objeto invocable (funciones, expresiones lambda, etcétera) que deseemos ejecutar asíncronamente. La función miembro pública get_future() de std::packaged_task<> proporciona un objeto std::future<> como método de acceso al estado compartido almacenado en su interior.

Programación concurrente (III)

 Artículos de la serie:

1. Introducción básica: clase std::thread y función std::async
2. Paralelización de algoritmos
3. Comprendiendo std::async en más detalle
4. ¿Cómo funciona std::packaged_task?
5. Mecanismo de exclusión mutua (mutex)
6. std::jthread: hilo cooperativamente interrumpible
7. Queue sincronizado
8. Ejercicio resuelto de paralelización

---

Comprendiendo std::async en más detalle

En post anteriores empezamos a acostumbrarnos al uso de objetos std::future<> en el marco de la programación concurrente. Éstos proporcionan un mecanismo de acceso a los resultados producidos por operaciones asíncronas. Su función miembro pública get(), en particular, aguarda a que el objeto std::future contenga un resultado válido (valor o excepción) para retornarlo al agente invocador.

Ignoremos por el momento la existencia de la función estándar std::async con política de lanzamiento std::launch::async --muy ligada al uso de std::future y de enorme facilidad de uso-- y planteémonos la tarea (nada trivial) de replicar su comportamiento, es decir: ejecutar una operación de forma asíncrona en un nuevo hilo independiente y remitir el valor o excepción producida durante su ejecución al hilo padre. El objetivo no es otro, por supuesto, que el de aprender más acerca de la propia implementación de std::async.

Programación concurrente (II)

 Artículos de la serie:

1. Introducción básica: clase std::thread y función std::async
2. Paralelización de algoritmos
3. Comprendiendo std::async en más detalle
4. ¿Cómo funciona std::packaged_task?
5. Mecanismo de exclusión mutua (mutex)
6. std::jthread: hilo cooperativamente interrumpible
7. Queue sincronizado
8. Ejercicio resuelto de paralelización

---

Paralelización de algoritmos

Basándonos en la explicación proporcionada en el primer post de esta serie, es claro que la función std::async nos permitirá paralelizar de forma directa algoritmos tales como for_each, accumulate o quick_sort.

Un aspecto fundamental a tener en cuenta a la hora de paralelizar algoritmos es el de evitar la incidencia de data races, es decir, el acceso simultáneo a la misma localización en memoria por parte de diferentes hilos, siendo al menos uno de dichos accesos de escritura. No es éste un problema con el que debamos lidiar en este post, por lo que pospondremos su análisis por el momento (véase el artículo 5 de esta serie para más detalles).

Programación concurrente (I)

 Artículos de la serie:

1. Introducción básica: clase std::thread y función std::async
2. Paralelización de algoritmos
3. Comprendiendo std::async en más detalle
4. ¿Cómo funciona std::packaged_task?
5. Mecanismo de exclusión mutua (mutex)
6. std::jthread: hilo cooperativamente interrumpible
7. Queue sincronizado
8. Ejercicio resuelto de paralelización

---

Última actualización de la serie: 14 de agosto de 2021

Introducción básica: clase std::thread y función std::async

El estándar ISO C++ 2011 introdujo la clase std::thread [1] en la biblioteca <thread> con el fin de permitir la creación de nuevos hilos de ejecución, de forma que los distintos hilos de un proceso puedan llevarse a efecto de forma concurrente. En particular, dicha clase proporciona un constructor variádico de signatura

   template<typename Func, typename ...Args>    explicit thread(Func&& f, Args&&... args);

El abecé de la plantilla vector<>

Última actualización del post: Octubre de 2020

Introducción

Como sabemos, la estructura estándar std::vector<> se considera el contenedor dinámico por defecto en el lenguaje C++. Ésta representa un array alojado en el free store, cuyo tamaño puede aumentar o disminuir a conveniencia durante el tiempo de ejecución de un programa. El hecho fundamental de que todos los elementos almacenados en el vector ocupen entradas contiguas en memoria virtual convierte a esta estructura en especialmente eficiente dado el modo de funcionamiento de los distintos niveles de memoria caché de nuestra computadora (véase este post anterior en relación a la localidad espacial y temporal de un programa), en contraste con el comportamiento típico de, por ejemplo, una lista (ver la figura inferior).

En este artículo discutiremos brevemente el funcionamiento del método principal de esta estructura, de signatura void vector<T>::push_back(T const& val), el cual introduce una copia de su argumento val al fondo del vector. Simplificaremos enormemente nuestra presentación omitiendo detalles finos de la implementación del contenedor, que incluirían el uso de técnicas avanzadas de alojamiento en memoria o la posibilidad de utilizar la semántica de movimiento como método para evitar copias innecesarias de objetos. Nuestra implementación resultará, por tanto, poco eficiente y de utilidad ciertamente limitada, pero de claro valor pedagógico.

Guía rápida de creación de listas (III)

Artículos de la serie:

• Parte I
• Parte II
• Parte III

---

Pilas y colas

Una vez finalizada la plantilla de clase List<>, resulta inmediato implementar nuevas plantillas que proporcionen la funcionalidad de una pila o una cola.

Recordemos que una pila (stack en Inglés) es una estructura de datos que responde al esquema LIFO (Last-In, First-Out; último en entrar, primero en salir). La lista de funciones miembro que modifican dicha estructura se reduce, pues, a:

• top(): acceder al elemento en la cima de la pila.
• push(): insertar un elemento en la cima.
• pop(): eliminar el elemento en la cima.

A las que podemos añadir funciones adicionales tales como empty() o size() con el fin de averiguar si la pila está vacía o determinar el tamaño de la misma, respectivamente.

Esta nueva clase puede implementarse como un simple adaptador que almacene una lista como dato privado y dé acceso únicamente a un extremo de la misma (de acuerdo con el esquema explicado anteriormente) a través de su interfaz pública. En otras palabras, restringiremos la interfaz pública de la lista (mucho más amplia e inicialmente incompatible con la de la pila) para adaptarla a la deseada mediante un encapsulamiento apropiado. Así, resulta:

GCC en sistemas MS Windows

MinGW-w64 (mingw-w64.org) es una implementación para entornos MS Windows de la familia de compiladores GCC (GNU Compiler Collection), de uso muy extendido en los sistemas Unix, Linux y BSD. MinGW-w64 incluye un subconjunto de la API de Windows, lo que permite el desarrollo de aplicaciones nativas para dicha plataforma, tanto de 64 bits (x86-64) como de 32 bits (x86).

Una de las funcionalidades más destacadas de esta solución integrada es, sin duda, Winpthreads, una biblioteca POSIX Thread que da soporte a la programación concurrente de acuerdo a las especificaciones del estándar C++11. Puede encontrarse un instalador que permite seleccionar la versión del compilador con la que trabajar (desde 4.8.1 hasta 5.3.0) en la distribución de nombre MinGW-Builds (sourceforge.net/projects/mingw-w64).

Otra distribución a señalar es la proveída en el portal Nuwen.net (nuwen.net/mingw.html). Si bien no cuenta con soporte para programación concurrente estándar mediante Winpthreads, al utilizar Win32 como modelo de threading, sí contiene la versión más actual del compilador, G++ 6.1.0 (cuyas características fueron analizadas en un post anterior), así como la versión 1.61.0 de las bibliotecas Boost (boost.org).

Guía rápida de creación de listas (II)

Artículos de la serie:

• Parte I
• Parte II
• Parte III

---

Una vez definidos los algoritmos de inserción, eliminación e intercambio de nodos en la lista mediante la estructura detail::Node_base (véase el primer post de esta serie), procederemos a implementar la lista doblemente enlazada como una plantilla uniparamétrica de clase List<>, donde el parámetro indique el tipo de variable almacenada.

Los elementos almacenados en la lista (nodos) constarán de tres campos, a saber: los punteros prev y next a los nodos inmediatamente anterior y posterior, respectivamente, así como el área de datos. Emplearemos la herencia como mecanismo básico para añadir la información contenida en la estructura detail::Node_base (es decir, los punteros de posicionamiento) a una nueva estructura privada List<>::Node que contenga, esta vez sí, el área de datos:

   template<typename T>    class List {       struct Node : detail::Node_base { // herencia pública          T dat; // dato almacenado          Node(T const& d) : dat{d} { };       };       detail::Node_base dnb_; // nodo centinela    public:       struct List_iterator; // ver definición más abajo       struct List_const_iterator;       // resto de la interfaz pública...    };

Observemos que una lista contiene un subobjeto detail::Node_base, de nombre dnb_, que actuará como nodo centinela. Éste no almacenará, por supuesto, ningún dato: tan sólo proporcionará un indicador natural para finalizar las iteraciones a lo largo de la estructura. Asimismo, y con el fin de facilitar la implementación de los métodos de la clase, enlazaremos la lista circularmente a través de dicho nodo centinela, tal y como se muestra en la figura inferior. De esta manera, será posible acceder al inicio o al fondo de la lista partiendo del nodo centinela con una sola operación de avance o retroceso, respectivamente (dnb_.next en el primer caso y  dnb_.prev en el segundo).

Guía rápida de creación de listas (I)

Última actualización de la serie: Noviembre de 2019.

Artículos de la serie:

• Parte I
• Parte II
• Parte III

---

En este post analizaremos los aspectos básicos del diseño de una lista lineal doblemente enlazada, inspirándonos en las implementaciones de estructuras dinámicas de datos estándar de este tipo facilitadas por compiladores profesionales, muy especialmente GCC [1]. Como es habitual, nuestra motivación aquí es puramente educativa, de manera que algunas de las elecciones en la implementación de la lista serán ciertamente discutibles y mejorables, pero no restarán valor pedagógico al conjunto.

En contraste con un vector, donde los objetos ocupan posiciones adyacentes, los elementos contenidos en una lista (a los que nos referiremos desde ahora bajo el nombre de nodos) se encuentran generalmente desperdigados en memoria (ver la imagen superior), siendo necesario que cada uno de ellos almacene la posición del elemento inmediatamente posterior (resultando una lista simplemente enlazada) así como, opcionalmente, del elemento inmediatamente anterior (lista doblemente enlazada). Centraremos nuestra atención en este segundo caso (doble enlace), al ser el más general.

Acerca del puntero implícito this

Puntero this

Última actualización del post: Diciembre de 2019

En C++, todo proceso llevado a cabo por una función miembro no-estática de una clase se realiza implícitamente sobre el objeto *this, siendo this el nombre del puntero que almacena la dirección en memoria del objeto que invocó a dicha función.

El tipo del puntero this será cv X*, siendo X el nombre de la clase a la que pertenezca la función miembro y cv los calificadores const-volatile que dicha función pudiese tener. Observemos, a este respecto, que los constructores y destructores no pueden acompañarse de dichos calificadores, por lo que el puntero this siempre será de tipo X* en su interior.

El puntero this puede ser empleado en el cuerpo de cualquier función miembro no-estática, en la lista de inicialización de un constructor y en los inicializadores por defecto de datos miembro. La indirección this-> es añadida implícitamente al comienzo del nombre de cualquier miembro no estático de la clase. Consideremos, por ejemplo, la siguiente función miembro de nombre reset_id() perteneciente a la interfaz pública de la clase Student:

   class Student {       int id_;       std::string name_;    public:       // constructores y resto de interfaz pública...       void reset_id(int id) { id_ = id; }    };

Podríamos referirnos explícitamente al objeto que invoque dicha función, si así lo deseáramos, a través del puntero this que lo referencia:

   void Student::reset_id(int id) { this->id_ = id; }

GCC 6.1

El equipo encargado del desarrollo de la familia de compiladores GCC acaba de anunciar el lanzamiento inminente de su versión 6.1. En relación a C++, el compilador dará soporte experimental a varias de las especificaciones técnicas (Technical Specifications o simplemente TS) publicadas en los últimos tiempos por el comité de estandarización ISO/IEC 14882 en su afán por mejorar y extender el lenguaje. Concretamente:

• Concepts TS: Una extensión del sistema de plantillas de clase y de función (templates) que permite la incorporación de restricciones sobre los tipos con los que operan, mejorando sustancialmente la legibilidad de los mensajes de error emitidos por el compilador en caso de no cumplirse dichas ligaduras.
• File System TS: Biblioteca basada en Boost.Filesystem que permite la gestión avanzada de sistemas de archivos y sus componentes (ficheros, árboles de dirección, etcétera).
• Library Fundamentals TS: Contiene mejoras en el funcionamiento de clases como std::functional o std::promise, nuevas herramientas como std::any, std::optional o std::basic_string_view, soporte para matrices en std::shared_ptr, etcétera.
• Transactional Memory TS: Un nuevo modelo de programación concurrente que sincroniza el acceso a datos compartidos por múltiples hilos de ejecución a través de transacciones ejecutadas atómicamente.

Puede encontrarse más información acerca de las nuevas características del compilador en la dirección gcc.gnu.org/gcc-6/changes.html. Para una descripción más detallada de los nuevos TS, consúltese en.cppreference.com/w/cpp/experimental.

Inferencia automática de tipos (auto)

Última actualización: 15 de agosto de 2020.

Artículos de la serie:

• Categorías de valor. Referencias lvalue y rvalue
• Inferencia automática de tipos (auto)
• Always auto: Una sintaxis moderna para C++
• Referencias de reenvío y auto&&

Introducción

La inferencia automática de tipos mediante la palabra clave auto --técnica introducida por vez primera en el estándar ISO C++ 2011 y refinada en estándares posteriores [1]-- permite la declaración de variables de forma tal que sus tipos sean deducidos automáticamente a partir de los tipos de sus inicializadores, siguiendo las reglas clásicas de deducción de argumentos en plantillas de función (template-argument-deduction o TAD) [2]. A partir de C++14, la inferencia automática puede ser también empleada en la signatura de una función para requerir que el tipo retornado sea deducido a partir de sus instrucciones de retorno.

Esta potente herramienta de programación fue diseñada por Bjarne Stroustrup a principios de los años 1980, pero tuvo que aguardar hasta su inclusión definitiva en C++11 por motivos de compatibilidad con el lenguaje C.

Por ejemplo, en sustitución de

   std::unique_ptr<int> p = std::make_unique<int>(1);

podemos escribir, sin riesgo de introducir ambigüedad en el código:

   auto p = std::make_unique<int>(1);

de forma que el compilador infiera de forma automática el tipo del puntero inteligente p a partir del tipo retornado por la función std::make_unique<int>, en este caso std::unique_ptr<int>.

Paso de parámetros a funciones. ¿Copiar o referenciar?

Última actualización: Diciembre de 2019

Supongamos que deseamos comunicar a una función la dirección en memoria de una variable con el fin de modificar su valor. Si descartamos la posibilidad de que el objeto pueda ser inválido (y, con ello, el uso de un puntero tradicional y la subsiguiente comprobación de puntero nulo), declararíamos el parámetro de la función como una referencia lvalue al tipo de variable que se desea modificar. A modo de ejemplo, en el siguiente código creamos un objeto obj de tipo Object, el cual es pasado como argumento a una función do_something() con el fin de realizar ciertas modificaciones sobre el mismo:

   class Object;    // ...    void do_something(Object& ob) { /* la función modifica el objeto referenciado */ }    // ...    auto obj = Object{};    do_something(obj); // llamada a función do_something() para modificar el objeto obj