Apple's Grand Central Dispatch Ported To FreeBSD

bonch writes "Apple's Grand Central Dispatch, which was recently open sourced, has been ported to FreeBSD and is planned to be included by default in FreeBSD 8.1. Also known as libdispatch, the API allows the use of function-based callbacks but will also support blocks if built using FreeBSD's clang compiler package. There's already discussion of modifying BSD's system tools to use the new technology." The port was originally unveiled last month at the 2009 Developer Summit in Cambridge. Slides from that presentation are available via the Dev Summit wiki.

Comments

Bad Apple

[93 Escort Wagon]

Always taking from the open source community, and never giving back!

Multicore Enhancements!! :)

[jpedlow]

My first question was "So...what does this do?" Apparently it is a more efficient way of scheduling threads on multi-core systems http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090903.pdf apple's site says this: "Grand Central Dispatch (GCD) in Mac OS X Snow Leopard addresses this pressing need. It’s a set of first-of-their-kind technologies that makes it much easier for developers to squeeze every last drop of power from multicore systems. With GCD, threads are handled by the operating system, not by individual applications. GCD-enabled programs can automatically distribute their work across all available cores, resulting in the best possible performance whether they’re running on a dual-core Mac mini, an 8-core Mac Pro, or anything in between. Once developers start using GCD for their applications, you’ll start noticing significant improvements in performance. " So this seems good then.

Re:Multicore Enhancements!! :)

[zn0k]

While you certainly don't deserve a "Troll" rating, the real improvement GDC brings over current implementations of concurrency is that one central authority is aware of all GDC enabled applications, and can therefore make decisions with knowledge of the entire system load and its capabilities when spinning of threads. When you spin of threads independently in each app you have to guess what the rest of the system looks like. You also have to either guess, investigate or have the user configure the general capabilities of the system.

Re:Multicore Enhancements!! :)

[moosesocks]

Ars Technica has a great overview of what GCD is, and why it's important.

I haven't done much multithreaded programming in C, although this looks like an absolute godsend to those who do. Maybe someday we can actually have a modern desktop as responsive as BeOS was...

The article also contains a bit of information about Apple's compiler strategy and refinements to the C language itself. Most of these have been open-sourced under a permissive license, which is pretty damn cool.

Re:Multicore Enhancements!! :)

[wootest]

GCD is far more encompassing than just spawning threads. It's mainly a library for task-based parallelization (my wording, not theirs) and has some other goodies in it as well.

For starters, unless it's not apparent by now, just spawning a new thread to run every such job is too heavy. Scheduling a new GCD job (and all of them will get run on one of a bunch of thread pool threads) is on the range of tens of CPU instructions; on Mac OS X, where GCD originated, spawning a new thread steals away in the vicinity of one megabyte (I can't seem to find an exact number) just for various bookkeeping. That's a lot of setup; even if there's a lot of fat to cut there, the best solution is probably not to spawn a new thread every time.

The API is also very neatly designed. Tasks can be created and added to groups or queues and run synchronously or asynchronously. Semaphores, queues and event sources (which will trigger the addition of an event handler to a queue automatically) can all be paused and resumed to more easily control the flow. Neat, especially combined with the creation of queues that you set up to just funnel work onto another queue.

Add to that the existence of several global queues with varying priorities (corresponding to a set of worker threads at each priority) and the potential for smarts for a system that can see the entire picture with regards to load within the program and across the system. I don't know the extent to which such smarts exist already, but I think you'll agree that with more metadata available, such a scheduler would be better equipped than one fiddling with coarser-grained threads.

So yeah, this is nothing like "just" spawning threads. (I've never worked directly with pthread; it may very well reuse threads, but it didn't look like it from the man page you referred to.) None of it, as far as I can tell, is Apple inventing something new and breakthrough, but it's still a damn good API with a good consolidated set of computationally cheap features whose level of abstraction solves problems.

Re:Multicore Enhancements!! :)

[Stratoukos]

Maybe someday we can actually have a modern desktop as responsive as BeOS was...

BeOS was indeed very responsive, but it was also notoriously difficult to program for. Apple seems to have done a great job at creating a powerful framework, while keeping it easy enough to be actually used by the developers.

Re:Multicore Enhancements!! :)

[Just Some Guy]

Been there, done that on Solaris and Linux 10 years ago in plain old C. No magic required, just

#include <pthread.h>

and away you go.

Piece of cake! Of course, you have no idea how many other processes are tossing threads at their workload and so have no idea if this is a great time to spawn another 8 to really load out the CPU or whether you should just spawn 2 and let some other processes have their time. That's what GCD buys you.

Re:Multicore Enhancements!! :)

[Anonymous Coward]

In your zeal to take one statement out of context, you missed the point of the framework. Using dispatch queues, I don't have to create threads, an expensive operation, and I don't have to agonize over performance profiles to determine the right number of threads to use. The operating system automatically maintains a global pool of worker threads based on available system resources, and you submit an asynchronous block of code which the system will assign to a thread and run for you based on current system state--that's what the "automatically distribute their work across all available cores" part means. Quite different from merely creating a pthread. Your code will run in an optimal number of threads for the system it's on, whether it's a Mac Mini Core Solo or an eight-core Mac Pro.

