0votos

La tela de araña en C#

por josejuan hace 6 años

Misma estrategia que la que usé en Clojure pero con C# ¡es muchísimo más rápido!

Un problema fácil de resolver imperativamente... ¿y funcionalmente? (inmutabilidad y transparencia referencial). Aun así (el enfoque funcional), creo que puede ser un buen kata para practicar punteros y/o TAD's.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using System; 
using System.Linq; 
using System.Threading.Tasks; 
 
namespace spiders { 
 
    // un nodo de una estructura cualquiera, almacena 'shared' la información 
    class Node { 
        private object m; 
        private int n; 
 
        public Node() {n = 0; m = new object();} 
        public void Inc() {lock(m) n++;} 
        public int Read() {return n;} 
 
    // una araña en una estructura toroidal 
    class Spider { 
        private int x, y; 
        private System.Random r; 
 
        public Spider(int _x, int _y) {x = _x; y = _y; r = new Random();} 
 
        public int Move(int size) { 
            int k = r.Next(), d = (k & 1) == 1 ? 1 : -1; 
            if((k & 2) == 2)    x = (size + x + d) % size; 
            else                y = (size + y + d) % size; 
            return x + y * size; 
 
        public void doSteps(int n, int size, Node[] g) {while( n-- > 0 ) g[Move(size)].Inc();} 
 
    class MainClass    { 
 
        public static void Main(string[] args) { 
 
            var n = 5; 
            var g = Enumerable.Range(0, n * n).Select(i => new Node()).ToArray(); 
            var s = Enumerable.Range(0, n).Select(i => new Spider(i, i)).ToArray(); 
 
            var steps = 500; 
            Task.WaitAll(s.Select(i => Task.Factory.StartNew(() => i.doSteps(steps, n, g))).ToArray()); 
 
            Console.WriteLine("Sum node values: {0}", g.Sum(i => i.Read())); 
 
 
 
 
/* 
En un AMD con 6 cores, tenemos: 
 
Lanzando con 60 arañas 1.000.000 pasos, los tiempos y CPU usada son: 
 
$ time -f "t: %E, cpu: %P, mem: %M" clj spiders.clj 
60000000 
t: 1:04.15, cpu: 565%, mem: 778312 
 
$ time -f "t: %E, cpu: %P, mem: %M" mono ./spiders.exe  
Sum node values: 60000000 
t: 0:02.60, cpu: 250%, mem: 8864 
 
la versión C# sólo muestra 250% de CPU porque no le da tiempo ni a arrancar, si ponemos 10M pasos: 
 
$ time -f "t: %E, cpu: %P, mem: %M" mono ./spiders.exe  
Sum node values: 600000000 
t: 0:14.76, cpu: 505%, mem: 11148 
 
 
Si lanzamos 6 arañas y 10M pasos, tenemos: 
 
$ time -f "t: %E, cpu: %P, mem: %M" clj spiders.clj 
60000000 
t: 1:17.54, cpu: 551%, mem: 749208 
 
$ time -f "t: %E, cpu: %P, mem: %M" mono ./spiders.exe  
Sum node values: 60000000 
t: 0:05.11, cpu: 337%, mem: 9784 
 
 
En definitiva, tanto en procesamiento como en uso de memoria NO HAY COLOR. 
 
Obviamente debería haber una forma de hacerlo en Clojure tal que no haya tantísima diferencia, la cuestión es que mi versión Clojure es similar al ejemplo que ponen de uso de concurrencia y 'refs' (hacen un test de intercambio aleatorio de enteros, la referencia está en mi solución). 
 
Entonces, hay dos preguntas a responder respecto Clojure: 
 
1. porqué es lenta esta versión. 
2. como hay que hacerla bien y porqué. 
 
*/ 
16 comentarios
0votos

Escrito por jneira hace 6 años

Es dificil que cualquier libreria o mecanismo abstracto de modificacion concurrente pueda ganar al lock manual igual que es dificil que un garbage collector gane al manejo manual de la memoria con free y malloc. En un problema sencillo establecer un lock o manejar la memoria manualmente es trivial, es en los problemas complejos cuyos requisitos cambian donde las abstracciones automaticas pueden ahorrarte tiempo de desarrollo si te puedes permitir un rendimiento peor.
Tambien hay que tener en cuenta que estas comparando un programa en c# (compilado a codigo maquina no?) con un lenguaje que corre sobre la jvm y habria que comparar el mismo programa pero hecho en java (que casi seguro sera mas lento que el de c#) O hacer el mismo programa en clojure para .net y compilar el programa a ver si la diferencia es tanta.
Aun teniendo en cuenta esto la diferencia es muy muy grande.. a ver si estudio el tema para ver donde esta el cuello de botella y si se puede solucionar sin cambiar demasiado la semantica del codigo.
0votos

Escrito por jneira hace 6 años

Aqui hay una discusion muy interesante sobre el uso de las referencias de clojure comparandola con el manejo a bajo nivel de los locks.
0votos

Escrito por josejuan hace 6 años

_The problem with manual locking - and it applies equally well to
transactions - is that the there's no name-space-control over what
needs to be locked/transacted._

No se si al final lo escribí en algún otro comentario, pero eso es tanto como decir que metemos todo nuestro programa en una transacción. Tú vas a tener igualmente que saber donde acotar la transacción. :P

Reconozco que efectivamente dada una función g(x), el mero hecho de protegerla mediante "dosync(g(x))" elimina cualquier posibilidad de objeto "no shared", y por tanto tiene una ventaja frente a un "lock" directo.

Sin embargo, existe el efecto colateral, puesto que puedes no saber donde debe empezar y terminar la transacción (lo que equivale a saber donde poner o no el "lock"), ejemplo:

dosync {
   a = @desref DATO
   b = f(a)
   @desref DATO = b
}

¿que pasa sí se hace?

dosync {
   a = @desref DATO
}
   b = f(a)
dosync {
   @desref DATO = b
}

¡pues que Clojure no dice nada y la hemos pifiado!


Cierto que ese error es más difícil de cometer que no proteger un shared. Aun así, tiene graves contrapartidas (ya comentadas) y no menor es la que digo en este primer párrafo, debes saber qué cosa encerrar en una transacción.

Por ejemplo, el problema de hacer una o dos transacciones a la que has apuntado antes da pie a este análisis: "cómo, cuando y de que manera hay que encerrar en 'dosync'?".
0votos

Escrito por jneira hace 6 años

No puedes hacer b=f(a) en clojure fuera de una dosync ya que a tendria que ser a su vez otra referencia (tendrias que hacer un @desref a).
En clojure no existe (sin hacer hacks o usar java por debajo) la asignacion mutable (a=...) de variables no concurrente...
0votos

Escrito por jneira hace 6 años

Perdon si que se puede hacer algo parecido a lo que has escrito aunque todavia estoy pensando cual es el posible error que puede producir (Esto de la concurrencia...)

(def DATO (ref 1))
(def a (ref 0))
(dosync
 (ref-set a @DATO))
(let [b (inc @a)]
  (dosync (ref-set DATO b)))
0votos

Escrito por josejuan hace 6 años

cual es el posible error que puede producir

¡pues el que he indicado! XD XD XD

el ejemplo, realmente lo que hace es mandar al traste con la atomicidad de la transacción, igual con SQL te resulta más fácil verlo

DECLARE @n int

BEGIN TRANS
SELECT @n = COUNT(*) FROM TABLA
COMMIT TRANS

BEGIN TRANS
IF @n > 10 THEN INSERT INTO TABLA(n) VALUES (@n)
COMMIT TRANS

Es obvio que aunque dentro de cada transacción los estados de los datos se respetan, se está usando @n para saltarse a la torera, porque en el "IF" el valor que representa @n puede haber cambiado.

Es por eso que el uso de STM no abstrae la concurrencia; es otra estrategia (insisto, con sus pros y cons), pero debe ser el programador quien debe seguir controlando donde y como se accede a los datos.

Si es más o menos cómodo, dependerá de quién lo haga y qué tipo de problemas, etc...
0votos

Escrito por josejuan hace 6 años

No, no compila a código máquina sino a una máquina virtual (igualito que java).

donde las abstracciones automaticas

A ver que me lías, que nunca pillo por donde vas (te veo por peteneras). Pero por centrarme:

A. ¿que abstracción se está haciendo en Clojure que no se hace en C#?

B. yo no he propuesto el uso de STM y decir que mi problema es demasiado sencillo para Clojure es demagogia. O lo soluciona, o no lo soluciona, que mi problema eran las arañas, no STM.

C. interbloqueos y stm son diferentes estrategias para problemas similares, cada cual con sus ventajas e inconvenientes, lo que yo tenía entendido es que stm es útil en sistemas distribuidos, porque en lugar de tener una máquina parada, ésta puede hacer el trabajo y si luego tiene que rehacerlo pues mala suerte, pero en un grid, tener una cpu libre para hacer otras cosas es mejor. Pero bueno, estoy atento a lo que se diga porque es lo que uno tiene ahí al fondo del baúl.

D. la diferencia entre las implementaciones es una burrada y mi hipótesis es la que he comentado, que hay otra forma de hacerlo (efectivamente, algún cuello de botella por ahí). De todos modos, tomaré el código exacto del ejemplo de Clojure y lo compararé con C# a ver.

E. "And in any case in which the STM is failing you performance wise, you can opt out and use manual locks outside of transactions."

claro, claro, eso tiene mucho sentido: me lo curro de una manera y "pruebo a ver" y si no va bien (definamos "no va bien"), pues lo hago de otra manera; lo que hay que leer... (¡y de la mano de Hickey!).

F. "STM can drastically reduce the complexity of a system."

bien, por ahí podemos tirar, pero aún tengo que ver donde reduce drásticamente la complejidad (repito, mis arañas usan [intenté y no veo error] una estrategia como la de su doc). [ironic] ¿Algún ejemplo digno de tan magnánima estrategia? [/ironic]


Hablando más en serio, mi hipótesis siguen siendo las conclusiones que puse en el otro lado:

"tú haz un proceso inmutable y STM te ayudará"

sólo que no veo claro que así sea (que te ayude), tu puedes tener todos los procesos inmutables que quieras, que si luego van a dar al mismo sitio, todos los procesos (menos uno) deberán repetirse, comparemos el peor caso para STM:

i) Tenemos N procesos que hace K=K+Qn al mismo K (el Qn es espcífico de cada proceso).
ii) En el primer intento todos leen K y escriben K+Qn, entonces (N-1) procesos se van al garete y uno logra pasar (digamos que el 'a').
iii) En el segundo intento, todos leen KQa y escriben KQa+Qn, entonces (N-2) procesos se van al garete y uno logra pasar (digamos que el 'b').
iv) Así sucesivamente KQaQbQc...
vi) Se han realizado NN-1N-2N-3...N-(N-1) sumas, es decir N(N1)/2 sumas.

Con bloqueos, todos quedan bloqueados menos uno que es el que hace la suma, luego otro, etc... y se realizan N sumas.

En un sistema de procesadores local, creo que es mejor estrategia general los bloqueos, lo de la abstracción no tengo ni idea aún.

(Voy a seguir leyendo el link que es largo)
0votos

Escrito por josejuan hace 6 años

¡arrrrghhhh con las sumas!

i) Tenemos N procesos que hace K=K+Qn al mismo K (el Qn es espcífico de cada proceso).
ii) En el primer intento todos leen K y escriben K+Qn, entonces (N-1) procesos se van al garete y uno logra pasar (digamos que el 'a').
iii) En el segundo intento, todos leen K+Qa y escriben K+Qa+Qn, entonces (N-2) procesos se van al garete y uno logra pasar (digamos que el 'b').
iv) Así sucesivamente K+Qa+Qb+Qc+...
vi) Se han realizado N+N-1+N-2+N-3+...+N-(N-1) sumas, es decir N(N+1)/2 sumas.
0votos

