Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #14696 > unrolled thread

Small Variant Records in C

Back to article view | Back to comp.lang.c

Contents

  Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 10:16 -0800
    Re: Small Variant Records in C Seebs <usenet-nospam@seebs.net> - 2011-12-18 18:50 +0000
      Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-18 15:00 -0500
        Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 12:23 -0800
          Re: Small Variant Records in C Seebs <usenet-nospam@seebs.net> - 2011-12-18 21:15 +0000
            Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 14:13 -0800
              Re: Small Variant Records in C Seebs <usenet-nospam@seebs.net> - 2011-12-19 00:26 +0000
              Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 02:25 +0000
                Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 19:08 -0800
                  Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 17:24 +0000
                    Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-19 11:43 -0800
                      Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-19 15:21 -0500
                        Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-19 13:38 -0800
                          Re: Small Variant Records in C James Kuyper <jameskuyper@verizon.net> - 2011-12-19 16:48 -0500
                          Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-19 17:19 -0500
                            Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-19 15:14 -0800
                      Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 21:44 +0000
                        Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-19 14:02 -0800
                  Re: Small Variant Records in C Kaz Kylheku <kaz@kylheku.com> - 2011-12-19 18:38 +0000
                Re: Small Variant Records in C jgk@panix.com (Joe keane) - 2012-01-04 03:52 +0000
                  Re: Small Variant Records in C Ian Collins <ian-news@hotmail.com> - 2012-01-04 20:25 +1300
            Re: Small Variant Records in C Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 15:53 -0800
          Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-18 18:35 -0500
            Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 16:01 -0800
              Re: Small Variant Records in C Seebs <usenet-nospam@seebs.net> - 2011-12-19 00:26 +0000
                Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 17:02 -0800
              Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-18 19:53 -0500
                Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 01:36 +0000
                  Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 18:21 -0800
                    Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 02:52 +0000
                      Re: Small Variant Records in C Marco Devillers <marco.devillers@gmail.com> - 2011-12-18 19:17 -0800
                  Re: Small Variant Records in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-19 09:24 -0500
                    Re: Small Variant Records in C "BartC" <bc@freeuk.com> - 2011-12-19 17:18 +0000

Page 2 of 2 — ← Prev page 1 [2]

#15398

On 01/ 4/12 04:52 PM, Joe keane wrote:
> In article<jcm7d3$e0s$1@dont-email.me>, BartC<bc@freeuk.com>  wrote:
>> How important is it to have the minimum number (of bytes usually rather than
>> bits)?
>
> supposing that you *know* the subclasses
>
> e.g.

<snip hybrid language>

> then it may be useful

Unless you are writing C!

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#16242

Seebs <usenet-nospam@seebs.net> writes:

> On 2011-12-18, Marco Devillers <marco.devillers@gmail.com> wrote:
>>
>>> ? ? ? ? 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.
>
> 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.

I believe the Standard expects otherwise.  That's why 6.5.2.3 p5
(and now p6) gives the requirement that "a declaration of the
completed type is visible" at the point of access.  If the union
type had to be used to access the contained struct's there would be
no reason to include such a statement.  Indeed, that's what makes
this "a special guarantee" at some level - because accesses to
struct's _not_ through a union must be understood to potentially
alias each other, being as they are both present in the same union
type.

[toc] | [prev] | [next] | [standalone]

#14710

On 12/18/2011 3:23 PM, Marco Devillers wrote:
> > [...]
>> 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."

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#14711

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

[toc] | [prev] | [next] | [standalone]

#14712

On 2011-12-19, Marco Devillers <marco.devillers@gmail.com> wrote:
>
> 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
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

[toc] | [prev] | [next] | [standalone]

#14716

> 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

[toc] | [prev] | [next] | [standalone]

#14714

On 12/18/2011 7:01 PM, Marco Devillers wrote:
>
> 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.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#14719

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message 
news:jcm1v5$mfa$1@dont-email.me...


>     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).

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#14723

> 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

[toc] | [prev] | [next] | [standalone]

#14727

"Marco Devillers" <marco.devillers@gmail.com> wrote in message
news:4574386b-4d90-4548-911c-a5e372aae2f6@n39g2000yqh.googlegroups.com...
>> 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).

> 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).

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#14733

> 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

[toc] | [prev] | [next] | [standalone]

#14754

On 12/18/2011 8:36 PM, BartC wrote:
> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
> news:jcm1v5$mfa$1@dont-email.me...
>
>
>> 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).

     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?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#14757

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
news:jcnhev$ff5$1@dont-email.me...
> On 12/18/2011 8:36 PM, BartC wrote:
>> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
>> news:jcm1v5$mfa$1@dont-email.me...
>>
>>
>>> 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).
>
>     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.

-- 
Bartc 

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web