Category Archives: tech talk

Only a Mathematician would say

I came across a version of Dijkstra’s “Goto Considered Harmful” annotated by David Tribble. A lot has changed since then; the annotated version is perfect for acquiring the right context to read the paper.

There was a particular line by the annotator that continues to amuse me:

Dijkstra seems to imply that iterative looping (inductive) statements are intellectually harder to grasp than recursion, which is the kind of thing only a mathematician would say.

Among the ways you can bisect computer science, is whether this statement insults or compliments.

Native Client at UWCS lecture

Available for streaming and download, Google Native Client presented at UW’s computer science lecture series. Covers the restrictions on x86 code, new alignment rules, and performance on various benchmarks. 5% overhead, that’s nothing compared to many other sandboxing techniques.

Native client is 50KB download?  Wild. It really is just a gatekeeper, runtime library separate.

Of course, I would love to get away from x86.  LLVM, or ARM, or even Amd64.  x86 makes me a sad panda.

Meijer throws down!

Okay, not really. Saw this latest on LtU, regarding the recent JVM conference.  Erik Meijer was talking his recent work on the .Net Reactive Framework, and had this to say in passing:

And of course you say, “Erik, [why] are you making a big deal?  Category s–t like that.  The design pattern book fifty years ago mentioned these things [Iterator and Observer].”  The funny thing is that if you look in the back of the book at the related patterns, these two patterns are completely unrelated.  They are not even mentioned that they’re related.  Where as in reality these are super-duper related, right?  No two more interfaces on the planet, in the universe, are more intimately connected than these guys, because they’re connected by mathematics, ok.  And these guys — I think this book is crap — [audience laughter, nervous chuckling] I cannot trust these guys anymore

He’s kidding, about the GoF book being crap of course.  “Design Patterns: Elements of Reusable Object-Oriented Software”.  At least that’s my interpretation.  He’s just expecting more of the book — it defines, observes, studies, and documents 23 different software patterns, drawing up relations about the patterns based on in-the-wild observations of what patterns fraternize with which others.  And somehow this relationship between Iterator and Observer has just never come up!

