Another difficulty is that of honoring.  Not for the person being honored, but for those that person may have wronged, or for those that feel they’ve been wronged.  It’s easy to deify someone you’ve not known your whole life, and it’s easy to censor memories when reality makes heroes less than heroic at all times.

Today I’m going to break that second rule and pay my respects to Dayle Jellings.  While he was almost certainly not perfect, I am ignorant of his misdeeds and have no desire to become privy to them.  I know that he rendered me service and friendship unlike that of any other, all while never asking for anything in return.  Transportation, ice cream, laundry money, hair cuts, fellowship, those are the things I remember him for.  Even after I moved out he still kept in touch, traveling far out of his way just to say hello.  After we left he remembered each of us years later.  When one of us made a poor decision, he didn’t abandon or condemn.

A Lauri Anderson lyric describes losing a father as a whole library burning down.  For me, Jellings was more than a library;  he was a friend.  He will be missed.

His facebook account has him immortalized (at least updated with a eulogy of sorts), complete with a friend wishing him a speedy recovery.  Such hollow wishes always choke me up.  How powerless we really are, how fragile life is.

cwright@phendrana:~/projects/test/cache>gcc -framework Foundation source.m -o source -Os

cwright@phendrana:~/projects/test/cache>./source

  &value1: 0x2014

  &value2: 0x2018

  same cache line!

  elapsed: 12639.155030ms

cwright@phendrana:~/projects/test/cache>gcc -framework Foundation source.m -o source

cwright@phendrana:~/projects/test/cache>./source

  &value1: 0x2020

  &value2: 0x2080

  different cache line!

  elapsed: 5614.167988ms

That above nonsense is me compiling the same piece of code (analyzed later) being compiled with optimization (and taking ~12.6 seconds to complete), and without optimization (taking ~5.6 seconds to complete).  Wait a minute.  Optimized takes over 2x as long?  If that’s not a teaser, I don’t know what is.

Modern CPUs have a few levels of cache between their registers (the fastest memory around) and the Harddrive (the slowest, unless you count the network).  You’ve probably heard of one of the most important caches, RAM — it’s filled with stuff from the harddrive (and temporary working data) because accessing the harddrive is so laughably slow that if you understood it you’d never refer to your computer making that grinding noise as “thinking” — it’s actually doing quite the opposite:  not thinking, but waiting for the slow disk to feed it more data.

Compared to the CPU, the harddrive is a glacier — it takes hundreds of thousands of clock cycles to get a response.  It’s like sending a letter across the ocean on a ship.  Compared to the CPU, even RAM, which is orders of magnitude faster than the harddrive, is really slow — it takes hundreds of cycles to get a response.  So to work around the slowness of RAM, a few more caches are in place:  L1, L2, and sometimes L3.  These are made of very fast, very expensive memory, and they’re often very small.  L1 and L2 live on the CPU, with L1 being per-core, and L2 usually being shared among all cores on the CPU, and on some newer processors L3 is also on the CPU and also shared (but sometimes it’s off the CPU).  The L1 cache is further divided into L1-I and L1-D, for Instructions and Data, but that’s a topic for a different day.  Generally L1 will be the smallest and the fastest, L2 will be slower but larger, and L3 will be slower but larger still.

RAM is divided into bytes.  In the old days, you’d even read and write it as individual bytes.  (some fancy-pants microcontrollers even offered bit addressing, but they typically worked on bytes and just hid that detail from you).  These days, its read and written in larger chunks (there are some exceptions, but generally reads and writes work on much much larger units).  These chunks are typically Cache Lines.  A cache line on a current X86 processor is 64 bytes.  So when your program reads byte at location 0, behind your back the cache will also fetch bytes 1-63 for you.  This may seem totally bizarre and wasteful, but the reason for it is because often programs that ask for a value at a certain location will ask for nearby locations shortly after (phenomena referred to as “spatial locality” and “locality of reference”).  The cache will hold on to that entire line until it seems like the program’s not interested in it any longer, at which point it evicts it, and asks for a new line.  You probably undergo a similar optimization when you’re putting on your socks and shoes:  you grab them in pairs, and put them on one at a time.  You could put one on, and then go and grab the second and put it on, but it’s easier to just get them all at once.

When a CPU core holds a cache line, it’s free to modify it as it needs to — this is known as the M state (for Modified).  When a line is “M”, it no longer matches what’s in other caches and RAM — this is ok, as long as it makes it back there eventually.  If a line in cache holds no valid data, it’s Invalid, or in the I state.  If a CPU holds a line unmodified, and no one else has it, it’s “Exclusive”, or E state.  And finally, when a line is held by 2 or more cores, it’s in the Shared, or S, state — this is where it begins to get complicated.

Let’s say that 2 cores are working on the same cache line.  Core 1 changes one of the bytes.  This means that Core 2′s version is Invalid (I state!).  So when Core 2 needs to read a byte from that line, it notes that it needs to get the latest version — this involves asking Core 1 for its latest copy.  Core 2 then changes a byte, invalidating Core 1′s line, so Core 1 then asks for Core 2′s copy, and the cycle repeats.  This, as you can imagine, gets really slow — the cache line is bouncing around between cores, continually invalidating each other, causing them to stall.

