www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 323] New: Error: need opCmp for class Bar

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323

           Summary: Error: need opCmp for class Bar
           Product: D
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla digitalmars.com
        ReportedBy: someanon yahoo.com


I think this use to work; now on Linux dmd.166, it reports:

Error: need opCmp for class Bar

============================================
template Valuable(T) {
protected:
  float m_value = 0.0;

public:
  float value()  {return m_value;}
  void  value(float v)  {m_value=v;}
  int opCmp(T other) {
    int r;

    if      (value < other.value)  {r = -1;}
    else if (value > other.value)  {r =  1;}

    return r;
  }
}

class Foo {
}

class Bar : Foo {
  mixin  Valuable!(Bar);  // defined opCmp to compare Bar

public:
  this(float v) {
    m_value = v;
  }
}

int main(char[][] args) {
  Bar[3] bars;

  for (int i = 0; i < 3; i++) {
    bars[i] = new Bar(i);
  }
  bars.sort;

  return 0;
}

============================================


-- 
Sep 03 2006
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #1 from someanon yahoo.com  2006-09-03 14:25 -------
Same problem on WindowsXP:

Error: need opCmp for class Bar


-- 
Sep 03 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #2 from someanon yahoo.com  2006-09-03 16:48 -------
Two more questions:

1) this is reported at compile time, but errors out at run-time. Maybe the
compiler does see the opCmp, but other things goes wrong.

2) Before I isolate the problem, in my real program: on Linux, it builds and
errors out at run-time.  But on WinXP, I have a link time error: "Unexpected
OPTLINK Termination at EIP=0044C37B".  Not sure if it's related to this opCmp
issue.


-- 
Sep 03 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #3 from someanon yahoo.com  2006-09-03 16:50 -------
Sorry, typo:

1) this is reported at compile time ...

should be:

1) this is NOT reported at compile time ...


-- 
Sep 03 2006
prev sibling next sibling parent Thomas Kuehne <thomas-dloop kuehne.cn> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

d-bugmail puremagic.com schrieb am 2006-09-03:
 http://d.puremagic.com/issues/show_bug.cgi?id=323

 I think this use to work; now on Linux dmd.166, it reports:

http://www.digitalmars.com/d/changelog.html#new0163 # # Object.opCmp now throws an error. Should override it # if used. Breaks existing code. #
 Error: need opCmp for class Bar

<snip>
   int opCmp(T other) {
     int r;

     if      (value < other.value)  {r = -1;}
     else if (value > other.value)  {r =  1;}

     return r;
   }

The cause is a nasty result of D's function inheritance and overriding. http://www.digitalmars.com/d/function.html # # A functions in a derived class with the same name and parameter types # as a function in a base class overrides that function. # Thus "int T.opCmp(T other)" dosen't override "int Object.opCmp(Object o)" ... Should do the trick: # # int opCmp(Object o){ # T t = cast(T) o; # if(t is null){ # return super.opCmp(o); # }else{ # return opCmp(t); # } # } # # int opCmp(T other) { # int r; # # if (value < other.value) {r = -1;} # else if (value > other.value) {r = 1;} # # return r; # } # Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFE/+hrLK5blCcjpWoRAn19AJ4xroQQhMNn1DkxLCAafdrzXw2UswCeNZfA 2eWscmpgVCkItONOreZGRmo= =UXBJ -----END PGP SIGNATURE-----
Sep 07 2006
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Since D's associative arrays use opCmp to resolve collisions, any class 
that has opEquals defined should probably have opCmp defined also.  The 
old default implementation of Object.opCmp in Phobos was not compatible 
with compacting GCs so it was replaced with a version that throws an 
exception on use.  However, there is a default implementation that 
actually works and is compatible with compacting GCs:

     int opCmp(Object o)
     {
	return this !is o;
     }

Compare to opEquals:

     int opEquals(Object o)
     {
         return this is o;
     }

