UNDF: UNDF-2026-000000369

crystal-0001: compare_strictness — O(N²) named arg lookup in overload ordering

Severity: HIGH

Location

src/compiler/crystal/semantic/restrictions.cr:94,104,141,148
Called from: src/compiler/crystal/types.cr:919 inside add_def loop

Description

DefWithMetadata#compare_strictness compares two method defs for overload ordering. For each element of self_named_args (an Array), it calls .any? or .find on other_named_args (another Array) to check for a matching named parameter by name. These are O(N) linear scans, making the function O(N²) where N = named param count.

compare_strictness is called from add_def (types.cr:919) which iterates over the existing list of defs with the same name, making the total cost O(D × N²) where D = number of overloads with the same name.

For methods with many named parameters (keyword-heavy APIs, DSL builders), this is a significant compilation bottleneck.

Root Cause

# restrictions.cr:92-98
self_named_args.try &.each do |self_arg|
  unless self_arg.default_value
    unless other_named_args.try &.any?(&.external_name.== self_arg.external_name)  # O(N)
      return nil
    end
  end
end

# restrictions.cr:140-145
self_named_args.try &.each do |self_arg|
  other_arg = other_named_args.try &.find(&.external_name.== self_arg.external_name)  # O(N)
  ...
end

# restrictions.cr:147-152
other_named_args.try &.each do |other_arg|
  next if self_named_args.try &.any?(&.external_name.== other_arg.external_name)  # O(N)
  ...
end

Fix

Build a Hash(String, Arg) from each named_args array once before the loops. Then all membership checks and lookups become O(1).

def compare_strictness(other : DefWithMetadata, self_owner, *, other_owner = self_owner)
  # ...
  self_named_args = self.named_arguments
  other_named_args = other.named_arguments

  # Build index maps O(N) once
  self_name_map = self_named_args.try { |a| a.to_h { |arg| {arg.external_name, arg} } }
  other_name_map = other_named_args.try { |a| a.to_h { |arg| {arg.external_name, arg} } }

  # Now all .any?/.find checks become O(1) hash lookups
  unless other.def.double_splat
    self_named_args.try &.each do |self_arg|
      unless self_arg.default_value
        unless other_name_map.try &.has_key?(self_arg.external_name)
          return nil
        end
      end
    end
  end
  # ... etc
end

Impact

Crystal programs with keyword-heavy method signatures (frameworks, DSL builders, configuration APIs) experience O(D × N²) compile time for method dispatch resolution.

2.5 KiB Raw Permalink Blame History Unescape Escape