4

I am wondering what is more performant in getting the difference between two sets:

Something like this:

method(Set<Id> a, Set<Id> b) {
   Set<Id> result = a; 
   result.addAll(b);
   result.removeAll(a);

   return result;
}

or:

method(Set<Id> a, Set<b>) {
    Set<Id> result = new Set<Id>();

    for (Id x : b) {
        if ( !a.contains(x) ) {
            result.add(x);
        }
    }

    return result;
}

Basically, how do addAll and removeAll work in Apex?

4
  • 2
    Why would you call addAll(a)? That part just seems wasteful.
    – Adrian Larson
    Jun 26, 2017 at 21:52
  • Gotcha, so say we don't initialize a new list to return and just use a, add b, remove a, and return the result - I'll edit it to reflect that insight, thanks.
    – moth
    Jun 26, 2017 at 21:56
  • 1
    Let's do some thinking. In case if set a has n elements, and set b has m elements, and (b-a) has o elements, has then scenario 2 will have O(m(n+o)) complexity (Java set Contains -- stackoverflow.com/questions/6769523/… -- constant time, f.e.) method, But we add into set O elements, that takes time. First scenario will have next complexity O(m-o), because removal has constant time (in avg scenario. Sample runs -- gist.github.com/kurunve/24322de8df1b85b7a45c956c52ab0016. Conclusion - if difference is small, result is same, because add is slow.
    – kurunve
    Jun 26, 2017 at 22:36
  • 1
    FYI, whenever you have a question like this, just ask yourself "how many method calls are involved?" The one with the lowest number of method calls is most likely the fastest, because method calls are brutally slow.
    – sfdcfox
    Jun 27, 2017 at 4:24

3 Answers 3

9

Note that you are calculating the Set Complement.

The set methods are 16x-25x faster. I ran 20 trials each with the following configurations, all with Set<Integer> of 1000 elements to generate the data below.


TL;DR

When there is 100% overlap, the Set methods are about 26 times faster. When there is 0% overlap, the difference is a factor of about 16. The for loop approach has much wider variability. Using Set methods, performance is faster as overlap increases. The converse is true for looping, performance slows as overlap increases.


Chart

Set Complement Profiling Chart


Results

  • Set Methods
    • 100% Overlap
      • Average: 317.7 μs
      • Min: 286 μs
      • Max: 371 μs
    • 0% Overlap
      • Average: 451.9 μs
      • Min: 394 μs
      • Max: 521 μs
  • For Loops
    • 100% Overlap
      • Average: 8,216.5 μs
      • Min: 5,570 μs
      • Max: 12,280 μs
    • 0% Overlap
      • Average: 7,291.5 μs
      • Min: 4,370 μs
      • Max: 10,690 μs
1
  • 1
    I knew it was slower, but... wow. This is good stuff.
    – sfdcfox
    Jun 27, 2017 at 4:22
1

addAll seems to be more efficient in terms of performance. Please check resultenter image description here

1

In general, because Apex is a wrapper over Java, most bulk operations that correspond to a single Java statement will probably be handled more efficiently than an Apex loop that runs many of the same Java statement.

Another good example is with strings. Apex doesn't have any sort of native StringBuilder class for repeated additions to the same string. Concatenating Java strings repeatedly without such a class is "expensive". On the other hand, Apex String.join is likely handled as a single Java statement more efficiently.

So the following trivial code exceeds the Apex CPU limit time in my dev org:

Integer n = 200000;
String s = '';
for (integer i = 0; i<n; i++){
    s += String.valueOf(i) + ',';
}

But the following does not, although the string it generates is even longer:

Integer n = 300000;
String[] sa = new List<String>();
for (integer i = 0; i<n; i++){
    sa.add(String.valueOf(i));
}
String s = String.join(sa, ',');

Having found that out some months ago, I now know that whenever I want to generate a large string in Apex from smaller pieces (e.g. log files, CSV), it's much more efficient to collect the pieces in an array and String.join them once.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .