That said, Objective-C++ is invaluable for integrating C++ into Objective-C. And while I am not a great lover of C++, it is a very useful language and there is a great deal of excellent code written in it that is well-worth reusing in your Cocoa projects. Many of Apple’s frameworks are implemented in C++.

So my recommendation for those who have existing C++ logic code has always been thus: write your UI in pure Objective-C (.m). Write your “middleware” in pure C++ (.cpp). And have a thin Objective-C++ (.mm) wrapper layer to glue them together. Your ObjC++ API should ideally exactly match your C++ API, just converting types (for instance converting std::string to and from NSString).

(As a side note, I also recommend that OS-related things like file management, network management, and threading all be handled natively. GCD is much better than pthreads. NSURLConnection is much better than writing your own C++ networking layer in BSD sockets. But this is tangental to the main point.)

Saying all that, how do you wrap a C++ object so that Objective-C can read it? This used to be a question that required some significant thought. See Wrapping C++, Take 2 Part 1 and Part 2 for my previous thinking on the subject.

Improvements in Objective-C have made all of the previous hoop-jumping irrelevant. The problem all my previous solutions was trying to solve was that you had to declare ivars in the header. Your ivar was a C++ class (which might be in a namespace or might be a template), and that made it difficult to declare in the header without forcing all the importers to be ObjC++. So to solve this generally you needed opaque types, or at the very least forward declared structs, etc. And it was all a big pain.

But that’s over. You can now declare all your ivars in the implementation file. So everything’s easy. Your wrapper class can have C++ ivars without having any impact on users of the wrapper class.

Consider a simple C++ class (but throwing in the headache of a namespace):

namespace MY {
class Cpp {
  public:
    std::string getName() { return _name; };
    void setName(std::string aName) { _name = aName; };
  private:
    std::string _name;
};
}

The wrapper for this is trivial:

@interface CPPWrapper : NSObject
@property (nonatomic, readwrite, copy) NSString *name;
@end

@interface CPPWrapper ()
@property (nonatomic, readwrite, assign) MY::Cpp *cpp;
@end

@implementation CPPWrapper
@synthesize cpp = _cpp;

- (id)init {
  self = [super init];
  if (self) {
    _cpp = new MY::Cpp();
  }
  return self;
}

- (void)dealloc {
  delete _cpp;
}

- (NSString *)name {
  return [NSString stringWithUTF8String:self.cpp->getName().c_str()];
}

- (void)setName:(NSString *)aName {
  self.cpp->setName([aName UTF8String]);
}
@end

Couldn’t be easier really. The one headache that really remains in my experience is enums inside of a namespace (or more generally enums declared in a C++ header). The best solution is to use #if __cplusplus blocks to strip away the namespace and still declare the enum in pure C. Do this if at all possible. Otherwise you’ll wind up with an C enum that mirrors the C++ enum. This is a maintenance nightmare, since changes to the C++ enum will often be missed in the ObjC enum, and you’ll get very difficult-to-debug errors with enum mismatches.

Just to ask and answer a possible question: why *Cpp and not just Cpp? The reason is that in almost all cases the C++ object will be created outside of your wrappers. So in almost all cases, there’s going to be a method like initWithCpp:(Cpp *)cpp. How does that work? Easy, wrap it in #if __cplusplus:

#if __cplusplus
#include "Cpp.h"
...
- (CppWrapper *)initWithCpp:(Cpp *)cpp;
#endif

Anyway, most of my research into opaque types and generally how to manage C++ wrappers has now become trivial. I’m just giving one more post to let you all know that. (And because Orpheus asked.) Post comments if there are more questions.

Except for price. github is often the most expensive. Especially if you need what I need, which is several small repositories, each with a small number of collaborators (often just one or two). But just a few of those can push you into the Medium plan, or even into the Bronze plan.So I was complaining about this to my wife. I say “Wife, github is just too expensive. Why do they have to be like that? I really like using them.”

“Oh,” says Wife. “What are we talking about?”

“Well,” I say, “it could easily be $25/month.”

“$300/year?”

“Yeah.”

“And it works really well? And makes business go more smoothly?”

“Yeah…?”

“And you need some service for this, right?”

“One way or another.”

“Get over yourself. Pay them.”

And I started to think about it. If I’d billed the time I’d already spent researching and designing scripts to work around issues, I’d probably have covered a year or two of service.

