@benmmurphy `setbyte` is O(1) though, it seems.

```ruby
# encoding: utf-8
require "benchmark"

Encoding.default_internal = Encoding::UTF_8

def self.replace_invalid_characters(str)
  for i in (0...str.size)
    if !str[i].valid_encoding?
      str[i] = "?"
    end
  end
end

def encode1(str)
  str.force_encoding(Encoding::UTF_8)
  if !str.valid_encoding?
    replace_invalid_characters(str)
  end
  str
end

def encode2(str)
  str.force_encoding(Encoding::UTF_8).tap do |s|
    unless s.valid_encoding?
      s.each_char.with_index do |c, i|
        s.setbyte(i, 63) unless c.valid_encoding?
      end
    end
  end
end

def encode3(str)
  if str.force_encoding(Encoding::UTF_8).valid_encoding?
    str
  else
    str.each_char.map do |c|
      if c.valid_encoding?
        c
      else
        '?'
      end
    end.join
  end
end

def encode4(str)
  if str.force_encoding(Encoding::UTF_8).valid_encoding?
    str
  else
    ''.tap do |buf|
      str.each_char do |c|
        buf << if c.valid_encoding?
        c
        else
          '?'
        end
      end
    end
  end
end

N = 2000
VALID = "foo£bar£car".encode(Encoding::UTF_8).force_encoding(Encoding::ASCII_8BIT)

puts VALID.dup
puts encode1(VALID.dup)
puts encode2(VALID.dup)
puts encode3(VALID.dup)
puts encode4(VALID.dup)

Benchmark.bmbm do |x|
  x.report { encode1(VALID.dup * N) }
  x.report { encode2(VALID.dup * N) }
  x.report { encode3(VALID.dup * N) }
  x.report { encode4(VALID.dup * N) }
end

INVALID = "£foo\xC0\x8Abar\xC0\x8Acar".force_encoding(Encoding::ASCII_8BIT)

puts INVALID.dup
puts encode1(INVALID.dup)
puts encode2(INVALID.dup)
puts encode3(INVALID.dup)
puts encode4(INVALID.dup)

Benchmark.bmbm do |x|
  x.report { encode1(INVALID.dup * N) }
  x.report { encode2(INVALID.dup * N) }
  x.report { encode3(INVALID.dup * N) }
  x.report { encode4(INVALID.dup * N) }
end
```

```
foo£bar£car
foo£bar£car
foo£bar£car
foo£bar£car
foo£bar£car
Rehearsal ------------------------------------
   0.000000   0.000000   0.000000 (  0.000113)
   0.000000   0.000000   0.000000 (  0.000109)
   0.000000   0.000000   0.000000 (  0.000107)
   0.000000   0.000000   0.000000 (  0.000106)
--------------------------- total: 0.000000sec

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000096)
   0.000000   0.000000   0.000000 (  0.000095)
   0.000000   0.000000   0.000000 (  0.000096)
   0.000000   0.000000   0.000000 (  0.000107)
£foo�bar�car
£foo??bar??car
£fo??�ba??�car
£foo??bar??car
£foo??bar??car
Rehearsal ------------------------------------
   1.510000   0.010000   1.520000 (  1.528496)
   0.010000   0.000000   0.010000 (  0.009409)
   0.020000   0.000000   0.020000 (  0.014133)
   0.010000   0.000000   0.010000 (  0.013941)
--------------------------- total: 1.560000sec

       user     system      total        real
   1.530000   0.000000   1.530000 (  1.531837)
   0.010000   0.000000   0.010000 (  0.010602)
   0.010000   0.000000   0.010000 (  0.012334)
   0.010000   0.000000   0.010000 (  0.010228)
```