gistfile1.rb

# Copyright (c) 2015 Oracle and/or its affiliates. All rights reserved. This
# code is released under a tri EPL/GPL/LGPL license. You can use it,
# redistribute it and/or modify it under the terms of the:
# 
# Eclipse Public License version 1.0
# GNU General Public License version 2
# GNU Lesser General Public License version 2.1

# Exercise Hash and Set (which is also Hash) insertion and lookup performance.
# Creates a graph with an adjacency map. Finds the connected subgraph from a
# root node, using an Array work list and a visited Set.

require 'set'

size = 100_000

class Node
end

nodes = []

size.times do
  nodes << Node.new
end

adjacency = {}

nodes.each do |node|
  adjacency[node] = nodes.sample(3)
end

def connected(adjacency, root_node)
  visited = Set.new
  to_visit = [root_node]

  while node = to_visit.pop
    unless visited.member? node
      visited.add node
      to_visit.concat adjacency[node]
    end
  end

  visited
end

root_node = nodes.sample

loop do
  start = Time.now
  connected(adjacency, root_node)
  puts Time.now - start
end

  %   cumulative   self                self     total
 time   seconds   seconds      calls  ms/call  ms/call  name
------------------------------------------------------------
[[[ JIT queued BasicObject#!= (method)  (32000)  ]]]
  73.50   84.82     84.82     215354     0.39     0.39  Array#concat
  10.76  107.97     12.42          3  4140.35 35990.28  Object#connected
   2.03    3.86      2.35     811514     0.00     0.00  Hash#find_item
   1.77    5.55      2.04     100001     0.02     0.06  Array#sample
   1.27    1.66      1.47     596086     0.00     0.00  Array#pop
   1.25    4.40      1.44     315383     0.00     0.01  Hash#[]=
   0.85    1.15      0.98    1935407     0.00     0.00  Hash::State#match?
   0.82    1.66      0.94     300004     0.00     0.01  Kernel.rand
   0.81    1.24      0.94         53    17.65    23.42  Hash#redistribute
   0.75    1.02      0.87     600095     0.00     0.00  Array#[]
   0.72    1.40      0.83     315383     0.00     0.00  Hash#new_bucket
   0.61    3.84      0.71     596081     0.00     0.01  Hash#include?
   0.45    0.62      0.52    1253907     0.00     0.00  Hash#key_index
   0.37    4.26      0.42     596071     0.00     0.01  Set#member?
   0.32    0.37      0.37        208     1.79     1.79  GC.collect_young
   0.25    0.37      0.29     100010     0.00     0.00  Array#initialize
   0.24    0.44      0.27     300007     0.00     0.00  Kernel#Integer
   0.22    0.29      0.26     596426     0.00     0.00  BasicObject#!=
   0.22    0.26      0.25     315383     0.00     0.00  Hash::Bucket#initialize
   0.19    3.32      0.22     215323     0.00     0.02  Set#add
   0.18    0.25      0.20    2159957     0.00     0.00  Rubinius::Tuple#[]
   0.17    0.19      0.19       4085     0.05     0.05  GC.collect_mature
   0.15    0.24      0.17    3433575     0.00     0.00  Fixnum#==
   0.14    1.18      0.17     215433     0.00     0.01  Hash#[]
   0.14    7.15      0.16        192     0.82    37.26  Array#each
   0.12    0.20      0.13    3092927     0.00     0.00  Fixnum#<
   0.11    0.20      0.13    3105529     0.00     0.00  Fixnum#+
   0.11    6.98      0.13     100000     0.00     0.07  Object::__script__<28> {}
   0.10    0.14      0.12     301274     0.00     0.00  Module#===
   0.10    0.14      0.12     300004     0.00     0.00  Numeric#abs
   0.09    0.13      0.11    1126923     0.00     0.00  Kernel#hash
   0.09    0.13      0.10    1569428     0.00     0.00  Fixnum#&
   0.08    0.16      0.09     100004     0.00     0.00  Rubinius::Type.check_convert_type
   0.08    0.14      0.09     100000     0.00     0.00  Object::__script__<22> {}
   0.07    0.11      0.09    1017591     0.00     0.00  Kernel#kind_of?
   0.06    0.22      0.07          1    73.40   219.20  Integer#times
   0.06    0.10      0.07    1298189     0.00     0.00  Rubinius::Tuple#at
   0.05    0.29      0.06     415987     0.00     0.00  Class#allocate
   0.05    0.06      0.06     100004     0.00     0.00  Rubinius::Type.object_respond_to?
   0.05    0.07      0.05     997099     0.00     0.00  Kernel#equal?
   0.04    0.05      0.04     300097     0.00     0.00  Array#at
   0.04    0.05      0.04     100005     0.00     0.00  Rubinius::Type.coerce_to_collection_length
   0.03    0.05      0.04     300004     0.00     0.00  Rubinius::Randomizer#random_integer
   0.03    0.05      0.04     100000     0.00     0.00  Rubinius::Type.coerce_to_collection_index
   0.03    0.06      0.04     897108     0.00     0.00  Fixnum#-
``