ProbabilisticGeneratorGrammarCoverageFuzzer really slow for CSV grammar (>30 times slower than GeneratorGrammarFuzzer)

[rindPHI]

Describe the bug
The ProbabilisticGeneratorGrammarCoverageFuzzer is over 30 times slower than GeneratorGrammarFuzzer when fuzzing 100 inputs from a CSV grammar (without generators or probabilities).

I do not know whether this is just part of the inherent, and unavoidable, complexity of coverage-based fuzzing, but it is really a significant slow-down compared to the standard grammar-based fuzzer. Maybe there is an avoidable bottleneck somewhere, or recent optimizations that can be integrated, and thus also presented to the readers of the fuzzing book?

To Reproduce
Execute the following code. It will demonstrate the relative performance loss.

from time import time

from fuzzingbook.GeneratorGrammarFuzzer import ProbabilisticGeneratorGrammarCoverageFuzzer
from fuzzingbook.GeneratorGrammarFuzzer import GeneratorGrammarFuzzer

grammar = {
    '<start>': ["<csv-record'>"],
    '<csv-record>': ['<csv-string-list>\n'],
    '<csv-string-list>': ['<raw-string>', '<raw-string>;<csv-string-list>'],
    '<raw-string>': ['<spaces>', '<spaces-1><raw-field><spaces-2>'],
    '<raw-field>': ['<simple-field>', '<quoted-field>'], '<simple-field>': ['<simple-character-1>'],
    '<simple-character>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e',
                           'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                           'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                           'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
                           'Y', 'Z', '!', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.',
                           '/', ':', '<', '=', '>', '?', '@', '[', '\\', ']', '^', '_', '`', '{', '|',
                           '}', '~', '\x0b', '\x0c'],
    '<quoted-field>': ['"<escaped-field>"'],
    '<escaped-field>': ['<escaped-character-1>'],
    '<escaped-character>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e',
                            'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                            'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                            'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
                            'Y', 'Z', '!', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.',
                            '/', ':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '^', '_', '`', '{',
                            '|', '}', '~', ' ', '\t', '\n', '\r', '\x0b', '\x0c'],
    '<spaces>': [' ', ' <spaces>'],
    '<spaces-1>': ['', '<spaces>'],
    '<spaces-2>': ['', '<spaces>'],
    '<simple-character-1>': ['', '<simple-character><simple-character-1>'],
    '<escaped-character-1>': ['', '<escaped-character><escaped-character-1>'],
    "<csv-record'>": ['<csv-record>']}


def fuzz(fuzzer):
    start_time = time()
    for _ in range(100):
        fuzzer.fuzz()
    return time() - start_time


fuzzer = ProbabilisticGeneratorGrammarCoverageFuzzer(grammar)
duration1 = fuzz(fuzzer)
print(f"Duration PGGC-Fuzzer: {round(duration1, 2)}s")

fuzzer = GeneratorGrammarFuzzer(grammar)
duration2 = fuzz(fuzzer)
print(f"Duration GeneratorGrammarFuzzer: {round(duration2, 2)}s")

print(f"Ratio: GeneratorGrammarFuzzer takes {round((duration2 / duration1) * 100, 1)}% of the time of PGGC-Fuzzer")
print(f"Ratio: PGGC-Fuzzer {round((duration1 / duration2), 1)} times slower than GeneratorGrammarFuzzer")

Example Output

Duration PGGC-Fuzzer: 6.4s
Duration GeneratorGrammarFuzzer: 0.19s
Ratio: GeneratorGrammarFuzzer takes 3.0% of the time of PGGC-Fuzzer
Ratio: PGGC-Fuzzer 33.9 times slower than GeneratorGrammarFuzzer

Expected behavior
I expect the ProbabilisticGeneratorGrammarCoverageFuzzer to be slower than GeneratorGrammarFuzzer, but not 40 times.

Desktop (please complete the following information):

• OS: macOS
• Python version: 3.9