Kevin's Weblog

Chapter 4 of Alexandrescu -- Small Object Allocator

Okay, this chapter didn't make me cringe. Here's a example of where using C is nice, because you can override fairly fundamental parts of the system (i.e. how things are layed out in memory.) This is a lot harder, if not impossible, in most other languages.

I got tripped up for a bit on a little issue of language semantics. The statement:

does totally different things in C++ and Java. I'm used to Java, at this point, where this just creates a null pointer, that you need to assign to later. However, in C++ this actually constructs a Lock object on the stack. Consequently, what looked to me like a bit of dead code can actually do something significant though the implicit invocation of the constructor and destructor (when you exit the block).

A lot of the discussion yesterday revolved around the fact that it seems that this chapter may be largely obsolete. Apparently in the 2 years since publication, compiler writers have learned some of these tricks, so some compilers are as good or better at small object allocation than Loki. Either that, or said compilers are not good at optimizing the Loki allocator.

There was also a bit of talk about the article on templates vs. ML that I posted last week: http://www.kuro5hin.org/story/2003/5/26/22429/7674 but we couldn't seem to remember the details well enough to really discuss the interesting questions.

Continuing through Alexandrescu (chapter 3 now), the thought that keeps coming to me is, why not just write in a functional language? The techniques of template meta-programming draw so heavily from functional techniques; so much that to someone familiar with them, the term "meta-programming" just sounds like hype. If you were using a more powerful programming language, there wouldn't be anything "meta" about it. I mean, he talks about typelists as if they were the second coming, but there's nothing remarkable about them. Virtually every language other than C can do it without the need for all these gymnastics.

Going back to my question to myself from a couple weeks ago, I think I know why I started getting so interested in languages. At some point a couple months ago, I realized that in my next job, I'd like to use a language I actually like. Perl, I tolerate. Java, I tolerate. C, I despise. Gotta learn some more Python and see if I can get past my distaste for whitespace-as-syntax.

Interesting question. We know that OCaml is essentially as fast as C for a wide variety of simple benchmarks. I wonder if there are any comparisons for more real life applications.

A continutation from where I left off last night...

The mind-boggling nature of this (optional interface features without ugly type checks or exceptions) isn't the fact that you can do it. Perl and Smalltalk programmers are immediately familiar with this form of polymorphism (interface polymorphism) (and the associated runtime errors when you screw up). Lispers would say, "Variables don't (shouldn't) have types, values have types". However, strongly typed languages like Java and C++ usually lock you into inheritance polymorphism. (Despite Java's use of the term "interface", it does not imply the same flexibility.) The magic here is interface polymorphism with compile-time type checking.

At some point I'll have to think more about type-inferring languages like OCaml and how exactly things work there. I'm not sure if that compiler will allow you the same flexibility and safety as the C++ template technique.

(Side note to all this: When did I become a language geek?)

I'm starting to read Modern C++ Design as part of the ALACPP group. It's a bit of an adventure given that my C++ experience is limited to a couple quarters in school.

We're reading the first chapter for tomorrow, which is an intro to advanced generics/templates using the concept of policies. I haven't quite grokked it fully, but I'm starting to get an idea of where this technique fits in.

The shortcomings of simple multiple inheritance are well-known. It's brittle and doesn't scale well, nor is it flexible enough to really deal with non-trivial interweaving of the constituents.

Standard pattern-based OO design generally prescribes composition rather than inheritance to acheive flexibility and scalability. At a first glance, policies look a lot like the Strategy pattern. However, the differences are the interesting bit.

First, and probably least importantly, the syntax is more concise for templated policies that for setting a bunch of strategies. Also, C++ typedefs can simplify your life, although factory methods are essentially semantically equivalent, if a litte more verbose.

Second, templates provide compile-time type safety, which isn't present with a strategy. This means that you can't accidentally assign a single-threaded instance of your class where you really needed a multi-threaded design, because the compiler will give a error. Also, because templates provide compile-time binding, there are performance benefits. The tradeoff is a slight loss of flexibility aas you can't change a policy in the course of execution the way you can a strategy. (Actually, this is not quite true. Alexandrescu talks a little bit about how to specify allowed type conversions between policies, but I haven't managed to absorb that section yet.)

The most intriguing difference to me at this point is way that you can deal with optional features of the policy. In a language like Java (pre-generics) you have to deal with this in one of two ways. Either you include optional methods in your policy interface and permit the hated UnsupportedOperationException, or you stick the optional methods into a subinterface and deal with a lot of "instanceof" checks, which also tend to make people ill.

However, two features of C++ make another option availible. First, the enhanced compile-time typing means that the runtime UnsupportedOperationExceptions turn into compiler errors. Second, the compiler doesn't actually enforce type-checking on methods which are never used! So, you can include methods which rely on optional features of a policy, but if a user of your class configures it with a policy that doesn't support them but doesn't use those methods of your class either, the compiler doesn't complain! Conversely, if they use a methods which relies on a feature their choice of policy doesn't allow, that is a compile-time error.

That's pretty wild. I'm not sure if I like it, but it's definitely a little mind-boggling.