19

我目前正在尝试将更具功能性的编程风格应用于涉及低级（基于 LWJGL）GUI 开发的项目。显然，在这种情况下，需要携带很多状态，这在当前版本中是可变的。我的目标是最终拥有一个完全不可变的状态，以避免状态更改作为副作用。我研究了 scalaz 的镜头和状态单子一段时间，但我主要关心的是：所有这些技术都依赖于写时复制。由于我所在的州既有大量的字段，也有一些相当大的字段，所以我担心性能。

据我所知，修改不可变对象的最常见方法是使用copya 的生成方法case class（这也是镜头在引擎盖下所做的）。我的第一个问题是，这种copy方法实际上是如何实现的？我对一个类进行了一些实验，例如：

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

通过基准测试以及查看它的输出，-Xprof看起来更新someState.copy(innocentField = 42)实际上执行了深层复制，当我增加 和 的大小时，我观察到性能显着largeMap下降largeArray。我以某种方式期望新构造的实例共享原始状态的对象引用，因为在内部引用应该只是传递给构造函数。我可以以某种方式强制或禁用默认的这种深层复制行为copy吗？

在思考写时复制问题时，我想知道 FP 中是否有更通用的解决方案来解决这个问题，它以一种增量方式存储不可变数据的更改（在“收集更新”或“收集变化”）。令我惊讶的是，我找不到任何东西，所以我尝试了以下方法：

// 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
}

现在这允许做这样的事情：

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()

我现在的问题是：你觉得这个设计怎么样？这是某种我不知道的 FP 设计模式（除了与 Builder 模式的相似性）吗？由于我没有发现任何类似的东西，我想知道这种方法是否存在一些重大问题？或者有没有更标准的方法来解决写时复制瓶颈而不放弃不变性？

是否有可能以某种方式统一 get/set/mod 功能？

编辑：

copy我执行深拷贝的假设确实是错误的。

4

2 回答 2

12

这与视图基本相同，是一种惰性求值；这种类型的策略或多或少是 Haskell 中的默认策略，并且在 Scala 中使用得相当多（参见例如 mapValues on maps、grouped on collections、Iterator 或 Stream 上几乎所有返回另一个 Iterator 或 Stream 的东西等）。这是一种行之有效的策略，可以避免在正确的环境中进行额外的工作。

但我认为你的前提有些错误。

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

实际上不会导致地图被深度复制。它只是设置参考。字节码证明：

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;

让我们看看那copy$default$2东西做了什么：

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

只返回地图。

而copy它本身呢？

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

只需调用常规构造函数。没有克隆地图。

因此，当您复制时，您只创建了一个对象——您正在复制的内容的新副本，其中填写了字段。如果您有大量字段，您的视图会更快（因为您必须创建一个新对象（如果您使用功能应用程序版本，则为两个，因为您还需要创建功能对象）但它只有一个字段）。否则应该差不多。

所以，是的，可能是个好主意，但要仔细进行基准测试，以确保它在你的案例中是值得的——你必须手工编写相当多的代码，而不是让案例类为你做这一切。

于 2012-11-06T22:24:34.463 回答
3

copy我试图为您的案例类操作的计时性能编写一个（相当粗略的）测试。

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)
}

在这台机器上：

  • CPU：64位双核i5 3.10GHz
  • 内存：8GB 内存
  • 操作系统：win7
  • 爪哇：1.7
  • 斯卡拉：2.9.2

我有以下结果，这对我来说看起来很正常。

(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)

也许您有不同的性能衡量标准。

或者可能是您的分析时间实际上花费在生成Map和 上Array，而不是复制case class？

于 2012-11-07T11:00:45.533 回答