Saturday, November 13, 2010

Coalescence

I spent the last several days experimenting with function-merging in the compiler, and the results are encouraging but not spectacular.

Take for example the following function in class ArrayIterator:

def next() -> ElementType or void {
  if (self.index < self.array._size) {
    return self.array._data[self.index++];
  } else {
    return;
  }
}

The type 'ElementType' is a template parameter. The interesting thing about this function is that it really doesn't care what ElementType is - it doesn't call any of it's methods or examine it's variables. Really, the only thing it cares about at all is it's size. For most arrays, that size will be the size of a pointer.

There's no reason, then, why ArrayIterator[String].next() and ArrayIterator[Object].next() can't be the same machine-code function. What I've managed to do is create a FunctionMergePass class that compares two functions and determines whether or not they can be merged. Currently I do not attempt to merge every function automatically, instead the merging behavior is manually triggered by the presence of the @Coalesce attribute on the class.

The pass works by walking the code-flow graph of both functions in parallel, and checks each pair of expression nodes to see whether or not they are equivalent in terms of their effect. If the merge pass finds any discrepancies between the two, the merge operation is canceled, and the function marked as non-mergeable.

Most expression types are trivial to compare, although some are more interesting. In the above code example, there's an implicit cast from 'ElementType' to 'ElementType or void' in the first return statement - in other words, it's constructing a union type and returning it. The merge pass in this case checks to see if the two union types are equivalent, which they are - 'Object or void' produces the exact same binary structure as 'String or void'.

The most common cause of merge failure is due to the function calling another non-mergeable function. Take for example this method in the template ArrayList[ElementType]:

def insert(index:int, e:ElementType) {
  Preconditions.checkIndex(index >= 0);
  Preconditions.checkIndex(index <= _size);
  grow(1);
  ElementType[].copyElements(_data, index + 1, _data, index, _size - index);
  _data[index] = e;
}

Everything in this function is mergeable except for the call to 'grow'. The reason 'grow' isn't mergeable is that it sometimes allocates a new Array instance, and calls to 'new' are generally unmergeable because the exact type of the object being created needs to be known. (There's a loophole around this which I have thought of but have not implemented - if the object being allocated is the same type as 'self', then we can just use the type information from 'self' instead of referring to the type information via a static constant.)

However, there is a way we could make the call to 'grow' mergeable - at a slight performance penalty. The answer is to make the call virtual. Right now it isn't virtual, because the "ArrayList" class is marked "final", which means that the compiler is smart enough to call 'grow' directly instead of dispatching through a virtual function table. (For those of you unfamiliar with Java, marking a class 'final' means that it cannot be subclassed, which allows the compiler to make significant optimizations.)

If the call to 'grow' were made virtual, then even if we merge ArrayList[String].insert() with ArrayList[Object].insert(), the correct version of 'grow' will be called in either case because it depends on the type of 'self'.

The question is whether or not this is worth doing, which comes down the question of what's more important, speed or size? At the moment, enabling the function merging behavior on the SwitchStmtTest unit test results in a 7K reduction in the size of the executable file. 7K out of 350K is not all that much.

Thursday, November 11, 2010

Tart: Still Too Large

Although the new reflection system has managed to reduce the size of the executables somewhat, I'm still concerned about the overall size.

For example, the unit test SwitchStmtTest weighs in at about 350K binary executable size. This is with optimization turned on (including dead code and global elimination), and with all debugging info stripped. That seems quite large to me - I'd like the size to be more on the order of 50K (that's my rough guess at how large an equivalent C++ program would be.) Note that with optimization off and debugging turned on, the size balloons to a whopping 1.5 megs.

I decided to do an analysis to see what exactly was taking up so much space. I used 'nm' for this purpose, along with a Python script that computed the size of each symbol in the object file based on the address deltas. These numbers are very rough, since there's a lot of stuff in the object file that is not accounted for. I'm only using the numbers as an order-of-magnitude guesstimate of sizes.

The contents of the object file can be broken down in several ways. Here's a breakdown by package:
  • tart.atomic: 16
  • tart.collections: 24712
  • tart.core: 37875
  • tart.gc: 288
  • tart.reflect: 34823
  • tart.testing: 3536
  • tart.text: 6179
  • SwitchStmtTest: 4435
  • Total: 111864
