Auto merge of #5539 - jules2689:master, r=segiddins

Change LockFileParse dependencies class variable from an array to a hash

What this addresses
---
The LockFileParser dependenies class variable is used throughout definition
using a series of select and find statements. While measuring Bundler performance, it was
noticed that pieces that interacted with @locked_deps took a fair chunk of time.

This chart shows some timings for `Definition.new` which is called during `require 'bundler/setup'`

![image](https://cloud.githubusercontent.com/assets/3074765/24419149/39598a98-13bc-11e7-8fa5-ee255abd79c3.png)

** Note: The time scale is a little off because `TracePoint` slows it down, but this does show us a slow point we can optimize.

Diving into that a bit more, we can see the following timings

![image](https://cloud.githubusercontent.com/assets/3074765/24419245/82891774-13bc-11e7-9449-6a0b0c28d520.png)

Again, despite the timings being off due to TracePoint, we can see that `locked_source = @locked_deps.select {|d| d.name == dep.name }.last (run 112812 times) :a1, 0.001, 0.182` was run upwards of 113K times for the Shopify application. Each one of these runs would run in `O(n)` time since we are literally iterating the array.

Looking at `LockFileParser`, we can see that the `dependencies` can easily be changed to a hash.

How this addresses it
---
This change makes the dependencies class variable a hash, which reduces the lookup
from `O(n)` to `O(1)` for each usage. Overall, the operation was `O(n^2)` as we iterated the array for each entry in the array. Now it's `O(n)` :tada:

In the Shopify application, this equated to a 20ms performance gain on each bundler/setup.

Some numbers
---
In particular, the `converge_dependencies` method in `definition.rb` took, on average, 24 ms for an application the size of Shopify. By simply changing the `dependencies` class variable, this was knocked down to 12ms. There was also a savings of a few ms on other method calls, such as `converge_locked_specs`.

Overall, I saw the time to `require 'bundler/setup'` from from 744ms to 724ms for a savings of 20ms.

2 files changed, 17 insertions, 18 deletions

diff --git a/lib/bundler/definition.rb b/lib/bundler/definition.rb
index 8e8897df02..5bff85332f 100644
--- a/lib/bundler/definition.rb
+++ b/lib/bundler/definition.rb
@@ -81,7 +81,7 @@ module Bundler
           @locked_sources = @locked_gems.sources
         else
           @unlock         = {}
-          @locked_deps    = []
+          @locked_deps    = {}
           @locked_specs   = SpecSet.new([])
           @locked_sources = []
         end
@@ -89,7 +89,7 @@ module Bundler
         @unlock         = {}
         @platforms      = []
         @locked_gems    = nil
-        @locked_deps    = []
+        @locked_deps    = {}
         @locked_specs   = SpecSet.new([])
         @locked_sources = []
         @locked_platforms = []
@@ -132,7 +132,7 @@ module Bundler
       # with a mismatch on #type.
       # Test coverage to catch a regression on this is in gemspec_spec.rb
       @dependencies.each do |d|
-        if ld = @locked_deps.find {|l| l.name == d.name }
+        if ld = @locked_deps[d.name]
           ld.instance_variable_set(:@type, d.type)
         end
       end
@@ -429,8 +429,8 @@ module Bundler
       new_sources = gemfile_sources - @locked_sources
       deleted_sources = @locked_sources - gemfile_sources
 
-      new_deps = @dependencies - @locked_deps
-      deleted_deps = @locked_deps - @dependencies
+      new_deps = @dependencies - @locked_deps.values
+      deleted_deps = @locked_deps.values - @dependencies
 
       # Check if it is possible that the source is only changed thing
       if (new_deps.empty? && deleted_deps.empty?) && (!new_sources.empty? && !deleted_sources.empty?)
@@ -455,7 +455,7 @@ module Bundler
 
       both_sources = Hash.new {|h, k| h[k] = [] }
       @dependencies.each {|d| both_sources[d.name][0] = d }
-      @locked_deps.each  {|d| both_sources[d.name][1] = d.source }
+      @locked_deps.each  {|name, d| both_sources[name][1] = d.source }
 
       both_sources.each do |name, (dep, lock_source)|
         next unless (dep.nil? && !lock_source.nil?) || (!dep.nil? && !lock_source.nil? && !lock_source.can_lock?(dep))
@@ -586,7 +586,7 @@ module Bundler
 
     def dependencies_for_source_changed?(source, locked_source = source)
       deps_for_source = @dependencies.select {|s| s.source == source }
-      locked_deps_for_source = @locked_deps.select {|s| s.source == locked_source }
+      locked_deps_for_source = @locked_deps.values.select {|dep| dep.source == locked_source }
 
       Set.new(deps_for_source) != Set.new(locked_deps_for_source)
     end
@@ -639,7 +639,7 @@ module Bundler
       @locked_specs.each do |spec|
         spec.source &&= converge_path_source_to_gemspec_source(spec.source)
       end
-      @locked_deps.each do |dep|
+      @locked_deps.each do |_, dep|
         dep.source &&= converge_path_source_to_gemspec_source(dep.source)
       end
     end
@@ -681,8 +681,8 @@ module Bundler
     end
 
     def converge_dependencies
-      (@dependencies + @locked_deps).each do |dep|
-        locked_source = @locked_deps.select {|d| d.name == dep.name }.last
+      (@dependencies + @locked_deps.values).each do |dep|
+        locked_source = @locked_deps[dep.name]
         # This is to make sure that if bundler is installing in deployment mode and
         # after locked_source and sources don't match, we still use locked_source.
         if Bundler.settings[:frozen] && !locked_source.nil? &&
@@ -696,7 +696,7 @@ module Bundler
         end
       end
       dependency_without_type = proc {|d| Gem::Dependency.new(d.name, *d.requirement.as_list) }
-      Set.new(@dependencies.map(&dependency_without_type)) != Set.new(@locked_deps.map(&dependency_without_type))
+      Set.new(@dependencies.map(&dependency_without_type)) != Set.new(@locked_deps.values.map(&dependency_without_type))
     end
 
     # Remove elements from the locked specs that are expired. This will most
@@ -709,12 +709,11 @@ module Bundler
       # and Gemfile.lock. If the Gemfile modified a dependency, but
       # the gem in the Gemfile.lock still satisfies it, this is fine
       # too.
-      locked_deps_hash = @locked_deps.inject({}) do |hsh, dep|
-        hsh[dep] = dep
-        hsh
-      end
       @dependencies.each do |dep|
-        locked_dep = locked_deps_hash[dep]
+        locked_dep = @locked_deps[dep.name]
+
+        # If the locked_dep doesn't match the dependency we're looking for then we ignore the locked_dep
+        locked_dep = nil unless locked_dep == dep
 
         if in_locked_deps?(dep, locked_dep) || satisfies_locked_spec?(dep)
           deps << dep
diff --git a/lib/bundler/lockfile_parser.rb b/lib/bundler/lockfile_parser.rb
index d885c049d2..8d89b8b4a3 100644
--- a/lib/bundler/lockfile_parser.rb
+++ b/lib/bundler/lockfile_parser.rb
@@ -61,7 +61,7 @@ module Bundler
     def initialize(lockfile)
       @platforms    = []
       @sources      = []
-      @dependencies = []
+      @dependencies = {}
       @state        = nil
       @specs        = {}
 
@@ -199,7 +199,7 @@ module Bundler
           end
         end
 
-        @dependencies << dep
+        @dependencies[dep.name] = dep
       end
     end