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 1 of 2  [1] 2  Next page →

#14696 — Small Variant Records in C

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

[toc] | [next] | [standalone]

#14700

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

#14702

On 12/18/2011 1:50 PM, Seebs wrote:
> On 2011-12-18, Marco Devillers<marco.devillers@gmail.com>  wrote:
>> 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.

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

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

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

#14704

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

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

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

#14707

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.

-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]

#14708

> 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

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

#14713

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

#14724

"Marco Devillers" <marco.devillers@gmail.com> wrote in message 
news:b31838b4-399d-452e-9531-9fa92b5d09db@m10g2000vbc.googlegroups.com...
>
>> 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?

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 

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

#14730

On Dec 19, 3:25 am, "BartC" <b...@freeuk.com> wrote:
> "Marco Devillers" <marco.devill...@gmail.com> wrote in message
> > 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)?

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

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

#14758

"Marco Devillers" <marco.devillers@gmail.com> wrote in message
news:fb727845-65e8-48a2-8cc9-a44d0c2d6f05@z12g2000yqm.googlegroups.com...
> On Dec 19, 3:25 am, "BartC" <b...@freeuk.com> wrote:
>> "Marco Devillers" <marco.devill...@gmail.com> wrote in message
>> > 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)?
>
> 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,

OK, I'll ask the obvious question: what's in the other 31 (or 28) bytes of 
the memory used by a single char?

-- 
Bartc 

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

#14761

> OK, I'll ask the obvious question: what's in the other 31 (or 28) bytes of
> the memory used by a single char?