The numbers represent the total size, in bytes, of all symbols whose names start with the package name.

One of the first things to notice is that the total is only about a third of the size of the object file. I'm not at all sure why this is.

Also, I'm curious why tart.atomic was even included at all, given that nothing refers to it.

In the case of templates, the template expansions are charged to the package defining the template, not the package that instantiated it. In fact, template expansions account for a large portion of these numbers. Two templates dominate:
  • class tart.core.Array: 26879
  • class tart.collections.ArrayList: 13840
This leads me to believe that I need to think very hard about how to reduce template expansion sizes. I tried Nick's -mergefunc LLVM pass (which coalesces functions that produce identical machine instructions), and it had very little effect. That may be due to a bug in the -mergefunc pass, or it may be that there are in fact tiny differences in the generated code for different templates.

Another way to break down the numbers is by symbol type. For example, if I add up all of the static metadata for reflection, the total comes to 27645.

Here's a breakdown of some of the symbols (only items > 500 bytes are listed):
  • Non-reflection data (dynamic dispatch tables, instance allocators, etc.)
    • Constant tart.core.String instances: 16256 (Average size 66)
    • Type info blocks: 6784 (average size 45)
    • Type base class lists: 1952 (average size 33)
    • Interface dispatch functions 3168: (average size 36)
    • Compiler-generated instance allocators: 800 (average size 38)
    • Trace tables for garbage collection: 736 (that seems low!)
  • Reflection-related data
    • Type adapter functions (for boxing / unboxing reflected calls): 20912
    • Class and module reflection structures: 13216
    • Compressed name tables: 7864
    • Field offset tables: 1080
    • Tables of pointers of types referred to by other types: 2400
Here's my list of take-aways from all this:
  • 64-bit code is really fat. Even a trivial function can be >1K
  • Template expansions are taking a large amount of space.
  • I can probably optimize the type adapter functions. (These are functions generated by the compiler that auto-box and unbox function parameters.)
  • The refection structures for classes and methods can probably be trimmed a bit if I am willing to use void* pointers (means I can combine multiple tables into one.)
  • It may be possible to reduce the number of generated strings somewhat.
Coming up with a solution for template expansions is going to be the hardest. Ideally, we want to re-use the generic code as much as possible - so instead of separate definitions for tart.core.Array[Object].Iterator.next() and tart.core.Array[String].Iterator.next() - which do exactly the same thing - we can point them both to a common definition. The problem is that not all template methods are type-independent. For example, the tart.core.Array[Object].copyOf() method allocates a new array instance, and the type of that instance will be different for different template instances of copyOf().

Each template class method will be impacted to a greater or lesser degree by variances in the type of the template parameter. We can group functions in to classes by the degree of this impact:
  • No impact - the function is exactly the same regardless of the template parameter. An example is the method that returns the length of an array, which is the same regardless of the type of the array element.
  • Different type sizes - for example, the array copyElements() treats all the array elements opaquely (it just memcpys them) so the only thing it cares about is the size of the elements. Thus, all pointer arrays are the same as far as it is concerned.
    • For these cases, the solution is to generate a version of the function for each distinct size - so you have a version for 1-byte array elements, 2-byte, 4-byte, and so on.
  • Parametrically polymorphic - this means that difference instances of the method do the same thing, but with different types - so for example, one version might add two ints, while another adds two floats.
    • One possible approach would be to somehow (I'm not sure how) to migrate the type references outside the function, possibly in the static class data - so for example, when copyOf() creates a new instance, instead of hard-coding the type, you look it up. However, this seems pretty complicated, and I'm not sure how to do it.
  • Ad hoc polymorphic - this basically means "anything goes" - two different versions of the same template method might end up with completely different behavior. While functional language purists frown heavily on such things, in practice there are a few cases where this can be useful, especially in the metaprogramming domain.
    • An example of how the code can be different: Suppose we have a type A which defines "foo" as a constant, and type B which defines it as a variable - if a template "Example" has a method method "bar" which operates on the "foo" property, then the generated code for Example[A].bar() will be very different from the generated code for Example[B].bar().
Detecting which group a method falls into requires tracing through the code flow graph of the function, and analyzing each expression, type, and value to determine how that item will vary based on the template's parameters.

In a language with a JIT, the solution to these problems is simple - you instantiate the template instance methods lazily. So for example, if no one ever calls tart.core.Array[String].copyOf(), then just don't generate that method. The problem with a language that generates native binaries (and this applies to more than just templates) is that everything has to be generated in advance, because you don't know ahead of time what will and won't be used.

A final issue that I need to consider is "when?". Do I need to address the size issues right now, or can it wait until more language features go in? I know that the common wisdom is "optimize last", but at some level a program can perform so poorly that no one will consider it worth the trouble of using, let alone optimizing. I know for example that a typical XBox developer would never bother to use Tart in it's current state, where program size is a critical issue (there's no virtual memory on the XBox and games tend to use all of memory.) Also, I don't like building on shaky foundations.

