[dmorill]

Hola me ha pasado algo muy extraño y he agotado varios días haciendo pruebas, preguntándole a amigos y a profesores, pero no he tenido éxito en resolver este problema.

Tengo un programa en c++ que ejecuta un algoritmo genético y resuelve un total de 480 problemas con dicho algoritmo, y saca un promedio del resultado de cada uno de ellos. Para esbozar un poco que es un algoritmo genético es un algoritmo que busca una solución para un problema para eso crea una población con muchas soluciones, luego mediante algunos mecanismos mezclan dichas soluciones para crear nuevas.

1. Crear población inicial de tamaño (= size), y se establece que estamos en la primera generación: (genera = 1).
2. mientras (genera < generaMax) se crean nuevas poblaciones a partir de de la anterior y se siguen creando hasta que se cumpla el criterio de parada.
3. Reportar la mejor solución.

Donde esta el problema? fácil para crear la población inicial y las poblaciones futuras se usan números aleatorios (con la librería #random) y para hacerlo más rápido uso Threads, con los respectivos #mutex para evitar problemas, pero cuando lo ejecuto con 7 threads me de un resultado y si lo ejecuto con 8 threads me da otro valor!!!!!!!!!

Me debería dar valores parecidos (no exactos pues uso valores aleatorios) pero me dí cuenta que cambia el valor cuando le cambio en número de threads y no tengo idea de porqué. Si lo ejecuto varias veces con el mismo número me da resultados muy similares, como se espera.

Como dato adicional el único momento donde el número de threads cambia algo en la programación de c++ es en los límites de para crear las poblaciones por ejemplo, si la población es de 100 individuos, y tengo dos threads pues los límites serán 50 cada uno, si fueran 8 threads el limite será casí 18 cada uno.

Espero que no les sea tan amargo de leer todo esto y que me puedan ayudar jeje.

saludos

[razpeitia]

Explicado porque:
http://www.forosdelweb.com/f96/uso-threads-c-1122642/

[dmorill]

Cita:

Iniciado por razpeitia

Explicado porque:
http://www.forosdelweb.com/f96/uso-threads-c-1122642/

Hola razpeitia, muchas gracias por tu respuesta, dime si te he entendido bien, tu dices que es un problema concurrencia, pues los aleatorios darán iguales cada vez que se llame la función de crear un aleatorio. O bien te refieres a que los thread puede escribir sobre una variable sumultaneamente y pueden generar problemas (para lo cual uso el mutex).

Te pongo un ejemplo de como uso los threads para que me expliques si eses es el problema (en el siguiente es un ejemplo de como lo utilizo en el algoritmo grande, que no lo pongo porque es super grande jeje y por tanto en este ejemplo no tengo problemas pero indica la manera de cómo los usos).

Código C++:

Ver original
#include <iostream>
#include <vector>
#include <mutex>
#include <random>
#include <thread>
 
 
using namespace std;
 
mutex barrera;
random_device rd;
mt19937 generator(rd());
uniform_real_distribution<double> distUni(0.0, 1.0);
 
void fun(double& suma);
 
int main(){
    int i; double suma = 0;
    vector<thread> v;
    for (i = 0; i < 8; i++){
        v.push_back(thread(fun, ref(suma)));
    }
    vector<thread>::iterator it;
    for (it = v.begin(); it != v.end(); it++){
        it->join();
    }
 
    cout << "suma: " << suma << endl;
 
    cin.get();
    return 0;
}
 
void fun(double& suma){
    double x;
    x = distUni(generator);
    barrera.lock();
    cout << x << endl;
    suma += x;
    barrera.unlock();
}
 

Agradezco mucho tu ayuda :D. saludos

[razpeitia]

No solamente cuando estés generando números aleatorios tienes que tener cuidado que sean thread safe si no también al alterar las listas.

En el ejemplo que pones, siempre que lo corro sin locks (mutex) o no me da el mismo resultado en la suma, en la impresión sin los locks si hace un mugrero.

En este caso si vas a ver resultados diferentes porque estas ligando directamente numero de threads == numero de elementos.

Hola; acomodé un poco el código caprichosamente más a mi gusto.

También quité el lock sobre cout que obligaba a una secuencia sincrónica, que si está sólo como una forma de debugear no está de más, pero no hay que olvidarse de sacarlo. En su lugar guardo los x en un vector que se muestra cuando todos los threads terminaron su trabajo.

Ah, agregué una seed al generator para obtener valores suma diferentes, que puede comentarse si no hace falta.

Creo que así está algo más eficiente, aunque me parece que en una discusión anterior había quedado la conclusión de que C++ y eficiencia no van de la mano. De todos modos yo insisto porque me divierte. Si te apetece, podrías comparar ambas versiones y contarnos si se ha ganado algo o no.

Código C++:

Ver original
#include <iostream>
#include <vector>
#include <random>
#include <future>
 
 
using namespace std;
 
int main()
{
    random_device rd;
    mt19937 generator(rd());
    generator.seed(time(nullptr));
    uniform_real_distribution<> distUni(0.0, 1.0);
 
    const unsigned int N_THREADS = 7;
    vector<double> out(N_THREADS);
 
    double suma = 0.0;
 
    vector<future<void>> f;
 
    for (auto i = 0u; i < N_THREADS; i++) {
        f.push_back( async(launch::async,
        [&generator, &distUni, &out, i]
        {
            double x = distUni(generator);
            out[i] = x;
        } ) );
    }
 
    for(auto& i : f) {
        i.get();
    }
 
    for(auto& i : out) {
        cout << i << '\n';
        suma += i;
    }
    cout << "\nsuma: " << suma << endl;
 
    return 0;
}
 

[dmorill]

Hola Lareto, gracias por respuesta. Quiero aprovechar y preguntarte para que sirve esa librería future. Sin embargo el tema principal era que yo uso unos threads más o menos como en el código que mostré (no copio todo porque es más de 2000 lineas) y el problema es que al correrlo con diferente número de threads me da resultados distintos. Razpeitia me dijo que eso era porque hay que tener cuidado con la generación de aleatorios y en el manejo de vectores comunes entre threads.

Un std::future se usa como una forma de esperar la ocurrencia de un evento, es el objeto devuelto por std::async.
async invoca a la función que recibe por parámetro (en este caso le estoy pasando una expresión lambda, pero puede ser un puntero a función, como fun de tu ejemplo, o una función objeto, o una closure), que va a ejecutarse en un nuevo thread (gracias al parámetro launch::async). Un sitio de referencia obligado para mí es
http://en.cppreference.com/w/cpp/thread/async

El mecanismo es similar al de std::thread y join, aunque future permite obtener el resultado devuelto por la función thread con get(), que en este caso no importa porque es void, pero que es bloqueante, por si el thread aún no ha terminado la ejecución.

Te comentaba que ese lock() en fun, hace que el sistema de threads termine siendo secuencial; no sé cómo estará en el sitema real, pero, si guarda esta analogía, convendría revisarlo.


---------- Edito: ¡Ah ha! -----------------
Dice el estándar C++11...

Cita:

26.5.6 Class random_device
1. A random_device uniform random number generator produces non-deterministic random numbers.

2. If implementation limitations prevent generating non-deterministic random numbers, the implementation
may employ a random number engine.

Y algo más abajo...

Cita:

double entropy() const noexcept;
5. Returns: If the implementation employs a random number engine, returns 0.0. Otherwise, returns an entropy estimate for the random numbers returned by operator(), in the range min() to log2 (max() + 1).

Entonces, con el compilador que estoy usando (gcc) yo siempre obtengo la misma lista de valores y la misma suma; y es porque el gcc emplea un random number engine.
El resultado de

Código:

std::cout << "randrom_device entropy = " << rd.entropy() << '\n';

me muestra un 0, redondamente.

Y ¿en el tuyo?
Prueba con esa misma línea y cuéntame si te muestra 0 (que espero que no) o algún otro valor (el de la entropía, me cache).



---------- Edito: de acá para abajo, no va más ---------
Con respecto al problema de los resultados distintos, la verdad es que no me doy cuenta. Yo entiendo que si pones a correr 8 threads vas a obtener 8 valores x al azar, y la suma de ellos; y si corres 500 threads obtendrás 500 valores y una suma mayor. Es posible que no te haya entendido y que nos estemos refiriendo a cosas diferentes.

Cuando ejecuto tu programa con 7 threads, obtengo:
0.726249
0.915339
0.594324
0.515358
0.975149
0.661561
0.528652
suma: 4.91663

Y si lo ejecuto con 8 threads:
0.726249
0.915339
0.594324
0.515358
0.975149
0.661561
0.528652
0.788493
suma: 5.70513

donde los primeros 7 valores son los mismos para las dos listas, como era de esperar.
(Edito: como era de esperar en el compilador que estoy usando, pero evidentemente no en el tuyo)

[dmorill]

Hola lareto gracias por tu detalla respuesta, todo mucho más claro respecto a la nueva librería. Pero respecto al problema con resultados diferentes me refiero a lo siguiente:

1. El programa resuelve 480 problemas con un algoritmo que usa unos aleatorios dentro pero que el valor que retorna es cercano a la respuesta correcta, por ejemplo, el resultado para un problema dado es 9 y el programa da 7.865, o 7.956 o 7.885 pero resultados muy parecidos a pesar de usar valores aleatorios..

2. El problema es que al usar 8 threads me da 8.265 o 8.354 o 8.411 y con 7 threads me da 7.453 o 7.315 o 7.542. y pues no debería ser, deben dar resultados parecidos con diferentes cantidades de threads, pues se supone que se hace lo mismo pero procesando en paralelo.

3. Una pregunta muy importante, yo uso los locks(), y me dices que esos no son tan buenos porque hacen que el procesamiento es casi como serial, y me recomiendas usar #async , entendí bien?

saludos y muchas gracias

1. Me llama la atención que todos los valores que mencionas sean menores que 9 ¿Es imposible que exista un resultado mayor que 9? Si fuera posible, para descartar errores, podrías hacer alguna prueba donde se llegue a uno mayor.


2. Sin conocer los detalles, apostaría a que el problema es de tipo aritmético, y que no debe tener nada que ver con los threads sino con los cálculos que debes estar haciendo con ellos.

Ahora que sabemos que la secuencia:

Código:

random_device rd;
mt19937 generator(rd());

en algunos compiladores genera siempre la misma serie y en otros series distintas, yo haría pruebas generando siempre series iguales para comparar los resultados con distinto número de threads.

Por ejemplo, ejecutar el programa para 1, 2, 7, 8, 10, 20, 50, 500 y 1000 threads, para ver si hay alguna regularidad en los resultados. Lo que resulte de esa prueba seguramente será muy significativo.

El procesamiento que describes no es paralelo, es concurrente. Si fuera paralelo no tendrías esos errores.

3. Lo que te decía sobre los locks era sobre la forma en que los usas, no a que si son mejores o peores que async. Hay varias maneras de controlar el acceso a datos compartidos entre threads, y no creo que haya recetas del tipo "este es mejor que aquél"; seguramente depende de cada caso en particular y de cómo puede uno plantear su solución.

[amchacon]

No es buena práctica hacer locks() directamente, es mucho mejor usar una clase envolvente como unique_lock:

Código C++:

Ver original
void fun(double& suma){
    double x;
    x = distUni(generator);
    unique_lock<std::mutex> control(barrera);
    cout << x << endl;
    suma += x;
}
 

Los unique_lock cierran el mutex en el constructor y lo liberan en el destructor. Esto es mucho más seguro porque en caso de que salte una excepción, te aseguras que se suelte el mutex.

[dmorill]

Hola, muchas gracias a todos ya he encontrado el error, y básicamente era que leía y escribía sobre un arreglo que a pesar de usar locks pues no funcionaba bien.

Salduos