From 559e7f94506ac3c3e8553f9510f43923e7c804da Mon Sep 17 00:00:00 2001 From: Aaron Patterson Date: Mon, 17 Aug 2015 15:57:06 -0700 Subject: drop object allocation during routes setup This commit introduces a functional Path AST visitor and implements `each` on the AST in terms of the functional visitor. The functional visitor doesn't maintain state, so we only need to allocate one of them. Given this benchmark route file: ```ruby require 'action_pack' require 'action_dispatch' route_set = ActionDispatch::Routing::RouteSet.new routes = ActionDispatch::Routing::Mapper.new route_set ObjectSpace::AllocationTracer.setup(%i{path line type}) result = ObjectSpace::AllocationTracer.trace do 500.times{|i| routes.resource :omglol } end result.find_all { |k,v| k.first =~ /git\/rails/ }.sort_by { |k,v| v.first }.each { |k,v| p k => v } ``` node.rb line 17 was in our top 3 allocation spot: ``` {["/Users/aaron/git/rails/actionpack/lib/action_dispatch/journey/nodes/node.rb", 17, :T_OBJECT]=>[31526, 0, 28329, 0, 2, 1123160]} {["/Users/aaron/git/rails/actionpack/lib/action_dispatch/routing/mapper.rb", 2080, :T_IMEMO]=>[34002, 0, 30563, 0, 2, 1211480]} {["/Users/aaron/git/rails/actionpack/lib/action_dispatch/routing/mapper.rb", 2071, :T_IMEMO]=>[121934, 1, 109608, 0, 7, 4344400]} ``` This commit eliminates allocations at that place. --- .../lib/action_dispatch/journey/nodes/node.rb | 6 +- actionpack/lib/action_dispatch/journey/visitors.rb | 127 ++++++++++++++------- 2 files changed, 89 insertions(+), 44 deletions(-) diff --git a/actionpack/lib/action_dispatch/journey/nodes/node.rb b/actionpack/lib/action_dispatch/journey/nodes/node.rb index 2b57c368dc..542e8c6577 100644 --- a/actionpack/lib/action_dispatch/journey/nodes/node.rb +++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb @@ -14,15 +14,15 @@ module ActionDispatch end def each(&block) - Visitors::Each.new(block).accept(self) + Visitors::Each::INSTANCE.accept(self, block) end def to_s - Visitors::String.new.accept(self) + Visitors::String::INSTANCE.accept(self, '') end def to_dot - Visitors::Dot.new.accept(self) + Visitors::Dot::INSTANCE.accept(self) end def to_sym diff --git a/actionpack/lib/action_dispatch/journey/visitors.rb b/actionpack/lib/action_dispatch/journey/visitors.rb index 52b4c8b489..537c9b2f5c 100644 --- a/actionpack/lib/action_dispatch/journey/visitors.rb +++ b/actionpack/lib/action_dispatch/journey/visitors.rb @@ -92,6 +92,45 @@ module ActionDispatch end end + class FunctionalVisitor # :nodoc: + DISPATCH_CACHE = {} + + def accept(node, seed) + visit(node, seed) + end + + def visit node, seed + send(DISPATCH_CACHE[node.type], node, seed) + end + + def binary(node, seed) + visit(node.right, visit(node.left, seed)) + end + def visit_CAT(n, seed); binary(n, seed); end + + def nary(node, seed) + node.children.inject(seed) { |s, c| visit(c, s) } + end + def visit_OR(n, seed); nary(n, seed); end + + def unary(node, seed) + visit(node.left, seed) + end + def visit_GROUP(n, seed); unary(n, seed); end + def visit_STAR(n, seed); unary(n, seed); end + + def terminal(node, seed); seed; end + def visit_LITERAL(n, seed); terminal(n, seed); end + def visit_SYMBOL(n, seed); terminal(n, seed); end + def visit_SLASH(n, seed); terminal(n, seed); end + def visit_DOT(n, seed); terminal(n, seed); end + + instance_methods(false).each do |pim| + next unless pim =~ /^visit_(.*)$/ + DISPATCH_CACHE[$1.to_sym] = pim + end + end + class FormatBuilder < Visitor # :nodoc: def accept(node); Journey::Format.new(super); end def terminal(node); [node.left]; end @@ -117,104 +156,110 @@ module ActionDispatch end # Loop through the requirements AST - class Each < Visitor # :nodoc: - attr_reader :block - - def initialize(block) - @block = block - end - - def visit(node) + class Each < FunctionalVisitor # :nodoc: + def visit(node, block) block.call(node) super end + + INSTANCE = new end - class String < Visitor # :nodoc: + class String < FunctionalVisitor # :nodoc: private - def binary(node) - [visit(node.left), visit(node.right)].join + def binary(node, seed) + visit(node.right, visit(node.left, seed)) end - def nary(node) - node.children.map { |c| visit(c) }.join '|' + def nary(node, seed) + last_child = node.children.last + node.children.inject(seed) { |s, c| + string = visit(c, s) + string << "|".freeze unless last_child == c + string + } end - def terminal(node) - node.left + def terminal(node, seed) + seed + node.left end - def visit_GROUP(node) - "(#{visit(node.left)})" + def visit_GROUP(node, seed) + visit(node.left, seed << "(".freeze) << ")".freeze end + + INSTANCE = new end - class Dot < Visitor # :nodoc: + class Dot < FunctionalVisitor # :nodoc: def initialize @nodes = [] @edges = [] end - def accept(node) + def accept(node, seed = [[], []]) super + nodes, edges = seed <<-eodot digraph parse_tree { size="8,5" node [shape = none]; edge [dir = none]; - #{@nodes.join "\n"} - #{@edges.join("\n")} + #{nodes.join "\n"} + #{edges.join("\n")} } eodot end private - def binary(node) - node.children.each do |c| - @edges << "#{node.object_id} -> #{c.object_id};" - end + def binary(node, seed) + seed.last.concat node.children.map { |c| + "#{node.object_id} -> #{c.object_id};" + } super end - def nary(node) - node.children.each do |c| - @edges << "#{node.object_id} -> #{c.object_id};" - end + def nary(node, seed) + seed.last.concat node.children.map { |c| + "#{node.object_id} -> #{c.object_id};" + } super end - def unary(node) - @edges << "#{node.object_id} -> #{node.left.object_id};" + def unary(node, seed) + seed.last << "#{node.object_id} -> #{node.left.object_id};" super end - def visit_GROUP(node) - @nodes << "#{node.object_id} [label=\"()\"];" + def visit_GROUP(node, seed) + seed.first << "#{node.object_id} [label=\"()\"];" super end - def visit_CAT(node) - @nodes << "#{node.object_id} [label=\"○\"];" + def visit_CAT(node, seed) + seed.first << "#{node.object_id} [label=\"○\"];" super end - def visit_STAR(node) - @nodes << "#{node.object_id} [label=\"*\"];" + def visit_STAR(node, seed) + seed.first << "#{node.object_id} [label=\"*\"];" super end - def visit_OR(node) - @nodes << "#{node.object_id} [label=\"|\"];" + def visit_OR(node, seed) + seed.first << "#{node.object_id} [label=\"|\"];" super end - def terminal(node) + def terminal(node, seed) value = node.left - @nodes << "#{node.object_id} [label=\"#{value}\"];" + seed.first << "#{node.object_id} [label=\"#{value}\"];" + seed end + INSTANCE = new end end end -- cgit v1.2.3