Plan and decide how to make mutators faster.

[planetis-m]

Currently mutators for collections are written like this:

mutate:
  copy = value
  # delete
  while copy.len > 0 and rand(bool):
    copy.deleteRandomItem
  # insert
  while copy.size < sizeIncreaseHint and rand(bool):
    copy.insert newInput(remainingSize)
  # iff copy is different return
  if copy != value: return copy
  # fallback case
  if copy.len == 0:
    copy.insert newInput(remainingSize)
  else:
    mutateRandomItem(copy) # does not guarantee changes

# called by
tmp = value
repeat 10:
  value = mutate(value)
  if tmp != value: return

Although these steps enhance our chances to get unique mutations, the mutator can be made faster, since a lot of copies and comparisons happen.

I have some solutions in mind but we need to experiment and try other fuzzers as well.

[planetis-m]

FuzzCheck-rs runs the example in the readme at 1mil iter/s but can't grow it's coverage! In comparison we finish in 2mil iterations. Needs more careful investigation why it fails so bad.

From a first look, it seems to me using weights based on the bytes (so called complexity in Fuzzcheck) makes fuzzers stuck (as in no new coverage but increasing features, mutations are rejected). Could be wrong but that idea doesn't seem to work.

In our case a shrinking from ~20% rejected inputs versus a stable 14% with a default weight. Still to explain the large slowdown, the answer might be in libfuzzer's entropic power schedule.

[planetis-m]

There is a large speedup in iter/s by not choosing the seq mutator all the time, but mutating individual items. This is no longer an issue.