For this first post, let’s explore allocating, deallocating, and protecting memory pages.

The functions we’re interested in here are vm_allocate, vm_deallocate, and vm_protect.  You can find them in /usr/include/mach/vm_map.h.

vm_allocate, unsurprisingly, allocates memory pages into a task (process).  It takes a target task (usually mach_task_self()), an address pointer, a size, and some flags.

The address pointer is often best left unspecified.  This allows the kernel to map in pages wherever there’s room.  on 64 bit systems this isn’t particularly interesting, but for 32 bit processes address space can be fairly constrained.

Size is often a multiple of a page size (4k, or 4096 bytes).  It defines how large of an area you want to map.

Flags is where things get interesting.  There are several to choose from, tersely documented in vm_statistics.h.  A couple notes on them:

VM_FLAGS_FIXED – This controls whether or not it should try to map the pages at the address you specified. It’s actually implied by the absense of VM_FLAGS_ANYWHERE.
VM_FLAGS_ANYWHERE – This indicates that it’s ok to ignore the input address, and simply allocate the pages wherever they’d fit (and return the base address in address).
VM_FLAGS_PURGABLE – This indicates that it’s ok for the pages to get purged (that is, discarded without first being written to disk).  This can be useful for caches and other data that can be recomputed.  I’ll discuss purging pages in a future update.
VM_FLAGS_NO_CACHE – This controls how the pager deals with prioritizing pages in low-memory situations.

vm_deallocate is used to undo an allocation.  Or in other words, free the memory vm_allocate makes use of.  It takes a task (again, often mach_task_self()), a base pointer, and a size.  It behaves largely how you might expect.

vm_protect is interesting (and potentially useful).  With it you can mark pages are readable (VM_PROT_READ), writable (VM_PROT_WRITE), and executable (VM_PROT_EXECUTE).  These are defined in /usr/include/mach/vm_prot.h.  Newly created pages (via vm_allocate) are readable and writable, but not executable.  There’s also a copy protection used for copy-on-write behavior, but that’s also for a future post.

Now for some sample code!

#include <mach/mach_interface.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
 
int main()
{
	unsigned char *base;
	kern_return_t ret;
 
	ret = vm_allocate(mach_task_self(), (vm_address_t*)&amp;base, 1024*1024,
					  VM_FLAGS_ANYWHERE);
	if (ret == KERN_SUCCESS) {
		printf("got allocation: %p\n", base);
		base[0] = 0x42;
	} else
		return -1;

this will allocate 1MB (256 pages) anywhere they’ll fit in the process. They’ll be read/write by default.

	ret = vm_protect(mach_task_self(), (vm_address_t)base, 4096, true, VM_PROT_NONE);
	if (ret == KERN_SUCCESS) {
		printf("access is now None!\n");
	} else {
		printf("setting permission to none failed!\n");
	}

This will set the pages to no access – no reads, no writes, no execution. This is pretty worthless, but it demonstrates something coming up

ret = vm_protect(mach_task_self(), (vm_address_t)base, 4096, true, VM_PROT_READ);
	if (ret == KERN_SUCCESS) {
		printf("access is now Read Only!\n");
	} else {
		printf("resetting protections failed\n");
	}

This would restore read permission to the pages, but the above call set the maximum protections to none. That will make this call fail (the pages will remain unreadable).

and finally, cleaning up

	ret = vm_deallocate(mach_task_self(), (vm_address_t)base, 1024*1024);
	if (ret == KERN_SUCCESS)
		printf("deallocated!\n");
	else
		printf("error deallocating!\n");
 
	return 0;
}

which will deallocate the pages.

And there you have it. Basic kernel-level memory allocation for your process. Now you can get page-aligned allocations of large slabs of memory (sometimes useful for storing GL textures with GL_APPLE_client_storage, among other things). Note that vm_allocate is _not_ faster than malloc/free. It is not wise to use these functions as a replacement for general allocation functions. Standard debugging tools will also not deal with these allocations (guard malloc won’t be able to help you, leaks won’t be able to help you, Instruments probably won’t be able to help you – vmmap will show them though, and you can tag them so that they stand out, using VM_MAKE_TAG as one of the vm_allocate flags).

It can also be useful for initializing some large set of data, and then marking it as read-only to ensure you don’t accidentally mutate it.

