14

Prelude

I did a couple of interwebs searches, and I used the following search terms here on SFSE...

apex map get set contains
apex map vs set
apex map set efficien*

...then looked through a number of Qs & As and some links within some of the As. If I missed the answer, please forgive and point me to it.


Background

I know just enough of Apex and other coding to be dangerous. Adhering to best practices as much as possible is preferable, but I don't know all the best practices. I also know that some debates are akin to "Toilet paper over or under?", in that there are lots of opinions but not often is there a real better answer. (There is a correct answer to the toilet paper question, btw.)

Item at hand

I was sent an Apex class with an invocable method which a different team had created and our team needs to use. One bit of functionality that it was supposed to be doing was not working as stated, and some parts seemed to me that they could use some improvement. So I modified the code, and it was sent back to the code owners for their consideration. They kept most of my changes, but a blanket statement was made that I want to know whether it is true. Not (necessarily) so that I can say that I am correct (if I am), but just to know as part of the aforementioned best practices.

Statement

Maps are more efficient [than Sets] when doing a lookup.


Question

Is it more efficient to use a map and call .get(), or use a set and call .contains()?


Code Comparison

Showing only the pertinent code (and changing names to protect the [not so] innocent), here is the original:

List<Group> groups = [SELECT Id, Name FROM Group WHERE Name LIKE :queryString];
Map<String, Group> groupMap = new Map<String, Group>();

for (Group g: groups) {
    groupMap.put(g.Name, g);
}

Group targetGroup;
String targetGroupName;

for (...) {
    targetGroupName = <something different every loop iteration>
    targetGroup = groupMap.get(targetGroupName);
    if(targetGroup != null){
        // Found the only one we're looking for, so set the output
        break;
    }
}

My suggested changes:

List<Group> groups = [SELECT Name FROM Group WHERE Name LIKE :queryString];
Set<String> groupNameSet = new Set<String>();

for (Group g: groups) {
    groupNameSet.add(g.Name);
}

String targetGroupName;

for (...) {
    targetGroupName = <something different every loop iteration>
    if (groupNameSet.contains(targetGroupName)) 
        // Found the only one we're looking for, so set the output
        break;
    }
}

UPDATES

After the first three answers, I just have to say that I love y'all here at SFSE.

2021.11.12 Normally I would choose an answer, because I don't like seeing questions with answers that clearly do answer the question and one is not accepted. However, all four of these answers are awesome, and helpful, and each contributes something different from the others. So if y'all don't mind, I'm not going to accept just one.

2
  • 3
    Worth remembering that every Map always has a key Set which is directly tied into the Map so updates to the Set update the Map (I strongly suspect the key Set is actually the Map or the Map's internal data structure simply exposed as a Set interface). Of course the internal data structure or implementation for Map and Set could be different, though it would make sense to share a common core and thus share general performance, ignoring heap allocation aspects.
    – Phil W
    Nov 10, 2021 at 22:31
  • 3
    aaaaaand welcome to being the topmost hot post across all stackexchange sites.
    – Derek F
    Nov 10, 2021 at 23:13

4 Answers 4

18

In pretty much every concievable scenario, the number of records (or data in general) that we can work with in Salesforce in a single transaction means that any difference between approaches is likely to be immeasurable.

Things like this (using a set vs using a map) is something I would say falls under the category of micro-optimization. Micro-optimizations are a waste of time (to be clear, this is aimed at the performance assertion of this other team). If you are looking to optimize something, you should do two things:

  1. Define a specific thing to be improved that can be measured (requests per second, heap space, cpu time, # of queries, etc...)
  2. Measure that thing before your change, make your change, then measure it again

Personally, given the information you've provided, I'd prefer using a Set here because it requires less typing.

Ok, but for real, which is faster?

My gut says the Set approach, and I think it'd take less heap space too. This should be a fairly simple thing to test, just a bit tedious to set up.

Here's my anon apex:

DateTime beforeDTControl, beforeDT1, beforeDT2, afterDTControl, afterDT1, afterDT2;
Long dtControl;
Integer beforeCPUControl, beforeCPU1, beforeCPU2, afterCPUControl, afterCPU1, afterCPU2, cpuControl;
Integer beforeHeap1, beforeHeap2, afterHeap1, afterHeap2;

Integer iterations = 100000;

// Set up benchmark data
Map<String, Account> acctMap = new Map<String, Account>();
Set<String> acctNameSet = new Set<String>();
List<Integer> randomIndex = new List<Integer>();
Long heapBefore = Limits.getHeapSize();
for(Integer i = 0; i < iterations; i++){    
    String name = 'testAcct' + i;
    acctMap.put(name, new Account(Name = name));
    randomIndex.add((Math.random() * 499).intValue());
}
Long heapAfter = Limits.getHeapSize();
acctNameSet = acctMap.keySet();
Long heapAfter2 = Limits.getHeapSize();

system.debug(heapAfter - heapBefore);
system.debug(heapAfter2 - heapAfter);
Set<String> randomNamesSet = new Set<String>();
for(Integer i = 0; i < 500; i++){
    Integer rand = (Math.random() * 10000000).intValue();
    randomNamesSet.add('testAcct' + rand);
}
List<String> randomNamesList = new List<String>(randomNamesSet);

// Timing our common loop so that we can remove its effect on the results
beforeDTControl = DateTime.now();
beforeCPUControl = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
}
afterCPUControl = Limits.getCpuTime();
afterDTControl = DateTime.now();

dtControl = afterDTControl.getTime() - beforeDTControl.getTime();
cpuControl = afterCPUControl - beforeCPUControl;

beforeDT1 = DateTime.now();
beforeCPU1 = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
    Account acct = acctMap.get(name);
    Boolean contained = acct != null;
}
afterCPU1 = Limits.getCpuTime();
afterDT1 = DateTime.now();

