Jobswarm, massively microthreaded code

[Kojack]

http://codesuppository.blogspot.com/200 ... -with.html

I've just been playing around with the recently released Jobswarm code by John Ratcliff ( http://www.mobygames.com/developer/shee ... erId,23659 )
It's a microthreading library, designed for spawning thousands of small, low overhead threads.

It comes with a demo which calculates 2048x2048 fractal images. It calculates them first using just a single thread, then it does it again using 65536 threads at once, each handling 64 pixels.
On my quad core i7 940 in vista 64, the 65536 threads version is 5.25 times faster than the single threaded version.
Cool!

Jobswarm comes as 4 headers and 3 cpps. It's currently only for windows, but the threading wrapper is already half ported to linux, mac and xbox.

It would be interesting to port the demo to OpenMP and see how it competes.

[tuan kuranes]

Parallelism may give some nice gsoc 2009 proposals

Jobswarm, openmp, cuda/opencl... lots of interesting bits that can help on skeletal animation update, image blit/copy/resize/save/load, particle update, visibility culling, threaded resources, etc...

On the same subject, DirectX Command Buffer Library (source code) port to Ogre might also give nice results.

quad core i7 940 in vista 64

how many "logical cpu" that gives at the end ? what says openmp ? 4 cores each with hyperthreading leads to 8 ?

[xavier]

If you are watching the gdalgorithms discussion, I'd wait until they get the actual locking/race-condition issues sorted out first.

[Klaim]

how many "logical cpu" that gives at the end ? what says openmp ? 4 cores each with hyperthreading leads to 8 ?

Yes 8 with HT activated but you can deactivate it. It seems it's better in some specific applications, but I guess the more general cases will be fine with 8 cpu.

[jacmoe]

Nice!
I've been interested in microthreads ever since I saw that article in Game Gems.

I wonder how it compares to POCO::processes ?

[xavier]

how many "logical cpu" that gives at the end ? what says openmp ? 4 cores each with hyperthreading leads to 8 ?

Yes 8 with HT activated but you can deactivate it. It seems it's better in some specific applications, but I guess the more general cases will be fine with 8 cpu.

The problem with HT is that L1 cache is shared -- and if one hardware thread stalls, the whole core stalls.

The results that many have reported (in the gdalgorithms thread) sum up to close (within statistical margin) to one full factor per core. So, your concurrent operations will run 200% faster on 2 cores compared to one, and 400% faster on 4 vs. 1, and so on. HT does not show these same results for the reasons outlined above.

And again, make sure you know what you are running -- deadlocks/race conditions have been pointed out in the various lockless versions of the algorithm; the performance of the locking version is not much different from the lockless version (from what I can tell of the discussion) so for safety's sake you probably just want to use the locking version.

[jratcliffscarab]

Hey guys, I might add that the little source library has gone through a ton of iterations and testing this past week and the current version is good to go. Most of the work this week was done by a guy named David Pangerl who lives in Slovenia. He has done extensive stress testing of the code under all kind of extreme use cases.

A few points, there are no race conditions. It is 100% lock-free. It is an extremely tiny code base and does not use STL or any other kind of template library that would make it more difficult to adopt. It uses the MIT license and, therefore, has no problems being adopted by any other project, commercial or non-commercial.

I have moved the project to SourceForge, as I plan to do with all of my open source projects going forward.

The link for the project on source forge is here: http://sourceforge.net/projects/jobswarm/

The SVN repository is here: svn co https://jobswarm.svn.sourceforge.net/svnroot/jobswarm jobswarm

One thing I am working towards is releasing more code examples which demonstrate heavy use of micro-threading.

Look, I'm not one to reinvent the wheel and, in fact, the Intel Thread Library is an excellent resource and much more useful than say just my little JobSwarm library. However, it is GPL and therefore entirely useless to anyone who might want to use it in commercial projects (or infect their open source project with this hideous viral license).

Here is why I released JobSwarm as opposed to just using any one of the dozens of other threading libraries out there.

(1) Other threading libraries are often honking monstrous code bases or have external dependencies to honking large code bases.
(2) Other threading libraries have idiotic GPL style licenses making them useless.
(3) Other threading libraries use STL and/or Boost making it more difficult to adopt them for consoles.
(4) Other threading libraries have complex APIs or are heavily templated making them more difficult to integrate into applications.

JobSwarm is going to be maintained going forward to run on all platforms, including game consoles. The main design goal was for it to be an absolute minimum implementation while also demonstrating the absolute minimum overhead for individual job tasks.

Thanks,

John

[CABAListic]

Look, I'm not one to reinvent the wheel and, in fact, the Intel Thread Library is an excellent resource and much more useful than say just my little JobSwarm library. However, it is GPL and therefore entirely useless to anyone who might want to use it in commercial projects (or infect their open source project with this hideous viral license).