2010 shaped up to be the most tumultuous years of my life. Quite unexpectedly too.  A few things were in-flight from 2009 that we were expecting to watch unfold, but we had no way to predict just how volatile it would ultimately be.

First, there was the relocation.  That ball was set in motion back in 2009, but we weren’t entirely sure how it would play out (at one point, there were 3 destinations on the table, including Munich, Boston, and Cupertino;  the last ultimately won out after several bizarre twists and turns).  There are only a couple times in my life where I’ve actually relocated.  In fact, pretty much just two:  going out west, and getting married.  In both of those cases, while the venue was different, as were the people, I had a pretty good idea of what was going on.  This time, not so much.  Moving with a family (of 2, thankfully) was a much larger logistical nightmare than I had anticipated, and thankfully I was able to defer that to Alisa, who graciously liquidated 90% of our belongings, and coordinated shipping of the rest.  Further chronicles of this operation can be had elsewhere in previous posts.

Second was a new car.  Never in my life would I have predicted that.  Not because it was impossible, but because it’s financially untenable.  Never the less, it worked out rather well, and long-term we haven’t suffered severe financial hits.  It’ll always be a loss, but such things are — cars fundamentally aren’t investments (unless you keep them 50 years).  The total maintenance costs have been excitingly negligible ($57 for the entire year, for an overpriced oil change that looks to be due about every 9 months at our driving rate), which offsets the monthly payments (which aren’t so negligible).

Shortly after the car came news that Alisa was expecting.  And shortly after that, she started dying from hyperemesis.  A trip to LA and a week-long hospital stay got her all patched up, and we hit  our insurance deductible in about 6 hours.  We’ll be making payments on that for months to come.

A free ticket to a WWDC I wouldn’t participate in was a bit unexpected;  I was glad to attend, but felt a bit useless being a desktop developer amid an army of iOS folks.  It will be interesting to watch the balance of powers shift (as they already have) over the next few years as things continue moving.  I had a hand in making a pretty cool wall though, which was an interesting experience to say the least.

Afterward, things calmed down for a bit.  Then they didn’t.

I had performed at least as well as expected, and I got moved to full time before my contract was up.  That provided all kinds of perks (insurance!) and bonuses (stock!), but also meant more responsibility (accountability!).  Handling prototypes was interesting at first, but the novelty has worn off.  I remember carefully unboxing my MacBook back in 2007, keeping all the pieces nice and dainty.  I’ve now unboxed untold number of systems, and find the packaging to be wearying.  “You mean I have to slide open another full-sized keyboard box again?” *sigh*.  Yes, everyone, I have truly become George Jetson.

Shortly after that there was a reorganization internally.  I’m still not sure what I can say about it, but it suffices me to say that things change in a quite unexpected manner (only one guy changed buildings though, and no one was fired, so perhaps it wasn’t that radical;  it sure felt like it at the time though).

A few more weeks of silence, and then somebody has the gall to show something to Steve Jobs.  I don’t know who it was, but I know what they showed.  Luckily, Steve liked it.  Unluckily, that meant our little team had to build it.  For a demo.  Aired live.  Nationally.  In 4 weeks.  We scrambled, scratched our heads, argued, pointed fingers, argued some more, called an intern back in for a week, and got carte blanche to tell other teams they weren’t working on Steve’s demo and thus re-prioritize their work for them.  To be fair, several other teams did a huge amount of work too, and in the end it went quite well.

The remainder was a blur.  Holidays such as Thanksgiving, Christmas, and New Years littered holiday time off in between periods of work.  Somewhere in there there was a holiday party at the Half Moon Bay Ritz Carlton;  Alisa and I had a lot of fun, and look forward to more cool parties like that (hopefully with better appetizers though).  Then back to work one last time before the last week before everything shut down.  18 hours into vacation, Alisa went into labor, and 18 hours after that Penelope was born on December 25th.  Alisa’s parents were on hand to cook up a storm and otherwise hold down the fort as we ferried to and from the hospital for a few days until they were able to come home in good spirits.  Those quickly faded, and Penny’s insatiable appetite prevented us from getting more than a couple hours of sleep at a time for the first several nights.

After all was said and done, by the time December 31st rolled around I was tired.  I rang in the new year in an unconscious heap upon my bed, only to be woken shortly thereafter by the dinner bell that tolls not for me.

MMXI is set to look even crazier…

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.