Using Scala's scala.collection.Set[T]. Given a small set s with only a few elements and another big set b with lots of elements, is there any performance difference between:

s & b // s intersect b

and

b & s // b intersect s.

If yes, which is the fastest?

The generic implementation seen in the GenSetLike using intersect is overriden for HashSet with an implementation which looks quite complex to me (see scala.collection.immutable.HashSet.HashTrieSet#intersect0). Based on my rough benchmark its performance is similar for both a & b and b & a and it is similar to the performance of a filter b, which is an order of magnitude faster than b filter a. My testing code is:

object Sets extends App {



  def time[R](block: => R): R = {

    val t0 = System.nanoTime()

    val result = block    // call-by-name

    val t1 = System.nanoTime()

    println("Elapsed time: " + (t1 - t0)/1e6 + "ms")

    result

  }



  val a = (0 until 10000 by 1).toSet      //smaller data

  val b = (0 until 1000000 by 2).toSet





  time {a & b}

  time {b & a}

  time {a & b}

  time {b & a}

  time {a & b}

  time {b & a}



  println("Filter")



  time {a filter b}

  time {b filter a}

  time {a filter b}

  time {b filter a}

  time {a filter b}

  time {b filter a}

}

Result is:

Elapsed time: 6.990442ms

Elapsed time: 4.25017ms

Elapsed time: 4.1089ms

Elapsed time: 4.480789ms

Elapsed time: 3.71588ms

Elapsed time: 3.160159ms

Filter

Elapsed time: 7.781613ms

Elapsed time: 68.33023ms

Elapsed time: 5.858472ms

Elapsed time: 42.491131ms

Elapsed time: 2.982364ms

Elapsed time: 52.762474ms

The answer is: it's complicated.

The default implementation of an immutable set is scala.collection.immutable.Set. This has special cases for sizes 1 to 4. As soon as you have more than 4 elements, it will use scala.collection.immutable.HashSet.

Very small s (1..4)

So let's say you have a large set b and a small set s, with s containing <4 elements.

Then it will make a large difference:

b & s will filter all elements of b against membership in s and therefore takes b.count * s.count equality comparisons. Since b is large this will be quite slow.

s & b will filter the few elements of s against a membership in b, which is s.length times a hashing and an equality comparison if the hashes match (remember b is a HashSet). Since is is small this should be very fast.

Small s (n>4)

As soon as s is larger than 4 elements, it also will be a HashSet. Intersection for HashSets is written in a symmetric and very efficient way. It will combine the tree structures of s and b and perform equality comparisons when the hashes match. It will use maximum structural sharing. E.g. if b contains all elements of s, the result will be the same instance as s, so no objects will be allocated.

General advice

If you just write generic code where you don't care much about high performance, it is fine to use the default implementations such as scala.collection.Set. However, if you care about performance characteristics it is preferable to use a concrete implementation. E.g. if s and b are declared as scala.collection.immutable.HashSet, you will have consistent high performance independent of order, provided that you have a good hash function.

Let us create two sets as per the condition mentioned

   val a = (0 until 10000 by 1).toSet      //smaller data

   val b = (0 until 1000000 by 2).toSet    //Relatively larger data

we can define a time function to check the execution time as below

def time[R](block: => R): R = {

    val t0 = System.nanoTime()

    val result = block    // call-by-name

    val t1 = System.nanoTime()

    println("Elapsed time: " + (t1 - t0) + "ns")

    result

}

Now we can check the intersection conditon

scala> time {a & b}

Elapsed time: 5895220ns

res2: scala.collection.immutable.Set[Int] = Set(892, 5810, 8062, ..)



scala> time {b & a}

Elapsed time: 6038271ns

res3: scala.collection.immutable.Set[Int] = Set(892, 5810, 8062, ...)

So by this we can conclude that intersection between a smaller and large dataset has performance difference and it is better to have the smaller dataset on the left side for faster execution for Scala set