By memory: A tag stating it's an opaque series of bits (a 0), the size
of the series of bits, the record and the type info (it's a char), the
value of the char. Each field aligned at 64 bits/8 bytes, four fields,
so 32 bytes.

It's a wasteful scheme, I knew that. But at a given point I was only
interested in a bootstrap, didn't give it a lot of thought, and ended
up at least two orders above of the imagined memory consumption. Guess
I should have done the numbers before.

Thing is, I am not even sure I want to go all the way of extreme bit
manipulation to end up with, say, 16 bit char representations. So the
thing takes a lot of waste, so do Java/Python chars. And in this case,
the real problem -given memory in abundance- is that I do too much low-
level stuff in what is supposed to be a high-level language. I rather
aim at a slow/robust high-level language al la Python with good
bindings to C, than aim at a high-level language with low-level
features which will never achieve C speed anyway.

We live and learn, cheers, Marco

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

#14762

On 12/19/2011 2:43 PM, Marco Devillers wrote:
>> OK, I'll ask the obvious question: what's in the other 31 (or 28) bytes of
>> the memory used by a single char?
>
> By memory: A tag stating it's an opaque series of bits (a 0), the size
> of the series of bits, the record and the type info (it's a char), the
> value of the char. Each field aligned at 64 bits/8 bytes, four fields,
> so 32 bytes.

     Guggh.  You don't need to "optimize" by playing games with type
punning structures; you need to re-think your representation.

> [...] And in this case,
> the real problem -given memory in abundance- [...]

     Can you octuple your cache when you octuple your memory use?

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

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

#14768

>      Can you octuple your cache when you octuple your memory use?

    Come again? I hope I can 'octuple' a lot of things if I know what
it means.

    I guess you are referring to the above wasteful scheme? I know I
need to design something which aims at the current hybrid of 32bit/
64bit processor models such that I can hopefully get away with packing
RTTI information into 32 or 64 bits headers instead of representing
each field with 64 bits. And that also supposes some understanding of
how, say, on Intel x64, C instructions and data representations are
usually compiled to specific data and microinstructions and the
resulting memory/cache behavior of programs, instead of the logically
correct but not very world aware representation I have now.

   My current thoughts are that I estimate I need something with a
cell size which is either a multiple of 32 or 64, I currently have no
idea of how either choice affects runtime behavior on Intel x64, and I
think I need a VM which is designed as a minimal series of convenience
macros so I can easily compile to that. And then note that to me the
biggest problem is not the representation, but the compiler which
doesn't use texts but uses lists of chars, as well as some other poor
choices I made internally.

   If you have specific thoughts on 64 bit VMs, please state them!

Ah well, cheers, Marco

PS. Note that this is just a project I once started to learn some
stuff and implement some new and funny ideas given what I read. It is
in no means a production compiler or a research project. Consequently,
some design choices I made are goofy and nice, some are plain horrible.

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

#14769

On 12/19/2011 04:38 PM, Marco Devillers wrote:
>>      Can you octuple your cache when you octuple your memory use?
> 
>     Come again? I hope I can 'octuple' a lot of things if I know what
> it means.

Multiply by 8.

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

#14774

On 12/19/2011 4:38 PM, Marco Devillers wrote:
>>       Can you octuple your cache when you octuple your memory use?
>
>      Come again? I hope I can 'octuple' a lot of things if I know what
> it means.

     Double = times two, triple (treble) = times three, ...
octuple = times eight.  My point being that it is often possible
to add RAM to a system, up to some limit, but less frequently
possible to expand a system's caches.  The lowest-level cache can
sometimes be grown (if so, usually by doubling, once), but higher-
level caches almost never.  The only way to grow the on-chip cache
is to get a new CPU chip.

>      I guess you are referring to the above wasteful scheme?

     Yes.

> I know I
> need to design something which aims at the current hybrid of 32bit/
> 64bit processor models such that I can hopefully get away with packing
> RTTI information into 32 or 64 bits headers instead of representing
> each field with 64 bits. And that also supposes some understanding of
> how, say, on Intel x64, C instructions and data representations are
> usually compiled to specific data and microinstructions and the
> resulting memory/cache behavior of programs, instead of the logically
> correct but not very world aware representation I have now.

     No.  Forgive the mixed metaphor, but you've gone down into the
weeds before taking the fifty-thousand-foot view.  At this stage you
do *not* need to aim at any particular family of processors, you do
*not* need to pay heed to instruction sets, you do *not* need to think
about microinstructions or pipeline architecture or any such matters.
And the only thing you need to know about memory and caches (again,
at this stage) is that memory is slow and cache is limited.  This
means that bloat has a speed penalty, sometimes a dramatic penalty.
It's not worth while to save 1K out of a data structure with six
instances, but it probably *is* worth while to save 8B out of a data
structure you will create by the hundreds of thousands.

     More mixed metaphors: You're driving a car that hasn't been tuned
since the Clinton administration, on under-inflated tires, with an empty
boat trailer dragging behind, and you're fond of jackrabbit starts.
Your fuel economy, of course, is dismal -- and it absolutely does not
matter one tiny little bit what brand of motor oil you use.  Cure your
bad driving habits, unhitch the trailer, pump up the tires, give the
jalopy some maintenance, and *then* you can start thinking about
which oils are slipperier under what conditions.

     Tricks of the kinds Kaz mentions are the super-fancy motor oil,
to be used after you've already wrung the utmost out of "normal"
methods and find you still need more zip.  They will not solve your
problem with the eight sacks of concrete mix in your trunk.

> PS. Note that this is just a project I once started to learn some
> stuff and implement some new and funny ideas given what I read. It is
> in no means a production compiler or a research project. Consequently,
> some design choices I made are goofy and nice, some are plain horrible.

     There's nothing wrong with learning by exploration; in fact, it's
got a lot to recommend it.  But this doesn't mean you should ignore
good sense altogether!

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

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

#14777

>      There's nothing wrong with learning by exploration; in fact, it's
> got a lot to recommend it.  But this doesn't mean you should ignore
> good sense altogether!

Good sense arrives after a bootstrap! Anyway, we got a bit too much
sidetracked.

Thanks for the help, cya'll later, Marco

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

#14767

"Marco Devillers" <marco.devillers@gmail.com> wrote in message 
news:f74b6815-7230-41a7-9c7f-78b342138c64@l29g2000yqf.googlegroups.com...
>> OK, I'll ask the obvious question: what's in the other 31 (or 28) bytes 
>> of
>> the memory used by a single char?
>
> By memory: A tag stating it's an opaque series of bits (a 0), the size
> of the series of bits, the record and the type info (it's a char), the
> value of the char. Each field aligned at 64 bits/8 bytes, four fields,
> so 32 bytes.
>
> It's a wasteful scheme, I knew that. But at a given point I was only
> interested in a bootstrap, didn't give it a lot of thought, and ended
> up at least two orders above of the imagined memory consumption. Guess
> I should have done the numbers before.

So you have an array of 15 million characters, but each one is stored inside 
a variant type.

That's always going to be wasteful: 32 bytes each here, 12 bytes if I did 
the same, unless you use a fiddly representation that uses spare bits. This 
is where a packed array should be considered, then each element can be 1, 2 
or 4 bytes depending on how much you need unicode.

But if this array represents a string, then definitely implement those 
first.

(I'm assuming your 15 million characters *are* together in a collection, but 
you also mention C code being generated that takes 15 minutes to compile. 
I'm not sure how that would come about, unless you represent your 
15-million-element data by initialising such an array of variants as 15 
million lines of C! That shouldn't be necessary, unless each element has a 
different initial value.)

-- 
Bartc 

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

#14772

> So you have an array of 15 million characters, but each one is stored inside
> a variant type.

Nope, I have a total of 15 million character data, distributed over a
few thousand lists of chars, which is probably the result of
flattening the names in namespaces. I.e., a function foo in namespace
bar becomes a non-unique list ['b','a','r','.','f','o',o']. So it's
more a problem of the compiler than of the representation - I need
native texts. If you would do the same in Haskell, you'ld end up with
a similar wasteful memory consumption. It's just exacerbated by the
current representation scheme too, so I want a bit more bitpacking and
native string support in the VM.

The 15 mins is the result of all those list operations implemented
directly in my language, instead of calling C, and the memory hog.
I.e., everything scales worse than linear, and probably exponential,
with the string operations. (Most list operations are at least linear
in the length of the list, and performance also degrades linear with
memory consumption in GCed languages. And I am not sure I should add,
or multiply, all these costs at the moment.)

As I said, it won't compile in 5 secs if I implement native texts, but
it will become more bearable than 15 mins. (I am hoping for something
around 45 secs at the moment.)

Cheers, Marco

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

#14759

On 2011-12-19, Marco Devillers <marco.devillers@gmail.com> wrote:
> On Dec 19, 3:25 am, "BartC" <b...@freeuk.com> wrote:
>> "Marco Devillers" <marco.devill...@gmail.com> wrote in message
>> > 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)?
>
> 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 ;-).

Stop heap-allocating types like characters and small numbers that
can fit into a machine word with a couple of tag bits to spare.
Your garbage collector should just be able to recognize a character
value and skip it.

In TXR, I used two bits to distinguish a pointer to a heap descriptor from
several other cases: fixnum integer, character and a static/ephemeral C string.

So on a system with 32 bit pointers, a character is 32 bits wide, and not heap
allocated. Since a wchar_t is often 32 bits wide also, there is no waste for
characters. (And a 16 bit wchar_t is broken anyway because it doesn't properly
cover all of Unicode.)   For strings, I used arrays of wchar_t,
null-terminated, so strings interoperate smoothly with C interfaces.

Heap objects have descriptors that are all the same size: four pointers wide.
This is because the type is a union of various structures (union obj).
The same size simplifies the garbage collector which allocates heaps
as arrays of this type.

Most types make full use of the descriptor, and in some cases I used bitfields
to make sure that this four pointer limit is not exceeded. (For instance, for
bignums, I used the MPI library which wanted to use an entire int to encode the
sign of a number!) The cons cell wastes a field since it has only three
fields. But even on a 64 bit system, it still fits into 32 bytes (8 * 4),
less than your 48. On a 32 bit system, it's down to 16.

Since the tag for a heap pointer is the bits 00, values that are pointers
don't have to be masked in any way to be used. If a check shows that a
value is a (non-null) pointer, you can dereference it directly to access the
structure (since the type "val" is a typedef for "obj_t *". The object nil
gets to be represented by a C null pointer, which helps to program in
a Lispy style:

 val func(val list) {
   if (list) { /* list is not empty */ }
 }

I wrote up some notes here: http://www.kylheku.com/cgit/txr/tree/HACKING

It may be worthwhile to look into some implementations of dynamic languages
to see what they do.  Corman Lisp's documentation nicely describes how types
are represented; it's worth havin a look. IIRC it uses a three-bit field.

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

#15396

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.

class Foo
{
    int foo_common;
}

class RedFoo : Foo
{
    char redbit;
}

class GreenFoo : Foo
{
    double greenvalue;
}

struct bluefooextra { ... };

class BlueFoo : Foo
{
    struct bluefooextra *blueextra;
}

[and there aren't any purple or oranges foos]

class AllFoos
{
    union {struct RedFoo af_r; struct GreenFoo af_g; struct BlueFoo af_b;} y;
}

typedef class AllFoos *CanHoldAnyFoo;

int f(...)
{
    ...
    CanHoldAnyFoo x;

    x = malloc(len * sizeof(AllFoos));
    if (x = NULL)
	do_something();
    ...
}

then it may be useful

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web