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.
