Silver Searcher Tab Completion with Exuberant Ctags

Improve your Silver Searcher game by introducing tab completion in zsh based on the tags file of the project.

Weird stuff with hashes

February 11, 2015

Ok, so this isn’t really weird stuff, I don’t think. But maybe people don’t know about it so I thought I would post.

Hashes dup string keys

When you assign a string key to a hash, the hash copies the string and freezes it. Here is an example:

>> x = 'string'
=> "string"
>> y = {}
=> {}
>> y[x] = :value
=> :value
>> { x => y.keys.first }
=> {"string"=>"string"}
>> { x.object_id => y.keys.first.object_id }
=> {70157126548460=>70157126526760} # object ids are different
>> { x.frozen? => y.keys.first.frozen? }
=> {false=>true} # frozen value is different

You can prevent the string from being duped by freezing the string before putting it in the hash:

>> x = 'string'
=> "string"
>> x.freeze
=> "string"
>> y = {}
=> {}
>> y[x] = :value
=> :value
>> { x.object_id => y.keys.first.object_id }
=> {70157126414020=>70157126414020} # note that both object ids are the same

Why is this important?

I’ve been working with @eileencodes to improve the performance of integration tests in Rails. It turns out that the tests are spending a significant amount of time in the garbage collector. We started tracking down allocations, and found that setting values in the header hash was creating many strings.

To partially fix this, we added a freeze to the string before inserting it in to the header hash. This cut the allocations down. The code used to allocate one string for the “downcased” version, then another when the downcased version was inserted in to the hash.

Setting strings as hash keys may be a source of unnecessary object allocation in your application. Now, don’t go freezing all the strings. Make sure to measure where object allocations are happening in your app first (a subject that I’ll cover in a later blog post), then freeze strings where appropriate.

Why does the Hash dup strings?

I think there are a few reasons.

One, if you mutate the string after adding it to the hash, it would be surprising (to me anyway) if the key for the hash was mutated too. For example:

>> x = 'string'
=> "string"
>> y = {}
=> {}
>> y[x] = :value
=> :value
>> x.sub!(/r/, '')
=> "sting"
>> y.key? x
=> false
>> { y.keys => x }
=> {["string"]=>"sting"}

I think it would be pretty surprising if, after mutating the object in place, it would still be part of the hash.

I think the other more technical reason is that mutating the string changes the hash value of the string, and means your hash would need to be rehashed in order to find the same key:

>> x.hash
=> 4078764570319932244
>> x.sub!(/r/, '')
=> "sting"
>> x.hash
=> -1518905602476999392

Note that the hash value changed.

Hash value, what does that have to do with anything?

If you change the hash value of a hash key, then the key will be in the wrong place in the hash. I think this might be more clear with a code example.

You may know about the two methods you need to implement for creating a custom hash key: hash indicates where in the hash the object will be stored, and eql? is used in the case there is a hash collision.

Lets make an object that allows us to mutate the hash value, and see how it behaves after inserting it in a hash:

class Foo
  attr_accessor :hash
end

x = Foo.new
x.hash = 10

hash = {}
hash[x] = :hello

p hash.key?(x)          # => true
p hash.keys.include?(x) # => true

x.hash = 11 # change the hash value

p hash.key?(x)          # => false
p hash.keys.include?(x) # => true

hash.rehash

p hash.key?(x)          # => true
p hash.keys.include?(x) # => true

First we see that x is a key to the hash, and is in the list of keys. After we mutate the hash value, Hash#key? returns false, yet Array#include? returns true when we check for the object in the list of keys.

The reason Hash#key? returns false is because it’s using the value of hash to find the object in the hash buckets. When we first inserted the object in the hash, it went in to the “10” bucket. But now that we’ve changed the value to “11”, the hash will look for the object in the “11” bucket, which is the wrong place!

To fix this, we call the rehash method on the hash. The rehash method will redistribute the keys. Since the object in the “10” bucket is now supposed to be in the “11” bucket, it will move the object to the right place, and Hash#key? will work correctly.

Wouldn’t it be annoying if you had to do the same song and dance as this if you mutated your strings? I think this is the main reason why hashes dup and freeze string keys.

What is the lesson?

Don’t mutate the hash value on hash keys! You’ll have a bad time.

Anyway, I don’t think this is weird or anything, it’s just something that we don’t have to deal with on a day to day basis. Maybe I should have titled the post “Uncommon things to do with hashes”.