Tuesday, November 9, 2010

Intervals in Gosu

Gosu has an interesting syntax for open and closed intervals:

   1..10   // Closed interval, i.e. the values 1-10 inclusive.
   1|..|10 // Open interval, the values 2-9

Having an easy syntax for open and closed intervals solves a number of problems I've been having: Sometimes you want intervals to be closed, other times half-open. For example, Python slice objects are half-open, and would be much less useful if they were fully open or fully closed. The interval notation would make it easy to do Python-style slices:

  let s = "Hello, world!";
  Console.out.printLn(s[0..|5]); // Prints "Hello"

Tart status update

I've been making substantial progress over the last couple of days, which is a welcome change after a couple of frustrating months.

The last few months have seen a lot of hard effort, with very little to show for it. I'd been focused primarily on getting debugging working - being able to inspect Tart data structures in the debugger. Unfortunately, it seems that LLVM's facilities for generating debug information aren't very robust - if you make even the smallest mistake in calling the debug factory functions, it will silently write out bad debugging data without telling you. In addition, the available tools for inspecting and checking DWARF debugging data are very primitive, producing at best a raw text dump of the debugging structures, requiring you to manually trace the cross references between debug entries. Nor is gdb particularly helpful in terms of it's error messages. Add to this the fact that DWARF itself is extremely complex, and that even a small program will produce many kilobytes of debugging data, and you can begin to see why it takes so long to get this stuff right.

The key to breaking this logjam was my attending of the LLVM developer's conference last week. I was able to talk directly to the people working on the parts of LLVM that deal with debugging info. I was able to clarify a number of critical points which I had not been able to do over email conversations. (I've noticed that any email question sent to the llvm-dev mailing list has approximately a 50% chance of being answered, so getting answers takes persistence.)

It took me a few days to be able to apply everything that I learned at the conference, with a lot of trial and error involved. During this time, I was at the Hacker's Conference, and I spent about half my time at the conference staring at my laptop working on Tart. Although I felt bad about not paying attention to the conference sessions, I really felt driven to try and get this stuff working.

As a result, the debug stuff is working much better. I can now set breakpoints, examine function parameters and data structures (although examining local variables is still not working).

In addition, I've also made progress switching over to the new, compressed reflection metadata. The old system has been completely removed, and the unit test framework has been switched over to use the new system.

In other news, I read last night on Slashdot the announcement of the Gosu programming language, which has a lot of similarities to Tart. In fact, it's quite discouraging to me to see how many of my ideas have been developed independently - discouraging because they have a shipping product and I don't. That being said, there are a few things that I think they didn't get right, and a few things that seem faddish, but none of these are serious.

I think the biggest difference between Gosu and Tart is that Gosu targets the JVM, whereas Tart produces native binaries. I'm not sure which of those two paths will prove to be smarter in the long run. Obviously, it's a lot easier to write a new language for the JVM, since you get a lot of stuff for free - garbage collection, a huge class library, and so on. The benefits to producing native executables is more subtle - a quicker startup time, ability to run on platforms that don't have a JVM, and so on.

There are also a number of downsides to native executables - for example, a lot of stuff has to be pre-generated (like type adapter functions for reflection) which can be generated dynamically as needed in the JVM. This potentially makes the native executable much larger than the equivalent Java .class file. Also, there's no way to do HotSpot-style profile-guided optimization, which you could do with a JVM.

In any case, each time someone comes out with a programming language that is similar to Tart or fulfills a similar need (Go, Gosu, Scala, etc.), it means that the chances of Tart achieving any sort of widespread adoption gets smaller. Nevertheless, I'm not ready to quit yet... :)

