Allocate N elements

[monarch_dodra]

On Monday, 15 July 2013 at 17:39:43 UTC, H. S. Teoh wrote:
> On Mon, Jul 15, 2013 at 07:32:37PM +0200, monarch_dodra wrote:
>> On Monday, 15 July 2013 at 15:54:57 UTC, bearophile wrote:
>> >monarch_dodra:
>> >
>> >>>But that (of new arrays) is a bad design, it wastes too much
>> >>>memory, and I think it should be fixed. In Python this 
>> >>>doesn't
>> >>>overallocate:
>> >>
>> >>So what? The only thing you showed, is that 
>> >>minimallyInitialized
>> >>doesn't know how much it allocated. If you allocate 513 
>> >>elements
>> >>with malloc, you'll way over allocate too. What's your point?
>> >>You'll waste memory either way.
>> >
>> >I didn't know it, sorry. I forgot.
>> >Can we let minimallyInitializedArray know the capacity?
>> 
>> I'm working on it ;)
>> 
>> >Regarding the small arrays, so to avoid the memory wasting you
>> >need to allocate a larger one and slice it.
>> >
>> >Bye,
>> >bearophile
>> 
>> One of the problems is that when you want an arbitrarily sized
>> allocation, it is usually standard to allocate 2^N in size. 
>> While
>> this is optimal for "traditional" malloc, it's actually the 
>> *worst*
>> allocation size you could ask for a GC array with appendable 
>> info
>> (eg, traditional new) :/
>
> This is wrong. The 2^N size should be applied *after* GC 
> appendable info
> (or whatever else bookkeeping info you need) has been accounted 
> for, not
> before. If the GC header/whatever requires, say, 16 bytes, then 
> the
> ideal array size should be 2^N-16, so that everything fits 
> neatly within
> a power of 2. Otherwise you end up with 2^N+16 bytes that are 
> actually
> allocated, and it just goes downhill from there.
>
>
> T

Just to be clear, the GC itself has no overhead. Only the 
APPENDABLE bookkeeping does any overhead.
EG: GC.malloc(1024);
This will allocate a 1024 byte block. No problem here.

HOWEVER, if you write:
int[] arr = new int[](1000); //Allocates a  4Ki block
int[] arr = new int[](1024); //Allocates an 8Ki block
The example is a bit extreme, but you should get what I mean.

If you do a malloc with GC.BlkAttr.APPENDABLE, you will also get 
exactly what you asked for. However, it will be the user's 
responsibility to take into account that some of those allocated 
bytes will not actually be useable (the APPENDABLE block).

FYI, the way APPEDNABLE works:
Arrays 1-255 bytes: 1 extra byte will be appended for used 
capacity info at the end of the array.
Arrays 256-2046: 2 extra bytes will be appended.
2047+: The array will *start* with a 16 byte block for appendable 
info. A dummy 1 byte block will also be appended to the end of 
the block, for "arr[$ .. $]". (So yes, you need to accound for a 
*17* byte overhead)

That said, allocating an array using a straight up 
malloc(APPEDNABLE) is *very* complicated, and it is all very 
specific to the current GC anyways: It is very very error prone, 
and non portable.