I’ve been looking a lot at the Iterator pattern, the Observer/Visitor patterns, and Continuation Passing Style lately.  The relationships between these different patterns are fascinating — the latter especially, because you are able to switch freely between Iterator and Observer features with CPS, choosing the best features you want.  Well, not quite freely, because there’s a cost, in that different languages support different patterns to different degrees.  Especially in the case of CPS, some languages support it well (Ruby, Scheme, JavaScript), others with some moderate effort (C# 3.0 and later), and others require exorbitant effort and skill (C# 1.0, Python, C++).  Don’t get me wrong, I’m not bashing or especially holding high any particular language here — these are all languages I enjoy and prefer, but they have different strengths and, on this dimension, show great disparity in code readability and maintainability, for me and some peers.

So I’ve been thinking a lot about this divide, on such a fundamental abstraction as a sequence, and different behavioral modes it takes on.

Excellent talk, the portion available on youtube at least.  If you want more info on his work or Reactive Programming in general, it looks like MSDN channel 9 covered Erik on Reactive Programming back in July, so check that out.  Or check out Erik’s personal page on Microsoft Research with links to papers and talks on past and present research and application.

Edit add:

Saw this added on the LtU discussion and found it a good overview of Rx, from the unfold blog: http://themechanicalbride.blogspot.com/2009/07/introducing-rx-linq-to-events.html

ICFP Competition

International Conference for Functional Programming.  Each year, they hold a conference on topics in programming language and functional programming techniques. 

Continue reading

50 in 50 at JAOO

[repost, from fall 2008]

I caught this talk on earlier blogs – well, not so much a technical talk as a performance.  Richard P. Gabriel and Guy L. Steele wax poetic on 50 programming languages in 50 statements each of 50 words.

“50-in-50”

http://blip.tv/file/1472720

That is all.

CLOS circa 1987, Dynamic Dispatch in C++/C#

As reported by programming musings,

http://www.archive.org/details/DanielGB1987

Common Lisp Object Standard presentation, by Daniel G Bobrow.

Some reflections:

Fast Multiple Dispatch

"[for dynamic method resolution] A cache of 1000 entries is hit 98% of the time".  Assuming this is accurate, it explains how you could get by with the cached virtual dispatch lookup that the desktop Microsoft CLR runtime does – while not exactly what Bobrow means, 1000s of cache locations spread through the program can get a hit rate fast enough to compensate for the slow resolution path that is taken.

Fastpath Optimization

"What we learned from smalltalk is … something like 60%-70% of generic functions have exactly one method implemented".  I’ve been seeing discussions lately about fastpath optimization in dynamic languages.  The technique is to take advantage of the fact that not all dynamic call sites are very dynamic.  You can sometimes statically dispatch calls (assume various parameters are fixed-width-integers, assume others strings, etc) as long as you have recovery code that can detect the difference before any results are visible.

Tech talks haven’t really changed that much in 20 years; apparently we’ve already long since found the local optimum.  Code samples that fit on slides are always stacked; don’t solve real problems.  Diagrams are always awkward but we keep trying anyway.  Oh, and we didn’t compile the code before putting it in!  But don’t get me wrong, I think this talk was well done, and to be fair, he knew of the error (I assume back then, editing slides was a bit harder than PowerPoint).

Some CLR tie-ins

I think both of these features play a significant role in performance of CLR performance characteristics.

For those not familiar, if you step through a virtual call in MSIL on x86 or x64, you’ll see that each call site caches the address of the function that was last hit from that call site.  Consider the pseudo code:

void some_object::do_something(int x)
{
    //...
}
int main()
{
   some_interface* p = get_an_object();
   p->do_something(42);
}

In C++, typically some_object has a vtable for each interface, and each member function has an entry in this table.  Actual execution looks something like:

// ----  C++ style dispatch ----
struct some_interface
{
    struct vtable_layout
    {
        void (*do_something)(some_interface*, int);
    };
    vtable_layout* vtbl;
};
some_object::some_object()
{
    static vtable_layout vtbl = {
        &some_object::do_something;
    };
    this->vtbl = &vtbl;
}
void some_object::do_something(int x)
{
    //...
}
int main()
{
   some_interface* p = get_an_object();
   p->vtbl->do_something(p, 42);
}

Note that because the dispatch mechanism is tied to the vtbl, then only the first argument (or, rather, only one argument, according to some convention) can affect dispatch.

The CLR dispatches calls differently, more like:

 

// ---- CLR style dispatch ----
struct object
{
    void* type_identifier;
}
void default_do_something(object* p, int x)
{
    void (**memfun_do_something)(object*, int);

    // find address of "last_function_called" variable
    memfun_do_something = find_callsite();

    // fill in value using dynamic type of 'p'
    *memfun_do_something = 
        global_function_table
        .find_type(p->type_identifier)
        .find_member_function("do_something");

    // finally, call the actual member function
    return (*memfun_do_something)(p, x);
}
some_object::some_object
{
    this->type_identifier = some_object_id;
}
void some_object::do_something(int x)
{
    // thunking code -- in case wrong function called
    if (this->type_identifier != some_object_id)
        __tailcall(default_do_something(this, x));
    
    // ...
}
int main()
{
   some_interface* p = get_an_object();

   static void (*last_function_called)(object*, int) 
    = default_do_something;
   last_function_called(p, 42);
}

This is much more complicated – though keep in mind that the function ‘default_do_something’ can be shared for all defaults, using the call site as a hint.  Here, if the default is called or if the ‘last_function_called’ cache is wrong, we pay the hit of searching the type system for the method to call.  However, if the call is on the same object as the last call, then the cache will allow us to make a single indirection initially.  And because it is not using dispatch tables but rather a single type id, we can in general get away with having only a single type id per object instead of one vtbl pointer per interface implemented, saving space as well. 

There are still two indirections going on, but only one indirection that will force a stall the instruction pipeline – the type check can take advantage of out-of-order execution and branch prediction.

Related to CLOS, this scheme’s performance is no longer linked to single dispatch – any lookup scheme can be implemented in default_do_something, provided that a good cache hit rate can be achieved.

As well, when only one implementation exists for a virtual function, the cache hit rate will be 100% after the initial call.  For fast path, this means that you could potentially recompile main() to always call some_object::do_something, and rely on the type check to dispatch correctly if the situation changes.

Static typing where possible, dynamic typing when needed

 

From the discussion paper by authors Erik Meijer and Peter Drayton, as reported on Lambda the Ultimate:

Unfortunately there is a discontinuity between contemporary statically typed and dynamically typed languages as well as a huge technical and cultural gap between the respective language communities.

The paper goes on to list 8 different static or dynamic language behaviors that programmers rely on, and in most cases this critical feature of the language has little or nothing to do directly with the static/dynamic choice.

Favorites are "I want contracts" from the static typing camp, and "I want higher order functions, serialization, and code literals" from the dynamic camp.  I think ‘GetHashCode’ from Java and C#/CLR show how static typing can fail at contracts, while C++ TR1 function and CLR delegates show how most higher order functions can work in static languages (although recursively defined function types can still be a problem).

In (seemly) unrelated research I’m doing for my parser writing hobby, these two authors came up again in another blog, Monadic Parser Combinators using C# 3.0, and also looks to be of some interest, but not  directly on programming language front.

The paper is also available on Meijer’s Microsoft research page, at http://research.microsoft.com/~emeijer/Papers/RDL04Meijer.pdf

PDC 2008 picks

Some of my favorite picks from PDC 2008:

  • IronRuby: the Right Language for the Right job – I didn’t realize how well developed the DLR and dynamic languages on the CLR really were.  And on that…
  • Deep Dive: Dynamic Languages in Microsoft .Net – it’s a dynamic language infrastructure that, out of the box, looks like it’s going to have C#, Python, Ruby, COM IDispatch, and looks to be easy to extend in existing .Net languages.  I’ve been critical of many portions of the CLR, but I have to admit that it has proved successful at bringing languages together.
  • "Oslo: building textual DSLs" – The rest of Oslo, not really in my interest areas, but the parser generator is certainly fun.  It still confounds me that modern languages and runtimes come with so many features, but most are missing good general purpose parser libraries.  Boost.Spirit for C++ is a notable exception.
  • Parallel Programming for C++ Developers… – C++ is needing a facelift in the world of concurrent software.  C++0x is providing basic cross-platform concurrency primitives, and Microsoft VC++ looks to be providing easier to work with high-level libraries, as well as the PDC announced support for interoperating with Intel Threading Blocks, with extensions support available for your existing home-grown concurrency libraries.  This should be interesting.

There’s a whole treasure trove of PDC talks available up on channel 9, check it out.