Hiệu suất của các collection immutable trong scala

Posted by 27/06/2018 in Scala

Mutable collection thường nhanh hơn một immutable bởi vì nó đang làm việc trên cùng một địa chỉ bộ nhớ. Do đó, dữ liệu sẽ không bị copy đi, copy lại. Trong Scala, vấn đề này có thể được giảm nhẹ bằng cách sử dụng lại các object giống như một vài hoạt động của List

1
2
3
val a = 1 :: Nil
val b = 2 :: a
val c = 3 :: b //List(3, 2, 1)

Chỉ có một instace của list đang nắm giữ các số 1, 2 và 3. Giá trị ‘a’ có một tham chiếu trỏ đến phần tử cuối cùng của List. Giá trị ‘c’ có một tham chiếu trỏ đến phần tử đầu tiên của List. Bởi vì list là một immutable, chúng ta không thể thay đổi giá trị của list, giúp nó an toàn để chia sẻ cùng một list cho cả 3 giá trị khác nhau (chúng ta chỉ nhìn thấy phần khác nhau của list)

2 cấu trúc dữ liệu thông thường mà hầu hết chúng ta sử dụng hàng ngày đó là map và list. Mảng trong Scala là mutable, nên, chúng ta sẽ không đề cập đến nó vì nó cũng giống như mảng trong Java

Chúng ta sẽ sử dụng Scalameter để đo benchmark bởi vì cài đặt nó tương đối đơn giản. Đây là cách cấu hình.

1
2
3
4
5
val standardConfig = config(
  Key.exec.minWarmupRuns -> 100,
  Key.exec.maxWarmupRuns -> 300,
  Key.exec.benchRuns -> 2000
) withWarmer(new Warmer.Default)

Map

Giả sử chúng ta có 2 case class đang giữ các immutable và mutable của map như sau.

1
2
case class MapImm(m1: Map[Int, Int], m2: Map[Int, Int], m3: Map[Int, Int])
case class MapMut(m1: mutable.Map[Int, Int], m2: mutable.Map[Int, Int], m3: mutable.Map[Int, Int])

Hãy tạo một range valrange= (1 to 1000), và sử dụng foldLeft để gán từng số trong range vào map

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
val timeMap1 = standardConfig measure {
  range.foldLeft(MapImm(Map.empty, Map.empty, Map.empty)) {
    (o, i) => MapImm(o.m1 + (i -> i),
                     o.m2 + (i -> (i + 1)),
                     o.m3 + (i -> (i + 2)))
  }
}
val timeMap2 = standardConfig measure {
  val l1 = mutable.Map.empty[Int, Int]
  val l2 = mutable.Map.empty[Int, Int]
  val l3 = mutable.Map.empty[Int, Int]
  range.foreach { i =>
    l1 += (i -> i)
    l2 += (i -> (i + 1))
    l3 += (i -> (i + 2))
  }
  MapMut(l1, l2, l3)
}
val timeMap3 = standardConfig measure {
  val l1 = mutable.Map.empty[Int, Int]
  val l2 = mutable.Map.empty[Int, Int]
  val l3 = mutable.Map.empty[Int, Int]
  range.foreach { i =>
    l1 += (i -> i)
    l2 += (i -> (i + 1))
    l3 += (i -> (i + 2))
  }
  MapImm(l1.toMap, l2.toMap, l3.toMap)
}

Bạn có thể nói rằng một mutable nhanh hơn một immutable. Nhưng chúng ta chỉ muốn biết liệu nó có nhanh hơn đáng kể hay không thôi. Một điểm thú vị là timeMap3 sử dụng dữ liệu mutable và cuối cùng sẽ chuyển đổi thành immutable.

1
2
3
Immutable Map (timeMap1): 0.4476 ms
Mutable Map (timeMap2): 0.1412 ms
Immutable Map được chuyển đổi từ Mutable Map (timeMap3): 0.6572 ms

Chắc chắn, chúng ta nên sử dụng immutable map mặc dù nó chậm hơn gấp 3 lần mutable. Chênh lệch 0.3 ms là quá nhỏ để cân nhắc. Nếu bạn đang phát triển một hệ thống thời gian thực, thì con số này không hề nhỏ. Nhưng, thực tế nếu bạn làm việc trên hệ thống thời gian thực, nơi mà 0.3 ms được coi là đáng kể, thì bạn không nên lựa chọn Scala ngay từ lúc đầu. Chi phí cho hàm chuyển đổi toMap mất 0.6 ms do đó làm cho tổng thời gian cao hơn cả immutable map.

Nếu bạn xem code thực thi hàm toMap, bạn sẽ thấy rằng nó tạo một immutable map hoàn toàn mới. Đó là lý do tại sao nó mất 0.5ms

1
2
3
4
5
6
def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] = {
  val b = immutable.Map.newBuilder[T, U]
  for (x <- self)
    b += x
  b.result()
}

List