Just a small correction: The Intel Threading Building Blocks library is released under GPL with the runtime exception. This exception is actually very unrestrictive, in fact, that exception makes the licence of TBB less restrictive than LGPL. It is definitely usable in commercial applications and does not enforce GPL on your own code.

[jratcliffscarab]

>>This exception is actually very unrestrictive, in fact, that exception makes the licence of TBB less restrictive than LGPL. It is definitely usable in commercial applications and does not enforce GPL on your own code....

We must not be reading the same thing. According to the announcement, TBB is under GPL2. On their site they refer to a commercial version and a commercially 'aligned' version whatever that is supposed to mean. At the end of the day it is released under GPL.

Please read the GPL license located here: http://www.gnu.org/copyleft/gpl.html

It is a massive and dense document that would require an attorney to figure out. Now, I'm not an attorney but, but let me tell you this, our attorneys tell us that under no circumstances can we use any GPL code in any way shape or form in any of our projects here at work. I don't care what little 'caveat' Intel shoved into their readme file so long as it has the word 'GPL' anywhere near it, I cannot touch it at my job period.

Realize that all of the source I release is also used by me at my job. I consult with my employer and we make selective decisions as to what code we will release open source and what we will not. We release open source for a variety of reasons: generating good karma, generally being a nice guy, and hoping that we will benefit from improvements and bug fixes made by others, or from software created by others that incorporates our code.

By comparison, here is the MIT license. I don't need to provide a separate link because it is so short and sweet one is not needed. It says the source is free, do with it as you will, and don't blame me if something goes wrong. That, in my opinion, is the only license any true 'open source' project should be in. It certainly should be no more than a paragraph or two, a couple of hundred words at best, not a massive document such as GPL.

By the way, I am not alone in my opinion on this topic. Here is a link to a developer who says almost word for word the same thing I just said. http://www.linuxjournal.com/article/5935

If you can't tell I’m really annoyed that Intel has this fantastic threading library that they ‘want everyone to use’ but then release it under GPL; a license that prevents virtually any commercial software developer from using it; based on company policy if nothing else. As I assume you know, it is corporate policy at virtually all companies that no GPL code can be used period. And, because of the damage GPL issues have raised, now many companies won’t allow any open source code of any kind period, no matter what the license. Which makes the job of a commercial software developer a giant pain in the ass when he has to completely rewrite open source code so that his company now ‘owns it’.

I know of one major company in particular that I do consulting for that has this restriction. I know from personal experience just how frustrating this can be. Until Intel removes the phrase 'GPL license' from TBB it will never be adopted by virtually any commercial projects.

** The MIT license:
**
** Permission is hereby granted, free of charge, to any person obtaining a copy
** of this software and associated documentation files (the "Software"), to deal
** in the Software without restriction, including without limitation the rights
** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
** copies of the Software, and to permit persons to whom the Software is furnished
** to do so, subject to the following conditions:
**
** The above copyright notice and this permission notice shall be included in all
** copies or substantial portions of the Software.

** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
** WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
** CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

[jacmoe]

Hi Ratcliff
Extremely cool that you are paying the Ogre3D community a visit!
Kudos to you for sharing your knowledge with everyone.

We must not be reading the same thing. According to the announcement, TBB is under GPL2. On their site they refer to a commercial version and a commercially 'aligned' version whatever that is supposed to mean. At the end of the day it is released under GPL.

GPL is extremely viral, we agree on that.

However, with the run-time exception, this virus is contained within the boundaries of the library itself.

GNU libstdc++-v3 is licensed under the GPL with the run-time exception.
They invented it.

And their explanation is really quite grok-able:

The Code: Runtime GPL

The source code of libstdc++-v3 is distributed under version 2 of the GNU General Public License, with the so-called "runtime exception," as follows (or see any header or implementation file):

As a special exception, you may use this file as part of a free software
library without restriction. Specifically, if other files instantiate
templates or use macros or inline functions from this file, or you compile
this file and link it with other files to produce an executable, this
file does not by itself cause the resulting executable to be covered by
the GNU General Public License. This exception does not however
invalidate any other reasons why the executable file might be covered by
the GNU General Public License.

Hopefully that text is self-explanatory. If it isn't, you need to speak to your lawyer, or the Free Software Foundation.

Q: So any program which uses libstdc++ falls under the GPL?
A: No. The special exception permits use of the library in proprietary applications.

Q: How is that different from the GNU {Lesser,Library} GPL?
A: The LGPL requires that users be able to replace the LGPL code with a modified version; this is trivial if the library in question is a C shared library. But there's no way to make that work with C++, where much of the library consists of inline functions and templates, which are expanded inside the code that uses the library. So to allow people to replace the library code, someone using the library would have to distribute their own source, rendering the LGPL equivalent to the GPL.

