Month: August 2013

Buckets and Hashes

I thought it might be interesting to share the differences between the isEqual methods used by NSDictionary and my new class to shed some more light on the situation.

Here’s the way I set up Skill Plan items prior to writing the custom class:

[[NSDictionary dictionaryWithObjectsAndKeys: [EVESkill skillWithID:@2345], @“skill”, [NSNumber numberWithInteger:1], @“level”, nil];

Here’s the way that I set them up now:

[EVESkillPlanItem skillPlanItemWithSkill: [EVESkill skillWithID:@2345] atLevel:1];

Now, I can’t speak specifically to the code that Apple uses to write NSDictionary’s isEqual method, but here are the things that are called when I profiled with that first method:

-[NSDictionary isEqual:]
-[NSDictionary isEqualToDictionary:]
-[NSDictionary countForKey:]
-[NSDictionary objectForKey:]
-[__NSDictionaryl objectForKey:]
-[EVESkill isEqual:]
-[__NSCFNumber isEqual:]
-[__NSCFNumber isEqualToNumber:]
…

And on and on and on! All of this to find whether the dictionary I’m looking for is contained in the set. It would be much easier if there were some quicker way of doing this, and there is.

The reason that the object method is so much faster is that it sets up not only a custom isEqual method, but a hash function that speeds up the lookups. If you haven’t looked into hashing and buckets, Apple has a good video from WWDC 13 called “Designing Code for Performance” which discusses hash-based organization, about halfway through the video (note that you will need a developer account to watch the video):

https://developer.apple.com/wwdc/videos/index.php?id=224

Long story short, things are arranged in buckets based on the value of the hash function. If there are multiple objects with the same hash, then the hash is not sufficient to check for equality in the set or array. What does NSDictionary return for hash? I wrote a small piece of code that outputs the hash function for a dictionary of random elements with random keys. And it turns out that in this case the hash is equal to the number of objects in the table. No wonder it is so spectacularly slow for my case. Every dictionary must be compared.

So here’s a better hash function for my class:

-(NSUInteger)hash {

     return _skill.hash ^ _level;

}

Easy. And it produces a hash function that is much closer to uniqueness than the dictionary method which was exactly the opposite of unique. I don’t know if it is truly unique, but it certainly collides less than “every time.” For clarity, _skill.hash basically just returns the internal Skill ID number from the EVE Database, which is guaranteed to be unique. The bitwise or with the level number makes it such that the same skill of a different level does not produce the same hash.

So there you have it. When we need to know if the EVESkillPlanItem is in the Skill Plan NSOrderedSet, we have an O(1) lookup instead of an O(n). Pretty nifty, eh?

Speed and Profiling

I’m embarking on the most difficult project I’ve written so far, and I have been making extensive use of Instruments, especially the Time Profiler. If you’re like me, you opened up Instruments after downloading Xcode for the first time because it looked cool. Then you shut the computer and cried for a while. But recently, I’ve been noticing that my application tends to be sluggish during some dragging operations, and I wanted to figure out precisely why.

First, let’s talk a little about the project and why it slows down where it does. I’ve been playing a game called EVE Online. One of the core mechanics of this MMO is that your character trains skills 24 hours a day, whether you are online or not. But skills can only be queued if they will start within 24 hours. And certain skills can’t even be trained until other skills have been reached. As a result, people really want help in planning longer skill queues. There’s a really good program for this called EVEMon… which runs only on the PC.

Enter fledgling developer. EVE Online has not been available on the mac for very long, so the options for us are quite slim. I’m hoping to come up with something that works well and eliminates the need for Wine (which doesn’t run EVEMon well) or Bootcamp (which is annoying).

So, I’ve downloaded all of the skill information, set it up in arrays and dictionaries, etc etc. Next I created a class called EVESkillPlan, which works with my EVESkill items. These are my Models (although I’ve integrated some Controller functionality in the EVESkillPlan, which is supposed to be a big no-no – more on this in another post).

Here’s where the Instruments comes into play.

I’ve set up a drag and drop interface. New skills are dragged from the source list on the left to the right:

image

Dragging into an NSTableView gives you two opportunities to validate the operation, once to give feedback to the user as to whether or not the drop will succeed (tableView:validateDrop:proposedRow:proposedDropOperation) and once to actually tell the data object to follow through with the data manipulation (tableView:acceptDrop:row:dropOperation:). The problem in my app is that the validation operation takes too long, and performance begins to suffer as the drag operation continues.

So what’s causing the slowdown? This is where Instruments is helpful.

image

It turns out there is an extensive test of the validation method when the application loads character files from dis (or when they are downloaded from the EVE API), as the program attempts to make an EVESkillPlan instance from the skills that the character has already trained. This is probably a really bad way of doing things, as the skills that the character has already trained can be assumed to be valid, because the game won’t allow them to be trained out of order, so the validity test is unnecessary. But if it works well now, I don’t care. In any case, at this point, testing the loading time for the characters can show us where the slowdowns happen. Here’s an example trace as the application ran last week:

image

image

image

4.24s doesn’t seem like a lot of time, but it represents the slowest part of the drag operation. Can we speed it up?

You can use the Time Profiler to determine what is taking the longest amount of time in the app. Previous to today’s improvements, the code stored data in an NSDictionary that contained the EVESkill instance and an NSInteger for the level (skills range from Level 1 to Level 5, and must be trained in order of increasing level). If you look closely at the trace, you’ll find that the lookups for these NSDictionaries takes a considerable amount of time, owing to the fact that the NSDictionary equality test has a number of steps. What if we created a class that uses a faster isEqual: method?

EVESkillPlanItem is a simple class that does just that. It has two properties, an EVESkill instance and a NSInteger for the level of the skill. Equality requires that the EVESkill object and the level number are equal. This cuts out at least one step from each equality statement, since the NSDictionary first makes sure that the two dictionaries have the same number of items. Who needs that when you’re sure that they will? In any case, here’s the trace for the updated code:

image

image

Voila, 1.58s. Huge, huge improvement. Notice that the isEqual: method for EVESkillPlanItem is almost three times faster than the corresponding method for NSDictionary.

And I find that dragging is much speedier as well, so the main goal is fixed for the time being. It’s possible there may be more improvements to be made, but I can live with the performance for now. Interesting how much things got better. Time Profiler is your friend!