Some services have gotten so cheap, you get used to what you think they “should” cost. I remember haggling in markets in Shanghai and friends saying “Rob, you’re buying a scarf for $2 and you’re haggling over the last 50 cents.” My attitude was, yeah, but in Shanghai that scarf should be 8 RMB and she’s asking 14. At home I’d think nothing of paying $10, but in Shanghai I feel ripped off paying more than a buck. The whole Internet is a Shanghai market sometimes.

Quality is worth paying for. As a developer, I expect to be paid for the quality code I write. Time to pay others for theirs.

“One point in his article that McConnell did not address–programmer compensation does not vary accordingly. This is a telling point–if the difference is productivity can be 10X, why is it that salaries rarely fall outside the 2X range for experienced developers?” [emphasis in original]

He then provides some fairly satisfying answers. “The other guy is actually overpaid.” “You’re confusing coding with actual business value.” “Companies pay the least they can get away with.” etc. All his answers make good, intuitive sense. Unfortunately, despite being a longtime fan of Steve McConnell’s work, I believe most are irrelevant or incorrect.

Let me state this a little more concretely. If a company pays Alice $X, but Alice generates $10X in marginal value, then there is a very strong incentive for another company to offer Alice $2X and receive $9X in marginal value. Alice would almost certainly accept $2X, and a competitor would be idiotic not to pay it. As long as Alice were free to change employers at will, and as long as employers were capable of determining Alice’s value in even a vague way, this would naturally continue until there were little marginal value left (less than the friction of recruiting and moving and within the precision of determining Alice’s productivity). That is to say, there should not be much money left on the table. In the normal version of this story, there is a massive amount of money on the table. It’s hard to believe this continues indefinitely in a highly competitive, unregulated, and mobile industry like ours.

Arguing that it’s impossible to measure Alice’s productivity to any precision makes the entire discussion moot, since it eliminates the ability to say that Alice is 10x more productive. How did you decide that if productivity is unmeasurable? Even intuitive measurements would be sufficient to create a bidding war if there were really 10x value on the table.

It also seems unworkable that a company would continue to pay large numbers of people dramatically above their total contribution. Sure, here and there; large companies are quite inefficient in my experience. And at the executive level, I believe there is enough collusion between compensation committees and CEOs to make the system significantly inefficient. But almost any argument for this being systemic suggests that companies are highly altruistic. It’s hard to believe that a greedy company would hold onto a significant number of low-level employees that would be cheaper to fire and replace with no one.

I suggest that there’s another answer that doesn’t require long-lived massive inefficiencies in the market. I suggest that Alice is being paid in another way and that our “loser” employee provides some other value. I’m further claiming that the value Loser provides is reasonably close to the money that Alice foregoes. In other words, Alice is paying Loser for his service, and thus a reasonably efficient economic system in equilibrium is restored. I’m not claiming to have created this idea. It’s directly from R. H. Frank’s “Are Workers Paid their Marginal Products?” where it is examined in detail in several industries, including ones where it is much easier to determine precise productivity than ours.

To see how this works, let’s play it out in a system where productivity==pay. You have the option of two jobs, one with Company A and another with Company B. At Company A, you would be one of the most productive people there. In fact, you’d be twice as productive as the average employee. The average employee at A makes $50k (all numbers are total compensation).

Company B, on the other hand, has some of the most brilliant people in the industry. You’d be half as productive there as the average employee. Since the average employee at Company B is 4x as productive as the average employee at Company A, they also make 4x as much: $200k. So in either case, your “fair” compensation would be $100k. Which job do you choose?

Well, let’s think about it some more. At Company A, you’re going to be at the top of the pile. You’re going to get the best assignments, designing the most cutting edge stuff that Company A does. That’s going to be less cutting edge than Company B’s most advanced stuff, but at Company B you’re not going to work on the most advanced stuff. You’re going to be at the bottom of the pile there, one of the most junior people. You’re going to do maintenance on their legacy products. You’re going to do the bug fixes that the senior guys don’t want to do.

So you’re faced with a very productive company where you’re Loser or a less productive company where you’re Alice. The question is, what kind of compensation would you require from each company in order to be willing to work there? Different people weigh these things differently. Some people would take a huge pay cut to do grunt work for a brilliant company (I know a guy who did this). But I’m guessing for most people Company B would have to pay them more to be at the bottom of the pile than Company A would to be at the top.

Now the math behind the pay compression should come into focus. If you demand $110k to work at Company B, you’d still be one of the lowest paid people there. But the average employee would only be paid 1.8x as much for 2x as much productivity. You just created the “unfair” situation we’re talking about. On the other hand, if you choose to work on more exciting projects at Company A and are willing to do it for $90k, then you’re on exactly the other side of the coin.