Q: I see. So, what restrictions are there on programs that use the library?
A: None. We encourage such programs to be released as open source, but we won't punish you or sue you if you choose otherwise.

I agree with you that FSF's documents really are dense.

Now, I'm not an attorney but, but let me tell you this, our attorneys tell us that under no circumstances can we use any GPL code in any way shape or form in any of our projects here at work. I don't care what little 'caveat' Intel shoved into their readme file so long as it has the word 'GPL' anywhere near it, I cannot touch it at my job period.

Please educate your attorneys. No offence meant.
This license means that the code itself - the library - is truly open source - and anything you do with it falls under the GPL.
However, if you use it, you are not required to be affected by that license.
Contrary to the LGPL, you can link however you want, be it static or dynamic. You can even drop the code in your project and use it directly.

I know of one major company in particular that I do consulting for that has this restriction. I know from personal experience just how frustrating this can be. Until Intel removes the phrase 'GPL license' from TBB it will never be adopted by virtually any commercial projects.

They chose the GPL because they want to protect their libary, and the runtime exception because they want everyone to use it, including other commercial companies.

Just my cents.

That does not mean that I am not excited by your microthreaded code, Jobswarm, which is am!

[CABAListic]

@jratcliffscarab:
http://www.threadingbuildingblocks.org/ Please notice on the right side relatively at the top the sentence "Licensed under GPLv2 with the runtime exception". I know what GPLv2 alone implies, but the runtime exception is very important, because it effectively disables most of the annoying parts of the GPL license.

[jratcliffscarab]

>>However, with the run-time exception, this virus is contained within the boundaries of the library itsel

So you are my attorney now? Look, I know I'm being a bit snotty but you are missing the point. It is company policy, dictated by our attorneys that no code with GPL can be used. Period.

Moreover, my own open source projects are MIT and I have absolutely no interest in 'infecting them' with TBB so long is transmits this virus.

I don't think their 'exception' would pass muster with our attorneys to be frank and, as I said, I don't want anything with the three letters 'GPL' anywhere near any code of mine.

John

[jratcliffscarab]

@jratcliffscarab:
http://www.threadingbuildingblocks.org/ Please notice on the right side relatively at the top the sentence "Licensed under GPLv2 with the runtime exception". I know what GPLv2 alone implies, but the runtime exception is very important, because it effectively disables most of the annoying parts of the GPL license.

Are you an attorney? I can assure you that this will not pass muster with our attorneys. Company policy doesn't change because Intel took a horrible license and then placed an 'asterisk' next to it.

John

[jratcliffscarab]

Just curious, is Ogre GPL and/or does it use any GPL code within it?

[jacmoe]

Just curious, is Ogre GPL and/or does it use any GPL code within it?

It does not.
And it does not use any LGPL code, either.
Because Ogre is available under two licenses: the LGPL and a commercial license.

Are you an attorney? I can assure you that this will not pass muster with our attorneys. Company policy doesn't change because Intel took a horrible license and then placed an 'asterisk' next to it.

That horrible license is based directly on the LibstdC++ license. And companies are using it all the time.
'Nuff said.

[jratcliffscarab]

>>They chose the GPL because they want to protect their libary, and the runtime exception because they want everyone to use it, including other commercial companies...

Let's be clear here. TBB is great, but the reason it is great is that it is a very modest set of header files. You can think of it as a thread-safe STL. Definitely cool. From a business standpoint Intel wants to sell hardware and the future of hardware is multicore. It is in their best interests to get developers chewing up all of the cycles possibly available on a multi-core processor (the same design goal as my little JobSwarm thingie).

I don't think Intel needs any protection for a handeful of template classes that help people program their hardware. The whole thing is absurd to me. My point is, and remains, that they should have chosen the MIT or BSD license or just frickin said 'free, don't sue us if anything goes wrong'. But GPL, asterisks or not, was not the correct decision in my view.

The reason I'm spamming the list with my personal rant is I'm hoping somebody at Intel reads it, goes 'doh', John's right, let's fix this.

John

[jacmoe]

I can agree that it is a bit excessive.
Personally, I prefer BSD/MIT, but that license - of which we rant - is not a mean as you think it is.

I truly appreciate your passion for sharing.
So, while I have the chance: Thank you so much for your code repository. Kudos.

[jratcliffscarab]

Thanks, the CodeSuppository is about to get much, much, better. I was going to put everything on SourceForge but I just found out about Google Code which is way cooler. I don't know if you have seen my new app framework, CodeSuppository.exe, but it combines the best of both worlds, small code snippets but still a rich interactive graphics application so you can visually see how they work. I also released a graphics demo app for the JobSwarm which is an interactive mandelbrot explorer that really shows off the difference in speed when you have more cores on your machine.

John

