drop millions of allocations by using a linked list #1188

tenderlove · 2015-03-13T03:18:12Z

I'm sending a PR because the reduction in allocations is so surprising to me that I'm afraid it's wrong. All tests pass on my machine, and I think it's backwards compatible, but I need review. /cc @evanphx @drbrain

Use a linked list to drop array allocations. The previous
implementation would dup arrays on every call to traverse. This patch
uses a linked list so that any block that is interested in keeping a
reference to trail can just keep the trail node around (the trail node
points at it's parents).

This approach reduces allocations from 11173668, to 2940.

Here is the test I used:

require 'stackprof'
require 'allocation_tracer'
require 'rubygems/test_case'
require 'rubygems/ext'
require 'rubygems/specification'
require 'benchmark'

class TestGemSpecification < Gem::TestCase
  def test_runtime
    make_gems do
      StackProf.run(mode: :wall, out: '/tmp/out.dump') do
        assert_raises(LoadError) { require 'no_such_file_foo' }
      end
    end
  end

  def test_alone
    make_gems do
      tms = Benchmark.measure {
        assert_raises(LoadError) { require 'no_such_file_foo' }
      }
      p tms.total
      assert_operator tms.total, :<=, 10
    end
  end

  def test_memory
    make_gems do
      ObjectSpace::AllocationTracer.setup(%i{path line type})
      r = ObjectSpace::AllocationTracer.trace do
        assert_raises(LoadError) { require 'no_such_file_foo' }
      end

      r.sort_by { |k,v| v.first }.each do |k,v|
        p k => v
      end
      p hash_alloc: ObjectSpace::AllocationTracer.allocated_count_table[:T_HASH]
      p array_alloc: ObjectSpace::AllocationTracer.allocated_count_table[:T_ARRAY]
      p :TOTAL => ObjectSpace::AllocationTracer.allocated_count_table.values.inject(:+)
    end
  end

  def make_gems
    save_loaded_features do
      num_of_pkg = 7
      num_of_version_per_pkg = 3
      packages = (0..num_of_pkg).map do |pkgi|
        (0..num_of_version_per_pkg).map do |pkg_version|
          deps = Hash[(pkgi..num_of_pkg).map { |deppkgi| ["pkg#{deppkgi}", ">= 0"] }]
          new_spec "pkg#{pkgi}", pkg_version.to_s, deps
        end
      end
      base = new_spec "pkg_base", "1", {"pkg0" => ">= 0"}

      Gem::Specification.reset
      install_specs base,*packages.flatten
      base.activate

      yield
    end
  end
end

Before:

{:TOTAL=>11173668}

After:

{:TOTAL=>2940}

tenderlove · 2015-03-13T03:21:15Z

I think this will fix #1169 and #1167

tenderlove · 2015-03-13T03:27:04Z

Also the runtime test:

master:

[aaron@TC rubygems (master)]$ ruby -I lib:test test.rb -n test_runtime 
Run options: -n test_runtime --seed 52721

# Running tests:

.

Finished tests in 34.727601s, 0.0288 tests/s, 0.0288 assertions/s.

1 tests, 1 assertions, 0 failures, 0 errors, 0 skips

This branch:

[aaron@TC rubygems (omg)]$ ruby -I lib:test test.rb -n test_runtime 
Run options: -n test_runtime --seed 7522

# Running tests:

.

Finished tests in 0.050260s, 19.8965 tests/s, 19.8965 assertions/s.

1 tests, 1 assertions, 0 failures, 0 errors, 0 skips

kuldeepaggarwal · 2015-03-13T03:27:54Z

@tenderlove: Awesome.. 👍

jcutrell · 2015-03-13T03:31:04Z

This is one of the coolest merge requests I've seen for so many reasons.

AnatoliiD · 2015-03-13T03:32:49Z

Yeah! Really awesome! 👍 👍 👍

evanphx · 2015-03-13T03:34:58Z

I'd believe it. But look at the linked list that resolver uses for exactly the same reasons, maybe we can use it here too.

tenderlove · 2015-03-13T03:41:29Z

@evanphx where can I find it? I don't know the resolver code very well.

tomciopp · 2015-03-13T03:53:22Z

@tenderlove I believe the code you are looking for is here:
https://github.com/rubygems/rubygems/blob/master/lib/rubygems/util/list.rb

tenderlove · 2015-03-13T04:33:47Z

@tomciopp thanks!

I've updated the PR to use the built-in linked list class. I think we can implement the current instance method traverse in terms of the class method I've introduced (though ultimately I'd like to deprecate the instance method), but I will do that if this PR is acceptable for merging.

skunkworker · 2015-03-13T10:50:19Z

lib/rubygems/specification.rb

+        stack = Gem::List.new(dep_spec, trail)
+        block[dep_spec, stack]
+        spec_name = dep_spec.name
+        traverse(dep_spec, stack, &block) unless


I may be wrong but shouldn't this be _traverse instead?

Adding a?

private_class_method :_traverse

libo · 2015-03-13T11:05:44Z

👍

chus · 2015-03-13T13:15:59Z

👍

byroot · 2015-03-13T13:25:00Z

lib/rubygems/util/list.rb

@@ -2,6 +2,8 @@ module Gem
  List = Struct.new(:value, :tail)

  class List
+    include Enumerable


If you include Enumerable you don't need the explicit find implementation anymore. The to_a implementation could go too if Struct didn't have a default one.

I'd rather do that in a different commit. 😨

@byroot This isn't quote true. You have to remove Struct (which has its own Enumerable inclusion and meaning), and reverse the to_a. See PR #1200 ;)

pawitk · 2015-03-13T13:59:54Z

👍

libo · 2015-03-13T14:22:17Z

Is the merge button you have to click @tenderlove,

tenderlove · 2015-03-13T14:24:24Z

@libo hah, I closed and reopened to get travis to build again.

libo · 2015-03-13T14:30:38Z

:-) eheh

By this PR was a hell of a #fridayhug thanks @tenderlove !

canweriotnow · 2015-03-13T14:38:41Z

draffauf · 2015-03-13T15:18:27Z

Mind blown. Great job.

Use a linked list to drop array allocations. The previous implementation would dup arrays on every call to `traverse`. This patch uses a linked list so that any block that is interested in keeping a reference to `trail` can just keep the trail node around (the trail node points at it's parents). This approach reduces allocations from 11173668, to 2940. Here is the test I used: ```ruby require 'stackprof' require 'allocation_tracer' require 'rubygems/test_case' require 'rubygems/ext' require 'rubygems/specification' require 'benchmark' class TestGemSpecification < Gem::TestCase def test_runtime make_gems do StackProf.run(mode: :wall, out: '/tmp/out.dump') do assert_raises(LoadError) { require 'no_such_file_foo' } end end end def test_alone make_gems do tms = Benchmark.measure { assert_raises(LoadError) { require 'no_such_file_foo' } } p tms.total assert_operator tms.total, :<=, 10 end end def test_memory make_gems do ObjectSpace::AllocationTracer.setup(%i{path line type}) r = ObjectSpace::AllocationTracer.trace do assert_raises(LoadError) { require 'no_such_file_foo' } end r.sort_by { |k,v| v.first }.each do |k,v| p k => v end p hash_alloc: ObjectSpace::AllocationTracer.allocated_count_table[:T_HASH] p array_alloc: ObjectSpace::AllocationTracer.allocated_count_table[:T_ARRAY] p :TOTAL => ObjectSpace::AllocationTracer.allocated_count_table.values.inject(:+) end end def make_gems save_loaded_features do num_of_pkg = 7 num_of_version_per_pkg = 3 packages = (0..num_of_pkg).map do |pkgi| (0..num_of_version_per_pkg).map do |pkg_version| deps = Hash[(pkgi..num_of_pkg).map { |deppkgi| ["pkg#{deppkgi}", ">= 0"] }] new_spec "pkg#{pkgi}", pkg_version.to_s, deps end end base = new_spec "pkg_base", "1", {"pkg0" => ">= 0"} Gem::Specification.reset install_specs base,*packages.flatten base.activate yield end end end ``` Before: {:TOTAL=>11173668} After: {:TOTAL=>2940}

sstelfox · 2015-03-13T15:48:41Z

Wow awesome. Nice find!

renatorozas · 2015-03-13T16:01:33Z

Way to go @tenderlove

vcavallo · 2015-03-13T16:53:11Z

8 O

amaltson · 2015-03-13T19:42:13Z

Awesome work @tenderlove, can't wait for this to be released 😄

gbxl · 2015-03-13T20:22:22Z

Dude that's awesome! Good job.

zeevallin · 2015-03-13T20:34:42Z

@tenderlove No matter what people on the internet say, what you're doing is fantastic. Please don't get discouraged. Thank you for spotting and optimising this! #FridayHug

seandmccarthy · 2015-03-13T20:38:28Z

lib/rubygems/specification.rb

+        stack = Gem::List.new(dep_spec, trail)
+        block[dep_spec, stack]
+        spec_name = dep_spec.name
+        _traverse(dep_spec, stack, &block) unless


I may have missed something, but I think this should be traverse rather than _traverse as the former is the only one (I can see) with a 3 element signature.

I think you have that backwards; traverse takes 1 param + block, _traverse takes 2 + block. And in any case the Gem::List is generated prior to the invocation, so traverse wouldn't be appropriate anyhow.

Yeah sorry, scratch that. I was looking at an earlier version and the call is correct now.

cheald · 2015-03-13T20:54:55Z

👍

drop millions of allocations by using a linked list

ghost · 2015-03-13T22:14:23Z

👍

tenderlove · 2015-03-13T23:25:36Z

@mfazekas you are totally right. Think we should revert?

mfazekas · 2015-03-16T08:48:35Z

@tenderlove i think it have to be reverted, and we need to add some test that fails with that implementation.

tenderlove · 2015-03-16T15:38:18Z

@mfazekas do you have any idea how to make a test that fails with this implementation? I don't want to revert until we can prove it's wrong (no doubt it is wrong, just need to make a test).

mfazekas · 2015-03-16T15:44:31Z

i'll try to came up with a testcase sometime later today

mfazekas · 2015-03-17T15:37:31Z

#1191 shows is a testcase, demonstrating the issue with your optimization. But it also shows that the original one despite all the multiple reverse's and exponential algorithm will prefer earlier and not later versions.

So we use find_in_unresolved_tree in case we cannot find a required file in any of the activated gems. The idea is that we check indirect dependencies of the activated gems and try to select a gem that contains the file, but doesn't cause a conflict. And from all of the possibilities we should prefer latest gem versions.

Current implementation is has many issues as its exponential, might select conflicting gems (#1169) and might not use the latest versions of the possibilities (#1191).

twelve17 · 2015-03-19T15:07:02Z

Some 👏 for @mfazekas too!

ghost · 2015-03-19T18:41:18Z

A valid reason to learn linked lists 👍

ms-ati · 2015-03-19T19:14:42Z

Hi @tenderlove, very cool.

After seeing this commit on Ruby Weekly News, I took a look at this code for the first time. I just submitted a PR to hopefully improve the linked list implementation used here (#1200).

Specifically, in the #to_a code path that is frequently called, Array#unshift was called for every list element. I believe this is quadratic performance, since unshift is linear. Is that right?

007lva · 2015-04-18T00:32:25Z

👍

tenderlove force-pushed the omg branch from 3b957bb to b674a65 Compare March 13, 2015 04:32

skunkworker reviewed Mar 13, 2015
View reviewed changes

byroot reviewed Mar 13, 2015
View reviewed changes

tenderlove force-pushed the omg branch from b674a65 to 6ba868a Compare March 13, 2015 14:10

tenderlove closed this Mar 13, 2015

tenderlove reopened this Mar 13, 2015

tenderlove force-pushed the omg branch from 6ba868a to b19051c Compare March 13, 2015 15:32

seandmccarthy reviewed Mar 13, 2015
View reviewed changes

tenderlove added a commit that referenced this pull request Mar 13, 2015

Merge pull request #1188 from tenderlove/omg

7d314e3

drop millions of allocations by using a linked list

tenderlove merged commit 7d314e3 into rubygems:master Mar 13, 2015

alloy mentioned this pull request Mar 15, 2015

Support what RubyGems needs CocoaPods/Molinillo#20

Merged

mfazekas added a commit to mfazekas/rubygems that referenced this pull request Mar 17, 2015

Testcast to demonstrate issue with rubygems#1188

9725a8e

mfazekas mentioned this pull request Mar 17, 2015

Testcast to demonstrate issue with #1188 #1191

Closed

ms-ati mentioned this pull request Mar 19, 2015

DRY up Gem::List in utils #1200

Merged

This was referenced Mar 14, 2016

require can be very slow with lot of gems #1167

Closed

Added test demonstrating issue with find_in_unresolved_tree #1169

Closed

drop millions of allocations by using a linked list #1188

drop millions of allocations by using a linked list #1188

Conversation

tenderlove commented Mar 13, 2015

tenderlove commented Mar 13, 2015

tenderlove commented Mar 13, 2015

kuldeepaggarwal commented Mar 13, 2015

jcutrell commented Mar 13, 2015

AnatoliiD commented Mar 13, 2015

evanphx commented Mar 13, 2015

tenderlove commented Mar 13, 2015

tomciopp commented Mar 13, 2015

tenderlove commented Mar 13, 2015

Choose a reason for hiding this comment

Choose a reason for hiding this comment

libo commented Mar 13, 2015

chus commented Mar 13, 2015

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

pawitk commented Mar 13, 2015

libo commented Mar 13, 2015

tenderlove commented Mar 13, 2015

libo commented Mar 13, 2015

canweriotnow commented Mar 13, 2015

draffauf commented Mar 13, 2015

sstelfox commented Mar 13, 2015

renatorozas commented Mar 13, 2015

vcavallo commented Mar 13, 2015

amaltson commented Mar 13, 2015

gbxl commented Mar 13, 2015

zeevallin commented Mar 13, 2015

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

cheald commented Mar 13, 2015

ghost commented Mar 13, 2015

tenderlove commented Mar 13, 2015

mfazekas commented Mar 16, 2015

tenderlove commented Mar 16, 2015

mfazekas commented Mar 16, 2015

mfazekas commented Mar 17, 2015

twelve17 commented Mar 19, 2015

ghost commented Mar 19, 2015

ms-ati commented Mar 19, 2015

007lva commented Apr 18, 2015