beforeDT2 = DateTime.now();
beforeCPU2 = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
    Boolean contained = acctNameSet.contains(name);
}
afterCPU2 = Limits.getCpuTime();
afterDT2 = DateTime.now();
    
system.debug(String.format('map.get approach:\nClock Time elapsed: {0}\nCPU Time used: {1}', new List<String>{
    String.valueOf(afterDT1.getTime() - beforeDT1.getTime() - dtControl),
    String.valueOf(afterCPU1 - beforeCPU1 - cpuControl)
}));
             
system.debug(String.format('set.contains approach:\nReal Time elapsed: {0}\nCPU Time used: {1}', new List<String>{
    String.valueOf(afterDT2.getTime() - beforeDT2.getTime() - dtControl),
    String.valueOf(afterCPU2 - beforeCPU2 - cpuControl)
}));

The results of 5 runs (100k operations) are as follows:

- run 1 run 2 run 3 run 4 run 5
map.get() 315ms clock, 297 CPU 354ms clock, 279 CPU 280ms clock, 257 CPU 355ms clock, 275 CPU 302ms clock, 294 CPU
set.contains() 346ms clock, 274 CPU 391ms clock, 312 CPU 230ms clock, 231 CPU 292ms clock, 274 CPU 338ms clock, 257 CPU

Conclusion

The run-to-run variance within each approach is on par with the difference between them, so there is no significant performance difference between the two approaches.

I was slightly kind to the map.get() approach in my measured runs by having the .get() and the comparison to null evaluated in a single expression (saving one assignment operation), but this difference is insignificant.

In either approach, you're looking at a cost of around 0.00275 CPU units per call. Like I said, this is a micro-optimization. The biggest difference here would be in characters typed.

