Trong bài viết này mình sẽ liệt kê một số vấn đề thường gặp trong Scala khiến cho code chạy chậm và cách giải quyết. Các ví dụ trong bài viết này được chạy bằng Scala trên command line, máy MacBook Pro (Retina, 15-inch, Mid 2015) bản processor 2.2 GHz. Thời gian chạy của các ví dụ trong bài viết này được đo bằng hàm:

def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block
    val t1 = System.nanoTime()
    println(""Elapsed time: "" + (t1 - t0) + ""ns"")
    result
}

1. For loop filtering

Ta không nên dùng hàm if ở trong for loop. Ví dụ 1: Tốc độ xử lý của good example trung bình nhanh gấp 1.56 lần.

//Bad example: cost 913308 ns in average
for (i <- 1 to 2000 if (i%777 == 0)) a += 1

//Good example: cost 585621 ns in average
for (i <- 1 to 2000) if (i%777 == 0) a += 1

Ví dụ 2: Tốc độ xử lý của good example trung bình nhanh gấp 156.22 lần.

//Bad example: cost 1790619173ns in average
for (
  a <- 1 to 1000;
  b <- 1 to 1000 - a;
  c <- 1 to 1000 - a - b;
  if (a * a + b * b == c * c && a + b + c == 1000)
) println((a, b, c, a * b * c))

//Good example: cost 11461775ns in average
for (
  a <- 1 to 1000;
  b <- 1 to (1000 - a)
) {
  val c = (1000 - a - b)
  if (a * a + b * b == c * c)
    println((a, b, c, a * b * c))
}

Nguyên nhân là do

for(x <- c; if cond) yield {...}

tương đương với

c.withFilter(x => cond).map(x => {...})

(Bạn có thể tham khảo thêm ở docs của Scala để rõ hơn về bản chất thực sự của for-yeild trong Scala). Khi dùng withFilter, một hàm ẩn danh mới có kiểu Function2[Object, Boolean] được tạo ra (hàm này được dùng ở đoạn lọc dữ liệu theo cond). Tham số được truyền vào hàm này sẽ bị boxed lại, vì kiểu dữ liệu đầu vào của hàm ẩn danh này là Object. Quá trình boxing/unboxing này chậm hơn rất nhiều so với việc cond được đánh giá trực tiếp ở trong thân của for loop vì lúc đó các tham số được truy cập trực tiếp chứ không cần qua boxing (Nếu bạn không rõ về khái niệm boxing/unboxing, bạn có thể đọc thêm về Functor ở trong bài viết này).

2. Tail recursion

Đệ quy đuôi là một trường hợp đặc biệt của đệ quy khi mà hàm không thực hiện tính toán thêm sau khi gọi chính nó. Ví dụ: Tốc độ xử lý của good example trung bình nhanh gấp 2.71 lần.

//Bad example:
def sum1(x: Int): Int = {
  if (x == 1) x
  else x + sum1(x - 1)
}
sum1(10000) //cost 440433ns in average

//Good example:
def sum2(x: Int, total: Int = 0): Int = {
  if (x == 0) total
  else sum2(x - 1, total + x)
}
sum2(10000) // cost 162473ns in average

Trong bad example, sau khi gọi lại chính mình, hàm còn thực hiện thêm 1 phép cộng và trả về giá trị sau tính toán, khác với good example trả về luôn giá trị mà hàm đệ quy trong trả về. Trong hàm đệ quy bình thường, ta phải đẩy địa chỉ trả về vào một stack trước khi mà nhảy lại vào chính nó. Điều đó có nghĩa là ta cần phải có 1 stack có kích thước bằng với độ sâu của lần gọi đệ quy. Khi dùng đệ quy đuôi, hàm ở lớp ngoài sẽ trả lại giá trị ngay khi hàm ở lớp trong trả về, do đó ta không phải phải return hàng loạt mà chỉ cần return 1 lần cho lần gọi hàm lớp ngoài cùng. Điều đó giúp tiết kiệm được thời gian và bộ nhớ cho hệ thống.