Escrito por josejuan hace 6 años

A partir de Bad Java syntax follows apuntan buenos ejemplos de lo que comentaba, "que hay que saber qué encerrar en dosync".
0votos

Escrito por vemv hace 6 años

public int Read() {return n;}


Debes sincronizar el acceso a variables si se van a leer desde múltiples hilos; de otro modo te expones a "stale values". Otra opción es declarar n como volatile.
0votos

Escrito por josejuan hace 6 años

No, no tengo, esa lectura puede hacerse en cualquier momento porque en el programa, la lectura de 'g' no tiene determinada una sincronización (las arañas pululan libremente, una puede haber dado 10 pasos y otra tan sólo uno); así, da igual si mientras leo el dato es modificado.

En otro escenario en el que se defina la lectura de 'g' habría que ver, y la solución, dependería de esta definición.

Aquí simplemente, no está definido (p.e. "cada 10 segundos", "cuando alguna araña haya dado 100 pasos", "cuando todas las arañas hayan dado al menos 100 pasos", etc...).
0votos

Escrito por josejuan hace 6 años

Por supuesto, si se quisiera congelar el grafo en un instante, habría que bloquear todo el grafo, lo que yo haría, sería un semáforo con contador a N, así todas las arañas podrán pasarlo sin interrumpirse unas a otras (toman y dejan un único valor del semáforo).

