No responde a la pregunta original de Angel, pero, para tener un "fast become" (o por lo menos no tener que escanear toda la memoria solo para eso), mas allá de las obvias (object tables (GemStone) o direct pointers pero con los headers separados apuntando a los bodies (VW), hay una más que yo conozco para implementar el becomeForward (no become): lazy become. La idea es (por lo que yo entiendo) es que al objeto viejo le pones unos flags en el OH y le pones un pointer al nuevo. Luego (lazily) el GC se encarga de actualizar las referencias al nuevo, hasta que ya no haya nadie apuntando al viejo. Bue, por si mandé fruta, copio lo que dijo Eliot:
- lazy become. The JIT's use of inline cacheing provides a cheap way of avoiding scanning the heap as part of a become (which is the simple approach to implementingbecome in a system with direct pointers). A becomeForward: on a (set of) non-zero-sized object(s) turns the object into a "corpse" or "forwarding object" whose first (non-header) word/slot is replaced by a pointer to the target of the becomeForward:. The corpse's class index is set to one that identifies corpses and, because it is a hidden class index, will always fail an inline cache test. The inline cache failure code is then responsible for following the forwarding pointer chain (these are Iliffe vectors :) ) and resolving to the actual target. We have yet to determine exactly how this is done (e.g. change the receiver register and/or stack contents and retry the send, perhaps scanning the current activation). See below on how we deal with becomes on objects with named inst vars. Note that we probably don't have to worry about zero-sized objects. These are unlikely to be passed through the FFI (there is nothing to pass :) ) and so will rarely be becommed. If they do, they can become slowly. Alternatively we can insist that objects are at least 16 bytes in size (see a8-byte alignment below) so that there will always be space for a forwarding pointer. Since none of the immediate classes can have non-immediate instances and since we allocate the immediate classes indices corresponding to their tag pattern (SmallInteger = 1, Character = 3, SmallFloat = 4?) we can use all the class indices from 0 to 7 for special uses, 0 = forward, and e.g. 1 = header-sized filler. 2012/11/20 Guillermo Schwarz <[email protected]> > +1 > > En memoria RAM típicamente se usa algún tipo de non-blocking > synchronization: > > 1. wait-free-concurrency > 2. lock-free-concurrency. > > http://blog.rethinkdb.com/lock-free-vs-wait-free-concurrency > > Típicamente se implementan usando un número de versión y primitivas a > nivel de CPU conocidas como CAS y LL/SC. Casi todas las CPUs impĺementan > alguna de las 2. > > Pero eso de tener transacciones es aún mejor. Es más grande y por ende > requieres algunos de los 2 anteriores + necesitas poder volver a una > versión particular para poder implementar el rollback (y automatic retry si > es que se quiere). > > > http://courses.cs.vt.edu/cs5204/fall10-kafura-BB/Papers/TransactionalMemory/QualitativeSurvey.pdf > > Lo que dice ahí es que no es necesario comprar una CPU especial ni una > memoria especial, sino que basta con usar algunas estructuras de datos + > CAS o LL/SC y se tiene memoria trasaccional. > > Saludos, > Guillermo. > > > 2012/11/20 Andrés Fortier <[email protected]> > >> El tema con la memoria transaccional es el rendimiento. Básicamente, si >> tenemos un código basado en locks para proteger datos compartidos, >> cuando un procesador toma un lock puede modificar los datos a su antojo. >> En cambio, si lo hacemos mediante una transacción, es necesario guardar >> las dos versiones (la vieja y la nueva) por si eso falla. Esto hace que >> las operaciones a memoria se dupliquen, el tamaño necesario para >> bufferes de escritura (o undo-logs) se dispare en caso de tener >> transacciones grandes. De esta forma, si tenemos un código con poca >> "contención" en el acceso a los datos compartidos (y generalmente está >> optimizado para que así sea, ya que eso es el cuello de botella en >> programas paralelos) entonces la versión basada en locks proporcionará >> un rendimiento mejor. Además, tendremos numerosas llamadas al runtime >> que se encarga de proporcionar esas características (atomicidad, >> consistencia...) que enlentecen la ejecución. >> >> También hay propuestas hardware o híbridas, de Universidades o de >> fabricantes (como el sistema híbrido de Intel o el Rock de Sun, que >> también es híbrido). En estas propuestas, se pasa a algún mecanismo HW >> las tareas de mantenimiento de versiones, detección de colisiones, >> inicialización y commit de las transacciones, etc. >> >> A mi parecer, uno de los principales problemas, que creo que no se >> comenta en el artículo, es la falta de aplicaciones "serias" que >> utilicen memoria transaccional. Sí, tenemos micro-benchmarks (todos los >> artículos implementan de alguna manera red-black trees y linked lists), >> tenemos kernels de aplicaciones, pero en cualquier caso son aplicaciones >> generadas a base de "cambiar locks por transacciones". Una de las >> ventajas de las transacciones es que se pueden componer, es decir, se >> puede anidar una transacción dentro de otra sin ningún problema, y en >> cualquier orden. Esto no se puede hacer con locks, ya que puede llevar a >> deadlock (si dos threads pretenden tomar dos locks dados en orden >> inverso), lo que obliga al programador a ser consciente de todos los >> posibles caminos que puedan tomar los threads en el sistema. De esta >> forma, el diseño de una aplicación paralelo (el diseño completo, desde >> las estructuras de datos hasta el código de cada función) sería >> completamente diferente con memoria transaccional, y la mayoría de las >> aplicaciones de prueba que tenemos, simplemente, no son válidas. >> >> Pero ese no es el único problema, y es que la programación paralela no >> se simplifica tanto como se pudiera pensar en un principio. Las tareas >> de sincronización entre threads siguen siendo complejas, y existen >> estructuras de datos que son inherentemente muy paralelas utilizando >> locks, pero muy poco utilizando transacciones (como el acceso a un >> RB-tree, con congestión en la raíz). En muchos casos, un problema se >> soluciona de manera más sencilla utilizando un lock que una transacción >> (como la gestión de una cola de trabajo, a la que acceden los threads >> para determinar qué tienen que hacer) pero ambos sistemas, locks y >> transacciones, son incompatibles. De esta forma, difícilmente se pueden >> conseguir aplicaciones de prueba realmente válidas. >> >> Sin aplicaciones válidas para verificar la hipotética ventaja (de >> rendimiento, simplicidad de programación, etc) los fabricantes del >> hardware no se van a tirar a la piscina, y los programadores no tienen >> una herramienta válida (que no tarde días en ejecutar un micro-benchmark >> por simulación) para evaluar su sistema. Estamos en la pescadilla que se >> muerde la cola. Hay mucha gente y muchas empresas interesadas en que >> esto salga adelante (Intel, Sun, Microsoft, IBM, y muchos grupos de >> investigación por todo el mundo) pero la situación real no está clara. >> Ya veremos dentro de 15 años... >> >> Ahhh, ahora se lo que se siente ser un troll! >> >> Saludos! >> Andrés (el otro) >> >> Texto original: >> >> http://barrapunto.com/comments.pl?sid=79131&op=&threshold=1&commentsort=0&mode=thread&cid=1103532 >> >> >> On mar, 2012-11-20 at 16:57 -0300, Guillermo Schwarz wrote: >> > Si tienes memoria transaccional y las transacciones son versionadas >> > (optimistic locking), entonces se mantiene la coherencia transaccional >> > de cada una de las transacciones aunque ejecuten en paralelo. >> > >> > >> > >> > >> > 2012/11/20 Andres Valloud <[email protected]> >> > Si hay cosas como generaciones, entonces become: aun con >> > object table >> > es un quilombo porque te pueden quedar referencias cruzadas >> > que no se >> > permiten en tu implementacion. A veces puede que no te quede >> > otra que >> > copiar object bodies. Y ademas actualizar los remember tables >> > de >> > turno, hacer algo especial si esta andando el IGC, y todas >> > esas cosas. >> > >> > 2012/11/20 Hernan Wilkinson <[email protected]>: >> > > dependiendo de la implementacion del manejo de memoria, el >> > become puede ser >> > > simple o complejo... en el caso de usar forward references >> > (implementacion >> > > que usa la mayoria) el become es similar el paso del mark de >> > un gc de mark & >> > > sweep, o sea, hay que buscar todas las referencias, y por lo >> > tanto su >> > > implementacion sera similar a la del gc y en la mayoria de >> > los smalltalks el >> > > gc hace un "stop the world"... tene en cuenta que la mayoria >> > de las >> > > implementaciones usan green threads. >> > > >> > > En el caso de gemstone que usa object table, el become es un >> > simple swap de >> > > referencias y resuelven el conflico de concurrecia >> > simplemente por utilizar >> > > memoria transaccional, no tienen que hacer nada raro mas >> > alla de lo que ya >> > > proveen para trabajar concurrentemente (segun lo que >> > entiendo, puedo estar >> > > equivocado) >> > > >> > > Saludos >> > > Hernan. >> > > >> > > >> > > 2012/11/19 Angel Java Lopez <[email protected]> >> > >> >> > >> Hola gente! >> > >> >> > >> Hoy, mientras leia el Smalltalk-80 the language and its >> > implementation en >> > >> el desayuno, se me ocurrio pensar: >> > >> >> > >> Como hace un Smalltalk para hacer un become: si hay >> > multithreading (es >> > >> decir, si hay varios threads ejecutandose)? >> > >> Pues me imagino que mientras se hace >> > >> >> > >> a become: b >> > >> >> > >> alguno otro thread puede estar operando con b o con a (por >> > ejemplo, tomo >> > >> la clase de b ANTES del become, lookup de un metodo, y >> > luego lo aplica a b >> > >> DESPUES del become) >> > >> (o, si la implementacion interna es un object table (una >> > celda por >> > >> objeto), accedo a la celda de b, tomo algo de la celda (por >> > ejemplo, el >> > >> puntero a la clase), y mientras me cambian la celda, donde >> > esta el puntero >> > >> al resto de los datos) >> > >> (tambien me puedo imaginar una implementacion por object >> > table (una celda >> > >> por objeto), donde haya menos cosas que confundan a un >> > become: a medio >> > >> hacer; por ejemplo, que tenga apenas el puntero al >> > contenido del objeto, y >> > >> ahi en el contenido este el puntero a la clase). >> > >> >> > >> Bueno, no se si me explico .. >> > >> >> > >> Tienen idea? >> > >> >> > >> Me imagino respuestas: >> > >> >> > >> - No, los Smalltalks X, Y, Z solo manejan un thread, y todo >> > lo demas son >> > >> "green threads" >> > >> - En el Smalltalk W, hacemos become: multithreading, pero >> > sin controlar >> > >> nada (sin poner locks, semaforos o lo que sea) >> > >> - En el Smalltalk T, tenemos multithread y hacemos un lindo >> > bolonki para >> > >> hacer que el become: sea thread-safe >> > >> - En el Smalltalk S, tenemos multithread y la >> > implementacion interna >> > >> (object table con celda atomica, con pocos datos; o puntero >> > directo, o lo >> > >> que sea) es tal, que el become termina siendo thread-safe >> > por naturaleza >> > >> >> > >> Cual es? >> > >> >> > >> Nos leemos! >> > >> >> > >> Angel "Java" Lopez >> > >> @ajlopez >> > >> >> > >> -- >> > >> To post to this group, send email to >> > [email protected] >> > >> To unsubscribe from this group, send email to >> > >> [email protected] >> > >> >> > >> http://www.clubSmalltalk.org >> > > >> > > >> > > >> > > >> > > -- >> > > Hernán Wilkinson >> > > Agile Software Development, Teaching & Coaching >> > > Phone: +54 - 011 - 6091 - 3125 >> > > Mobile: +54 - 911 - 4470 - 7207 >> > > email: [email protected] >> > > site: http://www.10Pines.com >> > > Address: Alem 693, Floor 5 B, Buenos Aires, Argentina >> > > >> > > -- >> > > To post to this group, send email to >> > [email protected] >> > > To unsubscribe from this group, send email to >> > > [email protected] >> > > >> > > http://www.clubSmalltalk.org >> > >> > -- >> > To post to this group, send email to >> > [email protected] >> > To unsubscribe from this group, send email to clubSmalltalk >> > [email protected] >> > >> > http://www.clubSmalltalk.org >> > >> > >> > >> > >> > >> > -- >> > Saludos cordiales, >> > >> > Guillermo Schwarz >> > Sun Certified Enterprise Architect >> > >> > >> > -- >> > To post to this group, send email to [email protected] >> > To unsubscribe from this group, send email to clubSmalltalk >> > [email protected] >> > >> > http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [email protected] >> To unsubscribe from this group, send email to >> [email protected] >> >> http://www.clubSmalltalk.org >> > > > > -- > Saludos cordiales, > > Guillermo Schwarz > Sun Certified Enterprise Architect > > -- > To post to this group, send email to [email protected] > To unsubscribe from this group, send email to > [email protected] > > http://www.clubSmalltalk.org > -- Mariano http://marianopeck.wordpress.com -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] http://www.clubSmalltalk.org
