Are AAs broken? (Was: Why isn't bool allowed as AA key type?)

Timon Gehr timon.gehr at gmx.ch
Thu Jun 2 04:53:39 PDT 2011


Steven Schveighoffer wrote:
> That is not a removal:

So, destroying the container does not free it's elements, but removing one element
does free it?

>
> int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5];
> auto ret = 1 in aa;
> aa.remove(1);
> return ret; // ret now points to free'd memory

Weeh! It's a dangling pointer built right into the language =)! Is the memory
really free'd?

Because:

import std.stdio,core.memory;

int *test(){
    int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5];
    int* ret=1 in aa;
    aa.remove(1);//int* tmp=ret;clear(tmp);//replace line with this to get
segfault in main
    return ret;
}

void main(){
    int *u=test();
    assert(*u==1);
}

I do not get what is happening here, can you help?

>
> Your equivalent code using dcollections' custom allocator would work too,
> the GC backs up the custom allocator.

That implies that dcollections' hash map performs poorly in real-time constrained
environments too, right?

>
>>>
>>> BTW, dcollections' custom allocator does use the GC, it just uses it in
>>> bulk instead of allocating for each node.
>>>
>>> -Steve
>>
>> If AAs would do that, the whole bulk could be pinned by one pointer to
>> one element
>> inside it, which is still not optimal.
>
> No, but this is a compromise -- better performance vs. smaller footprint.
> It would be nice if the GC just performed better.

I agree. But GC runtime has to be at least linear in number of alive and garbage
objects. It is inherently quite slow.

>
>> Returning internal pointers into a data
>> structure is always a bad idea (assuming it must be safe).
>
> Then ranges on a container are not possible (a range contains a pointer to
> the next element).  Ranges can be invalidated using a "modification"
> count, but this removes some valid uses, and it also costs quite a bit
> (extra int to store range's copy of count, extra check on every range
> function to ensure counts are synchronized, possible extra pointer to
> store in range to point at owner container).
>
> -Steve

Well, it is possible unless you want to represent those ranges as pairs of raw
pointers.
Raw pointers have not enough type information to be useful as range
representation. Even if your ranges can get invalidated, I would not pick a raw
pointer as representation.
C++ iterators do not leak any pointers to the internal representation of the data
structure to the user afaik. &a[123] does on a std::vector, but Ds operator
overloading explicitly allows to prevent this. Therefore there _must_ be some
merit to the idea.

Aren't 'in' expressions returning pointers just a hack to prevent multiple lookups
of the same data? I do not think this optimization is worth all the GC overhead
(and dangling pointer issues?).


Timon


More information about the Digitalmars-d mailing list