Cuando quieres leer 'g', decrementas el semáforo N veces de golpe, así estarás bloqueado hasta poder recoger N valores del semáforo y podrás leer tranquilamente todo el grafo.
0votos

Escrito por vemv hace 6 años

Creo que no te estás refiriendo a lo mismo que yo. Ya no hablo de consistencia ("da igual si mientras leo el dato es modificado") si no de simple visibilidad de los cambios aplicados - cada procesador tiene su propia caché de n, posiblemente quedándose "anticuada" - salvo que indiquemos lo contrario con uno de los dos métodos que mencioné.
0votos

Escrito por josejuan hace 6 años

cada procesador tiene su propia caché de n

eso no tiene nada que ver, la caché es completamente transparente y no tiene "nada" que ver con que un objeto sea shared entre hilos de ejecución.

Estás mezclando un concepto hardware con uno software que (en lo referente) no tienen absolutamente nada que ver.

De hecho, yo podría no usar bloqueos, y una cuidadosa inspección de esa dirección de memoria (si, si, en la RAM) contendría todas las escrituras (que muy probablemente estarían desincronizadas con las lecturas, claro, y el resultado [el sumatorio] no sería correcto).
0votos

Escrito por vemv hace 6 años

Entonces para qué sirve la palabra 'volatile'? prácticamente lo mismo para 'lock' ('synchronized' en java): una de las dos herramientas debe utilizarse para lecturas, es un hecho.