What this boils down to is that without Loser, Alice can’t be at the top. Without someone to do the boring maintenance work, Alice would have to do it herself. So she willingly, if unconsciously, pays Loser a premium so she can work on cooler projects. Company B needs someone to do $100k junior work. You demand $110k to be junior there rather than $90k to be senior at Company A. So they pay Alice $10k less than her job is worth, you $10k more, and the system is back in balance. Except now you’re Loser and Alice keeps asking why she doesn’t make as much as her performance predicts.

This is not the only cause of what seem like unfair pay practices. There is absolutely a lot of inefficiencies in big companies that allow deadwood to coast. There are definitely politics that let do-nothings get to work on cool projects. In some cases Loser can make more than Alice for absurd reasons. But I’m arguing that these are the margins. If they were the primary cause, more efficient companies would destroy these idiotic firms by taking all their Alices. I’m saying that the core of the compression, the reason that 3x productivity can become 1.3x pay, is that it is the natural economic result of a free market working efficiently, and that Alice is paying Loser for her rank.

It may not be as satisfying an answer as “companies are messed up,” but I think it actually explains the situation most accurately.

Footnote: Frank has recently put out a new, related book called The Darwin Economy. I’m not a fan of the book, even when I agree with it, because it glosses over some important points too easily. But for $10 you can read the American Economic Association paper and see some of the real-world studies that back up this particular economic theory.

I’ll get back to writing about NEON assembly on the iPad in the next week or so.

For those who didn’t scribble notes fast enough, my Core Foundation presentation is attached (including the fix for my memory leak; was it Jay who found that?) I’ll make sure to fix the code in the book for the next edition.

Building a Core Foundation.pdf

In this installment, we’ll look at improving our algorithm. The code is available on github.

We tried the Accelerate framework, but it didn’t help us. The cost of the function calls obliterated our gains. What can we do? First, let’s look at the code again, and see if we’re doing anything foolish.

static inline CGFloat BezierNoPow(CGFloat t, CGFloat P0, CGFloat P1, CGFloat P2, CGFloat P3) {
  return
    (1-t)*(1-t)*(1-t) * P0
    + 3 * (1-t)*(1-t) * t * P1
    + 3 * (1-t) * t*t * P2
    + t*t*t * P3;
}

unsigned int copyBezierNoPow(CGPoint P0, CGPoint P1, CGPoint P2, CGPoint P3, CGPoint **results) {
  *results = calloc(kSteps + 1, sizeof(struct CGPoint));

  for (unsigned step = 0; step <= kSteps; ++step) {
    CGFloat x = BezierNoPow((CGFloat)step/(CGFloat)kSteps, P0.x, P1.x, P2.x, P3.x);
    CGFloat y = BezierNoPow((CGFloat)step/(CGFloat)kSteps, P0.y, P1.y, P2.y, P3.y);
    (*results)[step] = CGPointMake(x, y);
  }
  return kSteps + 1;
}

Notice how we’re recalculating a lot of things. For example, we calculate (1-t)*(1-t)*(1-t) twice with the same t. That can’t be good. What if we factor out the part that doesn’t change between x and y?

unsigned int copyBezierXY(CGPoint P0, CGPoint P1, CGPoint P2, CGPoint P3, CGPoint **results) {
  *results = malloc((kSteps + 1) * sizeof(struct CGPoint));

  for (unsigned step = 0; step <= kSteps; ++step) {
    CGFloat t = (CGFloat)step/(CGFloat)kSteps;

    CGFloat C0 = (1-t)*(1-t)*(1-t); // * P0
    CGFloat C1 = 3 * (1-t)*(1-t) * t; // * P1
    CGFloat C2 = 3 * (1-t) * t*t; // * P2
    CGFloat C3 = t*t*t; // * P3;

    CGPoint point = {
      C0*P0.x + C1*P1.x + C2*P2.x + C3*P3.x,
      C0*P0.y + C1*P1.y + C2*P2.y + C3*P3.y
    };

    (*results)[step] = point;
  }
  return kSteps + 1;
}

Hey, that gets us from 0.6s to 0.5s (10Mp/s). A 17% improvement’s pretty good. But let’s think about this some more. The values t can take are exactly dependent on kSteps, which is a constant for the program. And since the C variables depend only on t, that means they’re a fixed set as well. We should only have to calculate them once for the whole program. That seems a lot of work we don’t need to do. Let’s see how it turns out.