3. Move code out of the loop if any

Việc tránh những đoạn code y hệt được thực hiện đi thực hiện lại trong vòng lặp là điều hiển nhiên. Tuy nhiên với Scala đôi khi hơi khó để nhận ra sự trùng lặp này. Ví dụ: Tốc độ xử lý của good example trung bình nhanh gấp 638.96 lần.

//Bad example:
def intersect1(s1: Seq[Int], s2: Seq[Int]): Seq[Int] =
    s2.filter(elem => s1.toSet.contains(elem))

val s1 = (1 to 10000).filter(_ % 2 == 0).toSeq
val s2 = (1 to 10000).filter(_ % 7 == 0).toSeq
intersect1(s1, s2) // cost 1376163361ns in average

//Good example:
def intersect2(s1: Seq[Int], s2: Seq[Int]): Seq[Int] = {
    val set = s1.toSet
    s2.filter(elem => set.contains(elem))
  }

val s1 = (1 to 10000).filter(_ % 2 == 0).toSeq
val s2 = (1 to 10000).filter(_ % 7 == 0).toSeq
intersect2(s1, s2) // cost 2153736ns in average

Trong good exampke, phần s1.toSet được tách ra khỏi hàm filter khiến cho tốc độ xử lý được cải thiện rõ rệt. Vì Scala có rất nhiều hàm có sẵn cho Seq, đôi khi deverloper không nhận thức được độ phức tạp của các hàm có sẵn này.

4. Use map instead of find

Trong Scala, các collection thường được implement sẵn hàm find nhằm tìm ra phần tử tương ứng của collection thoả mãn điều kiện. Tuy nhiên, độ phức tạp của hàm find là O(n) với n là số phần tử trong collection. Nếu hàm find này được thực hiện nhiều lần, ta nên tạo một map từ collection với key là điều kiện tìm kiếm, value là phần tử và dùng map này để tìm phần tử tương ứng. Độ phức tạp sẽ giảm xuống còn O(1). Ví dụ: Ta cần tìm ra danh sách những học sinh kém dựa vào sequence badStudentIds:

//Good example
def findCorrespondingStudent1(students: Seq[Student], badStudentIds: Seq[StudentId]): Try[Seq[Student]] = {
    val studentMap = createStudentMap(students)
    badStudentIds.map(studentId => {
      val correspondingStudent = studentMap.get(studentId)
      correspondingStudent match {
        case Some(student) => student
        case None          => throw NotFoundException("Non-existed student ID")
      }
    })
}

//Bad example
def findCorrespondingStudent2(students: Seq[Student], badStudentIds: Seq[StudentId]): Try[Seq[Student]] = {
    badStudentIds.map(studentId => {
      val correspondingStudent = students.find(x => x.studentId = studentId)
      correspondingStudent match {
        case Some(student) => student
        case None          => throw NotFoundException("Non-existed student ID")
      }
    })
}

def createStudentMap(students: Seq[Student]): mutable.Map[StudentId, Student] = {
    val mapped = mutable.Map[StudentId, Student]()
    students.foreach(student => {
      val key = student.accountId
      mapped += Tuple2(key, student)
    })
    mapped
}

Trong ví dụ trên, thay vì dùng hàm find để tìm student dựa vào studentId, ta tạo ra một map với key là studentId và value là student tương ứng, sau đó dùng map để get ra student tương với với studentId. Giả sử students có độ dài n, badStudentIds có độ dài là m, thì độ phức tạp của bad example là O(mn), trong khi độ phức tạp của good example là O(n + m). Việc tạo map này sẽ phát huy tác dụng tối đa khi mà việc tìm kiếm phần tử được thực hiện nhiều lần. Hi vọng bài viết có thể giúp ích được cho bạn đọc. Nguồn tham khảo: https://stackoverflow.com/questions/15137360/scala-for-comprehension-performance