Monday, October 25, 2010

Switch statement syntax

Here's a few minor design puzzles. C's "switch" statement requires a "break" statement at the end of a switch case. I've long felt that this was a design misfeature, and while it is useful for some clever hacks, it's also a source of much trouble. I decided instead to make each case a first-class block. Here's a sample of what switch statements look like in Tart:

   switch value {
     case 1 {
       // something
     }

     case 2
     case 3 {
       // something
     }

     else {
       // something
     }
   }

Note that cases 2 & 3 go to the same block. Syntactically, the rule is that a case value can be followed by one of two things: Another case value, or the start of a statement block.

One alternative syntax I considered was to use a comma to separate case values: "case 2, 3". However, I discarded this for two reasons: first, because it looks ugly if there are a lot of case values and you need to break the line, and second, because I eventually want to be able to have case values that are tuples.

However, the lack of a delimiter after the case value is a bit troubling. I've discovered at least one bug where I typed a case value and forgot to write the subsequent block, which resulted in the executing falling through to the next block. If a delimiter were required, then the compiler would have caught that.

There's also a problem with the use of the keyword 'else' instead of 'default' - sometimes I like to put the default case first instead of last, and that doesn't read as well with the word 'else'.

Finally, there is the issue of the 'functional-switch'. A lot of functional languages have a switch statement which returns a value (let n = switch value { ... }). I've been wondering if Tart should have something like this. However, it's not clear to me how you would indicate which value to return in a block, especially in an imperative language which supports multiple statements. The choices are (a) return the value of the last statement in the block (if there is one), (b) have a special keyword for returning a value of a block. Both approaches have issues.

Having a functional-switch implies that there should also be a functional-if as well, which is nothing more than the C/Java/Python conditional operator. Tart doesn't have or need such an operator, since the 'cond' macro does the same job without needing special syntactic sugar. However, doing a switch statement as a macro is a little more difficult, since the number of arguments to the macro can grow arbitrarily large.

Tart status update

I've been working pretty hard on Tart the last few weeks. I've been focused on several areas:

DWARF debugging - There's not much progress in this area, despite my best efforts. Lately I've been attacking the problem from a different direction, which is to produce a reproducible test case that doesn't require the entire Tart infrastructure to be present. Unfortunately, doing this requires fixing a bunch of minor issues which would not otherwise be high priority. For example, the Tart linker fails unless optimization is enabled, due to a bug in the LLVM lowering pass for garbage collection intrinsics. Unfortunately, I need an unoptimized test case if I want to get the LLVM experts to help me with my problem. So I have to fix the second problem in order to even start working on the first.

Garbage Collection - The stack crawler is completely working now. The next step is to write a very simple test collector and a test for it.

One issue that concerns me is that I want Tart to be able to support pluggable collectors like Java does. Java has the ability to specify a collector when you launch the program - in other words, the selection of collection algorithm can be deferred until the program begins execution. In order to do this, I'd need some sort of plugin or loadable module system, something I haven't even begun to think about.

The best I can do for the moment is to make the collector algorithm a link-time decision, that is to have different static link libraries for different collectors.

Reflection - I've been working hard on the new reflection system, the one that uses compressed metadata to describe all of the various classes and methods in a module. Right now the compiler emits the metadata for both the old and new systems, which makes the resulting object files much larger than I would like them. Unfortunately, the new system isn't yet up to the task of replacing the old system. For example, the "execute by name" feature - which is used by the unit test framework - isn't ready yet.

I've also been plagued by a number of strange anomalies. CMake has been acting weird lately - a build rule that was working fine for several months suddenly stopped working. I didn't notice at first since the bug only manifests on a clean build. Although CMake is a great tool, there are certain kinds of build rules which really ought to be simple, but which are nearly impossible to do without truly ugly and non-intuitive work-arounds. For example, it's nearly impossible to define an add_custom_command() rule which has a dependency on a build product which was produced in a different directory.

Sigh...it seems like the last 3-4 months has been spent dealing with low-level details of LLVM, DWARF, and so on - I've spent virtually no time thinking about the Tart language per se, which is what I really want to be working on.

Thursday, September 16, 2010

More on TraceTables

