www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - AA invalidating pointers and references..?

reply simendsjo <simen.endsjo pandavre.com> writes:
unittest
{
	auto a = [1:2];
	auto p = 1 in a;
	// can p be invalidated by rehashing?
	// That is pointing to a different item or a memory location used for 
other things?

	auto b = a.rehash;
	
	// The spec also says it orders in place, but returns the reorganized 
array...
	// Is the spec right? That it rehashes in place and returns a reference to
	// itself?
	assert(a is b);
}

unittest
{
	auto a = [1:2];
	auto p = 1 in a;
	a.remove(1);
	// the memory for p can be reassigned by the gc,
	// so this is undefined behavior.. right?
	assert(*p == 2);
}
Aug 08 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
simendsjo:


 	auto a = [1:2];
 	auto p = 1 in a;
 	// can p be invalidated by rehashing?


Yes, I presume it can. p is meant for immediate consumption only.



 	// The spec also says it orders in place, but returns the reorganized 
 array...
 	// Is the spec right? That it rehashes in place and returns a reference to
 	// itself?
 	assert(a is b);


Yes, a and b are meant to be equal, because they are a reference, that doesn't
change. What changes is the data structures referenced by it (if what I have
just said turns out to be wrong, then probably it's an implementation bug that
needs to be added to bugzilla).



 	auto a = [1:2];
 	auto p = 1 in a;
 	a.remove(1);
 	// the memory for p can be reassigned by the gc,
 	// so this is undefined behavior.. right?


Right, such things show that it's probably better to change the D AA design
here:
1) make "x in AA" return a bool
2) improve dmd so it is able to remove most cases of dual lookups in AAs.

I will think if this needs to become an enhancement request.

Bye,
bearophile
Aug 08 2010
parent reply simendsjo <simen.endsjo pandavre.com> writes:
On 08.08.2010 17:51, bearophile wrote:

 simendsjo:


 	auto a = [1:2];
 	auto p = 1 in a;
 	// can p be invalidated by rehashing?


 Yes, I presume it can. p is meant for immediate consumption only.



 	// The spec also says it orders in place, but returns the reorganized
 array...
 	// Is the spec right? That it rehashes in place and returns a reference to
 	// itself?
 	assert(a is b);


 Yes, a and b are meant to be equal, because they are a reference, that doesn't
change. What changes is the data structures referenced by it (if what I have
just said turns out to be wrong, then probably it's an implementation bug that
needs to be added to bugzilla).


Ok, thanks.


 	auto a = [1:2];
 	auto p = 1 in a;
 	a.remove(1);
 	// the memory for p can be reassigned by the gc,
 	// so this is undefined behavior.. right?


 Right, such things show that it's probably better to change the D AA design
here:
 1) make "x in AA" return a bool
 2) improve dmd so it is able to remove most cases of dual lookups in AAs.

 I will think if this needs to become an enhancement request.


1)
I haven't worked much with AA's, but I find the "key in aa returns a 
reference to the value" to be handy. I think it's better than the following:

int value;
if( 1 in a )
   value = a[1];

or a[1] in a try/catch or other implementations.

2) I don't know what you mean. Does a single lookup often involve 
several under the hood?
Aug 08 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
simendsjo:


 I haven't worked much with AA's, but I find the "key in aa returns a 
 reference to the value" to be handy. I think it's better than the following:
 
 int value;
 if( 1 in a )
    value = a[1];
 
 or a[1] in a try/catch or other implementations.


Your examples have shown me that probably the current design can't be made
safe, and you can't use in SafeD code.
But performing "x in AA" is a very useful operation that I want to perform in
SafeD code.

And in my opinion this code:

int value;
auto ptr = 1 in a;
if (ptr)
    value = *ptr;


Doesn't look better than:

int value;
if (1 in a)
    value = a[1];



 2) I don't know what you mean. Does a single lookup often involve 
 several under the hood?


If your compiler is naive then code like this:
if (1 in a)
    value = a[1];
requires to perform two searches inside the hash, the first to tell if the key
is present, and the second to find it again and fetch its value.

A bit better compiler (LDC is already able to do this) can recognize that you
are performing two nearby key searches with the same key, and it can remove the
second one, essentially replacing that code with this one:

int value;
auto ptr = 1 in a;
if (ptr)
    value = *ptr;

Bye,
bearophile
Aug 08 2010
parent simendsjo <simen.endsjo pandavre.com> writes:
bearophile wrote:

 simendsjo:
 

 I haven't worked much with AA's, but I find the "key in aa returns a 
 reference to the value" to be handy. I think it's better than the following:

 int value;
 if( 1 in a )
    value = a[1];

 or a[1] in a try/catch or other implementations.


 
 Your examples have shown me that probably the current design can't be made
safe, and you can't use in SafeD code.
 But performing "x in AA" is a very useful operation that I want to perform in
SafeD code.
 
 And in my opinion this code:
 
 int value;
 auto ptr = 1 in a;
 if (ptr)
     value = *ptr;
 
 
 Doesn't look better than:
 
 int value;
 if (1 in a)
     value = a[1];
 
 

 2) I don't know what you mean. Does a single lookup often involve 
 several under the hood?


 
 If your compiler is naive then code like this:
 if (1 in a)
     value = a[1];
 requires to perform two searches inside the hash, the first to tell if the key
is present, and the second to find it again and fetch its value.
 
 A bit better compiler (LDC is already able to do this) can recognize that you
are performing two nearby key searches with the same key, and it can remove the
second one, essentially replacing that code with this one:
 
 int value;
 auto ptr = 1 in a;
 if (ptr)
     value = *ptr;
 
 Bye,
 bearophile


You can always use:
auto value = 1 in a;
if (value) // needs != null? Haven't looked at this in the spec yet.
   //work with *value

But if the compiler can optimize the calls either way, and this is 
unsafe, a safer way sounds nice.
Aug 09 2010