[jacmoe]

I am currently integrating your dynamic navmesh code (AI Wisdom 4) with OgreSteer (pathfinding/steering for Ogre), and your convex hull code too.
Plus, Jobswarm seems to be just perfect for that project of mine!

I'd definitely give it a go.
Since you wrote a great deal of OgreSteer already..

By the way: I'd love it if you chose to go Ogre3D!

[CABAListic]

Are you an attorney? I can assure you that this will not pass muster with our attorneys. Company policy doesn't change because Intel took a horrible license and then placed an 'asterisk' next to it.

Well, if you are not convinced that I understood the conditions of the license Intel chose correctly, then you can always contact Intel and have them clarify the conditions. I'm sure that's reasonable within any company policy?
But ranting about restrictions which are nullified by the exception's text (which Intel has chosen deliberately, after all they must have had a reason to put the runtime exception along) is not exactly helpful, imho.

Anyway, this is not the topic of this thread. Merely wanted to state that anyone interested in using TBB commercially or in closed-source projects should not be discouraged so easily. If you're releasing your own stuff under an even less restrictive license, all the better.
Even though personally I prefer zlib over BSD/MIT.

[xavier]

I don't think their 'exception' would pass muster with our attorneys to be frank

Have you asked them?

[jratcliffscarab]

Yikes, if you are trying to use my navmesh code, you should contact me so I can help you with it. That code has been radically dramatically improved as I did the integration int our own game. I also have an outrageously fast Astar implementation that I haven't published yet. Contact me via email and I will try to get you going on the latest version. I have also got some dramatic visualization improvements. The only issue is that my current version, in house, while based on the original code has changed a lot. Some of it includes concepts entirely specific to our game.

What I would like to do is take the version we are using in our own engine and kind of re-open-sourceify it, by removing our game specific stuff. Is this pathing stuff checked into Ogre3d right now? I would be happy to work directly with the integration. Is Ogre3d an SVN type thing, like SourceForge and Google Code? What do I need to do to become an official 'member'? I would love to get my latest pathing code into Ogre3d.

John

[Kojack]

Yep, Ogre is on sourceforge's svn system, as well as having zipped up releases and a prebuilt sdk.
Various download options: http://www.ogre3d.org/index.php?option= ... Itemid=149

Ogre itself is purely a graphics engine, it doesn't feature things like path finding. But there are a number of addons which support wrapping other projects in an ogre friendly way. Some are kept internal on a separate svn repository with each addon author having write permission to their section, while others are maintained externally by their authors. Addons include exporters for various 3d tools, wrappers for physics libraries, guis, editors, etc. The one Jacmoe mentioned, OgreSteer is an external addon which wraps OpenSteer.

[jacmoe]

Yikes, if you are trying to use my navmesh code, you should contact me so I can help you with it. That code has been radically dramatically improved as I did the integration int our own game. I also have an outrageously fast Astar implementation that I haven't published yet. Contact me via email and I will try to get you going on the latest version. I have also got some dramatic visualization improvements. The only issue is that my current version, in house, while based on the original code has changed a lot. Some of it includes concepts entirely specific to our game.

Wow, yes. I'd like that.

What I would like to do is take the version we are using in our own engine and kind of re-open-sourceify it, by removing our game specific stuff. Is this pathing stuff checked into Ogre3d right now? I would be happy to work directly with the integration.

No, it isn't. I recently returned to the Ogre community after a long period of absence, and started a brainstorming process about OgreSteer, and what to do with it. Just before Christmas I fell over your code, and was immediately impressed: you throw a polygon soup at it, and it does a great job of making a navmesh from it in real time. Couple that with some clever steering, and you've got a pretty decent solution.
Real navmesh code is extremely rare. The only other interesting code out there was off-line navmesh generation code from the Zombie project..
So, no: still in the planning stages.

Is Ogre3d an SVN type thing, like SourceForge and Google Code? What do I need to do to become an official 'member'? I would love to get my latest pathing code into Ogre3d.

We'll love to have it.
However, Ogre3D is awesome because it does one thing, and one thing only: render. That makes it enjoyable to work with, because you are free to integrate it with what you want.

But: This would be perfect for an Ogre Addon project.

[jacmoe]

The one Jacmoe mentioned, OgreSteer is an external addon which wraps OpenSteer.

Actually, I was given the permission to take over the project. And I did. It's now @ Sourceforge, (part of ogreconglo project). But open for relocation, if need be.
It evolved to be OpenSteer for steering and Micropather for pathfinding, but that seemed too limiting.
Now it's about navmeshes, designer tools (hopefully) and our own steering and pathfinding code.
A good way of honing the I-am-surprised-it-works coding skills, but also because it's something which many people from the Ogre community has an interest in.

Sorry for seriously hi-jacking your topic, Kojack!