I have a situation where I call a method to retrieve a value from a dictionary. In some situations this method is called a lot - with a very large set of test data (not really real world, but potentially the upper limit of what would be realistic) one section of my app may call this method several million times.
Here is the original version:
if dbPrefs.HasKey(key) then
What I’m wondering is whether I really need the hasKey() call in there at all, or if I could just do this instead:
Exception err as RuntimeException
I plan to use the profiler to see which feels faster, but wanted to know if one is a better approach for some reason, and if so, why?
I would think a positive event (hasKey) would be more effective than a Negative event.
For HasKey it is a hashed lookup… which will succeed or fail in a known and graceful manner
While allowing it to exception out invokes (I believe) not only the same requirements of HasKey (it has to know it failed), plus the addtion of processing the execption message events.
Have you considered the use of Lookup ?
Yes, but the failure rate should be very low. Perhaps only 1 in 1000 hits to this method would potentially fail.
In fact, it should be even lower than that, since I actually control all the keys it would ever look for. There are some circumstances where it will fail, but they should be quite rare.
So an expensive exception handler should be ok if it is rarely invoked.
I had not considered .lookup, because I didn’t know it existed… That’s what I get for learning the Xojo apis so long ago and not really re-reading all the docs for stuff I think I already understand.
Then again, .lookup may have been there forever.
At any rate, I wonder if .lookup is just hitting .hasKey under the hood to decide what to return.
I see your concern. If looking up a key takes x milliseconds, aren’t you doubling it by checking HasKey first, then returning the value? My guess is that Lookup is designed specifically to avoid that, but it’s easy enough to test.
In fact, I think I’ll test it now
Yeah, I’ve been using the profiler to check tweaks to things. My initial results show that the hasKey() check was actually faster than having an exception handler in there, but then I found an error that was sending a LARGE number of incorrect keys, so it was hitting the exception handler nearly 80% of the time.
I’ve fixed that, and am profiling again. Should have results in a few minutes.
I just tested with a 1% failure rate. I created a Dictionary with the keys set to each value from 1-99. Then I retrieved the values with keys from 1-100, and I did that 1,000 times. Results:
Lookup: 63,365 microsecs
HasKey: 107,584 microsecs
Exception: 2,807,338 microsecs
Conclusion: Use Lookup. Do NOT use Exceptions.
Here’s an interesting side-result. I reduced my If statement for HasKey to a single line, but that version actually takes slightly longer than doing it with the traditional construct:
dim x as integer = if( Dict.HasKey( i ), Dict.Value( i ).IntegerValue, 0 )
dim x as integer
if Dict.HasKey( i ) then
x = Dict.Value( i )
x = 0
HasKey: 108,287 microsecs
HasKey (single line): 118,373 microsecs
I can’t see why that would be.
Most likely variations in the underlying business of your system. Also, your sample size is pretty small - would be interesting to see if those ratios still hold true for both a larger sample size and a larger number of lookups. I’m working up an alternate test that is closer to what I’m actually doing. I’ll be back in a bit with numbers.
OK, I tested with keys from 1-9,999 and lookups from 1-10,000, repeated 1,000 times. The ratio between Lookup and HasKey held true, but Exceptions were faster than HasKey probably due to the very small failure rate. However, Lookups were still faster.
My next test it to increase the failure rate to 2%.
BTW, I’m using the Try/Catch structure to handle the Exceptions.
Keeping the repetitions roughly the same, I increased the failure rate to 2% and the ratio of Lookup to HasKey remains true with Lookup taking a little more than half the time as HasKey. I’d tell you the results with Exceptions, but it hasn’t finished running yet, so
I tested by creating a dictionary with a million buckets. Each key/value pair is a uuid for the key and another uuid for the value.
I then lookup every single key in the dictionary with lookup, hasKey, and Exception versions.
Here are my numbers:
Lookup: 2391430 Microseconds (2.39 seconds)
HasKey: 3034409 Microseconds (3.03 seconds)
Exception: 2335724 Microseconds (2.33 seconds)
Now, this is with a 100% hit rate (which my app currently has). So, if you can control the keys in the dictionary and the values you use for lookups are guaranteed to always be one of those keys, it looks like the exception version is actually best.
I am not using a try/catch - just an exception block at the end of the action on a button that does does the work.
Seriously though, how long has lookup been there? I’ve been using my own extension method to do the same thing for years. Can’t believe I’ve missed this basic function.
From the modified date on the language docs it’s been there since at least January of 2012.
If it has 100% hit rate, and you’re sure it will remain so (or nearly so), then I guess the Exception method provides the best optimization since it’s never used. For the difference, however, I’d still go with Lookup.
I just tried with a 0% failure rate and my results match yours. Value is faster than Lookup.
Since roughly the time fire was invented. Don’t feel bad, though. I’ve been using the product since 1.0 (or so I’m told) and am still finding features I didn’t know about.
We’ve beaten this horse to death, but I’ve got more results confirming what Kem found.
With 100 failures in 1M lookups:
With 1,000 failures in 1M lookups:
Exception: 7089259 (ouch!)
With 10,000 failures in 1M lookups:
Exception: 36316397 (36 seconds!)
So, if your miss rate will be less than 1/10th of 1%, it is probably faster to use an exception to handle any misses. Otherwise, just use lookup.
[quote=77632:@Kimball Larsen]I had not considered .lookup, because I didn’t know it existed… That’s what I get for learning the Xojo apis so long ago and not really re-reading all the docs for stuff I think I already understand.
Then again, .lookup may have been there forever.
It has been there for a VERY long time if not literally “forever”
I’ve seen variances like that in debug runs but they go away in a compiled app. It also could be the one liner uses the ternary if.
Are these timings in a compiled app with pragmas?