Hash has_key? improvement

Crystal Contrib
1

I’ve been doing a lot of profiling to speed up a very critical piece of code lately. The algorithm uses a large lookup table that is generated with a macro and I was checking if the value was in the table by using has_key?. The heaviest part of my algorithm ended up being that and a lot of time was spent in that call. I’m newish to Crystal so apologies, but was there a reason a more naive approach wasn’t taken?

The approach I use:

  def has_key?(key) : Bool
    !!self[key]?
  end

Current :

  def has_key?(key) : Bool
    !!find_entry(key)
  end

Simple test benchmark checking all keys in a generated lookup table:

current has_key  24.63k ( 40.60µs) (± 1.00%)  0.0B/op   1.82× slower
    new has_key  44.82k ( 22.31µs) (± 0.98%)  0.0B/op        fastest

Making that change caused it to not even show up on the profiler. Just wanted to see if there were other implications that were the reason for the current approach.

2

At a high level I’m somewhat surprised it makes a difference since #[]? ends up calling #find_entry anyway via #fetch. So would have thought #[]? would be slower since it ends up making more method calls.

1 Like
3

Disregard. After more profiling it came down to an extra branch in the old code that had the has_key check.
The old code as like this:

 table.has_key?(key) ? table[key] : default_value

New code after another optimization pass:

 table[key]? || default_value

My apologies, it’s been a long week of profiling and optimizing that I missed that I dropped the ternary approach as well. So I guess moral is that extra branch is slower than ||.

1 Like
4

I don’t think it would make much difference, but could also do table.fetch key, default_value.

5

Just gave that a try and ran it a couple times and it flip/flops between which is faster by 1.01-1.04x so doesn’t seem to make a difference. Though it is more readable in a sense, but I do feel the || is a little more explicit than the ,

Again, sorry about the initial non-issue.

6

The #[]? approach breaks if a key exists but its corresponding value is falsey.

1 Like
7

Ah yeah, that is true. In my case I wasn’t storing Bools but that would definitely be an issue.

You could also just do #[]?.nil? instead, but again this is a actually a non-issue and something that seemed to be a problem when it was something else.