Small Variant Records in C

[Marco Devillers]

Hi all, this must be one of the oldest questions in the book, but the
following:

I wrote a compiler. Values are either pointers or -opaque to the
compiler- series of size tagged bits. It works, it's slow, it's hardly
portable since the compiler needs to know the C bit representation of
values, I want to get rid of that.

So, I want more portable code, and, as most compiler writers, I want
to represent possible values as a type tagged sum, a variant record
where each concrete value is represented with a minimal number of bits
run-time.

What is the best portable manner for that? I thought overlaying
structures? Which compilers allow for initial segments of structures
to overlap unambiguously?

Cheers, Marco

 

[Seebs]

What is the best portable manner for that? I thought overlaying
structures? Which compilers allow for initial segments of structures
to overlap unambiguously?

Well, at least in theory, all of them -- if they're in a union. So
say you do something like:

typedef union {
struct { int type; } type;
struct { int type; int value; } integer;
struct { int type; double value; } floating;
} generic_data_t;

and pass those around, you should be able to access foo.type.type to
determine which one you have.

The reason for the union is so the compiler will know that writing to parts
of one of these through a pointer could modify others.

-s

 

[Eric Sosman]

Well, at least in theory, all of them -- if they're in a union. So
say you do something like:

typedef union {
struct { int type; } type;
struct { int type; int value; } integer;
struct { int type; double value; } floating;
} generic_data_t;

and pass those around, you should be able to access foo.type.type to
determine which one you have.

Caution: By leaving the member structs tagless Seebs' recipe
avoids a potential problem. Suppose you wrote an alternative like

struct s_int { int type; int value; };
struct s_double { int type; double value; };
typedef union {
struct { int type; } type;
struct s_int integer;
struct s_double floating;
} generic_data_t;

So far, everything's the same and no harm is done. Now you might
be tempted to create a bunch of free-standing s_int structs:

struct s_int digits[] = {
{ INT, 0 }, { INT, 1 }, { INT, 2 }, { INT, 3 }, { INT, 4 },
{ INT, 5 }, { INT, 6 }, { INT, 7 }, { INT, 8 }, { INT, 9 },
};

There's *still* no problem. Form a pointer to one of these things
and pass it to:

void generic(generic_data_t* ptr) {
switch(ptr->type.type) {
case INT: ... use ptr->integer ...; break;
case DOUBLE: ... use ptr->floating ...; break;
}
}
...
generic(&digits[7]);

.... and suddenly all Hell may break loose. The compiler "knows" that
`ptr' points to something that's at least as big as a generic_data_t
and properly aligned for the strictest of that union's members, and
may use that knowledge in its code generation. Since the actual
instances you're passing are (probably) smaller and (possibly) not
aligned tightly enough for a `double', you're in trouble.

