llvm dev - May 2009 - [LLVMdev] open source multithreaded garbage collector suitable for LLVM applications?

Hello All

Does any know about some opensource multithread-compatible (or 
concurrent) garbage collector library, if possible suitable for LLVM?

(I mean that I want several mutator threads; the collector can be 
stoptheworld or concurrent ....)

H.Boehm's conservative GC is multithread compatible, but seems quite 
slow (allocation is about the time of a C malloc).

And it is well known that coding concurrent GC is quite hard, much 
harder than coding a single-threaded GC.

And with LLVM, adapting to the constraints of the GC is easier.

Are there people using LLVM in multi-threaded applications with some 
other GC than Boehm's?

Regards.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

On May 1, 2009, at 1:27 PM, Basile STARYNKEVITCH wrote:
> Hello All
>
> Does any know about some opensource multithread-compatible (or
> concurrent) garbage collector library, if possible suitable for LLVM?
In fact, yes!
http://code.google.com/p/scarcity/

-Chris

On May 1, 2009, at 3:27 PM, Chris Lattner wrote:
>
> On May 1, 2009, at 1:27 PM, Basile STARYNKEVITCH wrote:
>
>> Hello All
>>
>> Does any know about some opensource multithread-compatible (or
>> concurrent) garbage collector library, if possible suitable for LLVM?
>
> In fact, yes!
> http://code.google.com/p/scarcity/
More information here:
http://code.google.com/p/scarcity/wiki/ProjectPlan
and an example here:
http://code.google.com/p/scarcity/wiki/FreeListHeap

-Chris

Chris Lattner wrote:
> On May 1, 2009, at 1:27 PM, Basile STARYNKEVITCH wrote:
>> Hello All
>>
>> Does any know about some opensource multithread-compatible (or
>> concurrent) garbage collector library, if possible suitable for LLVM?
> In fact, yes!
> http://code.google.com/p/scarcity/
Note that this is still a work in progress, and not quite ready for use 
in real programs. But yes, the goal is to create a concurrent garbage 
collector (or actually, several different collectors) for LLVM projects.

The project philosophy is based around the "building blocks" idea that
was discussed earlier in this list. By Using C++ policy-based design, 
Scarcity intends to provide essential components for building garbage 
collectors. The policy-based approach allows any aspect of the system to 
easily be replaced - so for example you can replace all of the threading 
primitives with ones that are specific to your runtime environment. 
Policies also allow the collector to be adapted to different object 
memory layouts without requiring the overhead of virtual method calls.

The ConcurrentCollector class supports both "stop the world" and 
"sliding window" collection algorithms via subclassing - it provides a
framework for synchronization between mutator threads and the collector, 
and it's up to the subclass to determine exactly what happens at each 
sync point. This means that there is room for a lot of different 
multithreaded collector algorithms to be implemented within this framework.

Anyway, there is lots to be done still. I have not even begun to work on 
the integration with LLVM proper.

-- Talin

Basile STARYNKEVITCH wrote:
> Does any know about some opensource multithread-compatible (or 
> concurrent) garbage collector library, if possible suitable for LLVM?
> 
> (I mean that I want several mutator threads; the collector can be 
> stoptheworld or concurrent ....)
> 
> H.Boehm's conservative GC is multithread compatible, but seems quite 
> slow (allocation is about the time of a C malloc).
It's true that the allocation path in the Boehm GC isn't as fast as
some, but overall I don't think that the collector itself performs
badly.  It's been carefully tuned over many years on a wide range
of systems, and I think it's extremely unlikely that a much simpler
approach will in generally result in better performance.

It's ferociously hard to benchmark things like this, because it all
depends critically on the allocation pattern of your application.
A tuned precise copying collector such as those used in the HotSpot
VM might do better than a more general-purpose tool, as you'd expect,
but it will need accurate type information to do so.

Andrew.

Andrew Haley wrote:
> Basile STARYNKEVITCH wrote:
>
>   
>> Does any know about some opensource multithread-compatible (or 
>> concurrent) garbage collector library, if possible suitable for LLVM?
>>
>> (I mean that I want several mutator threads; the collector can be 
>> stoptheworld or concurrent ....)
>>
>> H.Boehm's conservative GC is multithread compatible, but seems
quite
>> slow (allocation is about the time of a C malloc).
>>     
>
> It's true that the allocation path in the Boehm GC isn't as fast as
> some, but overall I don't think that the collector itself performs
> badly.  It's been carefully tuned over many years on a wide range
> of systems, and I think it's extremely unlikely that a much simpler
> approach will in generally result in better performance.
>
> It's ferociously hard to benchmark things like this, because it all
> depends critically on the allocation pattern of your application.
> A tuned precise copying collector such as those used in the HotSpot
> VM might do better than a more general-purpose tool, as you'd expect,
> but it will need accurate type information to do so.

I agree, but any LLVM user, since he is generating code, is able to 
provide the accurate type info you are mentionning.

Regards.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Apple's autozone is a concurrent non-copying collector written in C++  
that should be adaptable to your needs. You could even take a look at  
clang to see how to generate code for it; autozone is the collector  
used by Objective-C garbage collection.

It's under an Apache license and downloadable from the Darwin open  
source repository. Google should point you to it.

   -- Chris
   -- sent from my iPhone

On May 1, 2009, at 1:27 PM, Basile STARYNKEVITCH <basile at starynkevitch.net
 > wrote:
> Hello All
>
> Does any know about some opensource multithread-compatible (or
> concurrent) garbage collector library, if possible suitable for LLVM?
>
> (I mean that I want several mutator threads; the collector can be
> stoptheworld or concurrent ....)
>
> H.Boehm's conservative GC is multithread compatible, but seems quite
> slow (allocation is about the time of a C malloc).
>
> And it is well known that coding concurrent GC is quite hard, much
> harder than coding a single-threaded GC.
>
> And with LLVM, adapting to the constraints of the GC is easier.
>
> Are there people using LLVM in multi-threaded applications with some
> other GC than Boehm's?
>
> Regards.
>
> -- 
> Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
> email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
> 8, rue de la Faiencerie, 92340 Bourg La Reine, France
> *** opinions {are only mines, sont seulement les miennes} ***
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev