www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Unexpected behaviour in associative array

reply Arredondo <arm.plus gmail.com> writes:
Hi all,

I'm using a custom Struct as the key type in an associative 
array. I have defined the toHash() and opEquals(...) functions, 
and the problem I'm having is that the test

mykey in aa

always fails (returns null) even though there are keys in the aa 
that return identical toHash() values than mykey and return true 
for opEquals. This is beyond frustrating, because at this point 
I'm pretty much out of ideas.

Have you had this problem before? Any tips or suggestions would 
be much appreciated.
Arredondo.
Apr 19 2019
parent reply Andre Pany <andre s-e-a-p.de> writes:
On Friday, 19 April 2019 at 11:10:16 UTC, Arredondo wrote:

 Hi all,

 I'm using a custom Struct as the key type in an associative 
 array. I have defined the toHash() and opEquals(...) functions, 
 and the problem I'm having is that the test

 mykey in aa

 always fails (returns null) even though there are keys in the 
 aa that return identical toHash() values than mykey and return 
 true for opEquals. This is beyond frustrating, because at this 
 point I'm pretty much out of ideas.

 Have you had this problem before? Any tips or suggestions would 
 be much appreciated.
 Arredondo.


Could you please post the coding, otherwise it is quite hard to 
help you.

Kind regards
Andre
Apr 19 2019
next sibling parent reply Arredondo <arm.plus gmail.com> writes:
On Friday, 19 April 2019 at 11:32:17 UTC, Andre Pany wrote:

 Could you please post the coding, otherwise it is quite hard to 
 help you.

 Kind regards
 Andre


Yes, I'm working on isolating the problem. It's a bit laborious 
because the custom Struct is actually a wrapper around an ndslice 
matrix, and I still don't know if the issue is reproducible 
without this dependency.
Apr 19 2019
parent reply Andre Pany <andre s-e-a-p.de> writes:
On Friday, 19 April 2019 at 11:41:53 UTC, Arredondo wrote:

 On Friday, 19 April 2019 at 11:32:17 UTC, Andre Pany wrote:

 Could you please post the coding, otherwise it is quite hard 
 to help you.

 Kind regards
 Andre


 Yes, I'm working on isolating the problem. It's a bit laborious 
 because the custom Struct is actually a wrapper around an 
 ndslice matrix, and I still don't know if the issue is 
 reproducible without this dependency.


With D the tool Dustmite is included, it reduces the code 
automatically for you. You just provide the expected compiler or 
linked output. It is also very well integrated into Dub.

Kind regards
Andre
Apr 19 2019
parent reply Andre Pany <andre s-e-a-p.de> writes:
On Friday, 19 April 2019 at 11:53:37 UTC, Andre Pany wrote:

 On Friday, 19 April 2019 at 11:41:53 UTC, Arredondo wrote:

 On Friday, 19 April 2019 at 11:32:17 UTC, Andre Pany wrote:

 Could you please post the coding, otherwise it is quite hard 
 to help you.

 Kind regards
 Andre


 Yes, I'm working on isolating the problem. It's a bit 
 laborious because the custom Struct is actually a wrapper 
 around an ndslice matrix, and I still don't know if the issue 
 is reproducible without this dependency.


 With D the tool Dustmite is included, it reduces the code 
 automatically for you. You just provide the expected compiler 
 or linked output. It is also very well integrated into Dub.

 Kind regards
 Andre


https://dub.pm/commandline.html#dustmite
Apr 19 2019
parent reply Arredondo <arm.plus gmail.com> writes:
On Friday, 19 April 2019 at 11:55:41 UTC, Andre Pany wrote:

 https://dub.pm/commandline.html#dustmite


Thanks, but it appears that this tool is used to isolate the 
cause of build errors, and I'm not having build errors, just 
unexpected behavior at runtime.

Something I have observed while continuing the tinkering is that 
sometimes the call

key in aa

