Java code ported to Objective-C is very slow

Question

I want to illustrate a specific example to understand if there are better (and worst) methods when Java code is rewritten in Objective-C.

I ported the Java implementation of org.apache.wicket.util.diff.myers to Objective-C on OSX Snow Leopard (Xcode 4), but the result is very slow compared to the Java version.

The worst performing method is buildPath, basically it

• sparse access to the array (diagonal variable, this array is allocated inside the method and not returned)
• random access to the array (variables orig and rev)
• distribution of PathNode and its subclasses (an object with three properties, only a property is an element using an internal array)
• string comparison

Cocoa does not have any collection class for simple work with sparse arrays, so I allocated an array with malloc, this greatly improved the first version based on the NSDictionary and zillion NSNumber objects allocated for use as a key.

PathNode (s) distribution is done using the standard [[MyClass alloc] init] syntax, they are not auto-implemented because they are added to NSMutableArray (but released immediately after adding to the array)

Random access to the array is done using [NSArray objectAtIndex: index] I think (but I could be wrong) that moving it to C-like is not accelerated.

Do you have an idea to improve performance where you can find bottlenecks? Using tools, 74% of the time is spent on allocation, how can I improve selection?

EDIT I presented my actual github implementation, obviously this is an alpha version, not ready for production and not using the efficient Objective-C construct

Answer 1

You will go to a great start. You have profiled the code, isolated the actual bottleneck, and are now focused on how to solve it.

First question: which distribution is expensive? Obviously, you should focus on this first.

There are several effective ways to work with sparse arrays. First, consider NSPointerArray , which is designed to hold NULL values. It does not promise to be effective for sparse arrays, but @bbum (who knows such things) suggests that it is .

Next, take a look at NSHashMap , which is certainly efficient for sparse collections (this is a dictionary) and supports non-object keys (i.e. you don't need to create NSNumber ).

Finally, if distribution is really your problem, there are various tricks for it to work. The most common is the reuse of objects, rather than the destruction of one and the creation of another. Here's how UITableViewCell (and NSCell works differently).

Finally, if you switch to Core Foundation objects, you can create your own custom memory allocator, but it really is a last resort.

Note that 10.6 supports ARC (without nulling weak links). ARC dramatically improves performance over many common memory management patterns. For example, the very common “save + abstract + return” scheme is highly optimized in ARC. ("Save" does not exist in the language in ARC, but it still exists in the compiler, and ARC is much faster than manual execution). I highly recommend switching to ARC in any code you can.

Answer 2

You can use the NSPointerArray class as a replacement for your sparse array. NSPointerArray allows null elements.

If you publish code that generates the bulk of your distributions, we can help you more.