AngelCodeFont Class Performance Update
Jamie Hill who regularly comments on the blog has come up with a great change to the AngelCodeFont class. One of the last items added to the class was Kerning, which was using an NSDictionary as part of its implementation. This was proving to be really slow, so Jamie has come up with a change which I’ve placed below along with his full comment.
Hi,
I’ve just come across and solved a massive bottleneck in my code and thought I’d share it as it’s a quick fix for huge performance gains.
I was running around 35 frames per second on the iPhone and couldn’t find any obvious way of speeding things up. I thought it could be to do with the kerning dictionary so disabled it in the font class. It turns out that I was also using kerning the the method that gets the width for the text and this was slowing things down drastically.
The solution has been to implement a lookup table in straight C, it takes up around 64k for each font but I think it’s a small price to pay for the increase in speed. I am not up to a full 60 frames per second in my 1st gen iPhone.
I define, in place of the kerning dictionary the following (apologies if the code isn’t formatted properly):
// In the header file char kerning[256][256]; // When looping through the kerning read from file char firstCharID = [[properties objectForKey:@"first"] intValue]; char secondCharID = [[properties objectForKey:@"second"] intValue]; char kerningAmount = [[properties objectForKey:@"amount"] intValue]; NSLog(@"Kerning for first: %d, second: %d = %d", firstCharID, secondCharID, kerningAmount); kerning[firstCharID][secondCharID] = kerningAmount; // The method that gets the kerning value - (int)kerningForFirst:(unichar)first second:(unichar)second { return kerning[(int)first][(int)second]; }
Thanks for the info Jamie, that is something which will be going straight into my code :o)
Mike
16 Comments
mike on June 26th, 2009
@Pablo, thanks for the feedback. Jamie did say in his comment that it was not the most efficient use of memory. I like the sound of the approach you have taken.
If you are able to share any code when its ready that would be great and certainly help people out I’m sure. I’ll have to take a look at uthash as I’ve not heard of that.
Mike
mike on June 26th, 2009
Just had a look at uthash and it looks excellent. That could really sort out a bunch of problems I’ve had where an NSDictionary would be perfect but I don’t want to use it because of performance.
I’m certainly going to try it out and I’m sure others will as well.
Nice find Pablo.
Mike
Anonymous on June 26th, 2009
Great, simple but effective. Thanks.
@Mike
Hows tutorial 10 coming along?
mike on June 26th, 2009
Its getting there. I’m just tidying up some code and working on structure for the first part of the tutorial and I’ll then get it recorded. If things go to plan I should have something done this weekend :o)
Mike
Jamie Hill on June 26th, 2009
@pablo, I wasn’t completely happy with the amount of memory needed for this but figured 64k per font was a small price to pay for the sheer speed of this approach. I will look into uthash hash I could do with a fast way of handling hashes in general.
IPhoner on June 26th, 2009
What’s Kerning?
Pablo on June 27th, 2009
I copied all of my kerning code to your version of AngelCodeFont. To be honest I didn’t do much testing, neither did I bother commenting on my code (sorry, but I’m swamped with other work at the moment :( ). However the basics are working and it should help you see how to use uthash, which is unfortunately not very intuitive. The included file is a modified version of the AngelCodeFont files found in tutorial 6. I also bundled uthash.h which you’ll need to add to your project for this to work. You can find a zip file with all of this here. Hope this helps.
PS. I still plan to release my own classes sometime in the future but I need to get some free time to add some features which I personally don’t use but that any self-respecting font class should have :P
Pablo on June 27th, 2009
Oh, I forgot.
@IPhoner
In a font, there are certain pairs of letters that have different spacing between them. for example in “Wo” there’s less space between the W and the o than in “WO”. This pairs of letters are called kerning pairs, and the space between them is called kerning.
A Person on June 27th, 2009
Could you re-post the Angle code Font files, its hard for me to understand were this goes.
Jamie Hill on June 30th, 2009
Hi Mike sounds like you are making progress on optimising you rendering, just thought I’d share some of my ideas as I now have my tilemap up and running using the buffer class idea I sent you. The speed is up to 60fps except for when touches happen where it drops down to about 47 (this is rendering the same tilemap as in your example and a load of text).
What I’ve done is to create an array of all possible tiles in the MapSet class. This may use very slightly more memory for each tile, however, this way all the vertices and texture coords can just be referenced in glDrawElements. I then have a renderTileID:theID x:coordX y:coordY which handles all the buffering as 1 tileset normally equates to 1 texture.
Hope this helps it’s working nicely for me although I still need to optimise further to get up to 60fps with touches.
A Person on July 1st, 2009
@mike wouldn’t it be better if Frame was structure and there was tile structure aswell
mike on July 1st, 2009
@A Person, absolutely. There is an overhead in using objects in Objective-C. The original idea was to keep the code as much Objective-C as possible to start off with. This is so people could see the concepts using clear OO rather than things being hidden inside a more procedural approach.
For some things though, games being one of them, there are good reasons for using structures and its something I’ll go back and change.
I’m planning once I’ve got all of the core topics covered to go back and work on enhancing the code to improve performance. I’ve already created a new render manager which batches up geometry, texture and colours into a single Interleaved Vertex Array and loads that into a Vertex Buffer Object from where it renders. I’m not going to be releasing that code just yet as I’ve got more work I want to do on it, but it will find its way into a tutorial at some point :o)
In the mean time, if anyone has made changes to the code from the blog which has improved performance and wants to share, please feel free :o). Some have already been sharing their findings and its great to see what ingenious ideas people have around common problems.
Mike
Jamie Hill on July 1st, 2009
@mike. I’ve just noticed something interesting. It seems to be common knowledge that interleaving vertex and texture is faster, however, doing that there is no easy way of saying “I already have the texture coords for this so don’t bother calculating again and instead use pointer to existing” whereas there is with keeping them separate. So I am actually getting better performance storing them as two separate arrays due to being able to reference the same data when possible.
I’m sure there must be a way of doing this with interleaved data, but I can’t see anything obvious with my very limited experience of this stuff.
mike on July 1st, 2009
Hi Jamie
I am experimenting with this myself at the moment. One way to do this is to load an images vertices, tex coords and colour info into an Interleaved vertex array. Then when updating the location of the image, you just change the vertices for that image in the IVA, you don’t change the tex coords. I’m doing this in a skunk works I’ve got going by registering every new Image with my Render Manager which returns to the Image class a pointer to an entry in the IVA. This entry contains a structure which holds the vertices, tex coords and colour info.
In the Image then I can make changes directly to the data in the IVA, say vertices only and leave the tex coords and colour info untouched.
It also means I keep a copy of the original vertices, tex coords and colour info within the image as well, so I can transform the original i.e. translate or rotate and put the results straight into the pointer into the IVA. At the moment this is given me around 500 quads with blending on the screen at 30fps, which I don’t think is that bad.
Mike
Ricardo Quesada on July 20th, 2009
Hi,
I tried to use uthash in cocos2d, but uthash has an strange bug.
When you include uthash.h in your project (you don’t need to use it), your game will perform ~5% worse.
I don’t think it’s a uthash bug. Instead I think it’s a gcc, but anyway, it’s a nasty bug.
Now, in cocos2d, I’m using a modified version of Chipmunk’s cpHashSet.
Pablo on June 26th, 2009
The problem with that code is that it wastes a lot of memory. char kerning[256][256] is basically an array of 65,536 char variables and most of the time you’ll be using only around 100 of them. Not to mention that if you plan on using a font with some of the less traditional characters you’ll end up with an even larger array.
The way I solved this in my code is by using a C hash table instead of NSDictionaries. For my hash table implementation I went with uthash which is defined entirely with macros to make it as fast as possible (and certainly a lot faster than NSDictionary). This way only the necessary memory is allocated and the code is still quite fast.
I’ve actually been meaning to release my own version of the AngelFont class which includes some nice additions to your version but I haven’t had the time to clean up my code for public consumption. But if anyone is interested in my kerning implementation just let me know.