Results of the Evernote DevCup

Time flies! I just realized we didn’t offer any feedback about our participation in the Evernote DevCup back in July.

First of all, thank you so much for your support! We ranked 14th out of 174 contestants in public voting! That actually exceeded our expectations as we aimed for the 20th position (so drinks are on Julien!)

But even with all of your support, we didn’t make it to the finals. We would have loved to fly to San Francisco, but the six finalists all feature rich apps that merit their position. Congrats guys, and good luck! The conference is in a couple of days now, and I can’t wait to find out who will win the cup!

As for us, it was a truly great experience! Remember our post announcing our participation? Well, outside the slight frustration of not going to SF, the couple of days we spent building the Search for Evernote app was really worth it!

• We were able to correct a few corner case bugs which this new use case highlighted. It’s always better to find them yourself than let app developers stumble upon them :)
• We developed a new feature enabling prefix search on all words.
• Our participation led to an improved awareness of the company and helped our SEO.
• We created a new demo of the search lib which is much more compelling than Cities Suggest in many situations. It is actually a bit more than a demo for some people - as of today, it has 317 active users on google play!

That got us thinking… we may do this kind of contest again. But this time we’ll aim higher!

Algolia Search beta is out!

After a few months in the making, our first mobile library is finally ready to hit the shelves! Well, nearly! Before releasing it, we want all the feedback you can give us to ensure it’s bug-free, easy to use and responsive to your needs.

If you subscribed to the beta, you should already have received your access info. If not, you can request it directly on www.algolia.com.

You’ll be able to download both the iOS and the Android versions, along with all necessary documentation. Feel free to ask for any clarification or additional info. We’ll do a few technical posts which explore the product internals in the coming months.

We’re now eager to read your feedback! You just have one address to remember to report bugs, request features, or anything beta related: beta@algolia.com

Enjoy!

Free marketing @ WWDC 2012!

Let’s rewind time a bit. Back in June was the famous Apple Developer Conference, aka WWDC 2012. Algolia didn’t even have a website at that time, but what we did have is a friend who would attend: Thomas! That was an occasion we could not pass!

Thomas agreed to speak about us a bit and to invite people to visit our website. That simple action defined our deadline to have a website up and running. But wait! That would be better if people could also find the site when Googling our company name. That meant a few days to allow for indexing… and a tight deadline!

About two weeks of brainstorming and implementation went into the web site. Our goal was to have a clear presentation of our mobile search lib… and to be found on Google! And you know what? It’s damn difficult to do so in so short a time! Our site was up and running two days before the conf and we immediately submitted it to all search engines. Unfortunately we were not in first position when Googling for Algolia :(

Fortunately, things improved without delay. Two actions were particularly useful in helping our search rankings: our participation to the Evernote DevCup, and our blog opening! We quickly got the pole position for our brand and started to rank well for some key queries like mobile instant suggest :)

We also thought about creating some posters that explain our technology, but eventually we were so concentrated on the web site that we passed.

Result: Some awareness, one subscription to beta and more importantly, a running website! Next marketing related action would be to have a demo ready for LeWeb in London, but that’s another story…

And here is what you could see on WWDC whiteboards:

Thank you again for your help Thomas!

C/C++ is still the only way to have high performance on Mobile

When it comes to programming languages and performance, you can read all and its opposite on the web. It’s definitely a very controversial topic!

[Edit 15-Nov-2012] I had questions on reddit about the data-structures and algorithms we used. We develop an embedded search engine for mobile, and tests were done on our own data-structure that is far more efficient than SQLite or other platform options for this use-case. [/Edit]

For Algolia the story started when researching an instant suggest algorithm. I used Java for two reasons:

• Main reason: our first client was using Java on Google App Engine
• Secondary: at that stage, I was doing a lots of refactoring and Eclipse is very efficient for these tasks

Once our algorithm was designed, I started to optimize performance on a desktop computer (core I7 950). For this, I indexed all titles of the English version of Wikipedia (4 millions titles). I optimized the Java code mainly by reducing the number of allocations. All instant suggest queries were then faster than 10ms.