Hãy nhìn list, một cấu trúc dữ liệu khác thường được sử dụng.

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
case class ListImm(l1: List[Int], l2: List[Int], l3: List[Int])
case class ListMut(l1: mutable.MutableList[Int], l2: mutable.MutableList[Int], l3: mutable.MutableList[Int])
val timeList1 = standardConfig measure {
  range.foldLeft(ListImm(List.empty, List.empty, List.empty)) {
    (o, i) =>
    ListImm(o.l1 :+ i, o.l2 :+ (i + 1), o.l3 :+ (i + 2))
  }
}
val timeList2 = standardConfig measure {
  val l1 = mutable.MutableList.empty[Int]
  val l2 = mutable.MutableList.empty[Int]
  val l3 = mutable.MutableList.empty[Int]
  range.foreach { i =>
    l1 += i
    l2 += (i + 1)
    l3 += (i + 2)
  }
  ListMut(l1, l2, l3)
}
val timeList3 = standardConfig measure {
  val l1 = mutable.MutableList.empty[Int]
  val l2 = mutable.MutableList.empty[Int]
  val l3 = mutable.MutableList.empty[Int]
  range.foreach { i =>
    l1 += i
    l2 += (i + 1)
    l3 += (i + 2)
  }
  ListImm(l1.toList, l2.toList, l3.toList)
}

Kết qủa như sau

1
2
3
Immutable List (timeList1): 15.8006 ms
Mutable List (timeList2): 0.0436 ms
Immutable List được chuyển đổi từ Mutable List (timeList3) : 0.0871 ms

immutable list thực hiện chậm hơn mutable list 362 lần. Nó thật là khủng khiếp vì giá trị N chỉ là 1000 và hiệu suất của nó sẽ tồi tệ như thế nào nếu N là 2000

1
2
3
Immutable List: 67.1715 ms
Mutable List: 0.1117 ms
Immutable List được chuyển đổi từ Mutable List: 0.2081 ms

Bây giờ thì khoảng cách còn lớn hơn. Immutable list chậm hơn mutable list 610 lần.

Khi bạn đang xử lý một List dữ liệu lớn, bạn có thể nên sử dụng một mutable list rồi sau đấy chuyển đổi nó thành immutable list, giúp đảm bảo rằng bạn không chia sẽ dữ liệu mutable

Tôi muốn nhắc bạn một điều quan trọng là chúng ta đang thực hiện benchmark trên các hành động thêm vào. Scala list được thực thi như list liên kết đơn, chi phí của các hành động thêm vào làm thời gian lâu hơn. Nếu bạn muốn tìm hiểu thêm về các đặc tính của Scala collection, bài viết này, được tạo bởi Li Haoyi, rất hay và chi tiết.

Chúng ta biết rằng nhược điểm hoạt động :: mất một lượng thời gian, nó nhanh như chớp bởi vì chúng ta thêm một phần tử vào đầu list. Dựa trên thực tế này, hãy thử làm cái gì đó thú vị với nó

Chúng ta sẽ thử đo lai các hàm này một lần nữa. Nhưng lúc này chúng ta sẽ dùng hoạt động :: và sắp xếp đảo ngược immutable list để có được kết quả giống như hàm thêm vào các phần tử. Tôi chắc chắn rằng kết quả benchmark sẽ khiến bạn ngạc nhiên

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
val time1 = standardConfig measure {
  val l = mutable.MutableList.empty[Int]
  range.foreach { i => l += i}
  l
}
val time2 = standardConfig measure {
  val l = mutable.MutableList.empty[Int]
  range.foreach { i => l += i}
  l.toList
}
val time3 = standardConfig measure {
  range.foldLeft(List.empty[Int]){ (l, i) => l :+ i }
}
val time4 = standardConfig measure {
  range.foldLeft(List.empty[Int]){ (l, i) => i::l }.reverse
}

Kết quả như sau

1
2
3
4
Mutable List (time1): 0.0166 ms
Immutable List chuyển đổi từ Mutable List (time2): 0.0211 ms
Immutable List (time3): 4.2307 ms
Immutable List (cons + reverse) (time4): 0.0285 ms

Chú ý rằng hàm reverse cũng sử dụng :: . Hàm này được thực hiện sử dụng một cách tiếp cận bắt buộc là sử dụng vòng lặp while và 2 biến tạm thời với mục đích hiệu suất. Những gì nó làm chỉ đơn giản là thay đổi địa chỉ của con trỏ trong list liên kết đơn. Mặc dù phép tính reserve nhận được O(n). Hiệu suất thực tế là đáng kinh ngạc.

Nếu bạn không muốn gọi hàm reverse, bạn có thể dùng foldRight thay thế

1
range.foldRight(List.empty[Int]){ (i, l) => i::l }

Thông thường, chúng ta thích sử dụng foldLeft hơn foldRight, nếu thứ tự là không quan trọng. Bởi vì foldRight sẽ đảo ngược thứ tự trước khi gọi hàm foldLeft trong khi chạy

Đây là code thực hiện hàm foldRight

1
2
def foldRight[B](z: B)(op: (A, B) => B): B =
  reversed.foldLeft(z)((x, y) => op(y, x))

 

 

You May Also Like

Reduction of List

Pair and tuple

About the Author: Nguyen Dinh Thuc

Leave a Reply

avatar
  Subscribe  
Notify of