You can even distribute the iterations of a for-loop across queues using dispatch_apply(). Imagine doing a lot of expensive work on items in a collection, automatically threaded for the cores of the system it's running on. Here's an intro to Grand Central Dispatch. The followup articles on the site are also recommended.

The API to submit a block for asynchronous execution is very simple:

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        do_something_computationally_expensive();
});

Posting anonymously since my "bonch" account has been modbombed.

Re:They should use clang instead of GCC

[larry bagina]

Apple maintains their own gcc fork which supports blocks/closures.

Re:Apple's Grand Central Dispatch Ported To FreeBS

[larry bagina]

now it can die in parallel, optimized for the number of cores and other system activity.

No because they are different

[SuperKendall]

GCD is a mechanism to let one central authority dispatch threads across multiple cores, for all running applications (including the OS).

The other two things you mentioned are ways for programs to more easily use multiple threads, but they are still threads under the main process and not centrally managed - so you have to decide blind how much of the system you can take for your threading needs.

You can compare the Blocks syntax to ways those two systems specify work units to be done in parallel, but that is just a part of the story.

Re:No because they are different

[norton_I]

GCD is a mechanism to let one central authority dispatch threads across multiple cores, for all running applications (including the OS).

This is what most people talk about, and what is most obvious from the name, but it is not the interesting part of GCD.

The interesting part of GCD is blocks and tasks, and it is useful to the extent which it makes expressing parallelism more convenient to the programmer.

The "central management of OS threads" is marketing speak for a N-M scheduler with an OS wide limit on the number of heavyweight threads. This is only useful because OS X has horrendous per-thread overhead. On Linux, for instance, the correct answer is usually to create as many threads as you have parallel tasks and let the OS scheduler sort it out. Other operating systems (Solaris, Windows) have caught up to Linux on this front, but apparently not OS X. If you can get the overhead of OS threads down to an acceptable level, it is always better to avoid multiple layers of scheduling.

GCD is not multithreading, it's thread management

[diamondsw]

Grand Central is not introducing multithreading - it's introducing comprehensive thread management. So, how many threads are you going to spin for that task? Too many, and you waste a lot of time on thread management and preemption. Too few, and you have processors sitting idle. Now how will you handle this with multiple CPU's? Multiple cores? Hyperthreading? Different cache amounts and layout? OpenCL and GPU processing? Do you know what the rest of the operating system is doing to plan appropriately?

In short, your program can at best make a stab at these issues, and possibly even do a reasonable job if you put a lot of time, effort, and profiling into it. Or you could just use GCD, and let the framework handle it all for you, regardless of whether you're on a Core Solo Mac Mini or a Mac Pro with mutliple OpenCL graphics cards.

It's good stuff. And Apple gave it to the community (much like WebKit enhancements, launchd, etc).

Re:In other news...

[wootest]

Richard Stallman does not cry into his beer. Microsoft cries into their beer. Richard Stallman cries into his freedom.

Re:No. Really?

[beelsebob]

Yep, apple didn't give back all their code on WebKit, or all of Darwin, or all of launchd, or all their patches on zfs, or their code on MacPorts, or darwin streaming server, or CalDav, or iCal format, or their Calander server, or their code on their X server, or their code on ruby, or a bunch of code on smart card services...

Wait, yes they did.

Thank goodness for the GPL

[Anonymous Coward]

Thanks goodness for the GPL, or we might never have convinced Apple to release its code so that FreeBSD could use it!

Wait... what is that? Oh, nevermind then...

Re:Thank goodness for the GPL

[TheRaven64]

Clang is BSD licensed and, unlike GCC, supports blocks on FreeBSD and Linux, as long as you have the relevant runtime library. Etoile has been shipping one (MIT licensed) for about six months. Libdispatch is new code from Apple and is Apache 2 licensed, which is incompatible with the GPLv2 (GPLv3 has a special exemption for it).

Re:No. Really?

[zach_the_lizard]

Yes, WebKit is based on KHTML; Apple forked it, IIRC.

Re:No. Really?

[DurendalMac]

Several things didn't need to be open sourced, such as WebObjects and GCD. Quit your crying. FOSS zealots love to whine about Apple only doing what's required, but they fail to realize that it's a symbiotic relationship. Apple can use existing code to fit their needs, and in return, the open source community gets all of the improvements made by professional coders. It's a win/win, but the mini-Stallmans will never see it that way.

They are not mini-stallmans. They are Apple Haters

[SuperKendall]

It's a win/win, but the mini-Stallmans will never see it that way.

To the contrary: I am a huge fan of Stallman's philosophy and see Apple's work as win/win.

The people that are complaining are the looney Apple Haters, who try and find any point possible by which to attack Apple - never realizing until it is to late the latest position they are attacking from makes no sense.