For memory that doesn’t get written to (the instructions that make up the program, for example), this isn’t a problem — the lines are Shared (S state), and never modified, so both cores can happily operate simultaneously, each using their own identical copy with no stalls or invalidations.

So, how did we get the situation above?  Here’s the source code:

#import <Foundation/Foundation.h>
#import <libkern/OSAtomic.h>

static volatile uint32_t value1 = 1;
static volatile uint32_t padding1[16] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
static volatile uint32_t value2 = 1;
static volatile uint32_t paddings[16] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
static volatile uint32_t count = 2;

#define ROUNDS (0x8000000)

void *counterThread(void *arg)
{
 unsigned int i;
 for(i=0;i<ROUNDS;++i)
    OSAtomicIncrement32(arg);
 OSAtomicDecrement32(&count);
 return 0;
}

int main()
{
 pthread_t pth;

 printf("&value1: %p\n", &value1);
 printf("&value2: %p\n", &value2);
 if((ptrdiff_t)&value2 - (ptrdiff_t)&value1 < 64)
    printf("same cache line!\n");
 else
    printf("different cache line!\n");

 double now, then = CFAbsoluteTimeGetCurrent();

 pthread_create(&pth, NULL, counterThread, &value1);
 pthread_create(&pth, NULL, counterThread, &value2);

 while(count)
    usleep(1);
 now = CFAbsoluteTimeGetCurrent() - then;
 printf("elapsed: %fms\n", now*1000);

 return 0;

}

What we’re doing is spawning 2 threads, and having each of them count at a certain location. Note that our timing is not particularly accurate — it’s intended to give us the general magnitude of the duration, not the fine-grained timing information we have in other profiling posts.

When optimization is disabled, the compiler doesn’t do any cleanup, and just uses the variables as they’re described at the top (value1, value2, padding1, padding2).  Because of the Padding variables (64bytes of them, to be exact), we guaranteed that our value1 and value2 variables are at least 64bytes apart (thus, on different cache lines) in memory — this allows each CPU core to operate on a different cache line, never interrupting the other cores.

When we enable optimization, the compiler reasons about the code some.  It notices that we never actually use padding1 and padding2, and so it removes them (normally, fewer variables will improve performance, as the remaining live variables will be together in cache).  In this case, it puts these two variables adjacent (on the same cache line), unaware that they’re about to be hammered by 2 different Cores with 2 different Caches.  So even though the threads are operating on distinctly separate regions of memory, they’re the same logical cache line, and thus performance issues emerge.

One simple way to fix this is to tell the compiler to align each of the variables to its own cache line using the “aligned” attribute.  This will ensure that we have plenty of space around our values.

Variables aren’t typically the source of cache line contention like this;  the more frequent culprits are spinlocks and mutexs — thankfully, on OS X mutexes are big enough to be cache-line aligned already, but spinlocks are not.  So if you have a large block of spinlock definitions at the top of some source file, it might be useful to separate them some if contention is actually rears its head.

One of the more interesting aspects (on OS X at least) is that in 32bit mode, the heap is automatically executable (no need for mmap() and friends), while in 64bit mode, even the heap is NX’d.  This makes heap overflows much more difficult to exploit; you’re pretty much stuck needing to do a return-to-libc attack (which is still possible, mind you — NX does nothing to prevent that sort of attack).

Here’s some example code:

#include <stdio.h>
#include <unistd.h>

void (*f)();

int main()
{
        void *ptr = malloc(16);
        memset(ptr, 0xc3, 16);    // 0xc3 = RET
        f = ptr;

        printf("Executing from heap\n");
        f();
        printf("we're still alive.\n");

        char buffer[16];
        memset(buffer, 0xc3, 16);
        f = buffer;
        printf("next up, from the stack\n");
        f();
        printf("we're still alive.\n");

        return 0;
}

Compile using gcc nx.c -o nx -m32, and you’ll see the program crash on the “next up, from the stack” step. Swap in -m64 instead of -m32, and you’ll see it crash immediately after “Executing from the heap.”

None of this is particularly new or earth-shattering, but it’s a neat little concept to play with. For self-modifying code paths, or JIT compilers, this can be require a slight detour (though JITs should be using mmap() by now anyway).

My start date was set at February First.  This was established on January 29th, which didn’t leave a lot of time.  Being full of reckless bravado, I welcomed the challenge.

Packing was a mad dash — stuffing in lots of my clothes, but also some of Alisa’s less-frequently-used stuff.  The bulk of packing was unfortunately left to Alisa after my departure.

The flight had a layover in Las Vegas.  As always, the people flying to Las Vegas are looking for a good time, and this time was no exception.  Except that one of the passengers behind me had a little bit too much to drink, and decided that he was “done with the plane” half an hour before we landed.  He started unloading the overhead bins, and being obnoxious in general (all the while his boss was trying to get him to calm down).  Being seated in the next-to-last row on the plane, it took no less than 79 hours to get off the plane because people still haven’t mastered the art of fetching stuff from overhead _Before_ they need to move (so they don’t hold up everyone else) or simply having light (or no!) carry-on at all.  Due to the delay, our inebriated friend started talking about blowing up the plane, figuring that it’d encourage people to get off faster (and possibly for mild comic effect).  Instead all it did was make some passengers look horrified (in the “I pity what’s going to happen to you” sense, not the “I’m scared for my life!” sense) and make the flight attendants scramble to deal with him.

