www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Associative Arrays max length? 32bit/64bit

reply "sdvcn" <sdvcn 126.com> writes:
import std.stdio;

import std.utf;
import std.uni;
import std.string;
import std.random;
import std.conv;

int main(string[] argv)
{

	size_t[string] bary;

	try{
		for(size_t i=0;i<(size_t.max -1);i++)
		{
			bary["Key:" ~  to!(string)(i)] = i;
		}
	}catch(Exception e)
	{
		writeln(e);
	}
     return 0;
}
// This code will overflow?


bary.length <> size_t.max ?

32bit bary.length == 64bit bary.length ?
May 16 2014
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 17 May 2014 at 00:25:13 UTC, sdvcn wrote:
 import std.stdio;

 import std.utf;
 import std.uni;
 import std.string;
 import std.random;
 import std.conv;

 int main(string[] argv)
 {

 	size_t[string] bary;

 	try{
 		for(size_t i=0;i<(size_t.max -1);i++)
 		{
 			bary["Key:" ~  to!(string)(i)] = i;
 		}
 	}catch(Exception e)
 	{
 		writeln(e);
 	}
     return 0;
 }
 // This code will overflow?


 bary.length <> size_t.max ?

 32bit bary.length == 64bit bary.length ?

I cannot get the 32bit version to run on my computer, but what exactly is happening? I suspect you will simply run out of memory at some point, but this shouldn't be caught by catch(Exception), as it should throw an Error. Can you post the exact output of your program?
May 17 2014
parent reply FG <home fgda.pl> writes:
On 2014-05-17 12:46, sdvcn wrote:
 int main(string[] argv)
 {
 auto flog = File("results.txt", "w");

      size_t[string] bary;

      for(size_t i=0;i<(size_t.max -1);i++)
      {
          bary["Key:" ~  to!(string)(i)] = i;
          flog.write("stop i=" ~text(i));
          flog.seek(0);
          flog.flush();
      }
      return 0;
 }

 results:
 start i=0
 stop i=36495998
 ---------------
 start i=0
 stop i=36495992
 ----------------
 start i=36495998
 stop i=72991099

 I guess not see why Overflow.

This code will always make you run out of memory. Why are you surprised? Each key in the hash table is a string in the form "Key: 1234", so at stop (i = 36495998) the string has 13 bytes. Add to that 16 bytes for slice of that string (assuming 64-bit architecture), 8 bytes for the value, some space wasted on alignment, and don't forget the extra memory needed to store the tree for fast key look-up in the hash array. You said that you have 16 GB of memory. At i = 36495998 that means at most 470 bytes per item. As for capturing the problem, you can catch the Out-of-memory error but you cannot do that by catch(Exception e). OutOfMemory is not an Exception. It is an Error. Here is the updated example: import std.stdio, std.string, std.conv, core.exception; int main(string[] argv) { size_t[string] bary; size_t i = 0; try { for (; i < (size_t.max - 1); i++) bary["Key:" ~ to!(string)(i)] = i; } catch (OutOfMemoryError e) { writeln(e); } writefln("Last index was: %d", i); return 0; }
May 17 2014
parent reply FG <home fgda.pl> writes:
On 2014-05-17 21:35, bearophile wrote:
 FG:

 and don't forget the extra memory needed to store the tree for fast key
look-up in the hash array.

