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

Groups > comp.lang.c > #14759

Re: Small Variant Records in C

Show all headers | View raw

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.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web