Estimating a week-long apartment search, I booked a hotel through Thursday morning, and a car through Thursday evening — I figured the shorter duration would force me to take action, or at least force me to sleep on a park bench for a few nights if I failed.  The 55-60 degree weather of San Jose was a welcomed change from the 8 degree winter that Ohio was offering at the time, but even so park benches weren’t overly inviting.

Alisa pulled through and arranged some apartments using elite time-zone tricks like calling after-hours in Ohio (which is still business hours in Cali).  Additionally, a co-worker drove me through the nearby area on the way to dinner one evening, so I got to check out some more (from the safety of Troy’s Audi).  When a suitable place was determined (a 25 minute walk to/from the office, a 20 minute walk to/from Target and the bank, a 15 minute walk to/from church, a 10 minute walk to Whole Foods, and most important, a 5 minute walk to/from Panda Express), I pulled the necessary $2175 for rent, deposit, and application fees out of savings, and landed some living quarters Thursday morning (actually, there were 2 transactions, one of which was deposit + application fees;  that happened on Wednesday.  Rent was due when I actually got approved and signed the lease), and moved in my two suitcases.   (A fabulous reason to have an emergency fund — also, expenses piled up really quickly with plane tickets and car rentals and hotel stays and buying food, so having credit cards handy makes a huge difference despite what Dave Ramsey unwisely counsels.)

The next tricky bit was getting from the Airport (amusingly, San Jose is abbreviated “SJ” all over the freeway signs.  SJ is also an abbreviation for Steve Jobs, my new boss (no, I haven’t met him)) back to Cupertino.  Returning the car went ok (as long as you throw way too much money at them, and don’t kill the car, they don’t care all that much), but finding a Taxi for less than $60 to cross town was difficult.  To further complicate matters, it was monsoon season, so every minute I was outside looking for transit I was getting wetter and wetter.  Eventually someone overheard a quote, and offered a ride instead (citing $60 to cross town as high way robbery) — He was driving to Mountain View, which is just north of Cupertino, so it wasn’t too far out of his way.  We chatted some, and he’s in marketing, but was formerly a software engineer as well, so we had some interesting discussions along the way.  I offered him the cash I had upon safe arrival ($40), but he declined, saying “Welcome to California” — despite my usual low impression of people generally, California (or at least the Bay area) offers some extremely hospitable residents — a few years back at WWDC smokris and I got some pleasant breaks while ironing out transit (except when it came to the Taxi guy at the end).

Saturday was spent wandering around getting acclimated some more.  I picked up some basics (shower curtain, razors, trash can, food+juice for sunday, ordered internet (only Comcast is available where our apartment is, that sucks)), and also discovered that my key card doesn’t grant me access to my office building on weekends.  That’s a shame (as I’m accustomed to dumping 60+ hours a week into what I do because it’s a work of passion for me), but maybe I’ll work out some agreement and get access or something later.

Sunday was a nice relaxing day.  I got to catch a nap, and meet some new people.

Work-wise, it’s been stellar.  I’m surprised how effective an office is for me (I share an office with Troy at the moment, so he’s probably much less effective with my constant barrage of questions/thoughts), and the people are great.  The paranoia and secrecy you hear about is entirely true — the only other organizations that maintain this many secrets are probably the US Government and the KGB.  At first this was a bit saddening (coming from Kosada, where I knew basically everything that was going on), but after a day or two I realized how much more focused I could be.  There are rough edges of course (like trying to work with something “secret”), but those are exceptional cases.  This tends to make each team an expert on their particular project, which in turn allows for wildly fast turnaround times and equally impressive wide-scale refactoring/redesign that goes almost completely unnoticed on the outside.

The coworkers are great.  I’ve learned a lot already, and the group seems really close.  There’s a NeXTie who dates back to before OpenGL from what I can tell, and several other very talented, very sharp people.  And they all do things besides pressing buttons all day!  That’s amazing to me (computer nerds get a bad rap for living in their mom’s basement until they’re 35) for some reason (not that previously anyone was that bad, it’s just a stereotype that I expect for some reason).  After spending so many years reverse engineering the project I’m now working on, I felt pretty at home almost instantly, and immediately dug in and starting learning how to deal with bugs, features, and the development environment in general in an environment where the schedule is much more rigid than my previous experience.  There are all kinds of cool little details I’d love to chat about, but I’ve probably said more than I should have already.

And the lunches are fantastic!  It’s nice to be able to eat such a wide variety of food, and socialize with fellow engineers.  It’s almost impossible to walk through the courtyard area of Infinite Loop and not have a hugely goofy grin on my face

Being an employee referral, some cool perks came my way.  Specifically, I got to skip the phone interview entirely, and got flown out there, put up in a nice hotel (Cypress Hotel), and had a fun dark blue Mazda 5 waiting for me.  Very smooth, to say the least.  I’m pretty sure that everyone who gets interviewed receives such treatment.

From first contact to flight out there, it was 2 weeks.  Pretty darn fast.

