Ticket #95: benchmark_with_confidence_intervals.rb

require 'rubygems'
gem 'libxml-ruby', '<=0.3.8.4'
require 'xml/libxml'
require 'benchmark'
require 'hpricot'
require 'active_record'
require 'open-uri'
require 'rexml/parsers/streamparser'
require 'rexml/parsers/baseparser'
require 'rexml/light/node'



class REXMLUtilityNode
  attr_accessor :name, :attributes, :children
  
  def initialize(name, attributes = {})
    @name       = name.tr("-", "_")
    @attributes = undasherize_keys(attributes)
    @children   = []
    @text       = false
  end
  
  def add_node(node)
    @text = true if node.is_a? String
    @children << node
  end
  
  def to_hash
    if @text
      return { name => typecast_value( translate_xml_entities( inner_html ) ) }
    else
      #change repeating groups into an array
      # group by the first key of each element of the array to find repeating groups
      groups = @children.group_by{ |c| c.name }

      hash = {}  
      groups.each do |key, values|
        if values.size == 1
          hash.merge!( values.first ) 
        else
          hash.merge!( key => values.map{ |element| element.to_hash[key] } )
        end
      end

      # merge the arrays, including attributes
      hash.merge!( attributes ) unless attributes.empty?
      return { name => hash }
    end
  end

  def to_s 
    self.to_html
  end


  def typecast_value(value)
    return value unless attributes["type"] 
    
    case attributes["type"]
      when "integer"  then value.to_i
      when "boolean"  then value.strip == "true"
      when "datetime" then ::Time.parse(value).utc
      when "date"     then ::Date.parse(value)
      else                 value
    end
  end

  def translate_xml_entities(value)
    value.gsub(/&lt;/,   "<").
          gsub(/&gt;/,   ">").
          gsub(/&quot;/, '"').
          gsub(/&apos;/, "'").
          gsub(/&amp;/,  "&")
  end

   def undasherize_keys(params)
     params.keys.each do |key, vvalue|
       params[key.tr("-", "_")] = params.delete(key)
     end
     params 
  end

  def inner_html
    @children.join
  end

  def to_html 
    "<#{name}#{attributes_to_xml}>#{inner_html}</#{name}>"
  end

  def attributes_to_xml
    attributes.keys.map do |key| 
      "#{key}='#{attributes[key]}'"
    end.join
  end  
end

class ToHashParser
        def self.from_xml(xml)
                stack = []
                parser = REXML::Parsers::BaseParser.new(xml)
                
                while true
                        event = parser.pull
                        case event[0]
                        when :end_document
                                break
                        when :end_doctype, :start_doctype
                                # do nothing
                        when :start_element
                          stack.push REXMLUtilityNode.new(event[1], event[2])
                        when :end_element
                          if stack.size > 1
                            temp = stack.pop
                            stack.last.add_node(temp)
                          end
                        when :text
                          stack.last.add_node(event[1]) unless event[1].strip.length == 0
                        end
                end
                stack.pop.to_hash
        end     
end


class XMLUtilityNode #:nodoc:

   def self.parser
     @@parser ||= XML::SaxParser.new
   end

   def self.stack 
     @@stack ||= []
   end

   parser.on_start_element{ |e,a| stack.push( XMLUtilityNode.new( e,a )) }
   parser.on_characters{ |t| stack.last.add_node( t ) unless t.strip.length == 0 }

   parser.on_end_element do
     if stack.size > 1
       tmp = stack.pop
       stack.last.add_node( tmp )
     end
   end

   def self.hash_from_xml( xml )
     parser.string = xml
     parser.parse
     stack.pop.to_hash
   end

   attr_accessor :name, :attrs
   def initialize( _name, _attrs)
     @name = _name.tr("-", "_")
     @attrs = undasherize_keys( _attrs )
     @children = []
     @text = false
   end

   def attrs
     @attrs ||= {}
   end


   def add_node( attr )
     @text = true if attr.kind_of?( String )
     @children << attr
   end

   def text? 
     @text 
   end

   def to_hash
     if @text
       return { name => typecast_value( translate_xml_entities( inner_html ) ) }
      else
       #change repeating groups into an array
       # group by the first key of each element of the array to find repeating groups
       
       grps = @children.group_by{ |c| c.name }

       out = {}  
       grps.each do |k, v|
         if v.size == 1
           out.merge!( v.first ) 
         else
           out.merge!( k => v.map{ |elem| elem.to_hash[k] } )
         end
       end

       # merge the arrays, including attributes
       out.merge!( attrs ) unless attrs.empty?
      return { name => out }
     end
   end

   def to_s 
     self.to_html
   end


   def typecast_value( value )
     return value unless attrs["type"] 
     
     case attrs["type"]
       when "integer"  then value.to_i
       when "boolean"  then value.strip == "true"
       when "datetime" then ::Time.parse(value).utc
       when "date"     then ::Date.parse(value)
       else                 value
     end
   end

   def translate_xml_entities(value)
     value.gsub(/&lt;/,   "<").
           gsub(/&gt;/,   ">").
           gsub(/&quot;/, '"').
           gsub(/&apos;/, "'").
           gsub(/&amp;/,  "&")
   end

    def undasherize_keys(params)
      params.keys.each do |k, v|
        params[k.tr("-", "_")] =  params.delete(k)
      end
      params 
   end

   def inner_html
     @children.join
   end

   def to_html 
     "<#{name}#{attributes_to_xml}>#{inner_html}</#{name}>"
   end

   def attributes_to_xml
     attrs.keys.map do |k| 
       "#{k}='#{attrs[k]}'"
     end.join
   end
