> Firstly, rather than using a single 1 word pointer to represent a reference > I > chose to use 3 words including a pointer to the type and a pointer to the > value (as well as metadata). This allows typed nulls and that addresses an > important deficiency found in most other VMs including the CLR. Is Scarcity > able to handle such references or does its implementation of stack frames > require references to be a single word? >Three words sounds pretty expensive to me, I can see the use of an extra word for typed nulls. If you look at something like the CLR you will see that you have very fast access to an objects type, after all when you have a reference to an object what you really have is a reference to an objects' object header. From there you can access an objects syncblock (if it has one, which is before the obj header) and the objects' method table which includes the relevant pointers to the objects' type among other things. It simply means you do a few hops, each of which is a constant operation anyway. Maybe I'm missing something key about the language you are implementing the GC for, also is it really necessary to use an extra word for null types? Granville 2009/6/18 Jon Harrop <jon at ffconsultancy.com>> On Tuesday 16 June 2009 07:37:32 Talin wrote: > > A while back there was a discussion thread about whether an accurate, > > concurrent garbage collector could be "generic" in the sense of being > > able to support multiple different languages efficiently. After having > > done some work on this, I now believe that this is the case - using C++ > > policy-based design principles, you can create a set of modules that > > represent different aspects of collector behavior (such as > > mark-and-sweep, stop-the-world, and so on) along with different aspects > > of the runtime environment (object tracing strategies, heap structures, > > threading primitives, atomics), and encode these various behaviors as > > template classes which can be bound together to create an efficient > > collector. > > Hi Talin, > > This is great news! I have some questions... > > I had great success using some seemingly-unusual techniques in my > experiments. > > Firstly, rather than using a single 1 word pointer to represent a reference > I > chose to use 3 words including a pointer to the type and a pointer to the > value (as well as metadata). This allows typed nulls and that addresses an > important deficiency found in most other VMs including the CLR. Is Scarcity > able to handle such references or does its implementation of stack frames > require references to be a single word? > > Secondly, I used LLVM to JIT compile per-type code for garbage collection > in > order to traverse data structures as efficiently as possible. Moreover, I > chose to write the entire GC in an unsafe subset of the language that I was > implementing so that I could rely upon tail calls and so forth. Does > Scarcity > require the GC code to be written entirely in C? > > Finally, do you have any references describing the techniques you have used > to > implement a concurrent GC? I have been reading up on the subject for > several > years now, with a view to implementing my own concurrent GC. > > -- > Dr Jon Harrop, Flying Frog Consultancy Ltd. > http://www.ffconsultancy.com/?e > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Granville Barnett http://gbarnett.github.com -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090618/cc43709d/attachment.html>
On Thu, Jun 18, 2009 at 3:14 AM, Granville Barnett<granvillebarnett at googlemail.com> wrote:> >> Firstly, rather than using a single 1 word pointer to represent a >> reference I >> chose to use 3 words including a pointer to the type and a pointer to the >> value (as well as metadata). This allows typed nulls and that addresses an >> important deficiency found in most other VMs including the CLR. Is >> Scarcity >> able to handle such references or does its implementation of stack frames >> require references to be a single word? > > Three words sounds pretty expensive to me, I can see the use of an extra > word for typed nulls. If you look at something like the CLR you will see > that you have very fast access to an objects type, after all when you have a > reference to an object what you really have is a reference to an objects' > object header. From there you can access an objects syncblock (if it has > one, which is before the obj header) and the objects' method table which > includes the relevant pointers to the objects' type among other things. It > simply means you do a few hops, each of which is a constant operation > anyway. > > Maybe I'm missing something key about the language you are implementing the > GC for, also is it really necessary to use an extra word for null types?I'm also curious what language uses this and why it is useful :) Also, things like this would make lock-free algorithms difficult or impossible. -- Cory Nelson
On Thursday 18 June 2009 11:14:35 Granville Barnett wrote:> > Firstly, rather than using a single 1 word pointer to represent a > > reference I > > chose to use 3 words including a pointer to the type and a pointer to the > > value (as well as metadata). This allows typed nulls and that addresses > > an important deficiency found in most other VMs including the CLR. Is > > Scarcity able to handle such references or does its implementation of > > stack frames require references to be a single word? > > Three words sounds pretty expensive to me, I can see the use of an extra > word for typed nulls.The word is not really "extra" because I just moved the header out of the value and into the reference. For example, the three words for an array are a pointer to the type, the array length and a pointer to the (C-compatible) array data. In addition to providing typed nulls, this has the added advantage of simplifying interop.> If you look at something like the CLR you will see > that you have very fast access to an objects type, after all when you have > a reference to an object what you really have is a reference to an objects' > object header. From there you can access an objects syncblock (if it has > one, which is before the obj header) and the objects' method table which > includes the relevant pointers to the objects' type among other things. It > simply means you do a few hops, each of which is a constant operation > anyway.That is similar to the approach I used, although HLVM provides a pointer directly to the type, saving you a single hop.> Maybe I'm missing something key about the language you are implementing the > GC for, also is it really necessary to use an extra word for null types?I would not have considered it had I not seen the damage done to F# by the CLR's typeless nulls. You want an unallocated constant for many different purposes in F#, such as representing the empty option type None, the empty list [] and maybe the unit value (). Unfortunately, using "null" means you don't get any type information and that means that none of those values work correctly with anything requiring run-time type information such as generic printing, serialization and so on. The only alternative is to use an allocated value but the allocator and (concurrent) GC are very slow so that gives you the functionality you want but only at a grave cost in terms of performance. Consequently, they chose to represent the empty list with an allocated value (so [] prints correctly) but the option type uses null. Hence printf "%A" None prints "<null>". They've also used other tricks like having an internal set representation that uses nulls but is wrapped in another representation that handles them correctly but only at the cost of an extra level of indirection. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
On Thursday 18 June 2009 12:28:57 Cory Nelson wrote:> I'm also curious what language uses this and why it is useful :)HLVM is intended to be a general-purpose VM rather than a particular language.> Also, things like this would make lock-free algorithms difficult or > impossible.True. Perhaps that is a good argument for providing both kinds. However, nulls are certainly more common than concurrent data structures. :-) The entire source code for HLVM is available for free under a commerce-friendly BSD license, BTW: http://forge.ocamlcore.org/projects/hlvm/ -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e