Scala: recogiendo actualizaciones/cambios de estado inmutable.

design-patterns functional-programming

Question

Actualmente estoy tratando de aplicar un estilo de programación más funcional a un proyecto que involucra el desarrollo de GUI de bajo nivel (basado en LWJGL). Obviamente, en tal caso es necesario llevar mucho estado, que es mutable en la versión actual. Mi objetivo es eventualmente tener un estado completamente inmutable, para evitar cambios de estado como efecto secundario. Estudié los lentes de Scalaz y las mónadas estatales durante un tiempo, pero mi principal preocupación sigue siendo: Todas estas técnicas se basan en la copia en escritura. Como mi estado tiene un gran número de campos y también algunos campos de tamaño considerable, me preocupa el rendimiento.

Por lo que sé, el enfoque más común para modificar objetos inmutables es utilizar el método de copy generado de una case class (esto también es lo que hacen las lentes debajo del capó). Mi primera pregunta es, ¿cómo se implementa este método de copy ? Realicé algunos experimentos con una clase como:

case class State(
innocentField: Int,
largeMap: Map[Int, Int],
largeArray: Array[Int]
)

Al hacer una evaluación comparativa y también al observar la salida de -Xprof , parece que la actualización de someState.copy(innocentField = 42) realiza una copia profunda y observo una caída significativa en el rendimiento cuando aumento el tamaño de largeMap y largeArray . Esperaba de alguna manera que la instancia recién construida comparta las referencias de objeto del estado original, ya que internamente la referencia debería pasar al constructor. ¿Puedo forzar o deshabilitar de alguna manera este comportamiento de copia profunda de la copy predeterminada?

Mientras reflexionaba sobre el tema de la copia en escritura, me preguntaba si hay soluciones más generales para este problema en FP, que almacenan los cambios de datos inmutables de una manera incremental (en el sentido de "recopilar actualizaciones" o "recopilar cambios "). Para mi sorpresa no pude encontrar nada, así que intenté lo siguiente:

// example state with just two fields
trait State {
def getName: String
def getX: Int
def setName(updated: String): State = new CachedState(this) {
override def getName: String = updated
}
def setX(updated: Int): State = new CachedState(this) {
override def getX: Int = updated
}
// convenient modifiers
def modName(f: String => String) = setName(f(getName))
def modX(f: Int => Int) = setX(f(getX))
def build(): State = new BasicState(getName, getX)
}
// actual (full) implementation of State
class BasicState(
val getName: String,
val getX: Int
) extends State
// CachedState delegates all getters to another state
class CachedState(oldState: State) extends State {
def getName = oldState.getName
def getX = oldState.getX
}

Ahora esto permite hacer algo como esto:

var s: State = new BasicState("hello", 42)
// updating single fields does not copy
s = s.setName("world")
s = s.setX(0)
// after a certain number of "wrappings"
// we can extract (i.e. copy) a normal instance
val ns = s.setName("ok").setX(40).modX(_ + 2).build()

Mi pregunta ahora es: ¿Qué piensas de este diseño? ¿Es este un tipo de patrón de diseño de FP que no conozco (aparte de la similitud con el patrón de Builder)? Dado que no he encontrado nada similar, me pregunto si hay algún problema importante con este enfoque. ¿O hay alguna otra forma estándar de resolver el cuello de botella de copia en escritura sin renunciar a la inmutabilidad?

¿Existe incluso la posibilidad de unificar las funciones get / set / mod de alguna manera?

Editar:

Mi suposición de que la copy realiza una copia profunda fue realmente incorrecta.

Answer 1

Esto es básicamente lo mismo que las vistas y es un tipo de evaluación perezosa; este tipo de estrategia es más o menos el valor predeterminado en Haskell, y se usa en Scala un poco (vea, por ejemplo, mapValues ​​en mapas, agrupados en colecciones, casi cualquier cosa en Iterator o Stream que devuelva otro Iterator o Stream, etc.). Es una estrategia comprobada para evitar el trabajo extra en el contexto correcto.

Pero creo que tu premisa está algo equivocada.

case class Foo(bar: Int, baz: Map[String,Boolean]) {}
Foo(1,Map("fish"->true)).copy(bar = 2)

de hecho, no hace que el mapa se copie profundamente. Solo establece referencias. Prueba en bytecode:

62: astore_1
63: iconst_2 // This is bar = 2
64: istore_2
65: aload_1
66: invokevirtual #72; //Method Foo.copy$default$2:()Lscala/collection/immutable/Map;
69: astore_3 // That was baz
70: aload_1
71: iload_2
72: aload_3
73: invokevirtual #76; //Method Foo.copy:(ILscala/collection/immutable/Map;)LFoo;

Y veamos lo que hace esa copy$default$2 :

0: aload_0
1: invokevirtual #50; //Method baz:()Lscala/collection/immutable/Map;
4: areturn

Solo devuelve el mapa.

¿Y copy sí mismo?

0: new #2; //class Foo
3: dup
4: iload_1
5: aload_2
6: invokespecial #44; //Method "<init>":(ILscala/collection/immutable/Map;)V
9: areturn

Simplemente llama al constructor regular. No hay clonación del mapa.

Por lo tanto, cuando copia, crea exactamente un objeto: una nueva copia de lo que está copiando, con los campos rellenos. Si tiene una gran cantidad de campos, su vista será más rápida (ya que debe crear un nuevo objeto). (dos si usa la versión de la aplicación de la función, ya que también necesita crear el objeto de la función) pero tiene un solo campo). De lo contrario, debería ser más o menos lo mismo.

Entonces, sí, es una buena idea, pero evalúe cuidadosamente para asegurarse de que valga la pena en su caso: tiene que escribir un poco de código a mano en lugar de dejar que la clase de casos lo haga todo por usted.

Answer 2

Intenté escribir una prueba (bastante aproximada) para medir el rendimiento en la operación de copy su clase de caso.

object CopyCase {
def main(args: Array[String]) = {
val testSizeLog = byTen(10 #:: Stream[Int]()).take(6).toList
val testSizeLin = (100 until 1000 by 100) ++ (1000 until 10000 by 1000) ++ (10000 to 40000 by 10000)
//warmUp
runTest(testSizeLin)
//test with logarithmic size increments
val times = runTest(testSizeLog)
//test with linear size increments
val timesLin = runTest(testSizeLin)
times.foreach(println)
timesLin.foreach(println)
}
//The case class to test for copy
case class State(
innocentField: Int,
largeMap: Map[Int, Int],
largeArray: Array[Int]
)
//executes the test
def runTest(sizes: Seq[Int]) =
for {
s <- sizes
st = State(s, largeMap(s), largeArray(s))
//(time, state) = takeTime (st.copy(innocentField = 42)) //single run for each size
(time, state) = mean(st.copy(innocentField = 42))(takeTime) //mean time on multiple runs for each size
} yield (s, time)
//Creates the stream of 10^n with n = Naturals+{0}
def byTen(s: Stream[Int]): Stream[Int] = s.head #:: byTen(s map (_ * 10))
//append the execution time to the result
def takeTime[A](thunk: => A): (Double, A) = {
import System.{currentTimeMillis => millis, nanoTime => nanos}
val t0:Double = nanos
val res = thunk
val time = ((nanos - t0) / 1000)
(time, res)
}
//does a mean on multiple runs of the first element of the pair
def mean[A](thunk: => A)(fun: (=> A) => (Double, A)) = {
val population = 50
val mean = ((for (n <- 1 to population) yield fun(thunk)) map (_._1) ).sum / population
(mean, fun(thunk)._2)
}
//Build collections for the requested size
def largeMap(size: Int) = (for (i <- (1 to size)) yield (i, i)).toMap
def largeArray(size: Int) = Array.fill(size)(1)
}

En esta máquina:

• CPU: 64bits dual-core-i5 3.10GHz
• RAM: 8GB de RAM
• OS: win7
• Java: 1.7
• Scala: 2.9.2

Tengo los siguientes resultados, que me parecen bastante regulares.

(size, millisecs to copy)
(10,0.4347000000000001)
(100,0.4412600000000001)
(1000,0.3953200000000001)
(10000,0.42161999999999994)
(100000,0.4478600000000002)
(1000000,0.42816000000000015)
(100,0.4084399999999999)
(200,0.41494000000000014)
(300,0.42156000000000016)
(400,0.4281799999999999)
(500,0.42160000000000003)
(600,0.4347200000000001)
(700,0.43466000000000016)
(800,0.41498000000000007)
(900,0.40178000000000014)
(1000,0.44134000000000007)
(2000,0.42151999999999995)
(3000,0.42148)
(4000,0.40842)
(5000,0.38860000000000006)
(6000,0.4413600000000001)
(7000,0.4743200000000002)
(8000,0.44795999999999997)
(9000,0.45448000000000005)
(10000,0.45448)
(20000,0.4281600000000001)
(30000,0.46768)
(40000,0.4676200000000001)

Tal vez tengas diferentes medidas de rendimiento en mente.

¿O podría ser que sus tiempos perfilados se gasten realmente en generar el Map y el Array , en lugar de copiar la case class ?