unsigned int copyBezierTable(CGPoint P0, CGPoint P1, CGPoint P2, CGPoint P3, CGPoint **results) {
  *results = malloc((kSteps + 1) * sizeof(struct CGPoint));

  static CGFloat C0[kSteps] = {0};
  static CGFloat C1[kSteps] = {0};
  static CGFloat C2[kSteps] = {0};
  static CGFloat C3[kSteps] = {0};
  static int sInitialized = 0;
  if (!sInitialized) {
    for (unsigned step = 0; step <= kSteps; ++step) {
      CGFloat t = (CGFloat)step/(CGFloat)kSteps;
      C0[step] = (1-t)*(1-t)*(1-t); // * P0
      C1[step] = 3 * (1-t)*(1-t) * t; // * P1
      C2[step] = 3 * (1-t) * t*t; // * P2
      C3[step] = t*t*t; // * P3;
    }
    sInitialized = 1;
  }

  for (unsigned step = 0; step <= kSteps; ++step) {
    CGPoint point = {
      C0[step]*P0.x + C1[step]*P1.x + C2[step]*P2.x + C3[step]*P3.x,
      C0[step]*P0.y + C1[step]*P1.y + C2[step]*P2.y + C3[step]*P3.y
    };
    (*results)[step] = point;
  }
  return kSteps + 1;
}

0.16s. 31Mp/s. That’s over 3x faster by just calculating the piece that changes.

Lesson 2: In most cases, your biggest improvements will come from changing your algorithm. Whenever possible, get expensive things out of loops. Don’t make a calculation fast if you can get rid of the calculation entirely. Remember that if you’re called many times, that’s the same as a loop.

The cost of this is 4 floats (16 bytes) per step to store the constants. So for a 1000 step curve, that’s less than 16kB. Not a bad investment on iOS. This cost is for as many curves as you want, as long as they all use the same step size. Of course, if you want different numbers of steps, you could just pass a scale variable to calculate every other point, every fourth point, etc. But by the time we’re done optimizing this (and there’s still plenty of performance left to unlock), you may find that it’s faster and easier just to calculate the same number of points for all curves.

There is another common way to speed up Bézier calculation. Hannu Kankaanpää wrote an excellent article explaining forward differencing using a Taylor series. His approach is fast. About 50-60% faster than copyBezierXY(). But copyBezierTable() is about twice as fast as forward differencing if you calculate a lot of curves with the same step size. Forward differencing is fast if you have one incredibly expensive curve to calculate (say a large Bézier surface). But it loses when you need to calculate a lot of curves. Factoring out everything but the points themselves into a pre-calcuated table lets you skip almost all the work. And that’s the goal.

We still haven’t pulled out Instruments, and we’re still writing in portable C. I wonder what we might get if we go off-road and write directly for the NEON coprocessor. Yes, that means we’re moving onto ARM assembler in the next post. Think you can’t beat the compiler? Think it’s not worth it to try? Think again.

So you want to hand-calculate Bézier curves. Good for you. It comes up more often then you’d think on iOS, even though UIBezierPath is supposed to do it all for you. The truth is, sometimes you need the numbers yourself. For instance if you want to calculate intersections, or you want to draw text along the curve (like in CurvyText from iOS:PTL chapter 18). Just as a refresher, here’s the cubic Bézier function in C, written in the simplest possible way (we’re only going to discuss the cubic Bézier function here):

static CGFloat Bezier(CGFloat t, CGFloat P0, CGFloat P1, CGFloat P2, CGFloat P3) {
  return 
    powf(1-t, 3) * P0
    + 3 * powf(1-t, 2) * t * P1
    + 3 * (1-t) * powf(t, 2) * P2
    + powf(t, 3) * P3;
}

If you want to see this function in use, pull down CurvyText and look in CurvyTextView.m.

P0 through P3 are the control points. If you called addCurveToPoint:controlPoint1:controlPoint2:, then the starting point (wherever you “were”) would be P0. The end point would be P3 and the control points would be P1 and P2. t is a value that runs from 0 to 1; we’ll talk about it more in a moment. If you’re still really lost, you should take time out and read the Wikipedia article on Bézier curves.

The first thing to understand is that this is exactly the same function that UIBezierPath uses. (Well, exactly equivalent to the function they use. I’m certain they don’t use this one because it’s pretty inefficient as we’ll see.) So when we start calculating, we’re going to match UIBezierPath exactly. That’s great because it means you can mix-and-match your code and Core Graphics and everything will match-up.

