Efficiency of grouping a List of case classes by more than one field

Question

I have the following input:

case class Client(key: String, time: Option[Instant], bool: Boolean)
val l = List (
  Client("87658763", Some(Instant.EPOCH), false),
  Client("87658769", Some(Instant.EPOCH), false),
  Client("87658769", Some(Instant.EPOCH), true)
)

For context, this data is the result of concatenated Lists from two API calls - one to get all Clients, and one to specifically get all Clients where bool is true.

I want the info to be distinct on the key and time. Also, where there are multiple Clients with the same key and time, if at least one of the Clients contains bool = true, I want to return a single client with bool = true otherwise return a single client with bool = false ... ie I want the output of above to be:

List (
  Client(87658763,Some(1970-01-01T00:00:00Z),false),
  Client(87658769,Some(1970-01-01T00:00:00Z),true)
)

What I have so far is the following code:

import java.time.Instant

case class Client(key: String, time: Option[Instant], bool: Boolean)

val l = List (
  Client("87658763", Some(Instant.EPOCH), false),
  Client("87658769", Some(Instant.EPOCH), false),
  Client("87658769", Some(Instant.EPOCH), true)
)

l.groupBy(client => (client.key, client.time)).map {
  case (_, v) if v.exists(_.bool) => v.head.copy(bool = true)
  case (_, v) => v.head
}.toList

I am curious about efficiency and code style - this is the only way to solve this problem that I could come up with, but I wonder if there is a more efficient way to do this (I don't know much about what the Scala compiler does under the hood with things like groupBy and copy), or a more elegant way to do this.

I've not had to make elements distinct by more than one field before and this call will be made hundreds of times in my application (I am writing this as part of a Play! app) so need it to be as efficient as possible.

Answer 1

Your code is fine

There's nothing wrong with the way you've implemented it. It's readable, and will have reasonable O(n) performance.

Alternative implementation

You've mentioned l is created by concatenation of two lists. As far as I understood one of the lists contains only clients with bool=false and one only clients with bool=true. Some clients will appear on both lists. Example:

val l1 = List(
  Client("87658763", Some(Instant.EPOCH), false),
  Client("87658769", Some(Instant.EPOCH), false),
)

val l2 = List(
  Client("87658769", Some(Instant.EPOCH), true)
)

If this is correct, then an alternative way to implement you function is:

val m1 = l1.map(c => (c.key, c.time) -> c).toMap
val m2 = l2.map(c => (c.key, c.time) -> c).toMap

(m1 ++ m2).values.toList

Or for better (most likely) performance you can use the breakOut trick which will do the mapping and List to Map transformation in single step.

val m1: Map[(String, Option[Instant]), Client] = l1.map(c => (c.key, c.time) -> c)(scala.collection.breakOut)
val m2: Map[(String, Option[Instant]), Client] = l2.map(c => (c.key, c.time) -> c)(scala.collection.breakOut)

(m1 ++ m2).values.toList

Whether this solution is more elegant than your's is subjective. I leave it up to you to decide which one you like more. Whether it's faster should be determined by measurement under production-like load.

First measure & profile

First of all, if you're doing these operations once per the pair of mentioned API calls, then it's likely that the performance will get dominated by the API calls, not this code. If you're doing it more often, then you could remember the results. Before optimising the code I recommend you to measure the performance and determine where is the bottleneck.

Performance factors

If you come to a conclusion that performance of this code is indeed critical, then most likely the problem will be one of these:

• allocation of garbage - groupBy, map, toList each allocate a new data structure. No, the Scala compiler does not optimise this in any way. While allocation is a cheap process, all the garbage will have to be collected, and Garbage Collection can be expensive in some scenarios.
• passes over the data set - groupBy, map, toList each is an O(n) operation iterating over the data. Additional these operations may slow down if the data won't easily fit in CPUs cache.

Which one will be dominant, will depend on Heap and GC configuration, the size of l, other workloads in the JVM and other factors. Both can be improved by doing as small number of passes over the data as possible.

Less passes over the data

These are the hints I can give on reducing the number of passes over the data, in this, and other similar situations:

• Check If you can avoid some collection conversions. Maybe the Iterable[Client] returned by my is ok, and you don't have to convert it toList.
• Use breakOut.
• Try doing more in single step. foldLeft is a powerful operation which lets you combine many operations on a collection into one (at the expense of readability).
• Use mutable structures under the hood. Keep immutables in the API.