Friday, September 3, 2010

Tart status update and unsolved problems

I've been making fairly good progress on the reflection stuff. At the moment, I have both the old system and new system running in parallel, working towards a point where the old system can be completely deprecated.

There are two long-standing problems that I have not yet been able to solve, both of which are related to LLVM.

The first big problem is generating DWARF debugging info. I've put several man-months into this over the course of the past several years - I recently did a near-total rewrite of the code for generating source line information - and it still doesn't work.

Part of the problem is that the LLVM docs on source-level debugging, while extensive, are also vague and ambiguous in many places. I find that often times the only way to understand how things work is to cross-reference between the docs, the clang source code, and the LLVM source code. Even then, there are a lot of things aren't clear, especially when the code in clang contradicts what's in the doc. For example, according to the source-level debugging doc, the signature of a function is defined using an array of formal parameter descriptors using the DWARF tag DW_TAG_formal_parameter. However, according to Google code search, the identifier "DW_TAG_formal_parameter" appears nowhere in the clang source tree, and if you trace through the code that is used to generate a function type descriptor, you see that in fact the array is an array of type descriptors, not parameter descriptors.

Another difficulty with DWARF symbol generation is the difficulty of isolating a problem. If you make a mistake in your generator and then attempt to debug the compiled program, gdb prints various obscure error messages telling you that your debug info is invalid, but doesn't tell you where in your code the error lies or what debug symbol is having a problem. There's also dwarfdump, which pretty-prints the debug info for your program (typically thousands of pages worth, so good luck finding the problem by eye.) The easiest way to use use dwarfdump is to have it print out all of the debugging info using the -a option, and hope that it segfaults (which it usually does) when it gets to the point where the problem is. Based on the last few lines of printout before the segfault, you can sometime deduce which symbols are having problems, although if your problem lies in a call frame descriptor, this won't work because call frame descriptors aren't self-identifying - you can look at the text dump of a call frame descriptor, but it won't tell you which function's call frame is being described.

Tonight I am going to start experimenting with readelf, although that requires me getting it running on OS X.

The other big problem I have is with llvm.gcroot. This is the pseudo-function in LLVM which is used to mark a local variable as a garbage collection root. A linker plugin (which I have written for Tart) collects all of the calls to llvm.gcroot and uses that information to build the stack frame descriptors - a table which the garbage collector can use to trace the stack. The actual call to llvm.gcroot is removed, although it can have an effect on certain optimization passes.

The llvm.gcroot function has a curious limitation: It only works on data values that are pointers that have been allocated with a local alloc() instruction.