Para no estar citando libros/etc, una simple búsqueda en google basta: http://stackoverflow.com/questions/1668719/c-sharp-multi-threading-acquire-read-lock-necessary

No mezclo conceptos: por mucho que suceda en el "hardware", es un fenómeno visible en nuestros programas.
0votos

Escrito por josejuan hace 6 años

:)

La palabra "volatile" se usa normalmente para indicar al compilador que usar una dirección de memoria fija para representar el dato en cuestión.

Ésto es útil si queremos pasar un puntero a otro proceso para que sepa donde debe escribir, un dispositivo de hardware, una interrupción de sistema, etc...

Por ejemplo:

bool para = false;
bool *ppara = ¶
while(!para) {
   proceso(ppara);
}


podría o no terminar alguna vez aunque "proceso" establezca a true la variable, porque el compilador puede haber alojado (en el bucle while) la variable "para" en un registro del procesador, entonces, aunque "proceso" establezca la dirección de memoria, como el código generado no usa la dirección, la pifiamos.

Ésto, no puede ocurrir en nuestro caso, puesto que cada objeto "Node" es una estructura en memoria que el compilador no puede (debe) optimizar, por ejemplo en:

while(node.Read() > 0)
   node.Inc();


el compilador no debe realizar optimizaciones locales (eg. meter en un registro, para ello, debemos hacer

int k = node.Read();
while(k ...) ...;
node.Set(k);


entonces, el compilador "quizás" optimice, pero en tal caso nosotros no podemos hacer suposiciones sobre k de ahí que si sí quisíeramos, deberíamos ponerle (a k) el volatile.

¿porqué el compilador no puede/debe optimizar el while?, porque para ello, debería poder "controlar" (no meteré más royo, espero se entienda) el flujo de proceso que conlleva esa dirección de RAM y eso sólo lo pueden hacer lenguajes como Haskell (eg. inmutabilidad).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.