www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Vote: AA builtin method get()

reply David Medlock <noone nowhere.com> writes:
Walter,

I really think the following is a good solution to the AA issues.

1. Add a get method to all AAs:

bool get( in key, out value );

if the value is there, you get it and no double lookups.  A great side 
effect of this is the out value is initialized to the default! Which 
mimics the old behavior and allows you to determine if it was there.

2. Deprecate the in syntax.  It is really not useful because it cannot 
be overridden if I wish to replace an AA with a class.  Semantically it 
has no advantage to a method.  It also requires pointers which isn't 
really required elsewhere in the rest of D's core.

3. allow remove(..) to return a boolean if the key was removed.  An 
overloaded remove with an 'out key' paramter might be useful as well.

4. Upon implementing those, the don't create behavior is kept for normal 
lookups.

Comments?

Here's hoping Walter is reading...

-DavidM
Jul 13 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"David Medlock" <noone nowhere.com> wrote in message 
news:db3026$629$1 digitaldaemon.com...
 Walter,

 I really think the following is a good solution to the AA issues.

 1. Add a get method to all AAs:

 bool get( in key, out value );

 if the value is there, you get it and no double lookups.  A great side 
 effect of this is the out value is initialized to the default! Which 
 mimics the old behavior and allows you to determine if it was there.

question: would get() insert if not present? I assume not but that last sentance above made me not so sure. It might also be nice to have insert(key) which would equivalent to &aa[key] assuming & inserts key if it isn't present.
 2. Deprecate the in syntax.  It is really not useful because it cannot be 
 overridden if I wish to replace an AA with a class.  Semantically it has 
 no advantage to a method.  It also requires pointers which isn't really 
 required elsewhere in the rest of D's core.

overloading shall come someday. The current AA indexing behavior isn't overloadable either.
 3. allow remove(..) to return a boolean if the key was removed.  An 
 overloaded remove with an 'out key' paramter might be useful as well.

sounds good to me.
 4. Upon implementing those, the don't create behavior is kept for normal 
 lookups.

What do you mean by normal lookups? Do you mean rvalue aa[key]?
 Comments?

 Here's hoping Walter is reading...

 -DavidM 

Jul 13 2005
parent reply David Medlock <noone nowhere.com> writes:
Ben Hinkle wrote:

 "David Medlock" <noone nowhere.com> wrote in message 
 news:db3026$629$1 digitaldaemon.com...
 
Walter,

I really think the following is a good solution to the AA issues.

1. Add a get method to all AAs:

bool get( in key, out value );

if the value is there, you get it and no double lookups.  A great side 
effect of this is the out value is initialized to the default! Which 
mimics the old behavior and allows you to determine if it was there.

question: would get() insert if not present? I assume not but that last sentance above made me not so sure. It might also be nice to have insert(key) which would equivalent to &aa[key] assuming & inserts key if it isn't present.

I would assume it would not insert, which could be handled if it returned false. Since an insert into an AA isnt a lookup, this is still efficient. With get() I don't see a case where insert would be needed? MyClass var; if ( aa.get( key, var )==false ) aa[key] = ( var = new Class() );
2. Deprecate the in syntax.  It is really not useful because it cannot be 
overridden if I wish to replace an AA with a class.  Semantically it has 
no advantage to a method.  It also requires pointers which isn't really 
required elsewhere in the rest of D's core.

overloading shall come someday.

Overloading in? Whats wrong with a method? Seems like a novelty.... The current AA indexing behavior isn't
 overloadable either.
 

 
3. allow remove(..) to return a boolean if the key was removed.  An 
overloaded remove with an 'out key' paramter might be useful as well.

sounds good to me.
4. Upon implementing those, the don't create behavior is kept for normal 
lookups.

What do you mean by normal lookups? Do you mean rvalue aa[key]?

 
Comments?

Here's hoping Walter is reading...

-DavidM 


Jul 13 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"David Medlock" <noone nowhere.com> wrote in message 
news:db342u$97b$1 digitaldaemon.com...
 Ben Hinkle wrote:

 "David Medlock" <noone nowhere.com> wrote in message 
 news:db3026$629$1 digitaldaemon.com...