Typically, the call frame for a function contains pointers to objects on the heap. llvm.gcroot isn't responsible for the pointers which are contained inside of heap objects - that's the job of your collector. Instead, llvm.gcroot only deals with pointers that are on the stack. (Note that it does not deal with pointers that are SSA values, i.e. only in registers, since there's no way for a trace to access those anyway. Any pointer must have a location on the stack where it can be traced.)

The LLVM 'alloca' instruction is used to reserve a stack slot for a variable. So typically you would have a stack slot containing a pointer, which points to some heap object. The stack tracer  then iterates through all of these stack slots (only the ones containing pointers to heap objects) and trace the objects pointed to.

The problem comes when you have a stack slot that contains pointers, but isn't a pointer itself. An example would be a small structure that contains several pointers. Because the structure is not a heap object, it needs to be traced by the stack tracer. Unfortunately, llvm.gcroot won't accept a stack slot that's not a pointer - it simply emits a fatal error when you try. Nor can you call llvm.gcroot on the members of the structure either - the argument to llvm.gcroot must be the result of an alloca instruction (a stack slot) and not a member of a stack slot.

Now, this is not a problem for languages like Java - Java only allows stack slots for primitive types and pointers. (There's no such thing as a 'struct' in Java). It's not a problem for C and C++, which don't have garbage collection. It *is* a problem for C# and D - those compilers get around the problem by simply not using LLVM's garbage collection framework at all. I don't want to do that because it requires writing a whole lot of code that is specific to a each different CPU architecture, which I'm not up to.

So far the only helpful suggestion from the LLVM mailing list is to allocate an extra stack slot for each local struct variable, containing a pointer to that struct. You would then declare the pointer as a gcroot instead of declaring the struct directly. However, I've been hesitant to go this route because it seems like an ugly hack, not to mention that there's now an additional 8-byte overhead for each local structure variable. Also, it makes the tracer more complicated, because now you have to deal with pointers to stack objects as well as pointers to heap objects.

I've thought about digging in and changing the way llvm.gcroot works. But the code is complicated and I don't entirely understand it, and I don't like mucking around with things I don't understand.

Monday, August 16, 2010

Propitious Properties

Tart's property system is modeled after C#, and to a lesser extent Python. A property is defined with the following syntax:

   def length:int {
     get { return self._length; }
     set { self._length = value; }
   }

The idea behind properties is that you use them just as if they were member variables, but reading or writing the variable actually invokes the getter or setter method:

  return obj.length; // Calls the 'get' function
  obj.length = 1; // Calls the 'set' function

Properties are an improvement over Java's 'bean' reflection system, which I will explain. In Java, you can introspect an object to determine what properties it has. Properties are derived by looking for methods named 'getXXX' and 'setXXX':
  • A method named 'getFoo' is presumed to define a property named 'foo' - the 'get' prefix is stripped, and the initial character of the property name is converted to lower case.
  • The return type of the method (in the case of 'get') or the argument type (in the case of 'set') is presumed to define the type of the property. (The getter and setter type must match.)
Here's why a formal syntax for defining properties is superior to Java's syntax:
  1. Doing textual manipulation of the method to derive the property name is ugly.
  2. If you want to @Annotate the property, in Java you have to annotate either the getter or the setter, whereas in C# you can annotate the property directly. So for example, if you want to annotate a property as being non-serializable, for example, which method do you put the annotation on? In C# it's unambiguous.
  3. In C# the reflection system can give you a list of properties directly, whereas in Java you have to use a BeanIntrospection class which compiles the list of properties derived from examining the methods.
However, I've discovered that properties also have some drawbacks. These drawbacks have less to do with properties directly, and more to do with the style of code that results when properties are used:
  1. Name collisions. Often you will have a private member variable that is exposed through a property getter. Unfortunately, this means that you need to come up with distinct names for both the variable and the property. Up to now, I've been using '_name' for the internal variable, and 'name' for the property, however I don't really like using underscores in this way (my preference is to let people name things as close as possible to readable English, and not require funny prefix or suffix characters - I strongly feel that if the the programmer has to write special prefix or suffix characters onto more than 20% of the identifiers in a program, then the language design is deficient.)
    • In Java, this is not a problem, since 'getFoo' is always going to be named differently than 'foo'.
  2. Chaining. A very common code pattern in Java is the use of chained setters, each of which returns 'this' as a return argument: object.setName(name).setDescription(desc).setKey(key)...and so on. This is a very convenient pattern which I use all the time in Java, but unfortunately, it doesn't work with property assignments, since those don't return a value. You need to repeat the base expression ('object') once for each value set.
  3. I don't like taking the name 'get' and 'set' as keywords. These two names are very commonly method names in Java (See Provider.get() in Guice as an example). "get()" is often used when you have some class that defines a single value that it can produce, such as a factory or cache. I'd hate to break up a nice naming convention :)
I also wonder if it's a good idea to re-use the 'def' keyword to define a property. Syntactically it's unambiguous because of the colon, but the code might be more readable if I changed it to use the word 'prop' instead.

Tart status update

I've been busy this last week re-doing Tart's reflection data structures. Unlike the previous scheme, which used fully-realized, statically-compiled Tart objects to represent the various types, method descriptors, and other metadata needed for reflection, the new scheme uses a highly-compressed byte-encoding of the data. The compressed data is converted into objects lazily on first access.

By the way, all of this lazy evaluation makes heavy use of Tart's 'lazyEval' macro, which is part of the core library:

    return lazyEval(<variable>, <initialization-expression>);

Where 'initialization-expression' has type T, and 'variable' is declared as having type 'optional T'. Basically, lazyEval checks to see if 'variable' is initialized, and if not, it initializes it using 'initialization-expression'. The initialization expression is not evaluated if the variable is already initialized.

At some point I'll need to also do a 'lockedLazyEval' which is a synchronized version. But before that can happen I'll need mutexes (mutices?) to be implemened. That's going to be a bit tricky, for a number of reasons. For example, Tart objects can move around in memory, but I'm not sure whether or not it's legal to relocate a pthread_mutex_t. I suspect it isn't. Also, it gets into the whole realm of writing platform-dependent code in Tart (as opposed to platform-dependent code in the C runtime library, which is no problem), which I haven't really worked out yet.

Anyway, lazy evaluation is one of those common code patterns you see everywhere, but it's hard to refactor into a library routine unless your language gives you some way to selectively control evaluation. Macros are one way to do it - closures are another, although they are a bit more wordy.

Another aspect of reflection I am working on at the moment is the "invocation adapters". These are wrapper functions used when calling a method via reflection - it converts the argument list from type Object[] to the native types of the called method's argument list. Each distinct function type requires a distinct invocation adapter - in other words, if two functions take the same argument types, then they can share the adapter function. (Note that the invocation adapter does not handle the 'self' argument - that is handled by a prior stage in the calling process - so two instances methods can share the same adapter, even if they are members of different classes).

When the compiler generates the reflection metadata for a class, it creates a set of all of the unique function types defined by that class. Each of these is assigned an index. Each method definition in the class contains the index corresponding to it's function type, which is encoded using a VarInt, which typically takes one byte. The class metadata also contains a table of pointers to invocation adapter functions, which is also referenced by index. This information is used to lazily construct a method descriptor object, which contains a pointer to both the method itself and the invocation adapter for that method.

In other news, I implemented the Python-style String.join method: So now you can say either ", ".join(list) or String.join(", ", list). The 'list' argument must either be an Iterable[String], or a variable number of String arguments.

Friday, July 30, 2010

More thoughts on Arrays

The more I work on collections in Tart, the more I realize how odd Arrays are.

For example, in my work in Java I almost never use an array type. Sequential containers are almost always ArrayList or ImmutableList. Pythons 'list' class (and 'array' class as well) are much more like Java's ArrayList, in that they can grow as needed.

At the same time, fixed length arrays are needed because the other container type - such as ImmutableList and ArrayList - are implemented in terms of arrays.

Arrays are also problematic in other ways as well. For one thing, there is the dreaded array-initialization problem: In a language where the use of null pointers is heavily discouraged, what do you use for the initial fill value of an array? Not all types have an obvious "default value" instance.

One idea that I have been toying with is the idea of making the basic array class more like fixed_vector: That is, a container with a fixed capacity, but variable length up to that capacity. You could grow the array up to it's maximum size, but in doing so you would have to provide either an explicit fill value, or a list of elements to copy into the array. From an implementation standpoint, this would require adding one extra field to the array, which is the current length. (And moreover, that field would disappear from ArrayList, since it could now use the length field of the underlying array.)

One problem with doing this is that "variable size with a maximum size" is a more complicated concept than just a fixed size. People might be surprised when their arrays start throwing capacity exceeded exceptions.

Wednesday, July 28, 2010

More on templates and reflection

As I mentioned in my last posting, I'm working on a more efficient way to encode reflection data for templates. Rather than pre-generating the reflection data for each expansion of the template, instead I want to store the template definition, and let the expansion be generated lazily at runtime.

Note that under this scheme, the actual compiled methods, and the method dispatch tables, are still being generated by the compiler. It's only the reflection data that isn't generated.

One thing I need to work out still is how to integrate the compiled methods and dispatch tables into the reflection data when it is generated. With non-template classes, this is easy: The reflection data for each method (a static structure generated by the compiler) contains a pointer to that method. In the case of a template method, we need to somehow attach the method pointer to the method descriptor when it is created. This gets tricky because the compiler may have generated multiple copies of the original template method, one for each expansion of the template with different type parameters.

One way to approach this is to have some kind of map of functions: The key consists of all the elements that uniquely identify a function (the name, the arguments, the template arguments, etc) and the value is the function pointer. The trick will be representing the keys compactly.

For the name and template arguments, we can use indices. The name will be an variable-length index into the names table for the module, typically 1 byte. The template are represented as a tuple of types, which itself a type - given types T1, T2, you can create a new tuple type Tuple(T1, T2), and this new type can be assigned a unique index. This index can also be represented as a variable-length integer, and thus can also be (usually) stored in a single byte (it's rare that a module will have more than 128 unique types). The arguments to the method can be treated similarly, with the caveat that method arguments have additional properties than just the type, such as variadic arguments.

So, assuming we can figure a way to encode those additional properties compactly, we're looking at a key size of only a few bytes. Still, that's a minimum of a key and a pointer for each method, and if there's a lot of methods that adds up. Now, some of those methods are already in a table - the dispatch table for the class. It would be nice if we could use that table instead of having to generate a separate table for reflection purposes. Unfortunately, not all methods are in that table - for example, methods declared 'final' or 'static' don't need to be in the dispatch table because the compiler can determine at compile-time which method to dispatch to. And I'd like to avoid making the dispatch table longer, since every subclass has to include the dispatch table of its parent class. Also, methods which are not in the dispatch table can be discarded by the linker if they are never called elsewhere, whereas methods in the dispatch table must be included in the final binary.

One approach would be to create an additional table of only the methods that weren't in the dispatch table. Unfortunately, once we do this, it means that those methods can no longer be discarded by the linker. I'm not sure how to get around this, or even if it's important - one of the perils of reflection is that it breaks the compiler's ability to determine what symbols are reachable from other symbols - if you can access a class or method via it's name, then how can the compiler know whether or not it's called? It has to be conservative and include all potentially reachable symbols, which might be larger than what is actually needed.

(Another possible approach is to use the dwarf debugging information to be able to look up a function by name. However, I want to preserve the option to strip out all debugging symbols from the binary, which would cause reflection to break.)

In any case, assuming we have some small key that can uniquely identify a method, when we expand a template, we need to loop through all the methods, substitute type parameters, generate tuples from those types and look them up in the module's type registry to generate a unique index. Then combine the indices to generate a method key, look up that method in the map, and then use the resulting pointer to fill in the method slot in the method descriptor.

Monday, July 26, 2010

Starting to work on Tart again

My life seems to have calmed down quite a bit and lately I've started poking away at Tart again. It's been about 4 months since I worked on it, and although I've forgotten a few things, it's also given me an opportunity to step back and take a fresh look at some of the problems.

One problem that Tart has is that the binary files it produces are huge. There are a number of reasons for this:
  • DWARF debugging information
  • Template bloat
  • Reflection data
For DWARF, there's not much I can do except generate less code.

For templates, a big win will be gained once I start using Nick Lewycky's function merging pass. This merges LLVM functions which would produce the same sequence of machine instructions. It does this by effectively doing type erasure on pointer variables where possible, and then merging the resulting functions if they hash to the same value. Visual Studio has done this for a long time, and it is an effective way to deal with template bloat.

However, there's another kind of bloat caused by template expansion, which is the bloat in the amount of reflection data - that is, for each expansion of a template, you need to generate a copy of all of the reflection metadata for that class.

Reflection data is large because it needs to describe everything about a type, including the names of all methods and fields. A typical method takes around 128 bytes just to describe it's calling signature. My previous strategy was to combine identical definitions - so for example, if two different classes had a method named "foo", then they would both point to the same string. Similarly, if they had the same return type, they would both point to the same type descriptor struct.

The problem with this approach is that on a 64-bit machine, pointers are 8 bytes. So unless the method or field name is longer than 8 bytes, you're not really saving much by putting a pointer to the name instead of embedding the name directly.

I have two strategies for reducing the size of the template data:

1) Store the reflection data for template instances in an unexpanded form: In other words, instead of generating all of the metadata for each expansion of the template, merely store a reference to the original template definition and the list of type parameters. So for example, for type List[String] we simply store a reference to "List", along with the template parameter list "[String]". The reflection metadata for the specialized type will be generated lazily at runtime the first time someone attempts to access it. I would imagine that the large majority of such type descriptors will never be dereferenced, so the amount of memory consumed will be small compared to the amount required to store all templates in expanded form.

Of course, one drawback of this approach is that we now have to store the original template definition in a runtime-accessible form, which we were not doing before. References to template type variables can be represented by a special "type parameter" type (just as it is in the compiler). Creating an expansion of a template at runtime is a process of cloning all of the data structures of the template, replacing type variables with their associated definitions in the current context.

For purposes of reflection, we don't need the method bodies, just the type signatures of the methods. However, there's a reason why we might want to store the bodies of the methods anyway: To support importation of compiled modules. Right now, whenever the Tart compiler sees an import statement, it loads the source file for that import and (partially) compiles it, which may require resolving that module's imports, and so on. Instead I would like it to work more like Java - the compiler can load in a compiled module instead of having to recompile the original source. (Of course, this will also require the modules to have datestamp and size information so that it can detect when the object module is out of date. In essence the compiler needs to incorporate some of the responsibilities of "make".)

For regular (non-template) classes, we could simply use the existing reflection information that the compiler already generates. In other words, the reflection metadata within a module would have two uses: First, for runtime reflection, and second, for importation into the compiler.

With templates the situation is more complex, because currently unexpanded templates produce no output - a module that defines only templates will produce an empty binary module. In order for the compiler to instantiate a template that was imported from a binary module, the module needs to contain the *complete* definition of the template.

My current thinking is that the template data will be stored in two parts, which are the type descriptors and the method body ASTs. The reason for separating them is so that we can throw away the ASTs at linkage time (since they aren't needed in the final binary.) I will probably store the ASTs using LLVM metadata nodes. The type descriptors will be stored as static data structures, just like they are for non-template classes.

2) The other improvement to the reflection metadata is to transition from a pointer-based to an index-based reference system. Each module will contain a constants pool containing a list of strings, common types, and other information that is referenced by integer index. Variable-length integers will be used to refer to these tables, using an encoding scheme similar to UTF-8. This means that the first 128 entries in each table can be referred to with a single byte index; The first 4096 entries require a 2-byte index, and so on. All of these tables will be sorted in order of by number of references, so very few indices will be more than 1 byte.

Long path names will be stored using a tree-structure. So for example, the string "tart.core.Memory.Address" will be stored as (((tart . core) . Memory) . Address), where (X . Y) is a pair of varints. Here's what the tables might look like:

    Strings       Pairs
    ===========   ============
    s1: tart      p1: (s1, s2)
    s2: core      p2: (p1, s3)
    s3: Memory    p3: (p2, s4)
    s4: Address

Thus, to refer to the string 'tart.core.Memory.Address', we need only a single byte containing the value 'p3'. (The low bit of the byte determines whether it's a reference to a string or to a pair) Moreover, if there is another string with the same prefix (e.g. "tart.core.Memory.ptrDiff"), then only the last part needs to be added to the table, and the prefix parts only need to be stored once per module.

An additional side-benefit is that each unique string within a module now has a unique numeric ID which can be compared directly without having to do a string comparison (although a string comparison is still needed for cross-module references.)

The same scheme can be used for types. Each type descriptor is a string of bytes, which are a combination of type codes and indices into the module types table.

Of course, with a scheme like this, there will be a lot of duplication of definitions between modules: If module A has a definition of the tuple type (int, int) and module B has the same definition, then unlike the previous scheme they won't be shared. But that's OK, because each definition is only 3 bytes, whereas sharing a common definition would require an 8-byte pointer for each reference.

These highly-compressed type definitions will need to be expanded into data structures in order to be useful. This can be done lazily as types are inspected.

Sunday, April 18, 2010

Tart status

Things have been pretty quiet on this list lately, mostly because I've been taking somewhat of a break from working on Tart, hoping to get my creative batteries recharged. After two and a half years of working on it, I figure a vacation is in order. Also, I've found that stepping away from a project is sometimes an effective way to deal with intractable problems, as you often get a new insight by getting some distance from the problem. In fact, I can already see a couple of minor things I'd like to change.

In terms of garbage collection, I did make a some progress on tracing of stack roots. I was able to write a garbage collection "strategy" plugin for LLVM that lets me generate a stack frame descriptor for each function. For example, take the following test function:

def f3 {
  var a = "S3a";
  var b = "S3b";
  var c = b;
  f4();
}

The stack frame descriptor for this function looks like this (in assembly):

        .align  8
.Lgc_stack1:
        .quad   -8
        .quad   -16
        .quad   -24
        .quad   1

This contains three entries, followed by a end-of-list entry that has the low bit set. It says that there are 3 stack roots at offsets -8, -16 and -24 from the base pointer.

I wrote a test program that simply prints out the stack roots instead of doing actual collections, and here's what I see for this function:

Found frame 0x7fffd6826f50, return 0x40110d
Found var in frame 0x7fffd6826f50, offset -008 addr 0x7fffd6826f48 value 0x408010
Found var in frame 0x7fffd6826f50, offset -016 addr 0x7fffd6826f40 value 0x408040
Found var in frame 0x7fffd6826f50, offset -024 addr 0x7fffd6826f38 value 0x408040

Here's what the assembly for the function looks like:

        .type   GCTraceTest.f3,@function
GCTraceTest.f3:                         # @GCTraceTest.f3
.Leh_func_begin6:
.Lfunc_begin4:
.Llabel48:
# BB#0:                                 # %entry
        pushq   %rbp
.Llabel44:
        movq    %rsp, %rbp
.Llabel45:
        subq    $32, %rsp
.Llabel46:
        movq    $0, -8(%rbp)
        movq    $0, -16(%rbp)
        movq    $0, -24(%rbp)
.Llabel49:
        movq    $.string3, -8(%rbp)     # GCTraceTest.tart:24:8
.Llabel50:
        movq    $.string4, -16(%rbp)    # GCTraceTest.tart:25:8
.Llabel51:
        movq    $.string4, -24(%rbp)    # GCTraceTest.tart:26:8
.Llabel52:
        movq    (%rdi), %rax            # GCTraceTest.tart:27:4
        callq   *88(%rax)               # GCTraceTest.tart:27:4
.Llabel47:                              # GCTraceTest.tart:27:4
.Llabel53:
        addq    $32, %rsp               # GCTraceTest.tart:28:2
        popq    %rbp                    # GCTraceTest.tart:28:2
        ret                             # GCTraceTest.tart:28:2

In the above assembly, the label "Llabel47" defines a post-call safe point, meaning that from this function's point of view, a garbage collection could occur during the call that immediately precedes that label. There is a static map that contains an entry for "Llabel47" and maps it to the stack frame descriptor shown earlier. The stack walker uses the frame pointer to find the return address of the calling function, and looks that up in the map. It then gets the caller's frame pointer, and uses the offsets in the stack frame descriptor to find the locations of the variables containing stack roots.