Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!uwvax!sevenlayer.cs.wisc.edu!bothner
From: bothner@sevenlayer.cs.wisc.edu (Per Bothner)
Newsgroups: comp.std.c++
Subject: Re: A Proposal to Extend C++ with Variable-length Arrays
Message-ID: <11629@spool.cs.wisc.edu>
Date: 4 Nov 90 21:59:05 GMT
References: <11578@spool.cs.wisc.edu> <17109@thorin.cs.unc.edu>
Sender: news@spool.cs.wisc.edu
Reply-To: bothner@sevenlayer.cs.wisc.edu (Per Bothner)
Organization: University of Wisconsin--Madison
Lines: 50

In article <17109@thorin.cs.unc.edu>, leech@degas.cs.unc.edu (Jonathan Leech) writes:
>	But your proposal needs extra space for the array length,
>so it's a wash in this respect.  

The program *must* know the length of the array;
otherwise the array is useless. If the array is variable-length,
the program usually keeps this length in a variable.

In addition, the ARM (p. 64-65) mandates that the array length of
a (non-embedded, heap-allocated) array be squirelled away somewhere.

So using an embedded array typically saves *two* "words:"
one for the no-longer-needed pointer, and one for the
no-longer-needed squirelled-away length.

There also the extra space overhead inside the memory
allocator that may depend on how it is implemented and
alignment restrictions.
Consider the case of a binary buddy system (rounds
up to nearest power of two), and len==6:

	struct String : public Object {
	    const int len;
	    char c[len];
	    String(int l) : len(l) { }
	};
	String *s = new String(6);
The size of s is 4 (vtable) + 4 (len) + 6 (c), i.e. 16 bytes.

The alternative:
	struct String : public Object {
	    const int len;
	    char *c;
	    String(int l) : len(l) { c = new char[l]; }
	}
	String *s = new String(6);
The s structure takes 3 words (with vtable), i.e. 16 bytes.
The c string takes 6 bytes plus a 4-byte-length, i.e. 16 bytes.
Total: 32 bytes, i.e. double.

If no hidden count is allocated for s->c (since the compiler
knows that char's destructor is empty), it still takes 24 bytes.

The example is admittedly atypical, but it illustrates the overheads.
(It is possible that the embedded implementation may take more room,
if the string is just the "wrong" size such that the fixed fields
ush it just beyond a power of two. This is statistically unlikely.)
-- 
	--Per Bothner
bothner@cs.wisc.edu Computer Sciences Dept, U. of Wisconsin-Madison