Walter,

I really think the following is a good solution to the AA issues.

1. Add a get method to all AAs:

bool get( in key, out value );

if the value is there, you get it and no double lookups.  A great side 
effect of this is the out value is initialized to the default! Which 
mimics the old behavior and allows you to determine if it was there.

question: would get() insert if not present? I assume not but that last sentance above made me not so sure. It might also be nice to have insert(key) which would equivalent to &aa[key] assuming & inserts key if it isn't present.

I would assume it would not insert, which could be handled if it returned false. Since an insert into an AA isnt a lookup, this is still efficient. With get() I don't see a case where insert would be needed? MyClass var; if ( aa.get( key, var )==false ) aa[key] = ( var = new Class() );

That's still a double-lookup. I don't know what you mean exactly when you say "an insert into an AA isn't a lookup". In order to insert a key you need to compute the hash value and find an available slot for it. In particular if the key is already in the AA then an insert is 99% the same amount of work as looking up a key, which computes the hash and find the existing slot. I thought you were looking for an API that would mimic the C++ API - the point being that missing keys are inserted and an lvalue is returned.
2. Deprecate the in syntax.  It is really not useful because it cannot be 
overridden if I wish to replace an AA with a class.  Semantically it has 
no advantage to a method.  It also requires pointers which isn't really 
required elsewhere in the rest of D's core.

overloading shall come someday.

Overloading in? Whats wrong with a method? Seems like a novelty.... The current AA indexing behavior isn't
 overloadable either.


yes. The only overloads are opIndex and opIndexAssign
Jul 13 2005
parent reply David Medlock <noone nowhere.com> writes:
Ben Hinkle wrote:

 "David Medlock" <noone nowhere.com> wrote in message 
 news:db342u$97b$1 digitaldaemon.com...
 
Ben Hinkle wrote:


"David Medlock" <noone nowhere.com> wrote in message 
news:db3026$629$1 digitaldaemon.com...


Walter,

I really think the following is a good solution to the AA issues.

1. Add a get method to all AAs:

bool get( in key, out value );

if the value is there, you get it and no double lookups.  A great side 
effect of this is the out value is initialized to the default! Which 
mimics the old behavior and allows you to determine if it was there.

question: would get() insert if not present? I assume not but that last sentance above made me not so sure. It might also be nice to have insert(key) which would equivalent to &aa[key] assuming & inserts key if it isn't present.

I would assume it would not insert, which could be handled if it returned false. Since an insert into an AA isnt a lookup, this is still efficient. With get() I don't see a case where insert would be needed? MyClass var; if ( aa.get( key, var )==false ) aa[key] = ( var = new Class() );

That's still a double-lookup. I don't know what you mean exactly when you say "an insert into an AA isn't a lookup". In order to insert a key you need to compute the hash value and find an available slot for it. In particular if the key is already in the AA then an insert is 99% the same amount of work as looking up a key, which computes the hash and find the existing slot.

I assume Walter uses a bucket hashmap. This means a linked list has an entry inserted at its head for the key's bucket. This is a constant time operation(basically nil). Computing the key is not usually a hefty task(most are ints most likely), but searching through the bucket of entries can be(depending on the load). With cache-sensitive processors I would bet searching through the bucket list takes quite a bit longer. Besides, even in the cases where the key takes a couple of extra milliseconds to compute, it only happens the *first time*. If that is the crux of your program's performance, I would say it either: 1. Needs a better data strategy. 2. Is as fast as it is going to be, barring assembly.
 I thought you were looking for an API that would mimic the C++ API - the
 point being that missing keys are inserted and an lvalue is returned.

I actually like the idea of a Rvalue (var= aa[100]) lookup simply returning the default and *not creating* an entry, but this would break due to arrays being null proof... -DavidM
Jul 13 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"David Medlock" <noone nowhere.com> wrote in message 
news:db36p6$bt9$1 digitaldaemon.com...
 Ben Hinkle wrote:

 "David Medlock" <noone nowhere.com> wrote in message 
 news:db342u$97b$1 digitaldaemon.com...