Thanks for reading!!! <3<3<3<3<3

Performance P.S. (is that a P.P.S.?)

An interesting thing is that Hash#dup will rehash the newly created hash, where Hash[] will not:

class Foo
  attr_accessor :hash
end

x = Foo.new
x.hash = 10

hash = {}
hash[x] = :hello

p hash.key?(x)          # => true

x.hash = 11 # change the hash value

p hash.key?(x)          # => false
p hash.dup.key?(x)      # => true
p Hash[hash].key?(x)    # => false

This means that duping a hash with Hash[] can end up being faster than using Hash#dup. Here is a benchmark to demonstrate:

require 'benchmark/ips'

hash = Hash[*('a'..'z').to_a]
Benchmark.ips do |x|
  x.report("Hash#dup") do
    hash.dup
  end

  x.report("Hash[]") do
    Hash[hash]
  end
end

Results on my machine:

Calculating -------------------------------------
            Hash#dup     7.705k i/100ms
              Hash[]    15.978k i/100ms
-------------------------------------------------
            Hash#dup     93.648k (± 4.9%) i/s -    470.005k
              Hash[]    230.497k (±11.2%) i/s -      1.150M

Does this mean that you should switch to Hash[]? Only if your benchmarks can prove that it’s a bottleneck. Please please please don’t change all of your code because this shows it’s faster. Make sure to measure your app performance first. But you already knew that, which is why you’re reading the PS section. ;-)

[…]

Estimating versus Timeboxing, part 1

June 10, 2009

As if delivering projects wasn’t hard enough. Delivering projects on time is even harder. As practitioners, we’re all responsible for measuring up the obstacles in front of us and are accountable to those measurements. At least, we should be.

One of those measurements is time. Time is a funny thing. People have a lot of interesting things to say about time. Some say that it’s one of the most valuable things that we have… but I’ll avoid diving into a philosophical discussion for now.

What I wanted to talk about was project estimation. Specifically, estimates for deliverables. For the past several years, our team has put a lot of effort into becoming more accurate in our time estimating skills. Despite analyzing how often we over and/or underestimate the time each of us believes it’ll take to complete a task, we find ourselves coming back to the drawing board.

A few things that we’ve learned.

Tasks that we believe will take a few days/week/more to complete are often underestimated
Tasks that we believe will take less than a few hours are often more accurate or overestimated
Too many tasks were completed with a bigger budget than was necessary (lower ROI)
A lot of time was spent working on requirements refining to get better estimates

When we began to step back from this and look for patterns, we found that several of the tasks that we would budget hours for (versus estimate hours for) were proving to be more accurate. This approach is most commonly known as timeboxing. With timeboxing, we can place a dollar value on a specific task and work within that constraint. For example, with our clients, both parties can come to the conclusion that, “we believe that it’s worth up to $800 to implement this new functionality.” With that, we’re able take that dollar amount and figure out how many hours to box ourselves within.

The underlying question to our client with each change/feature request is, “How valuable is this to your business at this point in time?” Whereas, with a typical approach to time estimates, a client comes to you with a list of changes/features and you provide them with time estimates. “We estimate that it’ll take 6 hours at $200/hour for feature X and we’d do it like this…” The client will have to evaluate your estimate and figure out if it’s worth $1200 and make a decision. They can respond with, “no, that’s too expensive, can we do it for less?” The following steps would entail your team trying to find ways to reduce your estimate.

While these two paths might seem very similar, it’s been my experience that the standard approach to estimating takes more time for negotiating the terms of the agreement.

However, with timeboxing, you are asking your client to provide you with an initial budget. This will completely change how you respond to the feature request. When you have a timebox, from the moment that you begin to evaluate the request, your brain will add the necessary constraints to keep things within scope.

Through this process, we’ve revamped our estimating process so that as we’re building our iteration costs for clients. For each deliverable, we break down a series of objectives/tasks and apply timeboxes to each of those while knowing what the budget is for the deliverable as a whole. Usually, the deliverable is directly related to the request that came from our client with a budget. The process is completely transparent and our team is responsible for working within those constraints.

..and as we’ve learned from Ruby on Rails, constraints can be extremely beneficial.

While I don’t have all the answers yet, my goal is to share some of my experiences and lessons on the topic. I’d love to hear about how you’re adopting timeboxing in your project planning and estimating process.

Anyhow, just some thoughts that I wanted to share. More to come…

Read Related Articles

[…]

The Ruby Rails Aggregator