segfaults (Program exited with code -11) when key is not in the 
aa. Very strange indeed.
Apr 19 2019
next sibling parent Andre Pany <andre s-e-a-p.de> writes:
On Friday, 19 April 2019 at 12:03:33 UTC, Arredondo wrote:

 On Friday, 19 April 2019 at 11:55:41 UTC, Andre Pany wrote:

 https://dub.pm/commandline.html#dustmite


 Thanks, but it appears that this tool is used to isolate the 
 cause of build errors, and I'm not having build errors, just 
 unexpected behavior at runtime.

 Something I have observed while continuing the tinkering is 
 that sometimes the call

 key in aa

 segfaults (Program exited with code -11) when key is not in the 
 aa. Very strange indeed.


You can also use it for runtime, either use --program-status or 
--program-regex.

Kind regards
Andre
Apr 19 2019
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Friday, 19 April 2019 at 12:03:33 UTC, Arredondo wrote:

 key in aa


Keep in mind that D's `in` operator returns a *pointer* to the 
element, or null if it isn't there.

If you aren't treating the return value as a pointer, you could 
hit trouble.
Apr 19 2019
parent Arredondo <arm.plus gmail.com> writes:
On Friday, 19 April 2019 at 12:43:06 UTC, Adam D. Ruppe wrote:

 On Friday, 19 April 2019 at 12:03:33 UTC, Arredondo wrote:

 key in aa


 Keep in mind that D's `in` operator returns a *pointer* to the 
 element, or null if it isn't there.

 If you aren't treating the return value as a pointer, you could 
 hit trouble.


I understand that. The issue is that it should't return null if 
theres a matching element in the aa!
Apr 19 2019
prev sibling parent reply Arredondo <arm.plus gmail.com> writes:
On Friday, 19 April 2019 at 11:32:17 UTC, Andre Pany wrote:

 Could you please post the coding, otherwise it is quite hard to 
 help you.


Here's a reasonably-sized code fragment that demonstrates the 
issue. I hope the comments along the way are descriptive enough

Thanks,
Arredondo
----------

// this is a thin wrapper around a 2D byte matrix
// that uses an ndslice internally
struct State {
     import std.digest.murmurhash;
	import mir.ndslice;

     this(byte rows, byte cols) inout  safe pure nothrow {
         payload = slice!byte([rows, cols], 0);
     }

     size_t toHash() pure nothrow {
         byte[] data = payload.field();
         immutable digest = digest!(MurmurHash3!(128, 64))(data);
         immutable hash = *cast(size_t*) &digest[0];
         return hash;
     }

     bool opEquals(ref inout State q) inout  safe pure nothrow {
         return payload == q;
     }

     Slice!(Contiguous, [2], byte*) payload;
     alias payload this;
}

void main(string[] args) {
	import std.stdio;

	// create a key
	auto key1 = State(2, 2);
	key1[0, 0] = cast(byte) 1;

	// insert it in an assoc. array
	int[State] map;
	map[key1] = 101;

	// create the exact same key
	auto key2 = State(2, 2);
	key2[0, 0] = cast(byte) 1;

	// it is an identical key as far as the aa is concerned
	assert(key1.opEquals(key2));
	assert(key2.opEquals(key1));
	assert(key1.toHash == key2.toHash);

	// yet it is not in the map
	writeln(key1 in map); // prints some memory address
	writeln(key2 in map); // prints null <-- unexpected behaviour!!!!
}
Apr 19 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Friday, 19 April 2019 at 12:37:10 UTC, Arredondo wrote:

 Here's a reasonably-sized code fragment that demonstrates the 
 issue.


Oh dear, I don't know what's going on there. It might just be 
that toHash is secretly dependent on various attributes in the 
signature.

I'd try to match the attrs exactly from this:

https://dlang.org/spec/hash-map.html#using_struct_as_key

size_t toHash() const  safe pure nothrow;
bool opEquals(ref const typeof(this) s) const  safe pure nothrow;

and see if it makes a difference.


idk though.
Apr 19 2019
parent reply Arredondo <arm.plus gmail.com> writes:
On Friday, 19 April 2019 at 12:48:32 UTC, Adam D. Ruppe wrote:

 It might just be that toHash is secretly dependent on various 
 attributes in the signature.


You nailed it. This was it. It was not trivial to add the missing 
 safe and const attributes, but it worked.