After resting up that evening in San Jose, I awoke the next morning for the interview.  I was told that ongoings in said interview are confidential.  In general, things went pretty smoothly.  Getting to meet the QC team was quite exciting, and meeting several talented engineers is also always great.  Finally, the recruiter came in, we threw around some numbers, and then I left for my flight home.  My total time in interviews was around 4-4.5 hours, and my total time in San Jose was about 16 hours.  Very brief.

Within a week, the background check company had contacted me to verify my employment.  Paystubs, Articles of Incorporation, and all that went in.  Then, a turn for the worst:  a week of absolute silence.  2 weeks without hearing anything is never a good sign.

Today, the rejection letter finally came.  Total time from first contact to rejection:  28 days.  Citing budgetary issues etc.  Whether or not that’s valid is of no concern to me.  At least it frees me up to continue working on things here.  Though I am a bit worried about the future of the technology I’ve so lovingly dealt with…

So, there you have it:  a brief trip into the heart of the Reality Distortion Field itself, and then a successful deflection.

Locking is absolutely required for critical sections. These arise in multithreaded code, and sometimes their performance can have severe consequences in applications. The problem with the aforementioned benchmark is that it did a bunch of extraneous work while it was locking/unlocking. It was doing the same amount of extraneous work, so the relative order was correct (the fastest was still the fastest, the slowest still the slowest, etc), but it didn’t properly show just how much faster the fastest was.

In the benchmark, the author used autorelease pools, allocated objects, and then released them all.  While locking.  This is a pretty reasonable use-case, but by no means the only one.  For most high-performance, multithreaded code, you’ll spend a _bunch_ of time trying to make the critical sections as small and fast as possible.  Large, slow critical sections effectively undo the multithreading speed up by causing threads to block each other out unnecessarily.  So when you’ve trimmed the critical sections down to the minimum, another sometimes-justified optimization is to optimize the amount of time spent locking/unlocking itself.

Just to make things exciting though, not all locking primitives are created equal.  Two of the 4 mentioned have special properties that can affect how long they take, and how the operate under pressure.  I’ll get to that towards the end.

First up, here’s my “no-nonsense” microbench code:

#import <Foundation/Foundation.h>
#import <objc/runtime.h>
#import <objc/message.h>
#import <libkern/OSAtomic.h>
#import <pthread.h>

#define ITERATIONS (1024*1024*32)

static unsigned long long disp=0, land=0;

int main()
{
 double then, now;
 unsigned int i, count;
 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 OSSpinLock spinlock = OS_SPINLOCK_INIT;

 NSAutoreleasePool *pool = [NSAutoreleasePool new];

 NSLock *lock = [NSLock new];
 then = CFAbsoluteTimeGetCurrent();
 for(i=0;i<ITERATIONS;++i)
 {
 [lock lock];
 [lock unlock];
 }
 now = CFAbsoluteTimeGetCurrent();
 printf("NSLock: %f sec\n", now-then);    

 then = CFAbsoluteTimeGetCurrent();
 IMP lockLock = [lock methodForSelector:@selector(lock)];
 IMP unlockLock = [lock methodForSelector:@selector(unlock)];
 for(i=0;i<ITERATIONS;++i)
 {
 lockLock(lock,@selector(lock));
 unlockLock(lock,@selector(unlock));
 }
 now = CFAbsoluteTimeGetCurrent();
 printf("NSLock+IMP Cache: %f sec\n", now-then);    

 then = CFAbsoluteTimeGetCurrent();
 for(i=0;i<ITERATIONS;++i)
 {
 pthread_mutex_lock(&mutex);
 pthread_mutex_unlock(&mutex);
 }
 now = CFAbsoluteTimeGetCurrent();
 printf("pthread_mutex: %f sec\n", now-then);

 then = CFAbsoluteTimeGetCurrent();
 for(i=0;i<ITERATIONS;++i)
 {
 OSSpinLockLock(&spinlock);
 OSSpinLockUnlock(&spinlock);
 }
 now = CFAbsoluteTimeGetCurrent();
 printf("OSSpinlock: %f sec\n", now-then);

 id obj = [NSObject new];

 then = CFAbsoluteTimeGetCurrent();
 for(i=0;i<ITERATIONS;++i)
 {
 @synchronized(obj)
 {
 }
 }
 now = CFAbsoluteTimeGetCurrent();
 printf("@synchronized: %f sec\n", now-then);

 [pool release];
 return 0;
}