end


 class Hash

   class << self
       # Converts valid XML into a Ruby Hash structure.
       # <tt>xml</tt>:: A string representation of valid XML
       # 
       # == Typecasting
       # Typecasting is performed on elements that have a "<tt>type</tt>" attribute of
       # <tt>integer</tt>:: 
       # <tt>boolean</tt>:: anything other than "true" evaluates to false
       # <tt>datetime</tt>:: Returns a Time object.  See +Time+ documentation for valid Time strings
       # <tt>date</tt>:: Returns a Date object.  See +Date+ documentation for valid Date strings 
       # 
       # Keys are automatically converted to +snake_case+
       #
       # == Caveats
       # * Mixed content tags are assumed to be text and any xml tags are kept as a String
       # * Any attributes other than type on a node containing a text node will be discarded
       #
       # == Examples
       #
       # ===Standard 
       # <user gender='m'>
       #   <age type='integer'>35</age>
       #   <name>Homer Simpson</name>
       #   <dob type='date'>1988-01-01</dob>
       #   <joined-at type='datetime'>2000-04-28 23:01</joined-at>
       #   <is-cool type='boolean'>true</is-cool>
       # </user>
       #
       # evaluates to 
       # 
       # { "user" => 
       #         { "gender"    => "m",
       #           "age"       => 35,
       #           "name"      => "Homer Simpson",
       #           "dob"       => DateObject( 1998-01-01 ),
       #           "joined_at" => TimeObject( 2000-04-28 23:01),
       #           "is_cool"   => true 
       #         }
       #     }
       #
       # === Mixed Content
       # <story>
       #   A Quick <em>brown</em> Fox
       # </story>
       #
       # evaluates to
       # { "story" => "A Quick <em>brown</em> Fox" }
       # 
       # === Attributes other than type on a node containing text
       # <story is-good='fasle'>
       #   A Quick <em>brown</em> Fox
       # </story>
       #
       # evaluates to
       # { "story" => "A Quick <em>brown</em> Fox" }
       #
       # <bicep unit='inches' type='integer'>60</bicep>
       #
       # evaluates with a typecast to an integer.  But ignores the unit attribute
       # { "bicep" => 60 }

       def from_xml( xml )
         undasherize_keys(  Hpricot::XML( xml ).root.to_hash  )   
       end

     private

       def undasherize_keys(params)
         case params.class.to_s
         when "Hash"
           params.inject({}) do |h,(k,v)|
             h[k.to_s.tr("-", "_")] = undasherize_keys(v)
             h
           end
         when "Array"
           params.map { |v| undasherize_keys(v) }
         else
           params
         end
      end
   end

   def to_params
     result = ''
     stack = []

     each do |key, value|
       Hash === value ? stack << [key, value] : result <<  "#{key}=#{value}&"
     end

     stack.each do |parent, hash|
       hash.each do |key, value|
         if Hash === value
           stack << ["#{parent}[#{key}]", value]
         else
           result << "#{parent}[#{key}]=#{value}&"
         end
       end
     end
     result.chop
   end

   # lets through the keys in the argument
   # >> {:one => 1, :two => 2, :three => 3}.pass(:one)
   # => {:one=>1}
   def pass(*allowed) 
     self.reject { |k,v| ! allowed.include?(k) } 
   end
   alias only pass

   # blocks the keys in the arguments
   # >> {:one => 1, :two => 2, :three => 3}.block(:one)
   # => {:two=>2, :three=>3}
   def block(*rejected) 
     self.reject { |k,v| rejected.include?(k) } 
   end
   alias except block


   # Destructively convert all keys to symbols recursively.
   def symbolize_keys!
     keys.each do |key|
       unless key.is_a?(Symbol)
         self[key.to_sym] = self[key]
         delete(key)
       end
       if Hash === (sub = self[key.to_sym])
         sub.symbolize_keys!
       end  
     end
     self
   end

  def method_missing(m,*a)
    m.to_s =~ /=$/ ? self[$`]=a[0] : a==[] ? self[m] : raise(NoMethodError,"#{m}")
  end

   def respond_to?(method, include_private=false)
     return true if keys.include?(method)
     super(method, include_private)
   end

 end  


 class Hpricot::Elem  
   # Converts this Hpricto::Elem to a hash.  
   # If the element contains mixed content.  i.e. tags and text, the innerHTML will
   # be used.
   def to_hash
     result = {}
     # Get any attributes of the tag out and into the hash
     if !attributes.nil?
       result[name].merge!( attributes ) unless result[name].nil?
       result[name] = attributes if result[name].nil?
     end


     if children.detect{ |a| a.text? && a.to_s.strip.length != 0 }
       # There is text nodes in here. 
       # Just return the innerHTML of the node, typecasted if required 
       content = translate_xml_entities( inner_html.strip )
       result[name] = case attributes["type"]

         when "integer"  then content.to_i
         when "boolean"  then content.strip == "true"
         when "datetime" then ::Time.parse(content).utc
         when "date"     then ::Date.parse(content)
         else                 content
       end

     else      
       # Get the children in on the action

       child_array = children.map do |child|
         child_hash = {}
         if !child.text?
           child_hash = child.to_hash
         end
         # If there was no hash found for this child then make it nil so the compact will take it out
         child_hash.empty? ? nil : child_hash
       # We're grouping by the first key to see if this element has any duplicate child tag names
       end.compact.group_by{ |child| child.keys.first }

       # If any hashes in the child_array have a duplicate tag name collect these into an array
       child_array.keys.each do |a|
         if child_array[a].size == 1
           # There is only one of these elements
           # Grab it amd put it into the result
           result[name].merge!( child_array[a].first )
         else
           # There are more than one of these elements
           # They need to be put into an array
           result[name].merge!( { a => child_array[a].map{ |child| child[child.keys.first] }} )
         end
       end

     end
     result
   end


   private
   def translate_xml_entities(value)
     value.gsub(/&lt;/,   "<").
           gsub(/&gt;/,   ">").
           gsub(/&quot;/, '"').
           gsub(/&apos;/, "'").
           gsub(/&amp;/,  "&")
   end
 end


class Array
  def mean
    Float(self.inject {|sum, elem| sum += elem }) / Float(self.length)
  end

  def variance
    m = self.mean
          sum2 = self.inject(0) {|variance, elem| variance += (elem - m) ** 2}
    Float(sum2 / (self.size-1))
  end

  def stdev
    Math.sqrt(variance)
  end
end



n = 1_000

xml_feeds = []
xml_feeds << "http://feeds.feedburner.com/37signals/beMH" # Hpricot is faster for this feed 
#xml_feeds << "http://feeds.gawker.com/gizmodo/excerpts.xml"
xml_feeds << "http://brainspl.at/xml/rss20/feed.xml"
xml_feeds << "http://jobs.37signals.com/categories/2/jobs;rss"
xml_feeds << "http://www.aftenposten.no/eksport/rss-1_0/?seksjon=ece_frontpage"
xml_feeds << "http://merb.devjavu.com/projects/merb/report/9?format=rss"
xml_feeds << "http://odeo.com/profile/OdeoMusic/rss"

xml_feeds.each do |xml_feed|
  @xml = open( xml_feed ).read
  
  measures = Array.new

  n.times do
    measures << Benchmark.measure('libxml')  { XMLUtilityNode.hash_from_xml(@xml) } 
    measures << Benchmark.measure('hpricot') { Hash.from_xml(@xml) } 
    measures << Benchmark.measure('rexml')   { ToHashParser.from_xml(@xml) } 
  end
 
  puts "\n\n-- #{xml_feed} (n=#{n}) --"
  puts "           mean     95% interval"
  labels = measures.collect{|m| m.label}.uniq.sort
  labels.each do |label|
    times = measures.select{|m| m.label == label}.collect{|m| m.total}
    m = times.mean
    conf_low  = times.mean-1.96*times.stdev
    conf_high = times.mean+1.96*times.stdev
    puts "#{label.ljust(10)} #{sprintf("%.2f", m)}   " <<
         "(#{sprintf("%.2f", conf_low).rjust(5)} .. #{sprintf("%.2f", conf_high)} )"
  end

end