Thanks!
Apr 19 2019
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Apr 19, 2019 at 08:15:22PM +0000, Arredondo via Digitalmars-d-learn
wrote:

 On Friday, 19 April 2019 at 12:48:32 UTC, Adam D. Ruppe wrote:

 It might just be that toHash is secretly dependent on various
 attributes in the signature.
 


 
 You nailed it. This was it. It was not trivial to add the missing
  safe and const attributes, but it worked.


[...]

For the future, also note that if you want to test opCmp it's better to
use == instead of calling opCmp directly, that way you know for sure
that the compiler picked up your definition of opCmp. (IIRC if the
signature doesn't match for whatever reason the compiler may just
silently revert to the default implementation.)

Similarly, if you want to test toHash, use typeid(obj).getHash(&obj),
rather than calling toHash directly.  That way you know for sure that
the compiler has picked up your custom toHash, rather than just the
default implementation.


T

-- 
"Maybe" is a strange word.  When mom or dad says it it means "yes", but when my
big brothers say it it means "no"! -- PJ jr.
Apr 19 2019
prev sibling next sibling parent JN <666total wp.pl> writes:
On Friday, 19 April 2019 at 12:37:10 UTC, Arredondo wrote:

 Here's a reasonably-sized code fragment that demonstrates the 
 issue. I hope the comments along the way are descriptive enough


Hmm. Have you tried using a different compiler or 32/64 bit? I 
had a weird "null out of nowhere" bug going on with associative 
array some time ago - 
https://issues.dlang.org/show_bug.cgi?id=19662
Apr 19 2019
prev sibling parent reply 9il <ilyayaroshenko gmail.com> writes:
On Friday, 19 April 2019 at 12:37:10 UTC, Arredondo wrote:

     Slice!(Contiguous, [2], byte*) payload;


BTW, any reason not to use the new version of ndslice?

For new API it would be:

Slice!(byte*, 2, Contiguous)

or just

Slice!(byte*, 2)
Apr 20 2019
parent reply Arredondo <arm.plus gmail.com> writes:
On Saturday, 20 April 2019 at 14:24:34 UTC, 9il wrote:

 On Friday, 19 April 2019 at 12:37:10 UTC, Arredondo wrote:

     Slice!(Contiguous, [2], byte*) payload;


 BTW, any reason not to use the new version of ndslice?

 For new API it would be:

 Slice!(byte*, 2, Contiguous)

 or just

 Slice!(byte*, 2)


I think this new ndslice API is newer than my code. I might 
consider upgrading though, maybe in the new version Slice.field() 
is const, so I can use my preferred implementation of toHash()?
Apr 20 2019
parent reply 9il <ilyayaroshenko gmail.com> writes:
On Saturday, 20 April 2019 at 22:16:22 UTC, Arredondo wrote:

 On Saturday, 20 April 2019 at 14:24:34 UTC, 9il wrote:

 On Friday, 19 April 2019 at 12:37:10 UTC, Arredondo wrote:

     Slice!(Contiguous, [2], byte*) payload;


 BTW, any reason not to use the new version of ndslice?

 For new API it would be:

 Slice!(byte*, 2, Contiguous)

 or just

 Slice!(byte*, 2)


 I think this new ndslice API is newer than my code. I might 
 consider upgrading though, maybe in the new version 
 Slice.field() is const, so I can use my preferred 
 implementation of toHash()?


In the latest release you can do

yourSlice.lightConst.field

lightConst converts from const slice to slice of const.

I will add const and immutable field to the next major release.

Yoy can fill an issue in case you would also need other 
functionality.

Best,
Ilya
Apr 20 2019
parent Arredondo <arm.plus gmail.com> writes:
On Sunday, 21 April 2019 at 00:13:15 UTC, 9il wrote:

 In the latest release you can do

 yourSlice.lightConst.field

 lightConst converts from const slice to slice of const.

 I will add const and immutable field to the next major release.


That is very good to know. BWT, I think ndslice is an amazing 
contribution, and you are doing a great job. I do find it hard to 
navigate sometimes though, with the rather thin documentation 
that it has. More docs would definitely be at the top of my wish 
list :)

Kind regards,
Arredondo
Apr 21 2019