The opCmp function above forces the binary tree chaining mechanism into 
a linked-list, and equivalence is resolved by pointer equality rather 
than some ordering mechanism.  It won't be as fast as an ordering 
implementation of opCall for the degenerate case but it has the benefit 
of being immune to object movement.  If a default implementation of 
opEquals is to remain in Phobos then I suggest adopting the default 
opCmp implementation above as well.
Sep 07 2006
parent reply xs0 <xs0 xs0.com> writes:
Sean Kelly wrote:
 Since D's associative arrays use opCmp to resolve collisions, any class 
 that has opEquals defined should probably have opCmp defined also.  The 
 old default implementation of Object.opCmp in Phobos was not compatible 
 with compacting GCs so it was replaced with a version that throws an 
 exception on use.  However, there is a default implementation that 
 actually works and is compatible with compacting GCs:
 
     int opCmp(Object o)
     {
     return this !is o;
     }

That's not a really good solution, as no usable ordering is defined (a>b and b>a will always be true whenever a !is b). While it may work for (degenerate) insertion into a binary tree, it's (imho) worse than throwing an exception in practically all other cases. For example, a quick sort will not only run really slow in O(n^2) time but also produce an unsorted result without any indication of error. xs0
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
xs0 wrote:
 Sean Kelly wrote:
 Since D's associative arrays use opCmp to resolve collisions, any 
 class that has opEquals defined should probably have opCmp defined 
 also.  The old default implementation of Object.opCmp in Phobos was 
 not compatible with compacting GCs so it was replaced with a version 
 that throws an exception on use.  However, there is a default 
 implementation that actually works and is compatible with compacting GCs:

     int opCmp(Object o)
     {
     return this !is o;
     }

That's not a really good solution, as no usable ordering is defined (a>b and b>a will always be true whenever a !is b). While it may work for (degenerate) insertion into a binary tree, it's (imho) worse than throwing an exception in practically all other cases. For example, a quick sort will not only run really slow in O(n^2) time but also produce an unsorted result without any indication of error.

Ah good point. So any ideas? Personally, I'd be happy if the default AA used a linked-list for chaining and opEquals for comparison so this wasn't an issue, but that seems a foregone conclusion. I'm mostly concerned about providing default behavior that makes sense for the common case. The problem I've run into is that I have objects which need to be used as keys in an AA but are not inherently sortable.
Sep 07 2006
parent reply xs0 <xs0 xs0.com> writes:
Sean Kelly wrote:
 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the default 
 AA used a linked-list for chaining and opEquals for comparison so this 
 wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
 concerned about providing default behavior that makes sense for the 
 common case.  The problem I've run into is that I have objects which 
 need to be used as keys in an AA but are not inherently sortable.

Well, one possibly good solution would be to templatize AAs and remove opCmp from Object. That way, you'd get an error when using comparison on objects without opCmp (most other operators work that way) and the template could test for its presence and use different implementations for each. Another nice consequence would be the possibility of having optimized implementations for specific types; most probably even a single implementation could be considerably faster, because the compiler would know the exact type at compile-time, producing an optimized version of code for each. xs0
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
xs0 wrote:
 Sean Kelly wrote:
 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the default 
 AA used a linked-list for chaining and opEquals for comparison so this 
 wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
 concerned about providing default behavior that makes sense for the 
 common case.  The problem I've run into is that I have objects which 
 need to be used as keys in an AA but are not inherently sortable.

Well, one possibly good solution would be to templatize AAs and remove opCmp from Object. That way, you'd get an error when using comparison on objects without opCmp (most other operators work that way) and the template could test for its presence and use different implementations for each.

Some fancier AA support would be nice, but I'm not sure how to add templates to the built-in syntax. I just noticed something confusing in the spec however. Why are classes intended to be used as keys in an AA required to implement both opCmp *and* opEquals? Since the AA is backed by a binary tree I would expect it determine 'equality' as equivalence using opCmp. It's quite common for me to define classes that are equivalent but not equal, and also classes that can be compared for equality but not sorted. But it sounds like both would not be compatible with D's built-in AA implementation. I'm beginning to feel that any possible performance advantage that can be offered from binary tree chaining over linked list chaining is overshadowed by the limitations it imposes on the use of AAs in general. Can someone suggest an alternate default implementation for opCmp that solves these problems? Sean
Sep 07 2006
next sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Sean Kelly wrote:
 xs0 wrote:
 Sean Kelly wrote:
 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the 
 default AA used a linked-list for chaining and opEquals for 
 comparison so this wasn't an issue, but that seems a foregone 
 conclusion.  I'm mostly concerned about providing default behavior 
 that makes sense for the common case.  The problem I've run into is 
 that I have objects which need to be used as keys in an AA but are 
 not inherently sortable.

