Skip to content
  • Hartley McGuire's avatar
    9b49ba5a
    [rubygems/rubygems] Speed up Version#<=> ~20-50% when lengths differ · 9b49ba5a
    Hartley McGuire authored
    Previously, the comparison code would loop through segments up to the
    longest of the two versions being compared. However, this is inefficient
    because once one version has more segments than the other we can do a
    lot less work.
    
    This commit optimizes the differing segment length case by specializing
    the logic once the iteration has passed the shorter of the two segment
    lengths. At this point we only need to continue looking at the longer
    version's segment, and we know that any String encountered means the
    version is less than (pre), and any non-zero Integer means the version
    is greater than.
    
    Benchmark:
    
    ```
    {
      first: [Gem::Version.new("1.2.3"), Gem::Version.new("2.2.3")],
      second: [Gem::Version.new("1.2.3"), Gem::Version.new("1.3.3")],
      third: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.4")],
      length: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.3.4")],
      left_s_second: [Gem::Version.new("1.a.3"), Gem::Version.new("1.2.3")],
      left_s_third: [Gem::Version.new("1.2.a"), Gem::Version.new("1.2.3")],
      right_s_second: [Gem::Version.new("1.2.3"), Gem::Version.new("1.a.3")],
      right_s_third: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.a")],
      left_s_length: [Gem::Version.new("8.0.1.pre"), Gem::Version.new("8.0.1")],
      right_s_length: [Gem::Version.new("8.0.1"), Gem::Version.new("8.0.1.pre")],
      both_s: [Gem::Version.new("8.0.2.pre1"), Gem::Version.new("8.0.2.pre2")],
    }.each do |name, v|
      puts "== #{name} =="
    
      raise name unless v[0].fast_comp(v[1]) == (v[0] <=> v[1])
    
      Benchmark.ips do |x|
        x.report("fast") { v[0].fast_comp(v[1]) }
        x.report("original") { v[0] <=> v[1] }
        x.compare!(order: :baseline)
      end
    end
    
    == first ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   208.555k i/100ms
                original   199.789k i/100ms
    Calculating -------------------------------------
                    fast      2.075M (± 6.0%) i/s  (481.93 ns/i) -     10.428M in   5.055818s
                original      2.045M (± 3.9%) i/s  (488.94 ns/i) -     10.389M in   5.090034s
    
    Comparison:
                    fast:  2075002.8 i/s
                original:  2045227.4 i/s - same-ish: difference falls within error
    
    == second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   192.395k i/100ms
                original   183.000k i/100ms
    Calculating -------------------------------------
                    fast      1.892M (± 3.8%) i/s  (528.62 ns/i) -      9.620M in   5.094104s
                original      1.824M (± 3.5%) i/s  (548.11 ns/i) -      9.150M in   5.023163s
    
    Comparison:
                    fast:  1891722.2 i/s
                original:  1824435.3 i/s - same-ish: difference falls within error
    
    == third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   172.788k i/100ms
                original   162.934k i/100ms
    Calculating -------------------------------------
                    fast      1.719M (± 9.0%) i/s  (581.72 ns/i) -      8.467M in   5.025861s
                original      1.638M (± 3.6%) i/s  (610.36 ns/i) -      8.310M in   5.080344s
    
    Comparison:
                    fast:  1719042.9 i/s
                original:  1638389.6 i/s - same-ish: difference falls within error
    
    == length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   191.741k i/100ms
                original   155.952k i/100ms
    Calculating -------------------------------------
                    fast      1.920M (± 3.9%) i/s  (520.74 ns/i) -      9.587M in   5.002328s
                original      1.576M (± 6.2%) i/s  (634.42 ns/i) -      7.954M in   5.072507s
    
    Comparison:
                    fast:  1920362.1 i/s
                original:  1576240.9 i/s - 1.22x  slower
    
    == left_s_second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   176.441k i/100ms
                original   164.879k i/100ms
    Calculating -------------------------------------
                    fast      1.609M (± 7.3%) i/s  (621.51 ns/i) -      8.116M in   5.083414s
                original      1.620M (± 8.3%) i/s  (617.43 ns/i) -      8.079M in   5.028525s
    
    Comparison:
                    fast:  1608994.8 i/s
                original:  1619606.5 i/s - same-ish: difference falls within error
    
    == left_s_third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   160.562k i/100ms
                original   152.799k i/100ms
    Calculating -------------------------------------
                    fast      1.591M (± 3.6%) i/s  (628.40 ns/i) -      8.028M in   5.052029s
                original      1.528M (± 3.6%) i/s  (654.31 ns/i) -      7.640M in   5.007526s
    
    Comparison:
                    fast:  1591334.1 i/s
                original:  1528320.6 i/s - same-ish: difference falls within error
    
    == right_s_second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   135.938k i/100ms
                original   132.907k i/100ms
    Calculating -------------------------------------
                    fast      1.367M (± 1.2%) i/s  (731.77 ns/i) -      6.933M in   5.074030s
                original      1.320M (± 2.4%) i/s  (757.35 ns/i) -      6.645M in   5.036155s
    
    Comparison:
                    fast:  1366548.7 i/s
                original:  1320386.4 i/s - same-ish: difference falls within error
    
    == right_s_third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   129.971k i/100ms
                original   123.802k i/100ms
    Calculating -------------------------------------
                    fast      1.273M (± 4.1%) i/s  (785.25 ns/i) -      6.369M in   5.011805s
                original      1.215M (± 1.8%) i/s  (823.04 ns/i) -      6.190M in   5.096330s
    
    Comparison:
                    fast:  1273487.0 i/s
                original:  1215002.9 i/s - same-ish: difference falls within error
    
    == left_s_length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   211.093k i/100ms
                original   155.784k i/100ms
    Calculating -------------------------------------
                    fast      2.120M (± 1.9%) i/s  (471.63 ns/i) -     10.766M in   5.079336s
                original      1.565M (± 6.7%) i/s  (638.87 ns/i) -      7.789M in   5.007522s
    
    Comparison:
                    fast:  2120296.1 i/s
                original:  1565258.0 i/s - 1.35x  slower
    
    == right_s_length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   213.977k i/100ms
                original   142.990k i/100ms
    Calculating -------------------------------------
                    fast      2.154M (± 1.3%) i/s  (464.15 ns/i) -     10.913M in   5.066124s
                original      1.446M (± 1.8%) i/s  (691.75 ns/i) -      7.292M in   5.046172s
    
    Comparison:
                    fast:  2154455.3 i/s
                original:  1445607.9 i/s - 1.49x  slower
    
    == both_s ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   154.903k i/100ms
                original   131.011k i/100ms
    Calculating -------------------------------------
                    fast      1.515M (± 4.0%) i/s  (659.97 ns/i) -      7.590M in   5.019890s
                original      1.280M (± 5.3%) i/s  (781.28 ns/i) -      6.420M in   5.035387s
    
    Comparison:
                    fast:  1515223.3 i/s
                original:  1279957.8 i/s - 1.18x  slower
    ```
    
    https://github.com/rubygems/rubygems/commit/7195e77152
    9b49ba5a
    [rubygems/rubygems] Speed up Version#<=> ~20-50% when lengths differ
    Hartley McGuire authored
    Previously, the comparison code would loop through segments up to the
    longest of the two versions being compared. However, this is inefficient
    because once one version has more segments than the other we can do a
    lot less work.
    
    This commit optimizes the differing segment length case by specializing
    the logic once the iteration has passed the shorter of the two segment
    lengths. At this point we only need to continue looking at the longer
    version's segment, and we know that any String encountered means the
    version is less than (pre), and any non-zero Integer means the version
    is greater than.
    
    Benchmark:
    
    ```
    {
      first: [Gem::Version.new("1.2.3"), Gem::Version.new("2.2.3")],
      second: [Gem::Version.new("1.2.3"), Gem::Version.new("1.3.3")],
      third: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.4")],
      length: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.3.4")],
      left_s_second: [Gem::Version.new("1.a.3"), Gem::Version.new("1.2.3")],
      left_s_third: [Gem::Version.new("1.2.a"), Gem::Version.new("1.2.3")],
      right_s_second: [Gem::Version.new("1.2.3"), Gem::Version.new("1.a.3")],
      right_s_third: [Gem::Version.new("1.2.3"), Gem::Version.new("1.2.a")],
      left_s_length: [Gem::Version.new("8.0.1.pre"), Gem::Version.new("8.0.1")],
      right_s_length: [Gem::Version.new("8.0.1"), Gem::Version.new("8.0.1.pre")],
      both_s: [Gem::Version.new("8.0.2.pre1"), Gem::Version.new("8.0.2.pre2")],
    }.each do |name, v|
      puts "== #{name} =="
    
      raise name unless v[0].fast_comp(v[1]) == (v[0] <=> v[1])
    
      Benchmark.ips do |x|
        x.report("fast") { v[0].fast_comp(v[1]) }
        x.report("original") { v[0] <=> v[1] }
        x.compare!(order: :baseline)
      end
    end
    
    == first ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   208.555k i/100ms
                original   199.789k i/100ms
    Calculating -------------------------------------
                    fast      2.075M (± 6.0%) i/s  (481.93 ns/i) -     10.428M in   5.055818s
                original      2.045M (± 3.9%) i/s  (488.94 ns/i) -     10.389M in   5.090034s
    
    Comparison:
                    fast:  2075002.8 i/s
                original:  2045227.4 i/s - same-ish: difference falls within error
    
    == second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   192.395k i/100ms
                original   183.000k i/100ms
    Calculating -------------------------------------
                    fast      1.892M (± 3.8%) i/s  (528.62 ns/i) -      9.620M in   5.094104s
                original      1.824M (± 3.5%) i/s  (548.11 ns/i) -      9.150M in   5.023163s
    
    Comparison:
                    fast:  1891722.2 i/s
                original:  1824435.3 i/s - same-ish: difference falls within error
    
    == third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   172.788k i/100ms
                original   162.934k i/100ms
    Calculating -------------------------------------
                    fast      1.719M (± 9.0%) i/s  (581.72 ns/i) -      8.467M in   5.025861s
                original      1.638M (± 3.6%) i/s  (610.36 ns/i) -      8.310M in   5.080344s
    
    Comparison:
                    fast:  1719042.9 i/s
                original:  1638389.6 i/s - same-ish: difference falls within error
    
    == length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   191.741k i/100ms
                original   155.952k i/100ms
    Calculating -------------------------------------
                    fast      1.920M (± 3.9%) i/s  (520.74 ns/i) -      9.587M in   5.002328s
                original      1.576M (± 6.2%) i/s  (634.42 ns/i) -      7.954M in   5.072507s
    
    Comparison:
                    fast:  1920362.1 i/s
                original:  1576240.9 i/s - 1.22x  slower
    
    == left_s_second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   176.441k i/100ms
                original   164.879k i/100ms
    Calculating -------------------------------------
                    fast      1.609M (± 7.3%) i/s  (621.51 ns/i) -      8.116M in   5.083414s
                original      1.620M (± 8.3%) i/s  (617.43 ns/i) -      8.079M in   5.028525s
    
    Comparison:
                    fast:  1608994.8 i/s
                original:  1619606.5 i/s - same-ish: difference falls within error
    
    == left_s_third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   160.562k i/100ms
                original   152.799k i/100ms
    Calculating -------------------------------------
                    fast      1.591M (± 3.6%) i/s  (628.40 ns/i) -      8.028M in   5.052029s
                original      1.528M (± 3.6%) i/s  (654.31 ns/i) -      7.640M in   5.007526s
    
    Comparison:
                    fast:  1591334.1 i/s
                original:  1528320.6 i/s - same-ish: difference falls within error
    
    == right_s_second ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   135.938k i/100ms
                original   132.907k i/100ms
    Calculating -------------------------------------
                    fast      1.367M (± 1.2%) i/s  (731.77 ns/i) -      6.933M in   5.074030s
                original      1.320M (± 2.4%) i/s  (757.35 ns/i) -      6.645M in   5.036155s
    
    Comparison:
                    fast:  1366548.7 i/s
                original:  1320386.4 i/s - same-ish: difference falls within error
    
    == right_s_third ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   129.971k i/100ms
                original   123.802k i/100ms
    Calculating -------------------------------------
                    fast      1.273M (± 4.1%) i/s  (785.25 ns/i) -      6.369M in   5.011805s
                original      1.215M (± 1.8%) i/s  (823.04 ns/i) -      6.190M in   5.096330s
    
    Comparison:
                    fast:  1273487.0 i/s
                original:  1215002.9 i/s - same-ish: difference falls within error
    
    == left_s_length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   211.093k i/100ms
                original   155.784k i/100ms
    Calculating -------------------------------------
                    fast      2.120M (± 1.9%) i/s  (471.63 ns/i) -     10.766M in   5.079336s
                original      1.565M (± 6.7%) i/s  (638.87 ns/i) -      7.789M in   5.007522s
    
    Comparison:
                    fast:  2120296.1 i/s
                original:  1565258.0 i/s - 1.35x  slower
    
    == right_s_length ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   213.977k i/100ms
                original   142.990k i/100ms
    Calculating -------------------------------------
                    fast      2.154M (± 1.3%) i/s  (464.15 ns/i) -     10.913M in   5.066124s
                original      1.446M (± 1.8%) i/s  (691.75 ns/i) -      7.292M in   5.046172s
    
    Comparison:
                    fast:  2154455.3 i/s
                original:  1445607.9 i/s - 1.49x  slower
    
    == both_s ==
    ruby 3.4.2 (2025-02-15 revision https://github.com/rubygems/rubygems/commit/d2930f8e7a) +PRISM [arm64-darwin23]
    Warming up --------------------------------------
                    fast   154.903k i/100ms
                original   131.011k i/100ms
    Calculating -------------------------------------
                    fast      1.515M (± 4.0%) i/s  (659.97 ns/i) -      7.590M in   5.019890s
                original      1.280M (± 5.3%) i/s  (781.28 ns/i) -      6.420M in   5.035387s
    
    Comparison:
                    fast:  1515223.3 i/s
                original:  1279957.8 i/s - 1.18x  slower
    ```
    
    https://github.com/rubygems/rubygems/commit/7195e77152
Loading