The next thing to understand is that in this form, the Bézier curve function is effectively one-dimensional. We hand it an “x” value and we get back an “x” value. We hand it a “y” value and we get back a “y” value. So we have to call it twice per point. That’ll be important later for optimization purposes.

Finally, the strangest thing you need to understand is that this function is not linear for t. At t=0, the equation evaluates to P0. At t=1, the equation evaluates to P3. (The equation never evaluates to P1 or P2 since Bézier curves do not pass through these control points.) But between 0 and 1, things get much more complicated. t=0.5 does not represent “half-way along the curve.” Small changes in t can represent very small movement or very large movement along the curve depending on where you are on it. This fact is one of the headaches of Bézier curves.

Our goal is to figure out how to calculate Bézier very fast. So we’re not going to worry much about drawing. We’re just going to investigate ways to calculate this function quickly. Hopefully the process will help you when you’re investigating other functions.

First, let’s build a test project. You can get the full test code in BezierPerf. Starting with a basic project, you want this in didFinishLaunchingWithOptions: to simulate 100 curves drawn at 50 frames per second:

#define BEZIER_FUNC copyBezierSimple

const unsigned kFPS = 50;
const unsigned kNumCurves = 100;

CGPoint P0 = {50, 500};
CGPoint P1 = {300, 300};
CGPoint P2 = {400, 700};
CGPoint P3 = {650, 500};

CFAbsoluteTime start = CFAbsoluteTimeGetCurrent();
CGPoint lastPoint = {0};
for (unsigned i = 0; i < kFPS * kNumCurves; ++i) {
  CGPoint *points;
  unsigned count = BEZIER_FUNC(P0, P1, P2, P3, &points);
  lastPoint = points[count-1];
  free(points);
}
printf("Time: %f\n", CFAbsoluteTimeGetCurrent() - start);
printf("{%f, %f}\n", lastPoint.x, lastPoint.y );
exit(0);

Now we’ll start with the simplest approach (Bezier.c):

unsigned int copyBezierSimple(CGPoint P0, CGPoint P1, CGPoint P2, CGPoint P3, CGPoint **results) {
  *results = calloc(kSteps + 1, sizeof(struct CGPoint));

  for (unsigned step = 0; step <= kSteps; ++step) {
    CGFloat x = Bezier((CGFloat)step/(CGFloat)kSteps, P0.x, P1.x, P2.x, P3.x);
    CGFloat y = Bezier((CGFloat)step/(CGFloat)kSteps, P0.y, P1.y, P2.y, P3.y);
    (*results)[step] = CGPointMake(x, y);
  }
  return kSteps + 1;
}

This just calls Bezier() twice. On my iPhone 4, in Debug mode, with 1000 points, this takes over 20 seconds to run. In Release mode (with optimizations) it takes just over 3 seconds. Wow. 6x improvement. We’ll look into what it’s doing later, but 3s is still no good. We need these calculations every second, and we haven’t even drawn anything yet. Time to start optimizing.

It’s math, so Accelerate.framework is going to make it magically fast, right? I mean, everyone knows that Accelerate uses the fancy vector hardware and that means super-duper fast. So let’s do that. We’ll rewrite Bezier() to use Accelerate. This calculates P*B*T as we discussed in the last post.

static CGFloat BezierAccelerate(CGFloat t, CGFloat P0, CGFloat P1, CGFloat P2, CGFloat P3) {
  const CGFloat P[1][4] = {P0, P1, P2, P3};

  static const CGFloat B[4][4] = 
  { {-1,  3, -3, 1},
    { 3, -6,  3, 0},
    {-3,  3,  0, 0},
    { 1,  0,  0, 0}};

  const CGFloat T[4][1] = { powf(t, 3), powf(t, 2), t, 1 };

  CGFloat PB[1][4];
  vDSP_mmul((CGFloat*)P, 1, (CGFloat*)B, 1, (CGFloat*)PB, 1, 1, 4, 4);

  CGFloat result[1][1];
  vDSP_mmul((CGFloat*)PB, 1, (CGFloat *)T, 1, (CGFloat*)result, 1, 1, 1, 4);

  return result[0][0];
}

This is going to be great. We got rid of that long crazy function and replaced it with a couple of elegant matrix multiples running on the NEON vector processor. I can feel the speed already.

