Re: Grand Central
This block thingy looks interesting. Oh, while we're on the topic of
multi-processors, I've invented an algorithm that allows parallel
lock-less insertions on a linked list. Could be useful for
NSConnections, as it's WAY more efficient than anything else I've ever
seen (and, yes, I am including NSMutableArray methods here). It does
come at a price: it requires an atomic swap operation i.e. assembly.
The good news is that only one instruction is needed so the
portability issue isn't at the I feel like kissing the barrel of a
shotgun. I'll submit the paper for it as soon as Ive finished
polishing it, shoulda been this week (I am so fuckin' lazy...and
studying...and trying to work, don't ask).
On Sun, Jun 14, 2009 at 10:27 AM, Jens Aytonmailing-lists.j...@ayton.se wrote:
On Jun 14, 2009, at 14:53, Pete French wrote:
http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090608.pdf
Interesting - that ^{ syntax to describe a block is somewhat ugly, and it
doesnt
give any deats of how you associate data with a block (which is necessary
if
you want to get rid of locks).
There are two ways to pass data into blocks: constant copies from the parent
scope, and mutable access to block variables in the parent scope (the
latter makes blocks true closures). Here is a simple example:
typedef int (^IntIntBlock)(int);
IntIntBlock MakeExampleThing(int initial, int delta)
{
__block int accum = initial;
int (^block)(int) = ^(int i) { return accum += i + delta; };
return Block_copy(block);
}
In the block created above, accum is a block variable, and delta is a const
copy. If MakeExampleThing() is called twice, they get separate copies of
accum, so there's your data associated with the block. If two blocks were
created in the same function, both referring to accum, they would share it.
int main(void)
{
int (^a)(int) = MakeExampleThing(5, 2);
int (^b)(int) = MakeExampleThing(1, 0);
printf(%i\n, a(3)); // prints 10
printf(%i\n, b(1)); // prints 2
Block_release(a);
Block_release(b);
return 0;
}
The block runtime is set up to allow blocks to be ObjC objects, so that
Block_copy() and Block_release() can be replaced with retain and release
messages. (Block_copy() is conceptually a retain operation, although it
actually does copy in the above example because the block is initially
created on the stack.)
In case the new syntax and manual memory management overhead gets in the way
in the above code, here's a Javascript equivalent:
function MakeExampleThing(initial, delta)
{
return function(i)
{
return initial += i + delta;
}
}
I can't work out if GCD is supposed to be an extension for OSX or an
extension
to Objective-C itself. Obviously the block syntax requiures a language
extension,
but how do the bits fit together from there onward ?
Other than blocks, as far as I can see (I don't have Snow Leopard seeds)
it's just a library and an optimized thread scheduler.
--
Jens Ayton
___
Gnustep-dev mailing list
Gnustep-dev@gnu.org
http://lists.gnu.org/mailman/listinfo/gnustep-dev
--
Besos, abrazos, confeti y aplausos.
Jamie Ramone
El Vikingo
___
Gnustep-dev mailing list
Gnustep-dev@gnu.org
http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: Grand Central
On 15 Jun 2009, at 09:28, Jamie Ramone wrote: This block thingy looks interesting. Oh, while we're on the topic of multi-processors, I've invented an algorithm that allows parallel lock-less insertions on a linked list. Could be useful for NSConnections, as it's WAY more efficient than anything else I've ever seen (and, yes, I am including NSMutableArray methods here). It does come at a price: it requires an atomic swap operation i.e. assembly. The good news is that only one instruction is needed so the portability issue isn't at the I feel like kissing the barrel of a shotgun. I'll submit the paper for it as soon as Ive finished polishing it, shoulda been this week (I am so fuckin' lazy...and studying...and trying to work, don't ask). We're straying off-topic here, but have you read Keir Fraser's PhD thesis? He presents a lockless way of inserting into a linked list which only requires an atomic swap and a proof of its correctness. EtoileThread and MediaKit both use a hybrid structure based on the lockless ring buffer from this thesis (modified to permit it to enter a locked mode when there is no traffic and avoid polling; if the buffer stays full, there is no locking, when it empties the consumer thread waits on a condition variable). He also describes a concurrency-safe skip list implementation; this would be worth using for NSMutableArray if people want to use it concurrently (or to provide a GSConcurrentMutableArray, as a thread-safe NSMutableArray subclass). Atomic compare-and-swap is one of the builtins provided by clang and recent GCCs. Assembly is only needed while we continue to support archaic compilers. David ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: Getting reviews and submitting patches
В Sun, 14 Jun 2009 18:56:40 +0100, Richard Frith-Macdonald написа: On 14 Jun 2009, at 17:20, Dave MacLachlan wrote: Google has signed off on having them submitted to the project, so the legal steps are taken care of already. Including copyright assignment to the FSF? That's a requirement for anything substantial. Some companies (e.g. Red Hat, Google) have blanket copyright assignment which is valid for all employees (and all GNU packages). So if the contribution is made on behalf of Google and Dave is an employee, no personal assignment is necessary. ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: NSCalendar and NSLocale support
It is still readily available ( for instance, http://www.opencsw.org/packages/libicu ), and is required by common software such as OpenOffice. I remember looking into it a few years ago for my job, when estimating the effort to support non-English languages in our application. --Robert On Jun 15, 2009, at 4:07 AM, Richard Frith-Macdonald wrote: On 15 Jun 2009, at 00:26, Lars Sonchocky-Helldorf wrote: Am 14.06.2009 um 23:10 schrieb Riccardo Mottola: Hi, Dave MacLachlan wrote: Hey there... I'm looking to add NSCalendar and NSLocale to Foundation. I'm happy to implement them, but I was hoping to do it on top of ICU (http://site.icu-project.org/ ). Are we willing to add a dependency on ICU to gnustep? This is a typical dilemma. Usually I am a friend of having the smallest set of dependencies possible. I checked and ICU is for example readily available in gentoo (if not, I would have really worried) but it is not for example available on sunfreeware, this tells me that it is not that widespread. Really? SUN should use it: This link suggests that it ships with solaris 9 and 10 but not 8 or earlier ... http://sunsolve.sun.com/search/document.do?assetkey=1-66-233922-1http://sunsolve.sun.com/search/document.do ?assetkey=1-66-233922-1 ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: NSCalendar and NSLocale support
Hi Dave, Dave MacLachlan wrote: Hey there... I'm looking to add NSCalendar and NSLocale to Foundation. I'm happy to implement them, but I was hoping to do it on top of ICU (http://site.icu-project.org/). Are we willing to add a dependency on ICU to gnustep? The ICU license is GNU GPL compatible... http://userguide.icu-project.org/icufaq#TOC-How-is-the-ICU-licensed- Or perhaps I should be looking somewhere else? From a glance at what dependencies debian lists for that package that it requires C++. I would really dislike to have a hard dependency on something which requires C++. http://packages.debian.org/lenny/libicu38 Riccardo ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: NSCalendar and NSLocale support
Hi, Lars Sonchocky-Helldorf wrote: Really? SUN should use it: from http://site.icu-project.org/: cut: a long list of references Thanks, I am capable of looking up that myself. In fact, i even did before replying to the email. Besides, many of those references are more or less just there to make number. What does it mean that SuSE supports ICU? Well, I guess they package it. As Gentoo or Debian do. But do I have it installed? On one system I have it, just because I have Wine. I'm not saying it is a bad library and I am not saying it is not available. But I want to avoid me too logic. And I dislike depending on something which is C++. On the other hand, on Debian, if you have gworkspace you want libsqlite which on Debian is configured to use libicu so you end up using it. But on other systems libsqlite does not need libicu at all. A good solution could be then an internal, simplified, fall-back solution so not to have a hard dependency on it. It really depends on how much functionality is needed. Maybe the fall-back implementation ends up being very difficult or maybe it would cover 99% of what libicu does. Dave can tell us surely more. Riccardo ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: Grand Central
On Mon, Jun 15, 2009 at 6:42 AM, David Chisnallthera...@sucs.org wrote: On 15 Jun 2009, at 09:28, Jamie Ramone wrote: This block thingy looks interesting. Oh, while we're on the topic of multi-processors, I've invented an algorithm that allows parallel lock-less insertions on a linked list. Could be useful for NSConnections, as it's WAY more efficient than anything else I've ever seen (and, yes, I am including NSMutableArray methods here). It does come at a price: it requires an atomic swap operation i.e. assembly. The good news is that only one instruction is needed so the portability issue isn't at the I feel like kissing the barrel of a shotgun. I'll submit the paper for it as soon as Ive finished polishing it, shoulda been this week (I am so fuckin' lazy...and studying...and trying to work, don't ask). We're straying off-topic here, but have you read Keir Fraser's PhD thesis? He presents a lockless way of inserting into a linked list which only requires an atomic swap and a proof of its correctness. No I haven't, I'll look it up later. Thanx dude. Not that much off-topic as we're mainly talking about concurrency. If you like, we can just splinter this thread and keep presenting different concurrency algorithms to consider and compare there. EtoileThread and MediaKit both use a hybrid structure based on the lockless ring buffer from this thesis (modified to permit it to enter a locked mode when there is no traffic and avoid polling; if the buffer stays full, there is no locking, when it empties the consumer thread waits on a condition variable). He also describes a concurrency-safe skip list implementation; this would be worth using for NSMutableArray if people want to use it concurrently (or to provide a GSConcurrentMutableArray, as a thread-safe NSMutableArray subclass). I don't know much about that, don't really like Etoile and never heard of MediaKit until now. I should point out that my algorithm was created to replace both NSLocks and NSMutableArrays inside of NSConnecions. It is much simpler and smaller, as well as faster. That said there is room for improvement as the other algorithm included for the case where the only reader removes the last remaining element while the writers insert new ones does actually perform a kind of locking (not the ususual kind), but it does so ALL the sime. This detail I must work out in order to publish something usefull to us. But don't worry, I've already got an idea of how to solve this problem... Atomic compare-and-swap is one of the builtins provided by clang and recent GCCs. Assembly is only needed while we continue to support archaic compilers. Aha, and what does that matter? My algorithm and the one you mentioned require an atomic SWAP. TC's are another type of atomic operation, what I'm talking about is an instruction like the 80x86 exchg one which exchanges the content of two registers or memory addresses. Is this one included? If so...SWEET! David -- Besos, abrazos, confeti y aplausos. Jamie Ramone El Vikingo ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: NSCalendar and NSLocale support
I would concur, but IIRC from when I looked at it a couple of years ago, there is basically a pure C API and a C++ API side-by-side. The Just to save you some time, don't use the C API, as it doesnt work properly. I went through this a couple of weeks ago. Did a C version, got odd results, and ended up recoding the lot in C++ with C wrappers to interface to Obj-C. That works a lot better (much as I hate C++) I was doing transliterations, so I have no idea if the C API would work ffor other things, but my experinece was that it wasn't any good. Subtle wrong results, the worst kind of bug! -pete. ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
Re: NSCalendar and NSLocale support
Ouch. That is good to know. We ended up not doing the localization work anyway. The customer wanting it didn't want to fund it. We have no C++ code, but tons of C code (some around 30 years old) which would need this if the idea ever comes 'round again. --Robert On Jun 15, 2009, at 4:13 PM, Pete French wrote: I would concur, but IIRC from when I looked at it a couple of years ago, there is basically a pure C API and a C++ API side-by-side. The Just to save you some time, don't use the C API, as it doesnt work properly. I went through this a couple of weeks ago. Did a C version, got odd results, and ended up recoding the lot in C++ with C wrappers to interface to Obj-C. That works a lot better (much as I hate C++) I was doing transliterations, so I have no idea if the C API would work ffor other things, but my experinece was that it wasn't any good. Subtle wrong results, the worst kind of bug! -pete. ___ Gnustep-dev mailing list Gnustep-dev@gnu.org http://lists.gnu.org/mailman/listinfo/gnustep-dev