I realized that my object-tracing scheme, as outlined in the last posting, was unable to handle an important case: unions. Unions can contain both pointer and non-pointer types, and since I'm planning on building an accurate rather than conservative collector, that means that I'll need to examine the type of data stored in the union in order to determine whether to trace it. Otherwise, you might end up with the case where you store an integer value in the union, but the garbage collector attempts to interpret it as a pointer.

The internal structure of a union depends on whether or not it contains any value types. If a union contains only reference types (i.e. pointers to objects), then the union is simply a pointer. There's no need for anything else because each object type is self-identifying. Tracing this type of union is simple, just treat it like a regular pointer.

If a union contains any value types, however, then the union also contains a "discriminator" field, which is a small integer field that contains a code indicating what type of data is currently stored in the union. The tracer needs to examine the discriminator field in order to determine whether or not to trace the data stored in the union. Doing this will require the compiler to generate a special tracing function for the union. While it might be possible to generate data tables that tell the garbage collector where to look for the discriminator field, interpreting that data structure would make the garbage collector extremely complex. So a function it is.

At the same time, however, I still want most of the tracing to be data-driven rather than code-driven. The reason for this is efficiency and separation of concerns. The part of the garbage collector that handles object tracing is divided into two subcomponents: There is the part that understands the memory layout of all of the types generated by the compiler, and there is the part that implements the various tracing passes needed by the collection algorithm. Because there are potentially millions of pointers that need to be traced, the communication between these two subsystems needs to be very high bandwidth - we want to avoid having to do an indirect function call for each pointer traced. A data-driven strategy allows the the description of the memory layout for the whole object to be passed to the tracing algorithm as a single call, rather than a call per pointer field.

The new tracing strategy is a hybrid of the two methods. For object types which have a fixed, unvarying layout and interpretation, a purely data-driven approach is used. For fields which are variable length (such as FlexArrays), or which have a changing interpretation based on their contents (such as unions), tracing functions are used to augment the purely data-driven scheme.

Let's define some terms:

TraceAction - an object representing a specific tracing pass, which operates on pointer fields of an object. There are two methods for invoking the action: Either by applying it to a pointer field directly, or by passing it a base pointer and a list of field offsets.

Field Offset Table - A table of offsets into an object, specifying the location of pointer fields within that object.

TraceMethod - a method on the object being traced which takes a TraceAction as an argument, and applies the action to the various pointer fields within the object. TraceMethods are used for tracing object fields that are too complex to be described by a field offset table.

TraceDescriptor - an object representing a strategy for tracing a specific object type, although not necessarily all of the pointers within that type. There are two types of descriptors, field offset descriptors, which contain a pointer to a field offset table, and trace method descriptors, which contain a pointer to a trace method. Both types of descriptor have the same size and layout, and can be arranged together in a flat array.

TraceDescriptorArray - an array of TraceDescriptors sufficient to trace all of the fields within an object. For most types, the descriptor array will consist of a single field offset descriptor. For objects which contain flex arrays or unions, additional trace method descriptors will be in the array.

There are three places where TraceDescriptorArrays are referenced:
  • For classes, the TIB (TypeInfoBlock) of the class contains a pointer to the descriptor array.
  • For structs, tuples, unions, and other data types that are statically typed, the descriptor array is a static constant which can be accessed by name.
  • For stack frames, the descriptor array is accessed via the sync point table - this is a table containing all of the program counter addresses where a garbage collection could potentially take place. The idea is that when a collection occurs, you walk up the stack looking at all of the return addresses for each call frame. You then look up the address in the sync point table, which yields a pointer to the type descriptor array for that stack frame. 
Here's what a field offset descriptor looks like. It's designed to be exactly 16 bytes, even on a 64-bit system. (On a 32-bit system it will be padded.)

/** Struct containing information on how to trace a type. */
struct FieldOffsetDescriptor {
  /** If non-zero, it means that this is the last descriptor in the list. */
  readonly var endList:uint16;

  /** Number of fields in the field offset table. 0 = method descriptor. */
  readonly var fieldCount:uint16;

  /** Offset from base for this descriptor. */
  readonly var offset:uint32;

  /** Table of field offsets. */
  readonly var fieldOffsets:Address[uint16];
}

A trace method descriptor looks the same, except that the last pointer field will contain a function pointer rather than the field offset table.