The Set approach also takes less heap space (since you aren't storing the value as well as the key like you are with the Map approach). The Set approach takes roughly 57% of the heap space that the Map approach does in my test, and that would likely be even more in favor of the Set approach in real usage. Even if your query returns a single field, you automatically get the Id (and recordTypeId if you have a custom record type for the object).

4
  • 5
    +1 for running the actual performance numbers! Nov 10, 2021 at 15:47
  • Thanks for all that work. I really did not know where to start with to do that sort of comparison, and - as I stated in a comment on Kris's answer - honestly the reason I suggested the change was as much for readability and ease of following the code (and definitely less typing as you stated) as anything else. I didn't think about performance, really, until that blanket statement was made; and to be completely frank, heap space/size never appeared on my radar. Thanks for that insight as well.
    – Moonpie
    Nov 10, 2021 at 16:34
  • 1
    I might substitute the term "clock time" for "real time".
    – Adrian Larson
    Nov 10, 2021 at 16:38
  • 2
    By the way, the variation in time is mostly just server load. Under ideal situations, both methods behave nearly identical in terms of speed, as the underlying b-tree is used in very similar ways regardless; the Map takes very, very slightly longer because it also has to associate the key to a value.
    – sfdcfox
    Nov 10, 2021 at 16:44
13

I'd come at this from a different direction. I don't think the performance aspect is that interesting - it essentially falls into Premature Optimization and I presume the difference is negligible between the two methods.

sfdcfox has a good answer here that compares, not your situation, but containsKey() and get() within Map and makes the following statement

If you write code that ever only uses containsKey and doesn't use get, you should be using a Set, not a Map

It seems your code falls into the above as, from what you showed:

  • it seems to be using get() to accomplish the same thing as containsKey()
  • never uses the value of the map it stores except to check if it exists

Why bother with the storing a map/value if it's not going to be used? Not to mention the extra variable initialized to store the map's value to check if it's null. Technically, you could get rid of storing the value from the get() like so

if((groupMap.get(targetGroupName) != null)){

}

But, the point remains, there doesn't seem to be a use case for a map if you're not going to use the value. Those are the kinds of details/decisions you can bring up in discussions that are easier to grasp (less heap, confusing to readers, etc) rather than necessarily running large performance tests and arguing milliseconds if performance isn't already the concern.

The last interesting aspect, that I hinted above, is readability which I believe is more important in these types of reviews/questions. What is more readable? Different teams may come to different conclusions - but, I'd argue a contains() in Set or containsKey() in Map makes more sense if that's the only purpose you're doing (checking if it exists) versus a Map.get() which tends to imply you'll be utilizing whatever you're getting.

2
  • 1
    While it's true that premature optimization is the root of all evil, I have seen cases where get/put/contains/containsKey becomes so expensive that it's worth minimizing the number of calls used. That said, this is a heap issue, as you identified, rather than a speed issue. Definitely should use a set when called for.
    – sfdcfox
    Nov 10, 2021 at 16:22
  • 4
    To be honest, the reason I suggested the change was primarily because of readability. When I was reading through the code the first time, I was somewhat confused and thought that I had missed something. Then on a subsequent reading I realized the map value was never used/not needed, and my first thought was, "Why not just use a set?". My thoughts were not initially about performance per se, they just went there after that blanket statement was made. I did look over that sfdcfox answer & its associated question, but I overlooked that statement you quoted - thanks for that, too.
    – Moonpie
    Nov 10, 2021 at 16:23
10

The important thing isn't which method you use, but rather how many times you use them. All of the methods (get/put/add/remove/contains/containsAll) all essentially have to call a method to identify the correct "slot" first. That looks something like this:

Map<Integer, List<Object>> internalStorage = new Map<Integer, List<Object>>();
public Object findObject(Object source) {
  Integer hashCode = source.hashCode();
  if(!internalStorage.containsKey(hashCode)) {
    internalStorage.put(hashCode, new List<Object>());
  }
  Object[] possibleMatches = internalStorage.get(hashCode);
  for(Object possibleMatch: possibleMatches) {
    if(possibleMatch.equals(source)) {
      return possibleMatch;
    }
  }
  return null;
}

Obviously, it is not written like this literally, but you can imagine that's how it works. The actual implementation is, I believe, a b-tree structure, meaning that it uses O(log(2)) search time efficiency.

It takes longer for every power of two storage of hash codes (2, 4, 8, 16, 32, etc), meaning it can handle searching and storing hashes very efficiently exponentially better than using a List. And, of course, there's two different versions of this method; one for just searching (e.g. returns early if no hashCode is found) and one for storing potentially new values.

It first calls .hashCode, sees if there's an existing "bucket"; if not, a new one is created. Then for each item in the bucket, we call .equals to find a match.

This process can be expensive. Therefore, it is safe to say that calling .containsKey and .get is twice as expensive as just .get, whatever that means based on the incoming data.

So, given that, both versions are essentially the same, as far as performance is concerned. However, note that the Map will, by definition, use more Heap (memory) than just a Set, since you need to store the key and value.

In other words, I'd choose the Set if it makes sense, which it appears to. Heap is very easy to run out of, even compared to CPU time, so if you can save significant amount of bytes, I'd go for it. Also, you might be interested in reading more about heap, which I like to talk about time, and time, and time again (and probably more, I love speaking geek and technical details when I can).

2
  • 4
    So you're basically saying that you've talked about that subject heaps of times?
    – Moonpie
    Nov 10, 2021 at 17:03
  • 2
    For the curious, you can search by user (ex. sfdcfox) and the tag heap here. Or by the tag performance here Nov 10, 2021 at 17:12
9

I ran some benchmark tests based on your two examples. I assumed going into it the difference was going to be slight and the results seem to reflect that. Based on your use case, I don't see a reason to build a map at all since you're most interested in whether the keySet of the map itself contains a value (related, you can call containsKey on a map much like contains on a set). Your most likely performance hit will be in storing all of your map values in memory and not necessarily CPU time in accessing your data structure.

A few notes on my test:

  1. I'm using a traditional for-loop so that I can traverse the data set 100,000 times. There are performance differences between this loop syntax and the Apex for-in loop syntax.
  2. I'm using a map with 100 mock values in it. The size of the map or set shouldn't be a factor in performance where CPU is concerned, only in heap being used.
  3. The if statements are copied from your sample code, only I'm never interested in the loop actually exiting early so the conditions are the inverse so that the loop runs all the way through.

Using Map.get()

Map<String, String> mockMap = new Map<String, String>{
    'Land iguana' => 'Conolophus subcristatus',
    'Goliath heron' => 'Ardea golieth',
    'Pelican, great white' => 'Pelecans onocratalus',
    'White-faced whistling duck' => 'Dendrocygna viduata',
    'Bottle-nose dolphin' => 'Tursiops truncatus',
    'Bee-eater, nubian' => 'Merops nubicus',
    'Duck, white-faced whistling' => 'Dendrocygna viduata',
    'Galapagos hawk' => 'Buteo galapagoensis',
    'Egyptian cobra' => 'Naja haje',
    'Snake, carpet' => 'Morelia spilotes variegata',
    'Feral rock pigeon' => 'Columba livia',
    'Red-capped cardinal' => 'Paroaria gularis',
    'Eastern boa constrictor' => 'Acrantophis madagascariensis',
    'Eastern grey kangaroo' => 'Macropus giganteus',
    'Bear, grizzly' => 'Ursus arctos',
    'Duck, white-faced whistling' => 'Dendrocygna viduata',
    'Masked booby' => 'Sula dactylatra',
    'Squirrel, grey-footed' => 'Paraxerus cepapi',
    'Mississippi alligator' => 'Alligator mississippiensis',
    'Southern hairy-nosed wombat' => 'Lasiorhinus latifrons',
    'Squirrel, eastern fox' => 'Sciurus niger',
    'Malleefowl' => 'Leipoa ocellata',
    'Heron, giant' => 'Ardea golieth',
    'Great white pelican' => 'Pelecans onocratalus',
    'Ox, musk' => 'Ovibos moschatus',
    'Dusky gull' => 'Larus fuliginosus',
    'Black-throated butcher bird' => 'Cracticus nigroagularis',
    'African buffalo' => 'Snycerus caffer',
    'Palm squirrel' => 'Funambulus pennati',
    'Lizard, frilled' => 'Chlamydosaurus kingii',
    'Brown capuchin' => 'Cebus apella',
    'Monitor, two-banded' => 'Varanus salvator',
    'American woodcock' => 'Scolopax minor',
    'White-winged dove' => 'Zenaida asiatica',
    'Guanaco' => 'Lama guanicoe',
    'Crowned eagle' => 'Spizaetus coronatus',
    'Long-nosed bandicoot' => 'Perameles nasuta',
    'Adouri (unidentified)' => 'unavailable',
    'Lesser flamingo' => 'Phoeniconaias minor',
    'Wagtail, african pied' => 'Motacilla aguimp',
    'Boa, malagasy ground' => 'Acrantophis madagascariensis',
    'Red and blue macaw' => 'Ara chloroptera',
    'Barbet, crested' => 'Trachyphonus vaillantii',
    'Buffalo, american' => 'Bison bison',
    'Siskin, pine' => 'Carduelis pinus',
    'Boa, columbian rainbow' => 'Epicrates cenchria maurus',
    'Cat, kaffir' => 'Felis silvestris lybica',
    'Monitor, two-banded' => 'Varanus salvator',
    'Swan, trumpeter' => 'Cygnus buccinator',
    'Tsessebe' => 'Damaliscus lunatus',
    'Mocking cliffchat' => 'Thamnolaea cinnmomeiventris',
    'European shelduck' => 'Tadorna tadorna',
    'White-tailed jackrabbit' => 'Lepus townsendii',
    'Marmot, yellow-bellied' => 'Marmota flaviventris',
    'Crab (unidentified)' => 'unavailable',
    'Duiker, common' => 'Sylvicapra grimma',
    'Hyena, spotted' => 'Crocuta crocuta',
    'Pelican, australian' => 'Pelecanus conspicillatus',
    'Bird, magnificent frigate' => 'Fregata magnificans',
    'Mexican wolf' => 'Canis lupus baileyi',
    'Emu' => 'Dromaeus novaehollandiae',
    'Barking gecko' => 'Phylurus milli',
    'Eastern indigo snake' => 'Drymarchon corias couperi',
    'Salmon, sockeye' => 'Oncorhynchus nerka',
    'White-fronted bee-eater' => 'Merops bullockoides',
    'Antelope, roan' => 'Hippotragus equinus',
    'Bent-toed gecko' => 'Cyrtodactylus louisiadensis',
    'Sable antelope' => 'Hippotragus niger',
    'Tammar wallaby' => 'Macropus eugenii',
    'American badger' => 'Taxidea taxus',
    'Glider, feathertail' => 'Acrobates pygmaeus',
    'Weeper capuchin' => 'Cebus nigrivittatus',
    'Civet, small-toothed palm' => 'Arctogalidia trivirgata',
    'Coqui partridge' => 'Francolinus coqui',
    'White-lipped peccary' => 'Tayassu pecari',
    'Red-billed toucan' => 'Ramphastos tucanus',
    'Pigeon, wood' => 'Columba palumbus',
    'Cockatoo, red-breasted' => 'Eolophus roseicapillus',
    'Peacock, indian' => 'Pavo cristatus',
    'Carpet python' => 'Morelia spilotes variegata',
    'Monkey, black spider' => 'Ateles paniscus',
    'Black-backed jackal' => 'Canis mesomelas',
    'Lesser mouse lemur' => 'Microcebus murinus',
    'Crested barbet' => 'Trachyphonus vaillantii',
    'North American red fox' => 'Vulpes vulpes',
    'Snake (unidentified)' => 'unavailable',
    'Jackal, silver-backed' => 'Canis mesomelas',
    'Wolf, timber' => 'Canis lupus lycaon',
    'Chuckwalla' => 'Sauromalus obesus',
    'Sugar glider' => 'Petaurus breviceps',
    'Heron, green-backed' => 'Butorides striatus',
    'Blackbird, red-winged' => 'Agelaius phoeniceus',
    'Red meerkat' => 'Cynictis penicillata',
    'Wood pigeon' => 'Columba palumbus',
    'Starling, greater blue-eared' => 'Lamprotornis chalybaeus',
    'Giant otter' => 'Pteronura brasiliensis',
    'Suricate' => 'Suricata suricatta',
    'Flicker, field' => 'Colaptes campestroides',
    'Red-cheeked cordon bleu' => 'Uraeginthus bengalus'
};

List<String> commonNames = new List<String>(mockMap.keySet());
Integer commonNamesSize = commonNames.size();
String targetName;
String name;

Integer startTime = Limits.getCpuTime();
for(Integer i = 0; i < 100000; ++i) {
    name = commonNames[Math.mod(i, commonNamesSize)];
    targetName = mockMap.get(name);
    
    if(targetName == null) {
        break;
    }
}

System.debug('Elapsed CPU time = ' + String.valueOf(Limits.getCpuTime() - startTime));

Using Set.contains()

// Map instantiation code left out for brevity, see the code block above.

List<String> commonNames = new List<String>(mockMap.keySet());
Set<String> nameSet = mockMap.keySet();
Integer commonNamesSize = commonNames.size();
String targetName;
String name;

Integer startTime = Limits.getCpuTime();
for(Integer i = 0; i < 100000; ++i) {
    name = commonNames[Math.mod(i, commonNamesSize)];
            
    if(!nameSet.contains(name)) {
        break;
    }
}

System.debug('Elapsed CPU time = ' + String.valueOf(Limits.getCpuTime() - startTime));

Results

These code blocks were run in execute anonymous 5 times each.

╔═════╦════════════╦══════════╗
║ Run ║ Map (ms)   ║ Set (ms) ║
╠═════╬════════════╬══════════╣
║ 1   ║       1,238║     1,234║
║ 2   ║       1,344║     1,314║
║ 3   ║       1,267║     1,277║
║ 4   ║       1,481║     1,242║
║ 5   ║       1,376║     1,414║
╠═════╬════════════╬══════════╣
║ Avg ║       1,341║     1,296║
╚═════╩════════════╩══════════╝

Set.contains() wins by about 45ms.

3
  • 1
    If you're interested, Stackexchange did (somewhat) recently introduce the ability to format things as a table (which I used in my answer). It's basically just "have enough pipes to contain your columns" and "add a |-|-|-|...| line between your header and rows"
    – Derek F
    Nov 10, 2021 at 16:01
  • Wow, thanks for all of that work. As I stated on Derek's answer, I did not know where to start for doing such a comparison, and that performance did not really cross my mind until that blanket statement was made. I proposed that change mostly for readability/ease of following the code. I essentially thought what you stated: "I don't see a reason to build a map at all since you're most interested in whether the keySet of the map itself contains a value...."
    – Moonpie
    Nov 10, 2021 at 16:31
  • 1
    I would say that map/set size will have some impact on CPU usage, with additional layers in the bucket tree to be traversed, though not a huge impact.
    – Phil W
    Nov 10, 2021 at 22:34

You must log in to answer this question.

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