As we planned from the begining to support iOS and Android, I needed to optimize for high performance on mobile. I then ported the Java code to Android and ended up with a few modifications (we needed to support old Android versions which have not a full support of Java SDK).

In order to test performance, I created a small “demo” app: CitiesSuggest, a mobile application based on Geonames database to look for a city name. I filled the index with all places with a known population. In the end, the database contained 270 000 city names.

As could be expected, the resulting application was quite sluggish on my Galaxy S2. The worst queries could take more than one second of CPU.

I then applied all possible methods described in the Anroid documentation and was able to reduce the response time to 700ms for the longest queries. This is better but still gives end-users an impression of sluggishness! Fortunately, common queries worked well enough to present our very first demos at LeWeb’12 London. I was subsequently able to improve the user experience a lot by adding asynchronous support. At that point, we decided to start implementing the objective-C version for iOS.

I started a new implementation fully done in objective-C from scratch without any premature optimization. I then developed the same CitiesSuggest application for iOS. I first got stuck with some basic UI stuff. For example I needed to reimplement an UILabel that supports highlighting! The standard UILabel does no support this, and other implementations like Three20 just have too many dependencies (you can download AlgoliaUILabel on github, I released  the code under Apache licence). Once the UI was ready, I could see the actual performance was catastrophic! Instant suggest queries were between 200ms and 10 seconds on an iPhone 4S!

After profilling, I discovered that 95% of the time was spent in Objective-C messaging and ARC. Actually, I have millions of calls to very small methods with 1 or 2 lines of code, and I found a very good explanation in the internal of objc_msgSend (mainly on mikeask.com. There is in fact a hash table lookup behind objc_msgSend! This explains most of my performance problems.

To fix these problems, I started to replace all this low level objective-C implementation by a C++ implementation with inlined methods. Eventually, I finished with Objective-C code for high level classes while all the core was C++.

This change has dramatically improved performance with instant-search queries between 2ms and 90ms on a iPhone 4S. I struggled to find complex enough queries to reach 90ms! This resulted in a very nice user experience with a remarkably slick demo :)

After this succes, I decided to use the same C++ code on Android with Android NDK. With this approach I reduced our maximum query time from 700ms to 80ms on a Galaxy S2. But I was really disappointed by the Android display, as I did not reach the same level of interactive experience that I had with iOS. The display of results stays slower on Android, probably because I did not spend enough time to optimize this part.

In the end, I lost a lot of time with Java and Objective-C trying to optimize code when the real solution was to use C/C++. I am fully convinced that it is just not possible to reach the same speed with Objective-C only or Java only.

And there is also another good property with C++ code: Blackberry supports C++, and there is large chance that Windows Phone 8 SDK will support C++ when released in a few weeks. Actually, I do not see any other alternative than C/C++ when you are looking for performance on mobile devices, which is our case :)

I hope this article will prevent you from spending as much time on Java/Objective-C optimizations as I did.

iOS: When Automatic Reference Counting is a Bad Idea

I started developing for iOS in 2009 by learning about the Objective-C language. At that time ARC (Automatic Reference Counting) was not yet available and developers were responsible for alloc/release/autorelease. I found it pretty straightforward as it was very similar to C++ and the resulting code was very self-explanatory.

When ARC was released at the end of 2011 it made a great impression on me and looked like the perfect feature for any programmer coming from the Java world who was not familiar with memory management. I started using ARC and discovered a major flaw that completely changed my mind. Here is an example :

[Edit 28-Jan-2013] This post describes a bug in ARC that was fixed in Xcode 4.4.[/Edit]

Let’s start with an example in C++, the sample contains a constructor that allocates two vectors, a destructor that destroys them and a compute method that just performs a swap between the two vectors. This code is perfectly valid and a swap is the perfect operation when you have two sets of data to maintain because this is very efficient (just two pointers copy, no data copy).

