Edward Kandrot’s Programming Blog

Ran into this today, I wanted to put an image picker onscreen. Sounds easy, lots of examples out there, but the problem is that they do not seem to work on Universal apps.

According the Apple docs for the iPhone/iPod, one creates an UIImagePickerController. The code sample for that work great on the iPhone/iPod. When I tried to run it under the simulator for the iPad, it crashes with this message: “On iPad, UIImagePickerController must be presented via UIPopoverController”. Kind of odd, I would think that the API designer would have made it so that it would just work on the new devices, but they failed to make it so. Digging around in the Apple docs, which is the largest part of my development day, since the APIs for the iPhone are… well, too complicated to get stuff do with.

Anyway, I found the iPad dev docs, which showed how to do this on the iPad: one queries to see if the class exists like this,
Class popoverClass = NSClassFromString(@”UIPopoverController”);
if popoverClass is not nil, then go for it. That seems to work on the iPad. But now iOS4 is out, so I decide to give the code a try - it crashed with this error: “-[UIPopoverController initWithContentViewController:] called when not running under UIUserInterfaceIdiomPad.”

So, to create a Universal iPad, iPhone, iPod, iOS4 app, query the interface is no longer good enough, since the new methods exist under iOS4, they just crash. Searching online for others with the same API problems, which is how I spend the rest of my day usually, I found that one also has to check if it is running on an iPad as well.

Summary: with the latest APIs, you have to know if the class exists, whether the method under the class exists, and which device you are running on, before you call any API. Since they can change any existing API to suddenly crash on a new device, how can one write code that is future-proof? I haven’t figured it out within Apple’s API design philosophy. Stuff that could easily be hidden or made to work as default, but allow for overriding if the programmer wants more control, seems to be a foreign concept at Apple. Code that would work fine and be 100% correct for the iPhone/iPod will just fail on the iPod - not sure I understand their thinking on this.

Edward

PS By the way, the problem with adding the “is iPad” check to the exist code is that it now leaves open the door for Apple to release a device that isn’t an iPad, but requires the UIPopoverController in order to access the UIImagePickerController. I have found no way in the docs or in searching online to write a simple program to display the picker that will work on current and future devices. Ideas?

I’ve been working on a few different iPhone/iPad apps recently: games, graphics, and utilities. I decided to put what I’ve learned to the test and write a simple fun graphic toy for the iPad. I submitted it last week and it is now for sale on iTunes! It is called StaticFlow - be sure to check it out (I’ve added a screenshot and will create a video soon).

StaticFlow on iTunes

I also launched a website for my iPhone/iPad apps: prey4.us. I originally registered the domain for a game I was working on, it was only in the planning stages. I’m thinking about merging ArcaneFuture.com and prey4.us to make an all encompassing website for all of my shipping apps, code snippets, and web apps. I’ll let you know if I do that.

While waiting for approval, I decided to enhance the app - it now works on the iPhone and the new iPhone 4. I added high res graphics in OpenGL, which took longer than I thought it would. The documents were a little fuzzy, sending me back and forth between different APIs, but I figured out that in my view initialization I had to add these lines:

NSString *reqSysVerScale = @”4.0″;
if ([currSysVer compare:reqSysVerScale options:NSNumericSearch] != NSOrderedAscending) {
self.contentScaleFactor = UIScale_;
}

where UIScale_ was the scale I was going to set. The reason I did that rather than just slap a 2.0f in there was that during the touch events, it appears that the locations are not scaled. So, if the code gets a touch event at (101, 102), the code has to pass along (202, 204) to my hit detection code. I was unsure of what scale I could support without slowing down the iPhone, so I the view calculates the scaling the the processor can support, sets UIScale_, which is then used to notify the view of the new scaling, and is used later on by the touch handling code to get the correct hit detection coordinates.

It appears the scaling is easy if one isn’t using OpenGL on the iPhone iOS4 - it all happens behind the scenes by the programmer having images at both normal and scaled resolutions, then the OS selections the correct graphics for the device. Generating the graphics in OpenGL on the fly is the uncommon case, so it requires more work by the programmer, and it is less documented.

Edward