Well, one possibly good solution would be to templatize AAs and remove opCmp from Object. That way, you'd get an error when using comparison on objects without opCmp (most other operators work that way) and the template could test for its presence and use different implementations for each.

Some fancier AA support would be nice, but I'm not sure how to add templates to the built-in syntax.

I think xs0 was thinking of making AAs templates, and then the compiler would add syntactic sugar to that template to achieve current syntax. So something like char[float[]] a; would become something like AA!(char, float[]) a;
 I just noticed something confusing in 
 the spec however.  Why are classes intended to be used as keys in an AA 
 required to implement both opCmp *and* opEquals?  Since the AA is backed 
 by a binary tree I would expect it determine 'equality' as equivalence 
 using opCmp.

I would too.
 It's quite common for me to define classes that are 
 equivalent but not equal, and also classes that can be compared for 
 equality but not sorted.  But it sounds like both would not be 
 compatible with D's built-in AA implementation.  

It is a rather big limitation.
 I'm beginning to feel 
 that any possible performance advantage that can be offered from binary 
 tree chaining over linked list chaining is overshadowed by the 
 limitations it imposes on the use of AAs in general.  Can someone 
 suggest an alternate default implementation for opCmp that solves these 
 problems?

Yes: here is a suggestion: remove opCmp from Object. I think the only reason it is there is that when AAs where first implemented templates weren't where they are now so there was no way to check if an object has opCmp. These days a template version of AAs would be much better, and it would (if I'm not mistaken) remove the need for opCmp to be in Object.
Sep 07 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Ivan Senji wrote:
 Yes: here is a suggestion: remove opCmp from Object. I think the only 
 reason it is there is that when AAs where first implemented templates 
 weren't where they are now so there was no way to check if an object has 
 opCmp. These days a template version of AAs would be much better, and it 
 would (if I'm not mistaken) remove the need for opCmp to be in Object.

While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them. Can you give an example of a class that could not have a meaningful opCmp implementation that one would want to put into an AA?
Sep 07 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Ivan Senji wrote:
 Yes: here is a suggestion: remove opCmp from Object. I think the only 
 reason it is there is that when AAs where first implemented templates 
 weren't where they are now so there was no way to check if an object 
 has opCmp. These days a template version of AAs would be much better, 
 and it would (if I'm not mistaken) remove the need for opCmp to be in 
 Object.

While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them. Can you give an example of a class that could not have a meaningful opCmp implementation that one would want to put into an AA?

The one I've been wrestling with is a Thread class, as it has no data that is static and unique for the life of the object. The thread id is only guaranteed to be unique while the thread is active, and the id isn't even assigned until Thread.start is called. Threads simply have no features which inherently support ordering, but it makes sense to compare two Thread objects for equality simply by comparing object addresses. Sean
Sep 07 2006
next sibling parent Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

The one I've been wrestling with is a Thread class, as it has no data that is static and unique for the life of the object. The thread id is only guaranteed to be unique while the thread is active, and the id isn't even assigned until Thread.start is called. Threads simply have no features which inherently support ordering, but it makes sense to compare two Thread objects for equality simply by comparing object addresses.

One way to solve this is to have the Thread constructor add a unique sequence number.
Sep 08 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

The one I've been wrestling with is a Thread class, as it has no data that is static and unique for the life of the object. The thread id is only guaranteed to be unique while the thread is active, and the id isn't even assigned until Thread.start is called. Threads simply have no features which inherently support ordering, but it makes sense to compare two Thread objects for equality simply by comparing object addresses.

How do you do a hash for it if there's no constant data?
Sep 08 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

The one I've been wrestling with is a Thread class, as it has no data that is static and unique for the life of the object. The thread id is only guaranteed to be unique while the thread is active, and the id isn't even assigned until Thread.start is called. Threads simply have no features which inherently support ordering, but it makes sense to compare two Thread objects for equality simply by comparing object addresses.

How do you do a hash for it if there's no constant data?

Using address, currently :-p But that obviously has to change. What might make the most sense from a hash perspective would be something like this: class C { hash_t hash; hash_t toHash() { if (hash != hash.init) return hash; hash = cast(hash_t) this; return hash; } } But that leaves opCmp to wrestle with. An "object id" would be a reasonable universal solution, but I don't want to pay for the synchronized op on construction. I suppose I'm simply having a hard time getting over the idea that an object's address is is not a unique identifier in GCed languages. Sean
Sep 08 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 How do you do a hash for it if there's no constant data?

Using address, currently :-p But that obviously has to change. What might make the most sense from a hash perspective would be something like this: class C { hash_t hash; hash_t toHash() { if (hash != hash.init) return hash; hash = cast(hash_t) this; return hash; } }

That will fail if the object gets moved.
 But that leaves opCmp to wrestle with.  An "object id" would be a 
 reasonable universal solution, but I don't want to pay for the 
 synchronized op on construction.  I suppose I'm simply having a hard 
 time getting over the idea that an object's address is is not a unique 
 identifier in GCed languages.

An opCmp has the same problem that toHash does; fix it for either and it is fixed for both. I think you'll have to do a unique id for each in order to store them in an AA, or else wait until the thread id is assigned before storing it.
Sep 08 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 How do you do a hash for it if there's no constant data?

Using address, currently :-p But that obviously has to change. What might make the most sense from a hash perspective would be something like this: class C { hash_t hash; hash_t toHash() { if (hash != hash.init) return hash; hash = cast(hash_t) this; return hash; } }

That will fail if the object gets moved.

Not at all. The hash value is stored the first time it's computed, and it will remain constant for the life of the object. If the object is later moved and a new object created in its old position then the two objects would simply have the same hash value. Collisions would still be resolved with opCmp or opEquals depending on AA implementation. In the worst case however, I'll admit that this could result in long hash chains.
 But that leaves opCmp to wrestle with.  An "object id" would be a 
 reasonable universal solution, but I don't want to pay for the 
 synchronized op on construction.  I suppose I'm simply having a hard 
 time getting over the idea that an object's address is is not a unique 
 identifier in GCed languages.

An opCmp has the same problem that toHash does; fix it for either and it is fixed for both. I think you'll have to do a unique id for each in order to store them in an AA, or else wait until the thread id is assigned before storing it.

opCmp doesn't have quite the same problem as toHash because it's completely valid (if ill-advised) for toHash to always return zero while opCmp may only evaluate two objects as equivalent if they actually are equivalent. Essentially, I see toHash as a weak identity operation, opEquals as a strong identity operation, and opCmp as an ordering operation. I'll admit that the template idea is appealing, but not if it would require adding a ton of stuff to object.d. I think this could probably be avoided by passing the comparator as a delegate parameter however, and would allow the compiler to switch between two AA implementations (one for objects with opCmp, and one for objects with only opEquals) to handle each class of objects in a reasonable manner. This should also eliminate the need for a default opCmp and opEquals implementation: // implicit or in object.d: extern (C) { void* aaGetByCmp(void* key, int function(void*,void*) cmp); void* aaGetByEquals(void* key, bool function(void*,void*) equals); } bool doCmp(T)(void* a, void* b) { return a == b ? 0 : a ? (cast(T)a).opCmp(cast(T)b) : (cast(T)b).opCmp(cast(T)a); } bool doEquals(T)(void* a, void* b) { return cast(T)a == cast(T)b; } // user code: class C { hash_t toHash(); bool opEquals( C val ); } C[C] myAA; C key = new C; myAA[key] = key; // this call: C val = myAA[key]; // translates to: C val = cast(C) aaGetByEquals(key, &doEquals!(C));
Sep 08 2006
parent Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 How do you do a hash for it if there's no constant data?

Using address, currently :-p But that obviously has to change. What might make the most sense from a hash perspective would be something like this: class C { hash_t hash; hash_t toHash() { if (hash != hash.init) return hash; hash = cast(hash_t) this; return hash; } }

That will fail if the object gets moved.

Not at all. The hash value is stored the first time it's computed, and it will remain constant for the life of the object. If the object is later moved and a new object created in its old position then the two objects would simply have the same hash value. Collisions would still be resolved with opCmp or opEquals depending on AA implementation. In the worst case however, I'll admit that this could result in long hash chains.

Storing a sequence number, instead of the address, will produce the same result and will also work with opEquals and opCmp. The only downside is you'll need to sync the counter accesses upon construction, but thread stuff is sync'd anyway so I don't think that is a big problem.
Sep 08 2006
prev sibling next sibling parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Walter Bright wrote:
 Ivan Senji wrote:
 Yes: here is a suggestion: remove opCmp from Object. I think the only 
 reason it is there is that when AAs where first implemented templates 
 weren't where they are now so there was no way to check if an object 
 has opCmp. These days a template version of AAs would be much better, 
 and it would (if I'm not mistaken) remove the need for opCmp to be in 
 Object.

While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them.

I didn't mean change int[char[]] to AA!(int, char[]), I meant it would be nice to change the implementation to a template, without changing the syntax. I guess this is one thing in D I still can't get over the C++ way. (a couple of years back I thought iostream and <<, >> where the best :) But these AAs and their requirements are bugging me: Why do I have to (in my class ABC) declare opCmp to be int opCmp(Object o)? IMO that sucks because when used in an AA it's not like there is going to be objects of different types as keys. And that is a textbook example of when a template should be used.
 
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

Sean Kelly gave a good example. But I have nothing against AAs requiring opCmp, opEquals, toHash or what ever it needs, but would prefer for them not to be in Object.
Sep 08 2006
prev sibling parent reply xs0 <xs0 xs0.com> writes:
Walter Bright wrote:
 Ivan Senji wrote:
 Yes: here is a suggestion: remove opCmp from Object. I think the only 
 reason it is there is that when AAs where first implemented templates 
 weren't where they are now so there was no way to check if an object 
 has opCmp. These days a template version of AAs would be much better, 
 and it would (if I'm not mistaken) remove the need for opCmp to be in 
 Object.

While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them.

But if you hide the implementation via AA syntax sugar, those many programmers won't have to deal with templates at all?
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

Object :) OK, that may be a bit Java-ish, but the simplest way to obtain a unique key/identifier is simply "new Object()". It works in HashMaps, is equal only to itself, and that's about everything you need in some cases. ---- I think opCmp should be removed from Object, it causes nothing but grief: - it errors at runtime if not implemented, instead of at compile time - it requires you to cast the parameter - can never be inlined Further, I think toHash should also be removed from Object, because the current implementation is buggy wrt compacting GCs, and as Object has no inherent data except its possibly changing address, a correct default toHash can only return 0 (or another constant), making it useless (alternatively, we could acknowledge that a compacting GC for a systems language is practically impossible to do and stop calling the current implementation buggy). Then, a templated version of AAs can check for existence of those two functions and implements itself accordingly. Worst case is obviously just a list/array of key/value pairs with linear scanning on lookup, but - at least it works - can be still useful/fast enough for maps with only a few keys ---- BTW, is there any particular reason for hash_t? I think it would be better to use uint and make it non-platform-dependent (the latter is bad, and the extra 32 bits don't help at all in any realistic case) xs0
Sep 08 2006
parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
xs0 wrote:
 Walter Bright wrote:
 Ivan Senji wrote:
 Yes: here is a suggestion: remove opCmp from Object. I think the only 
 reason it is there is that when AAs where first implemented templates 
 weren't where they are now so there was no way to check if an object 
 has opCmp. These days a template version of AAs would be much better, 
 and it would (if I'm not mistaken) remove the need for opCmp to be in 
 Object.

While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them.

But if you hide the implementation via AA syntax sugar, those many programmers won't have to deal with templates at all?

Yes, everything would remain as it is now, except better.
 
 Can you give an example of a class that could not have a meaningful 
 opCmp implementation that one would want to put into an AA?

Object :)

LOL
 
 OK, that may be a bit Java-ish, but the simplest way to obtain a unique 
 key/identifier is simply "new Object()". It works in HashMaps, is equal 
 only to itself, and that's about everything you need in some cases.
 
 ----
 
 I think opCmp should be removed from Object, it causes nothing but grief:
 - it errors at runtime if not implemented, instead of at compile time
 - it requires you to cast the parameter
 - can never be inlined

Thanks xs0, you have put my exact thoughts into words :)
Sep 08 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Some fancier AA support would be nice, but I'm not sure how to add 
 templates to the built-in syntax.  I just noticed something confusing in 
 the spec however.  Why are classes intended to be used as keys in an AA 
 required to implement both opCmp *and* opEquals?  Since the AA is backed 
 by a binary tree I would expect it determine 'equality' as equivalence 
 using opCmp.  It's quite common for me to define classes that are 
 equivalent but not equal, and also classes that can be compared for 
 equality but not sorted.  But it sounds like both would not be 
 compatible with D's built-in AA implementation.  I'm beginning to feel 
 that any possible performance advantage that can be offered from binary 
 tree chaining over linked list chaining is overshadowed by the 
 limitations it imposes on the use of AAs in general.  Can someone 
 suggest an alternate default implementation for opCmp that solves these 
 problems?

Although the current AA implementation only uses opCmp, having both available means that an implementation could use both or either. Sometimes opEquals can be computed a lot more efficiently than opCmp. The current implementation uses hashing with binary trees, but an implementation isn't required to do it that way. Hashing with binary trees has proven in practice to be very efficient. It beats even C++ templated hash tables. I'm sure with some careful coding one can create a faster one customized to a particular data type, but the current general purpose one is pretty darned fast and compact. It's the central algorithm in DMDScript, for example, and DMDScript still beats the other javascript implementations around the block.
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 
 Although the current AA implementation only uses opCmp, having both 
 available means that an implementation could use both or either. 
 Sometimes opEquals can be computed a lot more efficiently than opCmp.
 The current implementation uses hashing with binary trees, but an 
 implementation isn't required to do it that way.

This is good to know. I'd considered playing with the current implementation, but was concerned about altering spec-defined behavior.
 Hashing with binary trees has proven in practice to be very efficient. 
 It beats even C++ templated hash tables. I'm sure with some careful 
 coding one can create a faster one customized to a particular data type, 
 but the current general purpose one is pretty darned fast and compact. 
 It's the central algorithm in DMDScript, for example, and DMDScript 
 still beats the other javascript implementations around the block.

I agree that it's got fantastic performance--my concerns here are really more practical, as I have objects I want to use as keys that don't contain any data which could be used for sorting purposes. But it sounds like there's enough wiggle room in the spec to find some reasonable middle ground. Thanks! Sean
Sep 07 2006
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 
 Although the current AA implementation only uses opCmp, having both 
 available means that an implementation could use both or either. 
 Sometimes opEquals can be computed a lot more efficiently than opCmp.
 The current implementation uses hashing with binary trees, but an 
 implementation isn't required to do it that way.

This is good to know. I'd considered playing with the current implementation, but was concerned about altering spec-defined behavior.
 Hashing with binary trees has proven in practice to be very efficient. 
 It beats even C++ templated hash tables. I'm sure with some careful 
 coding one can create a faster one customized to a particular data 
 type, but the current general purpose one is pretty darned fast and 
 compact. It's the central algorithm in DMDScript, for example, and 
 DMDScript still beats the other javascript implementations around the 
 block.

I agree that it's got fantastic performance--my concerns here are really more practical, as I have objects I want to use as keys that don't contain any data which could be used for sorting purposes. But it sounds like there's enough wiggle room in the spec to find some reasonable middle ground. Thanks! Sean

If I recall correctly, the old "standard" Object.opCmp simply compared addresses. Maybe that could be written into a mixin somewhere to be used by classes with no inherent logical order of their own. -- Chris Nicholson-Sauls
Sep 08 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #8 from bugzilla digitalmars.com  2008-06-25 02:57 -------
Covariant function parameters make it very difficult to do overloading - should
it be an overload, or an override?


-- 
Jun 25 2008
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323


bugzilla digitalmars.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX




------- Comment #9 from bugzilla digitalmars.com  2008-06-25 03:18 -------
I don't think Sean's default opCmp should be used, because it will hide errors
where one has not declared an overriding opCmp correctly. I think it is best to
leave the throwing one as the default.


-- 
Jun 25 2008