I think D now uses a linked list for the collision chains (so opCmp is useless, despite it's still required for the hashing protocol).

Indeed, I just read https://github.com/D-Programming-Language/dmd/blob/master/src/backend/aa.c Key hash is divided modulo the number of buckets and each bucket points to an ordered double-linked list. That list is walked left or right depending on what value Typeinfo::compare returns for two keys. Hmm... isn't opCmp used by that function? Why useless?
May 17 2014
next sibling parent FG <home fgda.pl> writes:
On 2014-05-17 22:30, bearophile wrote:
 Sorry, I didn't know the linked list is sorted. It's scanned sequentially,
because you can't use a binary search on a regular linked list. Perhaps a
skiplist is better to avoid O(n^2) behavour in presence of attacks or
degenerate cases (in past the AA used a tree there).

if (nodes > buckets_length * 4) rehash(); Skiplist doesn't seem necessary. As seen above, there shouldn't be much of a problem with long lists accumulating in some selected buckets, as long as the hash function is a proper hash (i.e. for any set of x (especially consecutive ones like 0, 1, ... n) hash(x) values cover the range of size_t evenly).
May 17 2014
prev sibling parent FG <home fgda.pl> writes:
Bloody Thunderbird. I think I pressed Reply instead of Followup.  Sorry, Steven.

On 2014-05-19 15:31, Steven Schveighoffer wrote:
 No, in that DMD file, the bucket is a tree, not a doubly-linked list.

Silly me. A look at the body of delnodes should have made it clear that it's a binary tree.
 opCmp is not used in D's AA.

Really? Then what does TypeInfo.compare(void*, void*) use? For example here: auto key_hash = keyti.getHash(pkey); Entry *e; /* ... */ if (key_hash == e.hash) { auto c = keyti.compare(pkey, e + 1); if (c == 0) goto Lret; }
May 24 2014
prev sibling next sibling parent reply "sdvcn" <sdvcn 126.com> writes:
On Saturday, 17 May 2014 at 09:26:32 UTC, Marc Schütz wrote:
 On Saturday, 17 May 2014 at 00:25:13 UTC, sdvcn wrote:
 import std.stdio;

 import std.utf;
 import std.uni;
 import std.string;
 import std.random;
 import std.conv;

 int main(string[] argv)
 {

 	size_t[string] bary;

 	try{
 		for(size_t i=0;i<(size_t.max -1);i++)
 		{
 			bary["Key:" ~  to!(string)(i)] = i;
 		}
 	}catch(Exception e)
 	{
 		writeln(e);
 	}
    return 0;
 }
 // This code will overflow?


 bary.length <> size_t.max ?

 32bit bary.length == 64bit bary.length ?

I cannot get the 32bit version to run on my computer, but what exactly is happening? I suspect you will simply run out of memory at some point, but this shouldn't be caught by catch(Exception), as it should throw an Error. Can you post the exact output of your program?

Does not capture. My computer is 16g memory, amd x2 250 cpu ,windows 2008 r2 int main(string[] argv) { size_t[string] bary; for(size_t i=0;i<(size_t.max -1);i++) { bary["Key:" ~ to!(string)(i)] = i; } return 0; } -m32 results are "ngram.exe 中的 0x7547c42d (KernelBase.dll) 处有未经处理的异常: 0xE0440001: 0xe0440001" -m64 Overflow I do not know bary.length results, Want to know the maximum capacity of the Associative Arrays 32bit? 64bit? Why will overflow? How to capture? How to Avoid?
May 17 2014
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, May 24, 2014 at 11:54:47PM -0700, Steven Schveighoffer via
Digitalmars-d wrote:
 On Sat, 24 May 2014 21:39:14 -0700, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 
On Sat, May 24, 2014 at 06:05:49PM -0700, Steven Schveighoffer via
Digitalmars-d wrote:
On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

Really? Then what does TypeInfo.compare(void*, void*) use? For
example here:

     auto key_hash = keyti.getHash(pkey); Entry *e;
     /* ... */
     if (key_hash == e.hash) {
         auto c = keyti.compare(pkey, e + 1);
         if (c == 0) goto Lret;
     }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point.

This has been argued over in a druntime pull before. I'm 100% for changing the above line (and all other instances of it) to use keyti.equals() instead. But that was shot down due to potential breakage of existing code. :-( :-( Nevermind the fact that it probably breaks a lot more *new* code than it ever will break old code... :-(

Any object/struct that defines opCmp but not opEquals is broken, and deserves to not work with AAs. It's a trivial change to add opEquals when opCmp is defined. This change should happen should happen. What pull request is it?

Sorry for the late response, I've been very busy with other things. I can't seem to find the PR anymore (it got closed over disagreement about how things should be fixed), but I did find the branch my code was in. The bugzilla issue is 10380. Looking at the bug, I see that apparently Denis has pushed through a hack fix for it: https://github.com/D-Programming-Language/druntime/pull/736 This still does not fix the fundamental issue, though, which is that AA's use keyti.compare instead of keyti.equal. It makes no sense because AA keys, by definition, are unordered, whereas types that define opCmp are by definition linearly-orderable. In any case, good luck getting the fix to go through. I would be very, very grateful.
It's been far too long that AA's have been broken in druntime.
Somebody should just take the aaA.d out in the back and shoot it, and
replace it with a better implementation. I think users will be far
happier with that.

I don't know that the current implementation is broken, just horrible. I'd rather focus on getting a full library type able to be up-to-par with the builtin type, and then switch the implementation over in the compiler. IIRC, the compiler does some magic (i.e. ignoring certain attribute requirements) that can't be done for a library type.

It's not that hard to get a library AA to be on par with the builtin type. The last time I tried it, though, I got stuck on trying that solve const issues that even the builtin type doesn't solve correctly. The main showstopper, however, is the amount of effort it takes to extricate the current AA implementation from the compiler. There are just too many places where it relies on compiler magic. T -- Freedom: (n.) Man's self-given right to be enslaved by his own depravity.
May 26 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 26 May 2014 19:03:22 -0400, H. S. Teoh via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Sat, May 24, 2014 at 11:54:47PM -0700, Steven Schveighoffer via  
 Digitalmars-d wrote:
 On Sat, 24 May 2014 21:39:14 -0700, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

On Sat, May 24, 2014 at 06:05:49PM -0700, Steven Schveighoffer via
Digitalmars-d wrote:
On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

Really? Then what does TypeInfo.compare(void*, void*) use? For
example here:

     auto key_hash = keyti.getHash(pkey); Entry *e;
     /* ... */
     if (key_hash == e.hash) {
         auto c = keyti.compare(pkey, e + 1);
         if (c == 0) goto Lret;
     }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point.

This has been argued over in a druntime pull before. I'm 100% for changing the above line (and all other instances of it) to use keyti.equals() instead. But that was shot down due to potential breakage of existing code. :-( :-( Nevermind the fact that it probably breaks a lot more *new* code than it ever will break old code... :-(

Any object/struct that defines opCmp but not opEquals is broken, and deserves to not work with AAs. It's a trivial change to add opEquals when opCmp is defined. This change should happen should happen. What pull request is it?

Sorry for the late response, I've been very busy with other things. I can't seem to find the PR anymore (it got closed over disagreement about how things should be fixed), but I did find the branch my code was in. The bugzilla issue is 10380. Looking at the bug, I see that apparently Denis has pushed through a hack fix for it: https://github.com/D-Programming-Language/druntime/pull/736

Hah, looking at that PR, it references the original PR (https://github.com/D-Programming-Language/druntime/pull/522). In which I commented, I remember this one. And look, there are the rules I outlined :) But I think there was some indication that a runtime-based version was imminent. I don't know what happened to that. Going to comment again on that PR. We should do something to make our way back to sane logic.
It's been far too long that AA's have been broken in druntime.
Somebody should just take the aaA.d out in the back and shoot it, and
replace it with a better implementation. I think users will be far
happier with that.

I don't know that the current implementation is broken, just horrible. I'd rather focus on getting a full library type able to be up-to-par with the builtin type, and then switch the implementation over in the compiler. IIRC, the compiler does some magic (i.e. ignoring certain attribute requirements) that can't be done for a library type.

It's not that hard to get a library AA to be on par with the builtin type. The last time I tried it, though, I got stuck on trying that solve const issues that even the builtin type doesn't solve correctly. The main showstopper, however, is the amount of effort it takes to extricate the current AA implementation from the compiler. There are just too many places where it relies on compiler magic.

Yes, it would be worth a lot to see if we can create an equivalent AA type in the library first, BEFORE trying to replace the builtin AA. The way it was done originally, was more of a mess than the fully compiler-defined AA. But this doesn't mean we can't fix the runtime. -Steve
May 27 2014
prev sibling next sibling parent "sdvcn" <sdvcn 126.com> writes:
int main(string[] argv)
{
auto flog = File("results.txt", "w");

	size_t[string] bary;

	for(size_t i=0;i<(size_t.max -1);i++)
	{
		bary["Key:" ~  to!(string)(i)] = i;
		flog.write("stop i=" ~text(i));
		flog.seek(0);
		flog.flush();
	}
     return 0;
}

results:
start i=0
stop i=36495998
---------------
start i=0
stop i=36495992
----------------
start i=36495998
stop i=72991099

I guess not see why Overflow.

hash table Collision?
May 17 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
FG:

 and don't forget the extra memory needed to store the tree for 
 fast key look-up in the hash array.

I think D now uses a linked list for the collision chains (so opCmp is useless, despite it's still required for the hashing protocol). Bye, bearophile
May 17 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
FG:

 and each bucket points to an ordered double-linked list.
 That list is walked left or right depending on what value
 Typeinfo::compare returns for two keys. Hmm... isn't opCmp
 used by that function? Why useless?

Sorry, I didn't know the linked list is sorted. It's scanned sequentially, because you can't use a binary search on a regular linked list. Perhaps a skiplist is better to avoid O(n^2) behavour in presence of attacks or degenerate cases (in past the AA used a tree there). Bye, bearophile
May 17 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 17 May 2014 at 20:30:30 UTC, bearophile wrote:
 Sorry, I didn't know the linked list is sorted. It's scanned 
 sequentially, because you can't use a binary search on a 
 regular linked list. Perhaps a skiplist is better to avoid 
 O(n^2) behavour in presence of attacks or degenerate cases (in 
 past the AA used a tree there).

 Bye,
 bearophile

*Technically*, for a sorted linked list (or forward iterators in general), you can find the result with O(N) *walk* iterations, but still only O(log(N)) *comparison* iterations. So saying "you can't use binary search on a regular linked list" is not quite 100% accurate. You can still get some bang for your buck out of a degenerated algorithm. http://www.cplusplus.com/reference/algorithm/binary_search/
May 17 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 for a sorted linked list (or forward iterators in general), you 
 can find the result with O(N) *walk* iterations, but still only 
 O(log(N)) *comparison* iterations.

I think I have never implement such algorithm, but you are right, and it's nice. Is Phobos using this idea somewhere? Are D AAs using it? Bye, bearophile
May 17 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 17 May 2014 at 22:05:03 UTC, bearophile wrote:
 monarch_dodra:

 for a sorted linked list (or forward iterators in general), 
 you can find the result with O(N) *walk* iterations, but still 
 only O(log(N)) *comparison* iterations.

I think I have never implement such algorithm, but you are right, and it's nice. Is Phobos using this idea somewhere? Are D AAs using it? Bye, bearophile

It's not used in phobos (as far as I know of anyways). It *could* be implemented in SortedRange's BinaryFind though. As for using it in AA's, you'd have to keep in mind you'd that (I think) you probably need a minimum size for the algorithm's lower complexity to kick in and actually give you better times.
May 17 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 It's not used in phobos (as far as I know of anyways). It 
 *could* be implemented in SortedRange's BinaryFind though.

Recently SortedRanges were changed, now they don't need to be random access ranges, so this is possible and I think it's good: https://issues.dlang.org/show_bug.cgi?id=12763 Bye, bearophile
May 18 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 17 May 2014 16:18:07 -0400, FG <home fgda.pl> wrote:

 On 2014-05-17 21:35, bearophile wrote:
 FG:

 and don't forget the extra memory needed to store the tree for fast  
 key look-up in the hash array.

I think D now uses a linked list for the collision chains (so opCmp is useless, despite it's still required for the hashing protocol).

Indeed, I just read https://github.com/D-Programming-Language/dmd/blob/master/src/backend/aa.c

This is dmd's source, not druntime. This is the representation of AA's in the compiler, not in your code. The appropriate code for druntime is here: https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
 Key hash is divided modulo the number of buckets and each bucket points  
 to an ordered double-linked list. That list is walked left or right  
 depending on what value Typeinfo::compare returns for two keys. Hmm...  
 isn't opCmp used by that function? Why useless?

No, in that DMD file, the bucket is a tree, not a doubly-linked list. opCmp is not used in D's AA. The D implementation used to mirror DMD, but it does not any more. It may be used for CTFE, I'm not sure. -Steve
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

 Bloody Thunderbird. I think I pressed Reply instead of Followup.  Sorry,  
 Steven.

It's OK, it went into my spam folder anyway ;)
 On 2014-05-19 15:31, Steven Schveighoffer wrote:
 No, in that DMD file, the bucket is a tree, not a doubly-linked list.

Silly me. A look at the body of delnodes should have made it clear that it's a binary tree.
 opCmp is not used in D's AA.

Really? Then what does TypeInfo.compare(void*, void*) use? For example here: auto key_hash = keyti.getHash(pkey); Entry *e; /* ... */ if (key_hash == e.hash) { auto c = keyti.compare(pkey, e + 1); if (c == 0) goto Lret; }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point. -Steve
May 24 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, May 24, 2014 at 06:05:49PM -0700, Steven Schveighoffer via
Digitalmars-d wrote:
 On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

Really? Then what does TypeInfo.compare(void*, void*) use? For
example here:

     auto key_hash = keyti.getHash(pkey); Entry *e;
     /* ... */
     if (key_hash == e.hash) {
         auto c = keyti.compare(pkey, e + 1);
         if (c == 0) goto Lret;
     }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point.

This has been argued over in a druntime pull before. I'm 100% for changing the above line (and all other instances of it) to use keyti.equals() instead. But that was shot down due to potential breakage of existing code. :-( :-( Nevermind the fact that it probably breaks a lot more *new* code than it ever will break old code... :-( It's been far too long that AA's have been broken in druntime. Somebody should just take the aaA.d out in the back and shoot it, and replace it with a better implementation. I think users will be far happier with that. T -- Trying to define yourself is like trying to bite your own teeth. -- Alan Watts
May 24 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 24 May 2014 21:39:14 -0700, H. S. Teoh via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Sat, May 24, 2014 at 06:05:49PM -0700, Steven Schveighoffer via  
 Digitalmars-d wrote:
 On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

Really? Then what does TypeInfo.compare(void*, void*) use? For
example here:

     auto key_hash = keyti.getHash(pkey); Entry *e;
     /* ... */
     if (key_hash == e.hash) {
         auto c = keyti.compare(pkey, e + 1);
         if (c == 0) goto Lret;
     }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point.

This has been argued over in a druntime pull before. I'm 100% for changing the above line (and all other instances of it) to use keyti.equals() instead. But that was shot down due to potential breakage of existing code. :-( :-( Nevermind the fact that it probably breaks a lot more *new* code than it ever will break old code... :-(

Any object/struct that defines opCmp but not opEquals is broken, and deserves to not work with AAs. It's a trivial change to add opEquals when opCmp is defined. This change should happen should happen. What pull request is it?
 It's been far too long that AA's have been broken in druntime. Somebody
 should just take the aaA.d out in the back and shoot it, and replace it
 with a better implementation. I think users will be far happier with
 that.

I don't know that the current implementation is broken, just horrible. I'd rather focus on getting a full library type able to be up-to-par with the builtin type, and then switch the implementation over in the compiler. IIRC, the compiler does some magic (i.e. ignoring certain attribute requirements) that can't be done for a library type. -Steve
May 24 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 25 May 2014 at 06:54:47 UTC, Steven Schveighoffer 
wrote:
 Any object/struct that defines opCmp but not opEquals is 
 broken, and deserves to not work with AAs.

If this is the case, then it needs to be documented in http://dlang.org/operatoroverloading.html (I'm not seeing it there), and the compiler needs to make it an error.
 It's a trivial change to add opEquals when opCmp is defined. 
 This change should happen should happen. What pull request is 
 it?

You mean have the compiler add it automatically?
May 25 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Sunday, 25 May 2014 at 06:54:47 UTC, Steven Schveighoffer 
wrote:
 On Sat, 24 May 2014 21:39:14 -0700, H. S. Teoh via 
 Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Sat, May 24, 2014 at 06:05:49PM -0700, Steven Schveighoffer 
 via Digitalmars-d wrote:
 On Sat, 24 May 2014 02:54:01 -0700, FG <home fgda.pl> wrote:

Really? Then what does TypeInfo.compare(void*, void*) use? 
For
example here:

    auto key_hash = keyti.getHash(pkey); Entry *e;
    /* ... */
    if (key_hash == e.hash) {
        auto c = keyti.compare(pkey, e + 1);
        if (c == 0) goto Lret;
    }

You know what, you are right. I assumed it used keyti.equals. This is a bug imo, since opCmp will be used, and opEquals will be ignored. Just checking for opCmp == 0 is identical to opEquals, except some types can define opEquals but not opCmp. But I don't know if it will get fixed. The whole AA runtime has to be redone at some point.

This has been argued over in a druntime pull before. I'm 100% for changing the above line (and all other instances of it) to use keyti.equals() instead. But that was shot down due to potential breakage of existing code. :-( :-( Nevermind the fact that it probably breaks a lot more *new* code than it ever will break old code... :-(

Any object/struct that defines opCmp but not opEquals is broken, and deserves to not work with AAs. It's a trivial change to add opEquals when opCmp is defined.

 -Steve

Perhaps I'm being naïve, but can't we just have a default compiler generated opEquals iff opCmp is defined and opEquals is not.
May 25 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 25 May 2014 03:19:37 -0700, Marc Sch=C3=BCtz <schuetzm gmx.net> =
wrote:

 On Sunday, 25 May 2014 at 06:54:47 UTC, Steven Schveighoffer wrote:
 Any object/struct that defines opCmp but not opEquals is broken, and =


 deserves to not work with AAs.

If this is the case, then it needs to be documented in =

 http://dlang.org/operatoroverloading.html (I'm not seeing it there), a=

 the compiler needs to make it an error.

In fact, you have to re-define opEquals, opCmp, and toHash all together = to = get it to work with AA's properly. None of this is enforced. See this = here: http://dlang.org/hash-map.html In particular this part: "The implementation may use either opEquals or opCmp or both. Care shoul= d = be taken so that the results of opEquals and opCmp are consistent with = each other when the struct/union objects are the same or not." But in reality, only opEquals and toHash need to be redefined together. = = opCmp is not needed for hashing, especially with the current = implementation. The docs should be updated to reflect so once this is = fixed. Somewhere on this newsgroup, I posted the rules that should happen, but = = I'm too lazy to look them up. I will post them again: 1. Any type that has one of opEquals or toHash defined, but not the othe= r, = should fail at compile time to become a key of an AA 2. Any type that has opCmp defined, but not opEquals, should fail to = become a key of an AA. Note, although it is advised to always override these 3 functions for = consistency, I don't think violating this rule should be a compiler erro= r. = But USING such a type as a key to an AA can rightfully be a compiler = error, as it is obvious such a thing will not operate properly, ever.
 It's a trivial change to add opEquals when opCmp is defined. This  =


 change should happen should happen. What pull request is it?

You mean have the compiler add it automatically?

No, I mean the runtime should rightfully penalize types that define opCm= p = but not opEquals by working incorrectly with them (i.e. using opEquals a= nd = not opCmp), similarly to how it currently works incorrectly with types = that define opCmp but not toHash or vice versa. In other words, TypeInfo.compare should be nowhere in AA code. -Steve
May 25 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 25 May 2014 04:59:43 -0700, John Colvin  =

<john.loughran.colvin gmail.com> wrote:

 On Sunday, 25 May 2014 at 06:54:47 UTC, Steven Schveighoffer wrote:
 It's a trivial change to add opEquals when opCmp is defined.

Perhaps I'm being na=C3=AFve, but can't we just have a default compile=

 generated opEquals iff opCmp is defined and opEquals is not.

That is a possibility. But this doesn't solve the issue of types which = have no valid opCmp, but have a valid opEquals. AA's really should never= = use opCmp, it's too limiting. -Steve
May 25 2014