The Fugue Counterpoint by Hans Fugal

6Dec/130

Reduce compilation time with template magic.

It is a common belief that templates must be implemented in header files, a lamentable situation that greatly increases build times because those full-blown headers must be compiled every time they are included. It also makes the headers less useful as brief documentation, which one of the things about headers that is actually good.

But that is not strictly true. You can separate template declarations and implementations. With a simple pattern and just a little thought, you can compile your template code once and link it just like you do regular objects or functions.

Let us begin with a function foo which just prints the T it was given to cout. Here is the header:

// foo.h
#pragma once

template <class T> void foo(T);

Now let's try to use it:

// a.cc
#include "foo.h"

int main(void) {
    foo(42);
    return 0;
}

And compile:

$ c++ -std=c++11 -c a.cc
$ c++ a.o
Undefined symbols for architecture x86_64:
  "void foo<int>(int)", referenced from:
      _main in a.o
ld: symbol(s) not found for architecture x86_64
collect2: error: ld returned 1 exit status

The object file compiles fine, but linking fails because void foo<int>(int) is undefined. So, let's define it:

// foo-tmpl.h
#pragma once

#include "foo.h"
#include <iostream>

template <class T> void foo(T t)
{
    std::cout << t << std::endl;
}

Now if we change a.cc to include foo-tmpl.h instead of foo.h, the implicit instantiation will work fine. But instead, let's explicitly instantiate the int specialization in foo.cc, because we believe everyone and their dog will want the int specialization, and we want to save compile time:

// foo.cc
#include "foo-tmpl.h"

template <int> foo(int);

And compile:

$ c++ -std=c++11 -c a.cc
$ c++ -std=c++11 -c foo.cc
$ c++ a.o foo.o
$ ./a.out
42

Success!

Ok, but what about implicitly instantiating templates? We don't want to give up this unique power of templates. We can do it. This is why I put the implementation of foo in foo-tmpl.h instead of foo.cc. When we need to instantiate, we include the -tmpl.h instead of the .h. We should try to avoid doing this in other headers, and prefer to do it (once) in an implementation file. To demonstrate let's introduce a new function bar:

// bar.h
#pragma once

void bar();

And its implementation:

// bar.cc
#include "bar.h"
#include "foo-tmpl.h"

void bar()
{
    foo("bar");
}

Now we are implicitly instantiating void foo<const char*>(const char*), but that's ok because we included foo-tmpl.h. Now we can use bar:

// b.cc
#include "bar.h"

int main(void) {
    bar();
    return 0;
}

Compile and run:

$ c++ -std=c++11 -c b.cc
$ c++ -std=c++11 -c bar.cc
$ c++ b.o bar.o
$ ./a.out
bar

And finally, let's use them together

// c.cc
#include "foo.h"
#include "bar.h"

int main(void) {
    foo(42);
    bar();
    return 0;
}

Compile and run:

$ c++ -std=c++11 -c c.cc
$ c++ c.o foo.o bar.o
$ ./a.out 
42
bar

Just to make sure we understand what's going on under the covers, let's look at the symbols with nm, and make sure things are defined where we expect them to be:

$ nm *.o | c++filt  # manually-filtered output follows
a.o:
                 U void foo<int>(int)

b.o:
                 U bar()

c.o:
                 U bar()
                 U void foo<int>(int)

foo.o:
0000000000000000 T void foo<int>(int)

bar.o:
0000000000000000 T bar()
0000000000000075 S void foo<char const*>(char const*)

I performed these explorations with gcc 4.8.


$ c++ --version
c++ (MacPorts gcc48 4.8-20130210_0) 4.8.0 20130210 (experimental)
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

With C++11 you also have extern template at your disposal, which lets you avoid implicit instantiation. So if you have many files which instantiate the MyClass specialization, and don't want foo.cc to even be aware of MyClass, you can add this to MyClass.h:

// MyClass.h
#include "foo.h"
class MyClass {
    //...
};

extern template void foo<MyClass>(MyClass);

And then MyClass.cc looks something like this:

// MyClass.cc
#include "MyClass.h"
#include "foo-tmpl.h"

// explicitly instantiate templates
template void foo<MyClass>(MyClass);