11s. In Release mode, with optimizations.

OK, so it’s twice as fast as the original Debug code. But it’s almost 4 times slower than just turning on -Os with the original function. What? Isn’t Accelerate supposed to make all things faster? We haven’t even tried to optimize the original Bezier() function, and still Accelerate is slower.

Lesson 1: Accelerate is not magic “go fast” fairy dust. It may even be slower than the simplest possible non-Accelerate implementation.

This is not to say that Accelerate isn’t awesome. It can be for certain problems. But day-to-day multiplication is often not one of them.

I promised we’d talk about what -Os is doing and why it’s giving us a 6x speedup. First, you can take a look at the code by editing the Scheme and setting the Build Configuration to Debug. Then use Product, Generate Output, Assembly File to see what happens. At the bottom of the assembler output window, you will see “Show Assembly Output For.” Switching between “Running” and “Archiving” will let you compare the debug and release output.

The easiest way to navigate this output is by searching for .thumb_func which will help you find your functions. You can then look for blx to find the places you make function calls. The .loc entries tell you where you are in the source file (filenumber, line, column). Handy, right? In debug mode, you can see the Bezier function and the four calls to powf(). But in release mode, the Bezier function is gone entirely. It’s been inlined. This is a big deal. Function calls can be expensive. This is one of the big reasons that hand-calculation can be so much faster than Accelerate. Accelerate is optimized for big matrices. For little tiny things, the cost of the function call dwarfs what you might save otherwise. Also, most Accelerate functions include fancy features like adjustable stride and parameter error checking. “Fancy features” translates into “probably slower.”

Back to the assembler, note that there are only two calls to powf(). Where did the other calls go? Well, if you dig a little, you’ll notice these lines:

vmul.f32    d16, d0, d0
...
vmul.f32    d17, d1, d1

These are squaring functions (d0*d0 -> d16). That is incredibly, insanely faster than pow(x,2). We got rid of a lot of function calls (both calls to Bezier and calls to powf), and we replaced a very expensive squaring function with a very cheap one using vmul.

Which brings us to the next point. vmul is a NEON instruction. You don’t have to use Accelerate to get NEON benefits. The compiler uses the NEON processor for all kinds of things.

So now that we know that the compiler will replace pow(x,2) with x*x, I wonder if cubing by hand is faster, too. Let’s try BezierNoPow():

static CGFloat BezierNoPow(CGFloat t, CGFloat P0, CGFloat P1, CGFloat P2, CGFloat P3) {
  return
    (1-t)*(1-t)*(1-t) * P0
    + 3 * (1-t)*(1-t) * t * P1
    + 3 * (1-t) * t*t * P2
    + t*t*t * P3;
}

Debug: 9.7s. Nice. 50% improvement over unoptimized powf().

Release: 0.6s. 5x speedup over optimized powf(). 30x speedup over the original function.

In fairness, we should try removing the powf() calls in the Accelerate function. That gets us to 6.5s. Still 10x slower then hand-coded.

Now 0.6s is still 60% of our available time, so it’s worth digging deeper to see what else we can do to speed things up. We’ll talk more about that later. We haven’t really gotten warmed up yet. We haven’t even launched Instruments. There is still plenty of speed we can pick up here. Read more at Even Faster Bezier.

For those of you who did your homework from last time, here’s the answer, this time in C, for the matrix you need to calculate the derivative (slope) of the Bézier function:

const float Bp[4][3] = {
  {-3, 6, -3},
  {9, -12, 3},
  {-9, 6, 0},
  {3, 0, 0}
};

Chapter 18 of iOS:PTL includes code for calculating points on a Bézier curve (see CurvyText in the sample code). In the book, I hinted that this operation would likely be well suited to the Accelerate framework. The Accelerate framework provides hardware-accelerated vector operations. Solving Bézier equations seems a perfect fit. I’ll get more into Accelerate in later posts (including some thoughts on when to use it), but first I need to introduce some mathematical groundwork.

In this post, I’m targeting a specific kind of developer; one like myself. My mathematically inclined friends will find this so trivial that it’s hardly worth discussing. For those of you who have never seen a matrix before, this may be a bit dense. But if you’re like me, and once upon a time you actually took linear algebra, but today you wouldn’t know a transpose if it invited you to dinner, this may help. (The last time I computed a dot-product, the Newton hadn’t been released…) My goal isn’t to teach you Guassian elimination or eigenvalues. My goal is to show you by example the specific tools you need to convert the math you find in a book into matrices so you can calculate it faster. (And how to cheat with the incredible new tools available to us.)

