Landa Function

As developers we all have our war stories, in which we fix a critical bug in the middle of the night or find an awesome solution to a really complicated performance issue. This war story is about the old “Introduction to CS” problem - create all of the possible couple combinations from a given collection of items matching a predefined filter. It was interesting to encounter this problem again during a load test when a single method took several hours instead of seconds. That method did exactly what we were requested to do in class!

So I had this inefficient code:

def groupCombinations(groupMembers: Seq[GroupMember]): Array[(Member, Member)] = {
 groupMembers.combinations(2).collect {
   case first +: second +: _  if first.groupId == second.groupId =>
     if (first.member.id > second.member.id) {
       (second.member,first.member)
     } else {
       (first.member, second.member)
     }
 }.toArray
}

Using thread dump I saw that this method creates numerous Seq objects. Diving into the code of groupMembers.combinations(2) made it clear that this line was the root cause for our performance problem. groupMembers.combinations(2) created an iterator that produced a Seq object for every single couple combination, even though most of these combinations were going to be filtered later on. As a result the entire method had a polynomial run and memory complexity of magnitude O(n^2).

To reduce the run time complexity I decided to sort the group members by their group. By sorting, the members of the same group were in indexes near each other. No need to iterate over groupMembers O(n^2) times.

groupMembers.sortBy(_.groupId)

Sorting is fine but it’s not enough, I wanted to have an efficient representation of a couple combination. Scala’s powerful Vector class came to the rescue. Due to its fast random-access of elements it was possible to represent any couple combination by using only two Int indexes pointing to the relevant locations in the vector. There are scenarios when sorting is not necessary, this happens when all the group members belong to the same group - in this case sorting is skipped.

val firstGroupId = groupMembers.head.groupId
val severalGroupsExist = groupMembers.tail.exists(_.groupId != firstGroupId)
val sorted  = if (severalGroupsExist) {
  groupMembers.toVector.sortBy(_.groupId)
}  else {
  groupMembers.toVector
}

To wrap the solution up I used Scala’s for statement to create “on the fly” only the relevant combinations:

def optimizedCombinations(groupMembers: Seq[GroupMember]): Array[(Member, Member)] = {
  val firstGroupId = groupMembers.head.groupId
  val severalGroupsExist = groupMembers.tail.exists(_.groupId != firstGroupId)
  val sorted  = if (severalGroupsExist) {
    groupMembers.toVector.sortBy(_.groupId)
  }  else {
    groupMembers.toVector
  }

 def getNextIndex(currInd: Int): Int = {
   val nextInd = sorted.indexWhere(_.groupId != sorted(currInd).groupId, currInd + 1)
   if (nextInd > 0) nextInd else sorted.length
 }

 (for {
   currInd <- 0 until sorted.size - 1
   currItem = sorted(currInd)
   nextInd <- currInd + 1 until getNextIndex(currInd)
   nextItem = sorted(nextInd)
 } yield {
   if (currItem.member.id > nextItem.member.id)
    (nextItem.member,currItem.member)
   else
    (currItem.member, nextItem.member)
 }).toArray
}

When we ran our load tests again with the optimized code it ran 30 times faster than before, in isolated benchmarks it ran even faster, being 600 times faster than before.

I don’t recommend optimizing your code before knowing where the bottleneck is, but when you get to the point that you have to optimize - start with the basics.