MyClass::MyClass() {
    // ...
}

// ...

Now the MyClass instantiation of foo will only be compiled once in MyClass.cc, but can be used in umpteen other files.

8Oct/090

AC_TYPE_UINT8_T and friends

If you get errors like this:

$ autoreconf
configure.ac:110: error: possibly undefined macro: AC_TYPE_UINT8_T
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
configure.ac:111: error: possibly undefined macro: AC_TYPE_UINT16_T
configure.ac:112: error: possibly undefined macro: AC_TYPE_UINT32_T
configure.ac:113: error: possibly undefined macro: AC_TYPE_UINT64_T
configure.ac:115: error: possibly undefined macro: AC_TYPE_SSIZE_T
autoreconf: /usr/bin/autoconf failed with exit status: 1

It probably just means you have an old autoconf. These macros were introduced in autoconf 2.60. But it's probably no big deal if you have a sensible stdint.h.

8Oct/090

EINVAL on sendmsg() to a UNIX Doman Socket

I'm seeing an EINVAL result when trying to do a sndmsg() call to a UNIX socket. The man page says that means that the sum of the iov_lens overflows an ssize_t, but an ssize_t is 8 bytes on this machine and there's only one iov and its length is 671. Last I checked that doesn't overflow anything but a char. What gives? Same code works fine in Linux and when using UDP or TCP.

20Mar/080

What was that macro?

I find myself asking this question a lot: "Now what was that define that detects annoying platform that makes porting otherwise perfectly-portable code difficult?"

This will narrow your search down to something useful:

echo | cpp -dM

Go ahead, try it. I wish I'd known this one earlier.

16Mar/080

Network Programming

If ever you find yourself wanting to do some network programming in C, C++, or any other language that uses the socket paradigm, you must be careful. You are only inches from the edge of the precipice of insanity.

Luckily, some guy who calls himself Beej wrote a fantastic guide to network programming. He takes you by the hand and leads you gently away from the precipice. His guide is fun and easy to grok, but doesn't water the topic down. It's a fine piece of writing.

Even if you're writing Ruby network code, for example, which streamlines much of the insanity (thanks to exceptions and some nice OO abstractions like TCPServer), the socket concepts you will gain from at least skimming this guide will be a huge help.

Tagged as: , , , No Comments
8Jul/062

Duck Typing Defended

Ever since I discovered ruby I've loved dynamic typing. I never paid much heed
to people who got their knickers in a knot over how dynamic typing is "unsafe".

While working on Ardour this
summer
, I've literally been wrestling with C++,
all because it is statically typed. The code I've been writing over the past
month could have been done in one week with half my brain tied behind my back
(which is the usual situation, by the way), if only C++ were dynamically typed.

In other ways static typing hasn't exactly got in my way, it just causes me to
jump through hoops that seem silly, unnecessary, and inelegant. A simple
concrete example will help. I'm doing undo serialization, and of course Ardour
already serializes other things in order to save sessions. In C++ this means
lots and lots of otherwise unrelated things all inherit from a common
serializable base class. This is why multiple inheritance is necessary in C++.
In Java you can use interfaces, which is better than multiple inheritance but
not by much. In dynamic languages, you don't even have to give it a second
thought. You just make sure everything that needs to be serialized responds to
a serialize method, et voilá!

So as I've been wrestling I've had this nagging feeling that it's *me* that's
broken, not C++. Have I become so spoiled by dynamic languages that I can't
program efficiently in a static language anymore? Are the static people right
and one day my whole world will come crashing in and all my ducks will keel
over? Feelings of self doubt are part of being human, and these were some of
mine this summer. Then I read a blog post by Bruce Eckel on Strong Typing vs.
Strong Testing
and my mind was put at
ease. The thrust is, dynamic typing is good, and testing is necessary. I think
this quote about Robert Martin (a C++ guru) sums things up nicely:

Robert came to more or less the same conclusion I have, but he did so by
becoming "test infected" first, then realizing that the compiler was just one
(incomplete) form of testing, then understanding that a weakly-typed language
could be much more productive but create programs that are just as robust as
those written in strongly-typed languages, by providing adequate testing.

