On Thu, Mar 08, 2012 at 09:13:13PM -0800, H. S. Teoh wrote:
> So, I'm plodding along with my AA implementation that *hopefully* will eventually reach the point where it's usable enough to be dropped into druntime. I'm writing .keys and .values right now, and wondering what's the best way to construct the returned array.
> 
> Obviously, using =~ repeatedly is a bad idea, since we already know the resulting array size. Would this be the best way to do it?
> 
> 	Key[] keys;
> 	keys.length = num_keys;
> 	for (size_t i=0; i < num_keys; i++) {
> 		keys[i] = ...;
> 	}
> 
> Looking at aaA.d, I see that _aaKeys calls gc_malloc directly and sets BlkAttr.NO_SCAN.  Should I just copy this code?
[...]

Another problem: if Key is a const/immutable type, then keys[i] is immutable, so the keys can't be copied into the resulting array. I tried inout but it doesn't seem to be good enough, because individual array elements need to be assigned to, which violates const/immutable, even though we're really just copying const/immutable data here.


T

-- 
He who sacrifices functionality for ease of use, loses both and deserves neither. -- Slashdotter

On Thursday, March 08, 2012 22:05:57 H. S. Teoh wrote:
> On Thu, Mar 08, 2012 at 09:13:13PM -0800, H. S. Teoh wrote:
> > So, I'm plodding along with my AA implementation that *hopefully* will eventually reach the point where it's usable enough to be dropped into druntime. I'm writing .keys and .values right now, and wondering what's the best way to construct the returned array.
> > 
> > Obviously, using =~ repeatedly is a bad idea, since we already know the resulting array size. Would this be the best way to do it?
> > 
> > 	Key[] keys;
> > 	keys.length = num_keys;
> > 	for (size_t i=0; i < num_keys; i++) {
> > 
> > 		keys[i] = ...;
> > 
> > 	}
> > 
> > Looking at aaA.d, I see that _aaKeys calls gc_malloc directly and sets BlkAttr.NO_SCAN.  Should I just copy this code?
> 
> [...]
> 
> Another problem: if Key is a const/immutable type, then keys[i] is immutable, so the keys can't be copied into the resulting array. I tried inout but it doesn't seem to be good enough, because individual array elements need to be assigned to, which violates const/immutable, even though we're really just copying const/immutable data here.

I see two options. Allocate the entire array, set the length to 0, and use assumeSafeAppend (or maybe the function that it uses, since assumeSafeAppend is in _object.d) so that appending doesn't cause reallocations, or create the array as mutable and then cast it to the appropriate type.

1.

auto keys = new Key[](num_keys);
keys.length = 0;
assumeSafeAppend(keys);
for(i; 0 .. num_keys)
    keys ~= ...;

2.

auto keys = new (Unqual!Key)[](num_keys);
foreach(ref key; keys)
    key = ...;

auto actualKeys = cast(Key[])keys;

Now, you couldn't use Unqual, since that's in Phobos, but you could copy it from Phobos and have a version internal to the AA stuff in druntime. However, the first choice is probably better, since it doesn't require any casting.

- Jonathan M Davis

Isn't this just as good?

Key[] keys;
keys.reserve(num_keys)
foreach (key; keys_in_aa)
   keys ~= key;

On Fri, 09 Mar 2012 01:59:34 -0500, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday, March 08, 2012 22:05:57 H. S. Teoh wrote:
>> On Thu, Mar 08, 2012 at 09:13:13PM -0800, H. S. Teoh wrote:
>> > So, I'm plodding along with my AA implementation that *hopefully* will
>> > eventually reach the point where it's usable enough to be dropped into
>> > druntime. I'm writing .keys and .values right now, and wondering  
>> what's
>> > the best way to construct the returned array.
>> >
>> > Obviously, using =~ repeatedly is a bad idea, since we already know
>> > the resulting array size. Would this be the best way to do it?
>> >
>> > 	Key[] keys;
>> > 	keys.length = num_keys;
>> > 	for (size_t i=0; i < num_keys; i++) {
>> > 	
>> > 		keys[i] = ...;
>> > 	
>> > 	}
>> >
>> > Looking at aaA.d, I see that _aaKeys calls gc_malloc directly and sets
>> > BlkAttr.NO_SCAN.  Should I just copy this code?
>>
>> [...]
>>
>> Another problem: if Key is a const/immutable type, then keys[i] is
>> immutable, so the keys can't be copied into the resulting array. I tried
>> inout but it doesn't seem to be good enough, because individual array
>> elements need to be assigned to, which violates const/immutable, even
>> though we're really just copying const/immutable data here.
>
> I see two options. Allocate the entire array, set the length to 0, and use
> assumeSafeAppend (or maybe the function that it uses, since assumeSafeAppend
> is in _object.d) so that appending doesn't cause reallocations, or create the
> array as mutable and then cast it to the appropriate type.
>
> 1.
>
> auto keys = new Key[](num_keys);
> keys.length = 0;
> assumeSafeAppend(keys);
> for(i; 0 .. num_keys)
>     keys ~= ...;
>
> 2.
>
> auto keys = new (Unqual!Key)[](num_keys);
> foreach(ref key; keys)
>     key = ...;
>
> auto actualKeys = cast(Key[])keys;

Use the second method.  This is low-level runtime code, it should be as fast as possible.  Casting is OK as long as it's justified.

-Steve