So by way of example, we will consider the cubic Bézier curve (as expressed by Wikipedia):

(1)  

This means that for each coordinate (x,y), you calculate the above for values running from t=0 to t=1. In C that translates into:

static CGFloat Bezier(CGFloat t, CGFloat P0, CGFloat P1, CGFloat P2,
                  CGFloat P3) {
  return 
    powf(1-t, 3) * P0
    + 3 * powf(1-t, 2) * t * P1
    + 3 * (1-t) * powf(t, 2) * P2
    + powf(t, 3) * P3;
}

For the four control points (P0…P3), you pass the x value to Bezier() and get back the x value of the curve. Repeat for y. There are many reasons that the above approach is inefficient. We’ll discuss that more in later posts. But for this post, the goal is to figure out how to convert this into an matrix operation so we can use some of of our fancy hardware to calculate it for us.

The first step is realizing what kind of matrix we want. Our goal is to collect all the t terms into one matrix, all the P terms into one matrix. and all the constants into a third matrix. When we’re done, it’ll look like this (where K is the constants):

(2)  

Written out, that looks like:

(3)  

The four P values are the control points from the Bézier equation (these are points, so they include an x and y). The four t terms are the powers that occur in the equation (remember: 1 = t⁰ ).

When you multiply matrices, the result has the number of rows in the first matrix and the number of columns in the second. So P is 1×4 and the constants are MxN (we’ll figure out M and N shortly). So that result is 1xN. Times T (4×1) and we’ll finish up with a 1×1 matrix. A single point value. This is why it matters that P is in a row and T is in a column.

But a “point” is a vector. Let’s make that a little clearer (I hope):

(4)  

OK, that’s a little closer to a CGPoint. One x, one y. But what about “the constants?” These are the multipliers for each of the terms in “expanded form.” What we want is our equation in a form like:

(5)  

This gives us the sum of every combination of each P with each power of t. When you see “the sum of every combination” you should be thinking dot product and matrix multiplication. From this equation, it shouldn’t take a lot of imagination to figure out what K looks like.

(6)  

Now, if only we had a way to figure out all those constants easily. We could do it with pencil and paper, but I always screw up simple algebra. If only there were some device that did mechanical operations really well. Just imagine if someone put up a free web service that would do algebra for you.

Bless you Wolfram. You are my hero.

So we head over to Wolfram|Alpha and ask it to expand the Bézier equation for us:

expand (1-t)^3 P_0 + 3 (1-t)^2 t P_1 + 3 (1-t) t^2 P_2 + t^3 P_3

And from that, we can work out our matrix:

(7)  

Now, in fairness, I have found this matrix several places on the internet. So why bother doing all this? Why not just copy the final answer? For the Bézier calculations I wanted to do, I also need the first derivative of this, and I couldn’t find the matrix for that anywhere. So sometimes the answer isn’t just out there for you. And from experience, let me say that trying to debug this kind of code when you don’t actually know what the matrix means is… challenging.

As an exercise, calculate the matrix for the Bézier derivative yourself. Wolfram|Alpha will give you the derivative of a function using the command derivative (instead of expand). I’ll give you a hint: the matrix is not 4×4. I’ll post the answer (and how to get it) in my next installment.

Your programs need to deal gracefully with being offline. Mugunth Kumar has built an excellent toolkit that manages REST connections while offline called MKNetworkKit, and Chapter 17 of our book is devoted to the ins-and-outs of this subject.

But sometimes you just have a simple UIWebView, and you want to cache the last version of the page. You’d think that NSURLCache would handle this for you, but it’s much more complicated than that. NSURLCache doesn’t cache everything you’d think it would. Sometimes this is because of Apple’s decisions in order to save space. Just as often, however, it’s because the HTTP caching rules explicitly prevent caching a particular resource.

What I wanted was a simple mechanism for the following case:

• You have a UIWebView that points to a website with embedded images
• When you’re online, you want the normal caching algorithms (nothing fancy)
• When you’re offline, you want to show the last version of the page

My test case was simple: a webview that loads cnn.com (a nice complicated webpage with lots of images). Run it once. Quit. Turn off the network. Run it again. CNN should display.

Exisiting solutions