I have a thought along these lines. Let's say you've got duck typing in full
swing as in his examples. Now in the real world it sometimes happens that you
choose a common ambiguous word for the duck method, like "run" perhaps, but
more often than not you have methods that are named fairly specifically, like
"speak" or "jump". The static argument is that you might accidentally call the
method on something that won't do what you anticipate because it's not of the
right type. But really now, how many of your objects that implement "jump" are
going to be the wrong kind of objects in your application? Often the answer is
none. So you jump through hoops for no reason.

Do read the article, it's fun and well-written. Even if you come out still
clinging to your beliefs that static typing is Good and Wholesome, at least
you'll see that us dynamic people aren't necessarily lazy, stupid heathens.

5Jun/060

Constructors, coercion and casting, oh my!

This little bit of C++ trivia I may have known once but had forgotten. If you
have the appropriate constructor, the compiler will happily coerce for you:

class Foo
{
public:
Foo(int);
int i;
};

int bar(Foo f)
{
return f.i;
}

int main(void)
{
return bar(42);
}

You can also explicitly cast, which is useful when you are feeling explicit, or
want to cast to a subclass for polymorphic reasons.

Tagged as: , , No Comments
7Apr/060

Zero Link

XCode has a feature called Zero Link, which apparently more or less skips the
linking step when you build your project. I don't know the details but it's
probably fair to say that it's like just-in-time compiling, but for linking.
The raison d'être of this feature is to reduce the time spent waiting for
things to compile during development. It's not to be used for released code, so
it is on by default in the development building style and off by default for
the release style.

That sounds really neat, but we just wasted a bunch more time than we could
possibly have saved with Zero Link, because there was no linker to complain
about this:

// foo.h
#ifndef FOO_H
#define FOO_H

short foo[2];
short *p;

#endif

The problem, if you don't already see it, is that those variables should be
declared extern and instantiated in one and only one .c file. ld would
complain about duplicate symbols when trying to link two .o files that had both
included this header file. But with Zero Link, there's no error. Instead, you
get crazy behavior from the debugger: assignments that seem to have no effect
and other odd things that make you think you've fallen into an alternate
universe.

So be careful.

Tagged as: , , , , No Comments
5Apr/063

% for Remainder

I had my lunch handed to me today because some C DSP code I had written was
wrong:

/* M is the size of the buffer,
 * w is the base pointer,
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;
}

What I did not realize is that the % operator in C does not wrap negative
numbers into the positive range like you would expect if you were a
mathemtician. i.e. -7 % 8 == -7 in C, where in mathematics -7 = 1 mod 8.

I can hear you now: "Didn't you test it, you fool?" Well, yes, I tested the
algorithm in Ruby, where mathematics hold true:

rb(main):001:0> -7 % 8
=> 1

How was I to know the C version was braindead?

So which is right? Well you can probably guess my bias by now. But inquiring
minds want to know, and no other type reads this blog so I did some research.

First, the mathematics. Wolfram has a dizzying
explanation
. Search for
modular
arithmetic

for any number of treatments of the subject. Too lazy for that? Fine, look at
your watch. If it's 10:05 and you go back in time 10 minutes, is it -5 past
10? Arguably so ("5 to"), but most people would agree that it's actually 9:55
by canon.

Now for the C argument. The 1999 ISO C Standard says:

If the quotient a/b is representable, the expression (a/b)*b + a%b shall
equal a.

So my compiler is fine. It's C that's broken. Before C99 the use of % on
negative numbers was IMPLEMENTATION DEPENDENT, which if you know anything about
C history means they didn't think it through well enough, or they made a
decision based on speed or ease of implementation. The C99 definition was
probably chosen either for ease of implementation or for the most common case.
Not exactly good enough to convince me.

Naturally, there's no going back now, so if you find yourself possibly needing
to do modular arithmetic on negative numbers in C, be sure to add again if
negative:

/* M is the size of the buffer,
 * w is the base pointer,
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;

if (*p - w < 0)
    *p += M;
}

Here's a coherent post
to the gcc-help list about the subject. Now, I don't want to hear anyone saying
that % is the modulus operator from now on. It's the remainder operator.