Just ran into this today while working on an iPhone app. I created some shaders for OpenGLES 2.0 and added them to the project. When I built, it would complain with this:

warning: no rule to process file ‘$(PROJECT_DIR)/Shaders/Simple.vert’ of type sourcecode.glsl for architecture i386

I wasn’t sure what it meant (searching online wasn’t illuminating), so I moved on to running my app. When I ran it, it would fail. I tracked down the failure to this line:

vertShaderPathname = [[NSBundle mainBundle] pathForResource:@”Simple” ofType:@”vert”];

which was returning nil. I did some searching online and found people talking about similar problems, but their solutions didn’t work for my problem.

I’m new to XCode, so I still do not know all of what it can do and how to set its options, so this is probably something most XCode developers know, though since I couldn’t find this solution anywhere else online, I am writing it down here.

Under XCode, there is a Targets turn-down under Groups & Files. Under Targets, there is the target name, which is also a turn-down. Under there are “Copy Bundle Resources” and “Compile Sources”, which lead to my solution. Sure enough, under “Compile Sources” were my shaders! So, I moved them to “Copy Bundle Resources”, recompiled, and ran it.

After this simple change, the bundle code worked correctly because XCode was finally copying over the files to be included in my final app. I didn’t find anything about this while searching, it is probably all there somewhere, but without the warning or keywords I’ve tried to add to this post. I hope this helps someone else!

Summary: the warning was caused by XCode trying to compile my shaders rather than just copying them to my app. Moving the files under the Targets from “Compile Sources” to “Copy Bundle Resources” fixed the warnings and allowed the app to locate the files when running.

-Edward

I went to NVIDIA to work on CUDA - I thought it was a very interesting architecture and the wave of the future for programming. Maybe I will talk about CUDA more in a future blog post, since this is supposed to be about my experiences with code. I have notes about various other code experiences, but I’ve been lacks about actually updating this blog - something I hope to change.

To kick it off, I’ll just talk about The Book. Jason Sanders and I just finished a book on CUDA called (according to Amazon): CUDA C by Example. The name should be close to that when it ships in a few months. If you want to pre-order from Amazon, click here.

What does the book cover? The target audience are people who know how to write programs in C, but want to learn CUDA. The book goes step by step through the basics for the first part of the book, then covers more advanced topics in the second half. CUDA will allow you to use your NVIDIA GPU (if it is CUDA capable) as a massively parallel compute processor - one could easily have 30,000 threads running, with many more scheduled. For example, if you wanted to do a ray tracer, you could have a thread per pixel. Before I started at NVIDIA, I took a simple ray tracer (very simple) and was able to get it to run in 30 frames per second with less than an hours work. I’ll try to find the code and upload it here at some point.

Well, I hope to write more in the near future! I am starting in on some new projects, so my plan is to talk about them here.

Edward

yahoo! destroyed 10 years of movie club data the other day. All of the movie reviews from club members, all of the movies we have seen, etc, gone. So, I decided to create a new version of the club on my server. There was something called phpBB already there, so I used that. Wow, does it really lack some nice features, but at least it is functional.

As soon as I created the club, I noticed a stream of spammers signing up. Very strange, since at the time I didn’t have any links to it, and searching for the spammers IP and email addresses, I found that they are commonly known spammers. Makes me think that phpBB gets a kickback…

I noticed that it was hard to block spammers with phpBB. Since I couldn’t block them by keyword, they could create user accounts, which would show up in the Member List as well as on the front page as New Accounts. So, they were still getting their message out, even though I deleted them as soon as I could.

So, today, I decided to put an end to this! I went into the php/sql code for phpBB and made it so that un-activated accounts do not show up in the Member List, nor in the count of active users, nor on the front page as new users. Until I active someone, it is like they never signed up!

I got the idea from this blog software. I have 2 or 3 spammers a day who create accounts here and post spam. But this blog software doesn’t show the world their spam until I approve it, which I never do. I am not sure why the default on phpBB isn’t to disable unapproved members - it is kind of weird in these days of spammers. Actually, it is weirder than that, they do not even have the option to do it - I had to learn enough php/sql to add this option for myself.

If anyone is interested in the changes, I will gladly give these back to the community - maybe 10+ lines worth of changes across 4-ish files to get it all working correctly for admin vs normal user.