Ben Hinkle wrote:


"David Medlock" <noone nowhere.com> wrote in message 
news:db3026$629$1 digitaldaemon.com...


Walter,

I really think the following is a good solution to the AA issues.

1. Add a get method to all AAs:

bool get( in key, out value );

if the value is there, you get it and no double lookups.  A great side 
effect of this is the out value is initialized to the default! Which 
mimics the old behavior and allows you to determine if it was there.

question: would get() insert if not present? I assume not but that last sentance above made me not so sure. It might also be nice to have insert(key) which would equivalent to &aa[key] assuming & inserts key if it isn't present.

I would assume it would not insert, which could be handled if it returned false. Since an insert into an AA isnt a lookup, this is still efficient. With get() I don't see a case where insert would be needed? MyClass var; if ( aa.get( key, var )==false ) aa[key] = ( var = new Class() );

That's still a double-lookup. I don't know what you mean exactly when you say "an insert into an AA isn't a lookup". In order to insert a key you need to compute the hash value and find an available slot for it. In particular if the key is already in the AA then an insert is 99% the same amount of work as looking up a key, which computes the hash and find the existing slot.

I assume Walter uses a bucket hashmap. This means a linked list has an entry inserted at its head for the key's bucket. This is a constant time operation(basically nil). Computing the key is not usually a hefty task(most are ints most likely), but searching through the bucket of entries can be(depending on the load). With cache-sensitive processors I would bet searching through the bucket list takes quite a bit longer. Besides, even in the cases where the key takes a couple of extra milliseconds to compute, it only happens the *first time*. If that is the crux of your program's performance, I would say it either: 1. Needs a better data strategy. 2. Is as fast as it is going to be, barring assembly.

Actually the current AA implementation doesn't use a linked list of buckets - it uses an unbalanced tree (or perhaps more accurately the tree will be balanced if the hashing algorithm is good). In any case "inserting" a key that is already in the map needs to locate and reuse the existing bucket otherwise you'll end up with duplicate entries in the map. So insert is essentially the same as a lookup. I agree if you know a key is not in the map and the map is using a linked list of buckets that inserting is faster than lookup but neither of those assumptions would be true for the "insert" function I was talking about. But I agree performance isn't the crucial difference. Convenience and making the code more explicit would probably be the true benefits.
 I thought you were looking for an API that would mimic the C++ API - the
 point being that missing keys are inserted and an lvalue is returned.

I actually like the idea of a Rvalue (var= aa[100]) lookup simply returning the default and *not creating* an entry, but this would break due to arrays being null proof...

ok.
Jul 13 2005
parent David Medlock <noone nowhere.com> writes:
Ben Hinkle wrote:

 "David Medlock" <noone nowhere.com> wrote in message 
 news:db36p6$bt9$1 digitaldaemon.com...
 
I assume Walter uses a bucket hashmap.  This means a linked list has an 
entry inserted at its head for the key's bucket.  This is a constant time 
operation(basically nil). Computing the key is not usually a hefty 
task(most are ints most likely), but searching through the bucket of 
entries can be(depending on the load). With cache-sensitive processors I 
would bet searching through the bucket list takes quite a bit longer.

Besides, even in the cases where the key takes a couple of extra 
milliseconds to compute, it only happens the *first time*.

If that is the crux of your program's performance, I would say it either:
1. Needs a better data strategy.
2. Is as fast as it is going to be, barring assembly.

Actually the current AA implementation doesn't use a linked list of buckets - it uses an unbalanced tree (or perhaps more accurately the tree will be balanced if the hashing algorithm is good).

Interesting, I didn't know this. In any case "inserting"
 a key that is already in the map needs to locate and reuse the existing 
 bucket otherwise you'll end up with duplicate entries in the map. So insert 
 is essentially the same as a lookup. 

True. Mea culpa.
 But I agree performance isn't the crucial difference. Convenience and making 
 the code more explicit would probably be the true benefits.
 

Hehe, right on. My work time is a constant, while the computer gets more 'work time' constantly(Moore's law). Thanks Ben. -DavidM
Jul 13 2005