We do 5 tests:  We test NSLock, NSLock with IMP caching, pthread mutexes, OSSpinLocks, and then finally @synchronized.  We simply lock and unlock 33554432 times (that’s 1024*1024*32 for those keeping score at home , and see how long it takes.  No allocation, no releases, no autorelease pools, nothing.  Just pure lock/unlock goodness.  I ran the test a few times, and averaged the results (so overall, the results are from something like 100 million lock/unlock cycles each)

1. NSLock: 3.5175 sec
2. NSLock+IMP Cache: 3.1165 sec
3. Mutex: 1.5870 sec
4. SpinLock: 1.0893
5. @synchronized: 9.9488 sec

Lock Performance

From the above graph, we can see a couple thing:  First, @synchronized is _Really_ expensive — like, 3 times as expensive as anything else.  We’ll get into why that is in a moment.  Otherwise, we see that NSLock and NSLock+IMP Cache are pretty close — these are built on top of pthread mutexes, but we have to pay for the extra ObjC overhead.  Then there’s Mutex (pthread mutexes) and SpinLock — these are pretty close, but even then SpinLock is almost 30% faster than Mutex.  We’ll get into that one too.  So from top to bottom we have almost an order of magnitude difference between the worst and best.

The nice part about these all is that they all take about the same amount of code — using NSLock takes as many lines as a pthread mutex, and the same number for a spinlock.  @synchronized saves a line or two, but with a cost like that it quickly looks unappealing in all but the most trivial of cases.

So, what makes @sychronized and SpinLock so different from the others?

@synchronized is very heavy weight because it has to set up an exception handler, and it actually ends up taking a few internal locks on its way there.  So instead of a simple cheap lock, you’re paying for a couple locks/unlocks just to acquire your measly lock.  Those take time.

OSSpinLock, on the other hand, doesn’t even enter the kernel — it just keeps reloading the lock, hoping that it’s unlocked.  This is terribly inefficient if locks are held for more than a few nanoseconds, but it saves a costly system call and a couple context switches.  Pthread mutexes actually use an OSSpinLock first, to keep things running smoothly where there’s no contention.  When there is, it resorts to heavier, kernel-level locking/tasking stuff.

So, if you’ve got hotly-contested locks, OSSpinLock probably isn’t for you (unless your critical sections are _Really_ _Fast_).  Pthread mutexes are a tiny bit more expensive, but they avoid the power-wasting effects of OSSpinLock.

NSLock is a pretty wrapper on pthread mutexes.  They don’t provide much else, so there’s not much point in using them over pthread mutexes.

Of course, standard optimization disclaimers apply:  don’t do it until you’re sure you’ve chosen the correct algorithms, have profiled to find hotspots, and have found locking to be one of those hot items.  Otherwise, you’re wasting your time on something that’s likely to provide minimal benefits.

Once opened, you can put money aside for college expenses later on while benefiting from some serious tax advantages.  You can read more about them on wikipedia: http://en.wikipedia.org/wiki/529_plan.  CollegeAdvantage offers a bunch of funds, and they’re generally quite high-quality funds.  With a 529, you can change the beneficiary at any time, so you can open it with yourself as the designated recipient (I’ve done that, as we have no kids right now), and change it later (once kids arrive).  Or, if you have kids now, you can set it to them today.

This offer’s good till December 15th, 2009, and requires an initial deposit of $25.  You’ll receive your $25 bonus shortly thereafter.

These methods look like the following (one method per line):

id anObject = [NSObject new]; // 3 total messages
id anObject = [[NSObject alloc] init]; // 3 total messages
id anObject = [[NSObject allocWithZone:NULL] init]; // 2 total messages
id anObject = [anotherObject copy]; // 3 total messages
id anObject = [anotherObject copyWithZone:NULL]; // 2 total messages

(There’s also a lower-level objc-runtime-only set of function calls to accomplish the above, but that’s more verbose than most people are willing to go — if you have to drop to that level for acceptable performance, your object model is fundamentally wrong, and should be revised.)

These all accomplish the same thing, with varying levels of performance.  -copy and -copyWithZone won’t actually work in the above because NSObject doesn’t implement copy.  But the top three can illustrate some interesting characteristics.

Here’s our breakdown (I did a few runs and averaged them — I ran the microbench on a 1.83GHz Core2 Duo MacBook running Mac OS X 10.5.8, as well as on a 2.4GHz Core2 Duo MacBook Pro running Mac OS X 10.6.0):

10.5.8/1.83GHz (32 bit):
new time: 8.413659 (420.682949ns/iteration)
alloc/init time: 8.282779 (414.138952ns/iteration)
allocWithZone/init time: 8.030380 (401.519001ns/iteration)

10.6.0/2.4GHz (32 bit):

new time: 6.439551 (321.977550ns/iteration)
alloc/init time: 6.351412 (317.570600ns/iteration)
allocWithZone/init time: 5.972713 (298.635650ns/iteration)

In 64bit mode, we have much better performance all around:

10.5.8/1.83GHz (64bit):

new time: 5.590315 (279.515749ns/iteration)
alloc/init time: 5.339382 (266.969100ns/iteration)
allocWithZone/init time: 5.173148 (258.657402ns/iteration)

10.6.0/2.4GHz (64bit):

new time: 4.058811 (202.940547ns/iteration)
alloc/init time: 3.873028 (193.651399ns/iteration)
allocWithZone/init time: 3.846562 (192.328098ns/iteration)

(yes, that’s right — object allocation in 64bits on Leopard at 1.83GHz is faster than 32bit allocations on Snow Leopard at 2.4GHz — that’s actually quite impressive evidence for switching to 64bit sooner, rather than later

Since we have different underlying hardware and operating systems, we aren’t going to generalize between the two sets, except to say that 2.4GHz/Snow Leopard is faster than 1.83GHz Leopard (a big surprise — 2.4 is simply faster all around, even without Snow Leopard).

In both 32 bit cases, doing the alloc/init dance gives a tiny ~1.5% performance improvement.  More interestingly, allocWithZone/init give a 4.5%-7% performance improvement.  In cases where lots of objects are getting allocated frequently, switching to allocWithZone instead of new can provide some slight but measurable benefits.   (Note that we didn’t profile other object classes in this test — we just wanted to test the raw allocation overhead.  In real life, this overhead is still present, but generally lower-weight.  Our optimization above will still reduce that overhead.)

64 Bit isn’t quite as dramatic, but the effect is still present — -WithZone is still faster by a tiny margin.

-copy and -copyWithZone have a relationship similar to alloc/allocWithZone, in that copy simply calls copyWithZone:NULL (alloc simply calls allocWithZone:NULL) – the benefit of using the -WithZone: variant up front is that you’re skipping the extra message-send (saving a few cache lines, some stack, and some potential objective-c method lookups).

It may seem like 10-20ns isn’t a very long time (and indeed, 20 billionths of a second is pretty darn short in human terms), but in heavy allocation contexts this can add up very quickly.  Stacking up with thousands of allocations, it’s possible to shave off larger portions of time employing this.  For no additional lines of code, a tiny overhead reduction can be a pleasant pick-me-up for almost no additional effort.

Note that with all optimization, it should only take place after working code has been written and profiled to locate hotspots, and after optimal (or at least somewhat tuned) algorithms have been employed (optimizing one-time init code generally doesn’t help anything, optimizing cold code doesn’t help much, and using fast slow algorithms is worse than using slow fast algorithms almost all of the time.)

(apologies in advance — this will be a rather technical post.  It’s eventually intended for fdiv.net, but while it’s getting migrated I figured I’d plop it down here.)

Instance Variables (or, more briefly, ivars) are a pretty simple trend in Object Oriented Languages.  They’re data that get carried along inside an object, helping to define its state.  While it would be fun to elaborate more on this, this particular article isn’t intended to teach the basics of OOP.  So if you’re unsure of what an ivar is, this article probably isn’t for you.

In Objective-C, (and possibly other languages), ivars have an interesting property — they’re volatile.  volatile is one of those shady regions of C and C-derived languages (like Objective-C) that few people talk about, but what it means is that the data behind the variable can change at any moment, so the compiler should reload it from memory whenever it’s used (the alternative is to load it once, and store it in a register — this is typically simpler and faster, but sometimes wrong if the data is in fact volatile). This is all well and good, and it performs exactly as intended. However, because of this reloading, we get some negative performance characteristics to go along with it.

To demonstrate, we’ll have this chunk of code:

#import <Cocoa/Cocoa.h>

#define ELEMENTS (1024*1024*4)
#define ROUNDS (50)

typedef struct Vertex
{
	float x, y, z;
} Vertex;

@interface PointCloud : NSObject
{
	Vertex *vertices;
	Vertex min, max;
	unsigned int count;
}

-(id)initWithCount:(unsigned int)count;

-(void)calculateMaxMin1;
-(void)calculateMaxMin2;
-(void)calculateMaxMin3;

@end

@implementation PointCloud
-(id)initWithCount:(unsigned int)pCount
{
	if(self = [super init])
	{
		count = pCount;
		vertices = (Vertex*)malloc(sizeof(Vertex)*count);

		unsigned int i;
		for(i=0;i<count;++i)
		{
			vertices[i].x = 4. * sinf(i);
			vertices[i].y = 4. * cosf(i);
			vertices[i].z = 4. * sinf(i)+cosf(i);
		}
	}
	return self;
}

-(void)calculateMaxMin1
{
	if(count == 0)
		return;

	min.x = max.x = vertices[0].x;
	min.y = max.y = vertices[0].y;
	min.z = max.z = vertices[0].z;

	unsigned int i;

	for(i = 1; i < count; ++i)
	{
		if(vertices[i].x > max.x)
			max.x = vertices[i].x;
		if(vertices[i].y > max.y)
			max.y = vertices[i].y;
		if(vertices[i].z > max.z)

			max.z = vertices[i].z;

		if(vertices[i].x < min.x)
			min.x = vertices[i].x;
		if(vertices[i].y < min.y)
			min.y = vertices[i].y;
		if(vertices[i].z < min.z)
			min.z = vertices[i].z;
	}
}

-(void)calculateMaxMin2
{
	if(count == 0)
		return;

	min.x = max.x = vertices[0].x;
	min.y = max.y = vertices[0].y;
	min.z = max.z = vertices[0].z;

	unsigned int i, lCount = count;

	for(i = 1; i < lCount; ++i)
	{
		if(vertices[i].x > max.x)
			max.x = vertices[i].x;
		if(vertices[i].y > max.y)
			max.y = vertices[i].y;
		if(vertices[i].z > max.z)
			max.z = vertices[i].z;

		if(vertices[i].x < min.x)
			min.x = vertices[i].x;
		if(vertices[i].y < min.y)
			min.y = vertices[i].y;
		if(vertices[i].z < min.z)
			min.z = vertices[i].z;
	}
}

-(void)calculateMaxMin3
{
	if(count == 0)
		return;

	unsigned int i, lCount = count;
	Vertex *verts = vertices;
	Vertex lMax = verts[0], lMin = verts[0];

	for(i = 1; i < lCount; ++i)
	{
		if(verts[i].x > lMax.x)
			lMax.x = verts[i].x;
		if(verts[i].y > lMax.y)
			lMax.y = verts[i].y;
		if(vertices[i].z > lMax.z)
			lMax.z = verts[i].z;

		if(verts[i].x < lMin.x)
			lMin.x = verts[i].x;
		if(verts[i].y < lMin.y)
			lMin.y = verts[i].y;
		if(verts[i].z < lMin.z)
			lMin.z = verts[i].z;
	}
	max = lMax;
	min = lMin;
}
@end

int main()
{
	unsigned int i;
	double then, now;

	printf("Initializing Object...\n");

	PointCloud *p = [[PointCloud alloc] initWithCount:ELEMENTS];

	printf("Performing tests...\n");

	then = CFAbsoluteTimeGetCurrent();
	for(i=0;i<ROUNDS;++i)
		[p calculateMaxMin1];
	now = CFAbsoluteTimeGetCurrent();
	printf("Method1: %f\n", (now-then)/ROUNDS);

	then = CFAbsoluteTimeGetCurrent();
	for(i=0;i<ROUNDS;++i)
		[p calculateMaxMin2];

	now = CFAbsoluteTimeGetCurrent();
	printf("Method2: %f\n", (now-then)/ROUNDS);

	then = CFAbsoluteTimeGetCurrent();
	for(i=0;i<ROUNDS;++i)
		[p calculateMaxMin3];
	now = CFAbsoluteTimeGetCurrent();
	printf("Method3: %f\n", (now-then)/ROUNDS);

	return 0;
}

So, in a nutshell:  we’ve got a Vertex structure, which holds an x, y, and z coordinate.  Then, we have a PointCloud object, which holds a bunch of points.  It also stores a max vertex, and a min vertex.  These would be used to create crude axis-aligned bounding boxes, or for set normalization or something.

And our task is finding the maximum and minimum x, y, and z values in the cloud.  (bonus points for using the phrase “in the cloud” without using buzzwords .  The algorithm to do this is pretty simple:  set our max/min value to the initial point in the cloud, and then check every other point to see if it’s higher than our max, or lower than our min.  If it is, set the max or min as needed, and continue.  In Computer Science class, they’ll tell you that this algorithm is O(N), which doesn’t suck too severely.  I believe it’s the optimal way to solve this problem (for an unordered set, at least), but I could be mistaken.

Anyway, to solve our problem, I have supplied 3 example methods:  calculateMaxMin1, calculateMaxMin2, and calculateMaxMin3.  They all follow the same pattern, but they have measurably different performance characteristics.

Let’s talk about these methods.  The first method uses only ivars.  The loop checks against count (an ivar), and it updates max/min (ivars) based on the vertices array (also an ivar).

The second method, calculateMaxMin2, is basically the same as calculateMaxMin1, except that instead of vertexCount, it stores the count locally in a local variable called “lCount”.

The third and final method, calculateMaxMin3, still follows the above pattern, but uses local variables of count, max/min, and the vertices array.

A casual glance at the code would lead one to believe that the running time for any of the three methods would be similar (with the last one possibly taking a teeny-tiny bit longer because it’s doing a couple more copies… probably immeasurably small though, as in 15 nanoseconds tops).  Instead of guessing though, we’ll run it and see what happens.

Running the program (for 4,194,304 points), we get this as the output:

cwright@phendrana:~/projects/ivar>./ivar
Initializing Object…
Performing tests…
Method1: 0.043917
Method2: 0.038990
Method3: 0.024590

Interpreting the results, we see that Method1 takes about 0.044 seconds to run, Method2 takes a little less, at 0.039 seconds, and Method3 takes a stunning 0.025 seconds to complete the exact same task.

Why does Method3 take so much less time?  It takes just 55% as long as Method1, yet it’s doing the same amount of work!

The answer lies in how the compiler/optimizer treats ivars compared to local variables.

Let’s pull out some assembly output to see what’s happening behind the scenes.  (This is going to get a bit more complicated, but don’t worry!)

calculateMaxMin1′s inner loop assembly code looks like this:

+59    00001a2d  f30f100401              movss          (%ecx,%eax),%xmm0
+64    00001a32  0f2e4214                  ucomiss      0×14(%edx),%xmm0
+68    00001a36  7605                      jbe          0x00001a3d
+70    00001a38  f30f114214              movss          %xmm0,0×14(%edx) (Vertex)max
+75    00001a3d  f30f10440104              movss          0×04(%ecx,%eax),%xmm0
+81    00001a43  0f2e4218                  ucomiss      0×18(%edx),%xmm0
+85    00001a47  7605                      jbe          0x00001a4e
+87    00001a49  f30f114218              movss          %xmm0,0×18(%edx)
+92    00001a4e  f30f10440108              movss          0×08(%ecx,%eax),%xmm0
+98    00001a54  0f2e421c                  ucomiss      0x1c(%edx),%xmm0
+102    00001a58  7605                      jbe          0x00001a5f
+104    00001a5a  f30f11421c              movss          %xmm0,0x1c(%edx)
+109    00001a5f  f30f100c01              movss          (%ecx,%eax),%xmm1
+114    00001a64  f30f104208              movss          0×08(%edx),%xmm0 (Vertex)min
+119    00001a69  0f2ec1                  ucomiss      %xmm1,%xmm0
+122    00001a6c  7605                      jbe          0x00001a73
+124    00001a6e  f30f114a08              movss          %xmm1,0×08(%edx) (Vertex)min
+129    00001a73  f30f104c0104              movss          0×04(%ecx,%eax),%xmm1
+135    00001a79  f30f10420c              movss          0x0c(%edx),%xmm0
+140    00001a7e  0f2ec1                  ucomiss      %xmm1,%xmm0
+143    00001a81  7605                      jbe          0x00001a88
+145    00001a83  f30f114a0c              movss          %xmm1,0x0c(%edx)
+150    00001a88  f30f104c0108              movss          0×08(%ecx,%eax),%xmm1
+156    00001a8e  f30f104210              movss          0×10(%edx),%xmm0
+161    00001a93  0f2ec1                  ucomiss      %xmm1,%xmm0
+164    00001a96  7605                      jbe          0x00001a9d
+166    00001a98  f30f114a10              movss          %xmm1,0×10(%edx)
+171    00001a9d  43                      incl          %ebx
+172    00001a9e  83c00c                  addl          $0x0c,%eax
+175    00001aa1  3b5a20                  cmpl          0×20(%edx),%ebx (unsigned int)count
+178    00001aa4  7287                      jb          0x00001a2d

Note all the jumps (jbe, highlighted in red), the overall length (+59 to +180 bytes, or 121 bytes in total (180-59)), and how our ivars are loaded/stored (movss (%ecx,%eax),%xmm0 loads max.x, for example, highlighted in blue).

Now let’s contrast it with calculateMaxMin3′s inner loop:

+62    00001ba2  f30f10500c              movss          0x0c(%eax),%xmm2
+67    00001ba7  0f28c2                  movaps      %xmm2,%xmm0
+70    00001baa  f30f5fc5                  maxss          %xmm5,%xmm0
+74    00001bae  0f28e8                  movaps      %xmm0,%xmm5
+77    00001bb1  f30f104810              movss          0×10(%eax),%xmm1
+82    00001bb6  0f28d9                  movaps      %xmm1,%xmm3
+85    00001bb9  f30f5fdc                  maxss          %xmm4,%xmm3
+89    00001bbd  0f28e3                  movaps      %xmm3,%xmm4
+92    00001bc0  f30f104014              movss          0×14(%eax),%xmm0
+97    00001bc5  0f28d8                  movaps      %xmm0,%xmm3
+100    00001bc8  f30f5f5df4              maxss          0xf4(%ebp),%xmm3
+105    00001bcd  f30f115df4              movss          %xmm3,0xf4(%ebp)
+110    00001bd2  f30f5d55f8              minss          0xf8(%ebp),%xmm2
+115    00001bd7  f30f1155f8              movss          %xmm2,0xf8(%ebp)
+120    00001bdc  f30f5dcf                  minss          %xmm7,%xmm1
+124    00001be0  0f28f9                  movaps      %xmm1,%xmm7
+127    00001be3  f30f5dc6                  minss          %xmm6,%xmm0
+131    00001be7  0f28f0                  movaps      %xmm0,%xmm6
+134    00001bea  42                      incl          %edx
+135    00001beb  83c00c                  addl          $0x0c,%eax
+138    00001bee  39da                      cmpl          %ebx,%edx
+140    00001bf0  72b0                      jb          0x00001ba2

No jump instructions, except for the loop’s jb at the end.  Size is +62 to +142 (80 bytes, almost 30% smaller!), and most of our variables live in registers (note how xmm0-xmm7 are all utilized, and %ebp (stack spillage) is only used twice, at 0xf4, and 0xf8.  Aside from the blue highlighted load/store lines, everything lives in a register, ready for screaming fast access (granted, most ivars will live in L1, so they’re only half as fast as registers, but as we see from the profiling above, that half-speed hit is actually measurable, even from L1!).

So, let’s analyze this a bit.  Our loop code’s smaller (so it can complete about 33% more loops per unit of time).  But that’s only part of the benefit.  We also get no jumps.  No jumps means no mis-predicted jumps, which helps the CPU pipeline stay loaded.  And finally, we have almost no memory loading except for the vertex data itself (and a tiny bit of stack spillage).  This means more CPU-RAM (or CPU-L1 Cache even) bandwidth is spent on loading relevant data, instead of reloading/storing ivars all the time.

Why are ivars implemented this way?  Because a method needs to work on fresh data at all times — if another thread comes along and changes an ivar on the object, it wouldn’t make sense to keep using stale data.  Local variables, in contrast, aren’t at all likely to get modified by another thread (you can do it, but it’s a rather contrived example).  As such, the compiler knows exactly when a value changes, and can let it live on the cpu for as long as possible, for optimum speed.

Disclaimer stuff:  This is a silly problem to solve, but it illustrates the point nicely.  There are better solutions (using SSE to check 4 values at once, and then coalescing at the end, for example), but that’s not the point.  Here we see how we can speed up (by almost a factor of 2!) loop intensive code by simply avoiding ivars in heavily trafficked loops.

Compiler command line to build:   gcc-4.2 ivar.m -o ivar -Os -g -framework Cocoa