-Edward

PS The movie club site: http://theedward.net/movieclub/ which is open to all who want to post about movies, or go see a movie with us on Tuesdays in the SF Bay Area (we try to go every Tuesday).

To recently took a job at NVIDIA to work on the CUDA team.  Someone told me about CUDA a few months ago, and I finally decided to look into it a month ago.  I was won over by its coding model and really wanted to work on it, so I sent my resume to NVIDIA.  Within a week or two, I was an employee!

I encourage you to look into CUDA.  The future of software development will tend towards multi-core and multi-thread programing and hardware.  I think CUDA is the best solution to this problem that I have found so far.

-Edward

I have this loop that loops over the 100 million plus entires of the Netflix Prize data set. I had read over the weekend something on reddit.com about performance, and there was a whole thread trying to answer the question: Why does performance matter? Many people were arguing that there is no reason to focus on performance. Some people even showed that by rewriting some examples, it would be slightly faster. Though, in their rewrites, they made the code more unreadable and not as optimal as it could have been. (it involved factoring numbers)

The biggest thing that most people seem to miss about performance is that why question. They think it can require large changes and if the code becomes unreadable, that is the cost of performance. I disagree. Performance can usually be gained with no cost to readability. As for why, because there is no reason to make the machine do more work than is needed to generate the correct answer. Back to my example.

This loop needed to update these 100 million pieces of data. In the loop, there was a number that worked out to be a constant. I had assumed that the compiler would generate the correct code: a divide by a constant can be turned into a multiply by the inverse for a huge speedup. It didn’t generate that code for me. After I made the code change myself, it went from 62 seconds to 47 seconds, just by adding a 1/ and changing the /= to a *=. Seems like that is worth it.

The second big win was from data ordering. In this loop, there is a 2-d array. I had moved this code from a different subsection where it was accessing the array like this: array[constant][variable] - iterating over the right-hand subscript. In this loop though, the access was different: array[variable][constant], which means it was not accessing memory contiguously per iteration. I made another small change, I swapped the subscripts and updated my dataset to reflect this change. After this change, the code went to 25 seconds per iteration.

So, with no changes in readability, I was able to go from 62 to 25 seconds, which is a big win. Why do it? Well, I can now run 2,000 iterations in 14 hours rather than the 34 hours it took before, to generate the exact same result. These are the kinds of important changes people should look for within their own code, once their algorithm works and is readable.

-Edward

I was reading a set of posts on reddit about functional programming.  At some point in the thread, the topic went to order of algorithms.  Someone commented that he had implemented something in an order n-squared since he was only using a few elements in the list.  He said that since no one noticed, it didn’t matter.  It was very frustrating to read that.

I wrote about this in my blog when I worked at Adobe and will write a bit about it now.  In all of my travels as a specialist in code optimization, the thing I see the most is people implementing code in O(n^2) that could be written in linear or constant time.  I know Netscape had a few of them when I was working on that project.  Since it is so pervasive, let me give some concrete examples of why/when/how to look for this.

Let’s create a table with elements being the number of elements in question, linear and n-squared being the time it would take to processes that number of elements with that algorithm:

See, it grows pretty fast!  If your n is 1, 10, or even 100, no one will notice a difference in the time.  But, if the number of elements goes a just a bit more, suddenly the time take will be noticeable.  But, there is a catch, sometimes it pays to use n-squared to much higher ranges.  The actual order is M*O(n) + K for linear, and M*O(n^2) + K for n-squared, with M and K different for each.  So, let us create a new table:  1000 * n + 1000 will be the linear, and 1 * n^2 + 1 will be the n-squared:

In this case, the linear takes more than a thousand elements before it is better than the n-squared algorithm.  M represents something that happens with each operation, like a data copy, while the K represents things like setup time, pre-calculating, etc.

So, the important thing to remember, algorithm selection depends on the dataset it will be used on.  In most cases, the number of elements will grow to be a lot larger than initially expect, so it almost always pays to switch to a linear algorithm if you can find one.  There are rare cases where the number of elements, the setup cost, and per operation cost of the linear doesn’t make it worth using, so you have to be aware of that.  This is only considering the speed cost of an algorithm, there is also the same set of arguments for memory cost.