Please do not taint all those of us who respect the GPL with the same brush the Haters paint themselves in corners with.

Re:No. Really?

[Jerry Smith]

When is the last time that Apple released an entirely new project? For example Sun released ZFS under the CDDL.

Why reinvent the wheel? They adopt it, improve it and release the improvements. At least they add. They deliver. When is the last time Stallman released an entirely new project? Or finished one? "Although nearly all components have been completed long ago and have been in production use for a decade or more, its official kernel, GNU Hurd, is incomplete and not all GNU components work with it." from the reliable-as-ever Wikipedia. Apple is not Stallman. They do not serve the same market. Apple is in hardware/software/platform, Stallman is in philosophy. Fair enough, einen Unterschied muß es geben.

Re:They should use clang instead of GCC

[jcr]

The probability that Apple migrates away from gcc is approaching 1 at great speed.

That writing's been on the wall for quite a long time now. GCC has been a severe limitation on what they could do with Xcode for far too long. With LLVM, I'm expecting shortly to get away from the edit/compile/debug cycle and have a pause/edit/resume cycle instead.

Right now in Quartz Composer, you can write GL SLANG shaders that are compiled on the fly as you type. It's amazing to see the effects of changes immediately.

-jcr

Re:No. Really?

[gutter]

Well, we have the subject of this article, Grand Central Dispatch. We also have Darwin & XNU, their version of the Mach kernel. There is also Bonjour, their version of zeroconf, and their streaming server (Quicktime Streaming Server). They also purchased the source to gimp-print (now called Gutenprint) so they no longer have any obligation to keep it open source, but they do, and they keep releasing the source. How much more do you need?

Re:No. Really?

[Anonymous Coward]

But apart from CUPS, LLVM/clang, Webkit, Darwin, launchd, patches for zfs, MacPorts, darwin streaming server, CalDav, iCal, the Calendar server, code for Ruby, code for X server and GCD, what has Apple ever done for us?

Re:They should use clang instead of GCC

[TheRaven64]

A massive case of NIH from the GCC team with regard to Apple. See also the patches that Apple submitted well over a year ago adding declared property support to GNU gcc. I found it easier to write all of the code required for clang to support the GNU Objective-C runtime than make even small changes to Objective-C support in GCC (in spite of not having used C++ for a few years and really hating the language).

Oh, and I've had blocks working with clang on FreeBSD for quite a while (since several months before Apple publicly released an OS supporting them, in fact). I added the required runtime library support into Etoile's ObjectiveC2 framework a while ago, which also provides the run time support for most of the Objective-C 2 features. This framework is going to go away soon, because I'm now maintaining a fork of the GNU Objective-C runtime in the GNUstep repository, which merges these improvements and also incorporates most of the ideas from my experimental Objective-C runtime library (without breaking backwards compatibility, although you don't get all of the features if you don't use the new ABI).

By the way, porting to *BSD is much easier than porting to Linux. Libdispatch is based around the kqueue mechanism for unifying kernel event sources, and there is currently no in-tree equivalent for Linux. There are four out-of-tree sets of patches providing equivalent functionality (that I know of, there may be more), as is common with Linux development. On Solaris you can do the same thing with completion ports, which are roughly semantically equivalent but have a different interface.

Re:That is more interesting but not what is differ

[TheRaven64]

Thread creation on Linux is much more expensive than adding a new block to a queue with GCD. This uses 'under 15 instructions'. That's slightly misleading because, on x86, one of those instructions has the LOCK prefix and so is quite expensive, but it's still only marginally more expensive than the cost of a function call. In contrast, creating a thread, at minimum, on Linux has these costs:

• Allocate at least one page for the stack.
• Allocate at least one page for the TLS segment and copy its data across.
• Create the in-kernel data structures required for the thread and insert it into the run queue (this involves a context switch into kernel space and back).

This is between one and two orders of magnitude more expensive than adding a block to a work queue with GCD.

Switching between the threads is also relatively expensive. At the very least, you need to save all of the registers and update the stack pointer (probably in response to a timer interrupt, so also factor in the cost of a transition from kernel space to users pace). With GCD, the kernel will give you one thread per CPU for each priority level (or fewer if there are already lots of CPU-bound threads), so you minimise number of context switches.

This is effectively what an N:M scheduler does, but is slightly better. With an N:M scheduler, you are switching between some threads in userspace, which saves some overhead, but the threads still have largely-disjoint working sets and so you end up with more cache churn (performance killer on modern CPUs). With GCD, you will only be switching between work queues in a given thread between blocks, so there is no cache churn (the old block's cache lines are no longer needed, so you'll kick them out but not then bring them back in immediately). The other nice side effect of this is that, because GCD knows which work queues are assigned to which threads, it can remove locks used for passing messages between work queues if both queues are in the same threads.

In short, it's an N:M threading model with preemptive kernel threads and cooperative userspace threads. If you read an OS textbook, you'll see that this is, at least in theory, about the most efficient scheduling model possible.