class Example {
public:
  Example() {
    nextPositions = new std::vector<int>();
    currentPositions = new std::vector<int>();
  }
  ~Example() {
    delete nextPositions;
    delete currentPositions;
  }

  void compute() {
    // some code here
    std::swap(nextPositions, currentPositions);
    // some other code here
  }

private:
  std::vector<int>* nextPositions;
  std::vector<int>* currentPositions;
};

Before ARC the objective-C code was very similar and perfectly valid:

// headers
@interface Example : NSObject {
  NSMutableArray* nextPositions;
  NSMutableArray* currentPositions;
}
-(void) compute;
@end

// implementation
@implementation Example
-(id) init {
  self = [super init];
  if (!self)
    return nil;
  nextPositions = [[NSMutableArray alloc] init];
  currentPositions = [[NSMutableArray alloc] init];
  return self;
}

-(void) dealloc {
  [super dealloc];
  [nextPositions release];
  [currentPositions release];
}

-(void) compute
{
  // some processing stuff here
  NSMutableArray* tmp = nextPositions;
  nextPositions = currentPositions;
  currentPositions = tmp;
  // some processing stuff here
}
@end

The semantics are very clear, it is exactly the same as in C++.

So when you start using ARC you tend to do exactly the same thing with less code, and you just delete the dealloc method:

// headers
@interface Example : NSObject {
  NSMutableArray* nextPositions;
  NSMutableArray* currentPositions;
}
-(void) compute;
@end

// implementation
@implementation Example
-(id) init {
  self = [super init];
  if (!self)
    return nil;
  nextPositions = [[NSMutableArray alloc] init];
  currentPositions = [[NSMutableArray alloc] init];
  return self;
}

-(void) compute {
  // some processing stuff here
  NSMutableArray* tmp = nextPositions;
  nextPositions = currentPositions;
  // Wrong, at that step this is too late! nextPositions was deallocated
  currentPositions = tmp;
  // some processing stuff here
}
@end

The error does not come from a missing strong attribute, because instance variables are strong by default. The problem is that ARC does not generate code in the variable assignation. You should explicitely add properties and use “self.variableName” notation like in the next example. I would encourage ARC designers to read this excellent article by Joel Spolsky “Making Wrong Code Look Wrong”. This ARC usage is a perfect example of wrong code that looks perfect but leads me to the conclusion that ARC is not trustworthy.

Here is the correct version:

// headers
@interface Example : NSObject {
  NSMutableArray* nextPositions;
  NSMutableArray* currentPositions;
}
-(void) compute;
@property (strong, nonatomic) NSMutableArray* nextPositions;
@property (strong, nonatomic) NSMutableArray* currentPositions;
@end

// implementation
@implementation Example
-(id) init {
  self = [super init];
  if (!self)
    return nil;
  nextPositions = [[NSMutableArray alloc] init];
  currentPositions = [[NSMutableArray alloc] init];
  return self;
}

-(void) compute {
  // some processing stuff here
  NSMutableArray* tmp = self.nextPositions;
  self.nextPositions = self.currentPositions;
  self.currentPositions = tmp;
  // some processing stuff here
}
@synthesize nextPositions;
@synthesize currentPositions;
@end

I am surprised Apple hasn’t corrected that flaw yet. This is a major issue as ARC does not generate code for variable affectation like it does for properties (if one of you reads this post and has a complete explanation, please tell me!):

• Is it because of a performance issue? I would prefer to have no ARC at all than to see such a behavior.
• Is this case too complex to be handled? The problem is it undermines ARC’s utility and might get stuck at the prototype stage.

To me, this is a perfect example of a technology driven product. The engineers know their product so well that they forget to step back and look at it with a fresh eye to analyse the full complexity of their system.

And that leaves me with two important lessons we’ll try to apply to our products:

• Always organize user tests, even when your users are developers themselves!
• Always keep a fresh eye when trying to simplify a product (this one may prove particularly difficult!)

I hope you’ll tell us when we will (inevitably) break these rules!