I’ll leave with this: at one point Netscape’s browser used linked lists with no tail pointer (and it still might), which means the operation to build a linked list would be n-squared.  This saved a 4-byte pointer, and if the lists were small enough, there was no impact on performance.  The easiest way to find n-squared is feed in a thousand or even ten thousand elements and see where the code “freezes” the machine.  Creating a website with a thousand elements would create a thousand link list elements, which would cause a million operations, which would then take many seconds to display while the user is waiting.  Switching it over to linear would have meant that one could create a page with a million elements before seeing this kind of slowdown, and the thousand element page would have been instantaneous from the users perspective.

-Edward

It was over a year ago now… Project Euler - I was in the top 10, then they posted Problem 127. All of the problems there should execute in under the minute, and I thought I had optimized my code, but it was running for many minutes when I stopped it to see what was going on. I instrumented my code to see and saw that it was just chugging away. It would have taken 10-ish hours to complete! What was the problem? Python.

Quite a few of the problems at Project Euler require numbers to be larger than 32 bits. I originally used Project Euler to teach myself Python, and Python deals with big numbers fairly easily in code. My language of choice at the time, C/C++/Asm, didn’t. Even in Python, an interpretted language, I was able to get most of my solutions to run in under a minute - and that was the goal. Every so often, like times where the code iterated over large arrays, or basically anything that had a large number of real operations that had to be performed, I would have to switch back to C/C++. If the solution was taking minutes to run under Python, it would complete in a second or two under C/C++. But the time I saved writing the code in Python for the cases it could solve was worth it.

Now I have F# - my new favorite language. It also has big number support built in (so does Erlang). I was able to recode my old solution from memory from last year, and suddenly, I had a solution in under a minute! Well, it took a bit of work, since I had a bug in my code - I missed an overflow, so it was doing way to many calculations - it was taking minutes to generate the wrong answer. (comparing numbers to see if a calculation needed to be done, but the numbers being compared overflowed, so it was always doing the calculation, which was very slow as well as incorrect)

Some important things I learned from this year-ish journey:

1) People always tell me that only the order of the algorithm matter, linear speed ups will be swamped by faster machines. If the linear is hundreds, thousands, or millions, that is false. Rewriting critical code in a compiled or assembly language will always be of use.

2) Numbers shouldn’t have ranges. The overflow bug that cost me a day wouldn’t have existed if the language could handle numbers cleanly, not just integers. I had written the code in Erlang last night, but it was too slow to complete (linked lists as were the killer there). Erlang transparently works with all numbers, so that code couldn’t have that bug. Couldn’t. Bug-free code is the goal, so the languages need to handle these types of things transparently.

3) Getting things done is important. I used Python because it was trivial to write most of the code needed for Project Euler. The code only had to execute once (well, I reused a lot of it, so it had to execute once per problem), so optimizing my time speeds up the time from start to answer-in-hand. And that is what programming is about, getting the correct answer as quickly as possible.

-Edward

I was working on a new problem from the Euler Project - they post new problems every week-ish.  I decided to try this one in Erlang, to give myself more exposure to the language to see what I think of it.  I realized that something was missing, and actually, I think it is missing from most languages:  GCD.

 Alex Stepanov has given many talks about the importance of GCD - I think there are a few four hour talks out there that have been recorded and are very interesting to watch.  I realize more and more how right he is about this.  (His paper on GCD is linked to at Stepanov Papers, which I have linked to on the right - some great reading on that site.)

It seems to be a useful function, one that should be built in.  Given that it is not, I’ve included one in this blog post.  Code like this should only be written once, programmers should be able to focus on the problem at hand, not worry about missing common functions - it takes away from focus.  Sure, everyone could write their own, but the same is true for sin, cos, etc.  GCD should be a standard, it is in J the programming language.

Before I wrote this, I did some searching, and found that a few people had written a GCD and posted their code.  It was after looking at their code that I decided to open a dialog about this, since some of the ones I found were wrong, or longer, or more complex than the actual GCD calculation.

-Edward

gcd(M, 0) -> M;
gcd(M, N) -> gcd(N, M rem N).