(Don't ask me how I learned about this particular trap ...)

 

[Marco Devillers]

   typedef union {
Okay, so I would need separate specific type definitions for subtypes
and a generic union type to wrap up and have the C compiler lay out
all fields unambiguously. So I'll go for the not too different
solution by the second poster.

        struct s_int { int type; int value; };
        struct s_double { int type; double value; };
        typedef union {
            struct { int type; } type;
            struct s_int integer;
            struct s_double floating;
        } generic_data_t;

Since the actual
instances you're passing are (probably) smaller and (possibly) not
aligned tightly enough for a `double', you're in trouble.

Yah, I see that, thanks for pointing it out. I think I am fine as long
as I can just cast between the generic and specific variants.

Great responses, thanks all, Marco

 

[Seebs]

Yah, I see that, thanks for pointing it out. I think I am fine as long
as I can just cast between the generic and specific variants.

You can't necessarily. You really have to use the union type in most
cases or the compiler will assume the types can't alias each other.

-s

 

[Marco Devillers]

You can't necessarily.  You really have to use the union type in most
cases or the compiler will assume the types can't alias each other.

Hmpf, so does a trick with not allocating more than the size of a
specific member of the union work?

I mean, the game is to have a variant type where each subtype
allocates a minimal number of bits (rounded of by a word size I
chose). Is there a solution?

According to C99, objects which share an initial prefix of common
types have similar memory layout, or am I mistaken? I.e., should I be
able to cast between s_int or s_double -below- and be sure that the
int type is shared? (I do it anyway in toy programs, but I never was
really sure if it worked because I assumed a naive compiler, or a
robust language feature.)

struct s_int { int type; int value; };
struct s_double { int type; double value; };

Cheers, Marco

 

[Eric Sosman]

[...]
Since the actual
instances you're passing are (probably) smaller and (possibly) not
aligned tightly enough for a `double', you're in trouble.

Yah, I see that, thanks for pointing it out. I think I am fine as long
as I can just cast between the generic and specific variants.

Perhaps "I see that" was premature, or just over-optimistic.

My point is that you *cannot* do the cast safely. Sure, it
looks safe -- but it isn't. I warned you not to ask how I learned
of this pitfall, but it looks like you need the story ...

As in your situation, the program was dealing with type/value
pairs. And it used the struct-for-each-kind dodge, with the type
code (and some other flags) at the same spot in each. And it put
all those structs into a union, and wrote a function that took a
union pointer, switched on the common type code, and didn't even
look at the type-specific parts until it got to the individual
switch cases.

Safe as houses -- in Joplin, Missouri.

Along came a compiler that was fairly aggressive (for its time;
this was more than fifteen years ago, and compilers have grown even
more devious since), and this compiler said to itself "Aha! I've got
a pointer to one of these union things, so there's an entire union
instance where it points. My data flow analysis shows that several
of the cases I'm about to switch between (not all, but several) will
want the doubleword at offset 8, and a few more will want the data
at offset 16, too. I'll save a few instructions by issuing prefetches
for those doublewords up at the top of the function, before the
switch. Ain't I the clever one?"

... and all was well, because if the type code took us to one
of the cases that didn't use the data, it just got prefetched and
ignored; no harm done.

... until the day an incomplete union instance just happened to
butt right up against the end of mapped memory, and the prefetches
took SIGSEGV's.

It took a while to unravel this one, in large part because it
was so hard to reproduce: The memory map had to look *just so* to
trigger it. Once it was understood, though, we saw we would also
have been in alignment trouble on a less forgiving CPU (this one
was taking a slow hardware-assisted fixup on half our instances;
another might have tossed SIGBUS instead).

Once again: The cast is *not* safe. In the immortal words: "If
you lie to the compiler, it will get its revenge."

 

[Marco Devillers]

What about solving it like this:

struct t_base { int type };
struct t_int { int type; int value };
struct t_float { int type; float value };

And passing around *t_base values instead of union values? C99 should
guarantee that the records are layed out similarly (if I got that
section/comment right,) and you can now only 'widen' after you
established the type...

Cheers, Marco

 

[Seebs]

What about solving it like this:

struct t_base { int type };
struct t_int { int type; int value };
struct t_float { int type; float value };

And passing around *t_base values instead of union values? C99 should
guarantee that the records are layed out similarly (if I got that
section/comment right,) and you can now only 'widen' after you
established the type...

This can probably work, but still exposes you to the aliasing thing resulting
in not spotting an update to .type.

-s

 

[Seebs]

Hmpf, so does a trick with not allocating more than the size of a
specific member of the union work?

That's an interesting question.

I mean, the game is to have a variant type where each subtype
allocates a minimal number of bits (rounded of by a word size I
chose). Is there a solution?
Maybe!

According to C99, objects which share an initial prefix of common
types have similar memory layout, or am I mistaken? I.e., should I be
able to cast between s_int or s_double -below- and be sure that the
int type is shared? (I do it anyway in toy programs, but I never was
really sure if it worked because I assumed a naive compiler, or a
robust language feature.)

They have the same layout, but that doesn't mean they are compatible
types.

struct s_int { int type; int value; };
struct s_double { int type; double value; };

Here's the thing:

void foo(s_int *p1, s_double *p2) {
int x = p1->type;
p2->type = x + 3;
printf("%d %d\n", x, p1->type);
}
void bar(void) {
void *s1 = calloc(sizeof(struct s_double), 1);
foo(s1, s1);
}

If I haven't botched this in some amusing way, you can clearly see that
p1->type and p2->type are the same object, yes? However! The compiler
is welcome to print "0 0", because it *KNOWS* that p1 and p2 point to
objects which are of different types, therefore, it is *IMPOSSIBLE* that
p1 and p2 point to the same space.

It's not a question of memory layouts (and much thanks to the several
folks in clc who finally got this through my skull a couple of years back);
it's that the compiler is welcome to assume that there's no aliasing going
on.

-s

 

[Eric Sosman]

What about solving it like this:

struct t_base { int type };
struct t_int { int type; int value };
struct t_float { int type; float value };

And passing around *t_base values instead of union values? C99 should
guarantee that the records are layed out similarly (if I got that
section/comment right,) and you can now only 'widen' after you
established the type...

Yes, that's the way to do it. As Seebs points out there are
still aliasing issues, but in the anticipated use cases you won't
encounter them. Not unless you do something awful like

void coerce_to_float(struct t_base *ptr) {
switch (ptr->type) {
case INT:
// t_int and t_float are the same size, so
// I can just do this in place, mwa-ha-haa!
ptr->type = FLOAT;
((struct t_float*)ptr)->value =
((struct t_int*)ptr)->value;
break
...

.... in which case all I can say is that you're working very hard
to create trouble for yourself, and may eventually succeed.

By the way, you're not relying on the "similar layout" thing
here, not the one that's special-cased for unions of structs. You
depend on the "pointer to struct is convertible to/from pointer to
first member" guarantee, which applies to all structs whether in
unions or not. In this case it's the `type' field that's relevant;
if you need more goodies you need to put them in their own struct:

struct t_base {
int type;
short coercion_class;
short equivalence_domain;
};
struct t_int {
struct t_base base; // *not* three members!
int value;
};
struct t_float {
struct t_base base; // *not* three members!
float value;
};

This level of squeaky-cleanliness may seem obsessive, but
remember: RAM is getting slower every year (in comparison to CPU),
and compilers are getting more and more inventive about avoiding
RAM accesses in creative ways. Moderately dingy code that works
today may fail on the next compiler, or the next machine -- my tale
of woe happened on just one platform out of the seven our code ran
on at the time. Squeaky-clean is your defense against the future.

 

[Marco Devillers]

This can probably work, but still exposes you to the aliasing thing resulting
in not spotting an update to .type.

So it's the updates in combination with aliasing which could pose a
problem, I can see that. I'll see whether I can work out a scheme
where all types/RTTI are known compile time.

Great puzzle, thanks a lot for all answers and the hideous, but
glorious, prefetch bug.

Cheers, Marco

 

[BartC]

This level of squeaky-cleanliness may seem obsessive, but
remember: RAM is getting slower every year (in comparison to CPU),
and compilers are getting more and more inventive about avoiding
RAM accesses in creative ways. Moderately dingy code that works
today may fail on the next compiler, or the next machine -- my tale
of woe happened on just one platform out of the seven our code ran
on at the time. Squeaky-clean is your defense against the future.

But the product might be too slow to be successful (if you have to take a
completely different, and less efficient, approach just so you can give the
compiler a chance to optimise, and it might not even manage that).

 

[Marco Devillers]

But the product might be too slow to be successful (if you have to take a

completely different, and less efficient, approach just so you can give the
compiler a chance to optimise, and it might not even manage that).

The 'product' is more of a pet project I started once -might even be a
decade ago- to keep a bit in touch with programming and compiler
construction. It compiles to C, btw. I managed to give algorithms
roughly the speed of the previous generation of Javascript, or Lisp, -
good enough, that's an order faster than Python- but it handles
strings as very expensive lists of characters, which makes the
compiler very memory hungry and slow.

Moving in this direction won't make it a very fast language like C or
OCaml, but I'll be able to bit-pack representations better and move
towards handling texts natively, so it looks like a good choice.

Anyway, I got a bit fed up with small incremental changes, so breaking
that routine and just redeveloping the VM bottom-up feels like a good
idea too. I like hacking in C. ;-)

I would appreciate examples of languages which use this representation
though.

Cheers, Marco

 

[BartC]

Hmpf, so does a trick with not allocating more than the size of a
specific member of the union work?

I mean, the game is to have a variant type where each subtype
allocates a minimal number of bits (rounded of by a word size I
chose). Is there a solution?

How important is it to have the minimum number (of bytes usually rather than
bits)?

What is the largest variant size likely? If your primitives are only going
to be ints and doubles, it might simpler to have everything the same size
(for example it means everything might be 12 bytes, instead of 8 bytes for
ints and 12 for doubles).

This can avoid some of the issues mentioned.

(And I don't know how you do arrays, but if you want arrays with mixed
elements, it will help there as well. If array elements are homogeneous,
then they don't need to be tagged at all, then your variants would only be
used outside of arrays, so the size is less significant.)

 

[BartC]

Moving in this direction won't make it a very fast language like C or
OCaml, but I'll be able to bit-pack representations better and move
towards handling texts natively, so it looks like a good choice.

Anyway, I got a bit fed up with small incremental changes, so breaking
that routine and just redeveloping the VM bottom-up feels like a good
idea too. I like hacking in C. ;-)

I would appreciate examples of languages which use this representation
though.

I use a variant structure roughly equivalent to:

struct {
int16 tag;
int8 stuff;
int8 other stuff;

int32 value/ptr;
int32 value2/length;
}

The two value fields can be accessed together as 64-bits, in a way that C
doesn't like! So I don't use C for this.

Used in a VM with solely dynamic typing, it's about 5x as slow, on average,
as lcc-win32 (a C compiler not known for it's fast code so better to compare
with...). This is for integer benchmarks. For strings, it uses counted
strings so compares much better with C.

For an example of a language with minimal tag bits, look at Euphoria; it
identifies integers with just a single bit! Leaving 31 bits for value. And
this was also very fast, although I believe it's partly typed. This language
also implements strings as integer arrays, and it doesn't seem to affect the
speed much..

Have a look also at the implementation of Lua (not the JIT version), which
uses a union/struct scheme along the same lines as yours
(http://www.lua.org/doc/jucs05.pdf).

 

[Marco Devillers]

How important is it to have the minimum number (of bytes usually rather than
bits)?

Well, the current problem is that I allocate *cough* 15M chars. So,
apart from that I didn't do some of the algorithms very bright
*cough*, that works out to
15 M chars
32 bytes for a char,
48 bytes for a cons cell,
a factor 2 overhead for GC, gives...
2.4GB of character data and 15mins for a self-compile. See my
problem ;-).

Basically, for the bootstrap, I didn't think a lot about
representation issues and -without packing- thought of a scheme where
fields are put in 64 bits cells. 64 bits without packing really hurts,
it isn't a nice number for compiler generated data.

Anyway, I might get away with packing most in 64 or 128 bits. (And
represent strings as text.) Despite everything, I think I'll hold on
to the 64 bits cell size for the collector. Which is rather awful,
since it will probably mean I'll need 128 bits at least for a single
char assuming a 64 bit header and a 64 bit data field. Hmm...

What is the largest variant size likely? If your primitives are only going
to be ints and doubles, it might simpler to have everything the same size
(for example it means everything might be 12 bytes, instead of 8 bytes for
ints and 12 for doubles).

This can avoid some of the issues mentioned.

(And I don't know how you do arrays, but if you want arrays with mixed
elements, it will help there as well. If array elements are homogeneous,
then they don't need to be tagged at all, then your variants would only be
used outside of arrays, so the size is less significant.)

For values, I want to support all primitive C types, user defined
record types with RTTI (field descriptor tag + type name tag + pointer
to values), and arrays of pointers to values. Where it might pay off
to conflate the last two for specific semantic voodoo.

Cheers, Marco

 

[Marco Devillers]

For an example of a language with minimal tag bits, look at Euphoria; it

identifies integers with just a single bit! Leaving 31 bits for value. And
this was also very fast, although I believe it's partly typed. This language
also implements strings as integer arrays, and it doesn't seem to affect the
speed much..

I partly know the OCaml runtime since it has be reproduced in so many
products. Tagged ints was one of the things I want to avoid since I
don't want to sacrifice too much C interoperability. (Along with the
mess the OCaml runtime has become.)

Ah well, can't say I fared better.

Cheers, Marco

 

[Eric Sosman]

But the product might be too slow to be successful (if you have to take
a completely different, and less efficient, approach just so you can
give the compiler a chance to optimise, and it might not even manage that).

A fan of "get the wrong answer quickly," are you?

Besides, in my experience an optimizer will do *at least* as well
with a cleanly-described program as with one that cuts corners. The
classic (and all-too-frequent) example is of the big program that is
mostly compiled with maximum optimization except for half a dozen
modules that the optimizer "gets wrong." Care go guess which side
the "wrong" is usually on?

 

[BartC]

A fan of "get the wrong answer quickly," are you?

No, more "get the right answer quickly". My suggestion would be to turn off
that particular optimisation, or do some combination of that and use
somewhat different implementations for each platform.

And language products such as VMs are special anyway; slightly different
rules apply. Most of the portability and code safety is part of the language
being implemented; and it's worth making a tweak, or doing something a bit
hairy, in the VM, as a thousand applications will then benefit, not just the
one.