The ever-brilliant Matt Gallagher has some interesting thoughts on how to subclass NSURLCache to handle this, but I find his solution fragile and unreliable, especially on iOS 5. The HTTP caching rules are complicated, and in many cases you need to connect to the server to re-validate your cache before you’re allowed to use your local copy. Unless everything works out perfectly, his solution may not work when you’re offline, or may force you to turn off cache validation (which could make your pages go stale).

AFCache is also promising, using essentially the same approach. I haven’t found the offline support to work very well, at least in my tests, for the same reasons as Matt’s solution. It’s designed to be an advanced HTTP-caching solution. The docs are limited and I couldn’t get it to pass my CNN test.

RNCachingURLProtocol

So, I present RNCachingURLProtocol. It isn’t a replacement for NSURLCache. It’s a simple shim for the HTTP protocol (that’s not nearly as scary as it sounds). Anytime a URL is download, the response is cached to disk. Anytime a URL is requested, if we’re online then things proceed normally. If we’re offline, then we retrieve the cached version. The current implementation is extremely simple. In particular, it doesn’t worry about cleaning up the cache. The assumption is that you’re caching just a few simple things, like your “Latest News” page (which was the problem I was solving). It caches all HTTP traffic, so without some modifications, it’s not appropriate for an app that has a lot of HTTP connections (see MKNetworkKit for that). But if you need to cache some URLs and not others, that is easy to implement.

First, a quick rundown of how to use it:

1. At some point early in the program (application:didFinishLaunchingWithOptions:), call the following:

   [NSURLProtocol registerClass:[RNCachingURLProtocol class]];

2. There is no step 2.

Since RNCachingURLProtocol doesn’t mess with the existing caching solution, it is compatible with other caches, like AFCache. In fact, the technique used by RNCachingURLProtocol could probably be integrated into AFCache pretty easily.

The cache itself is stored in the Library/Caches directory. In iOS 5, this directory can be purged whenever space is tight. Keep that in mind. You may want to store your caches elsewhere if offline access is critical.

Understanding NSURLProtocol

An NSURLProtocol is a handler for NSURLConnection. Each time a request is made, NSURLConnection walks through all the protocols and asks “Can you handle this request (canInitWithRequest:)?” The first protocol to return YES is used to handle the connection. Protocols are queried in the reverse order of their registration, so your custom handlers will get a crack at requests before the system handlers do.

Once your handler is selected, the connection will call initWithRequest:cachedResponse:client: and then startLoading. It is then your responsibility to call the connection back with URLProtocol:didReceiveResponse:cacheStoragePolicy:, some number of calls to URLProtocol:didLoadData:, and finally URLProtocolDidFinishLoading:. If these sound similar to the NSURLConnection delegate methods, that’s no accident.

While online, RNCachingURLProtocol just forwards requests to a new NSURLConnection, making copies of the results, and passing them along to the original connection. When offline, RNCachingURLProtocol loads the previous result from disk, and plays it back to the requesting connection. The whole thing is less than 200 lines of pretty simple code (not counting Reachability, which I include from Apple’s sample code to determine if we’re online).

There’s a subtle problem with the above solution. When RNCachingURLProtocol creates a new NSURLConnection, that new connection has to find a handler. If RNCachingURLProtocol says it can handle it, then you’ll have an infinite loop. So how do I know not to handle the second request? By adding a custom header (X-RNCache) to the HTTP request. If it’s there, then we’ve already seen this one, and the handler returns NO.

Again, this intercepts all HTTP traffic. That could intercept pages you don’t want. If so, you can modify canInitWithRequest: to select just things you want to cache (for instance, you could turn off caching for URLs that include parameters or POST requests).

Wrap-up

This technique isn’t a replacement for a full caching engine like AFCache or an offline REST engine like MKNetworkKit. It’s intended to solve a single, simple problem (though it can be extended to solve much more complicated problems). NSURLProtocol is extremely powerful, and I’ve used it extensively when I need to eavesdrop on network traffic (such as in PandoraBoy’s several ProxyURLProtocol classes). It’s well-worth adding to your toolkit.

The code is in the attached project. Look in RNCachingURLProtocol.m.

EDIT: Be sure to see Nick Dowell’s modification in the comments to handle HTTP redirect.

EDIT2: In cachePathForRequest:, I use hash to uniquely identify the URLs. For long, similar URLs, this collides a lot (See CFString.c for comments on how the hash function is implemented.) The better thing to use is MD5 or SHA1 or something, but those aren’t built-in on iOS prior to iOS5, so you’d have to implement your own (and I don’t need it that badly for my current projects). This is something you’d want to fix before using this seriously.

CachedWebView Example Project