Что может повлиять на производительность сравнения строк Python для строк более 64 символов?

Я пытаюсь оценить, будет ли сравнивать две строки медленнее по мере увеличения их длины. Мои расчеты показывают, что сравнение строк должно принимать амортизированное постоянное время, но мои эксперименты на Python дают странные результаты:

Вот график длины строки (от 1 до 400) по сравнению с временем в миллисекундах. Автоматическая сборка мусора отключена, а gc.collect выполняется между каждой итерацией.

Я сравниваю 1 миллион случайных строк каждый раз, подсчитывая совпадения следующим образом. Процесс повторяется 50 раз, прежде чем принимать мин всех измеренных времен.

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1

Что может объяснить внезапное увеличение длины 64?

Примечание. Следующий сниппет может использоваться для воспроизведения проблемы, предполагающей, что v1 и v2 - это два списка случайных строк длины n, а COUNT - их длина.

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)

Обратите внимание на. Я сделал два дополнительных теста: сравнение строки с is вместо == полностью подавляет проблему, а производительность - около 210 мс/1М. Поскольку упоминание о интернировании было упомянуто, я обязательно добавил пробел после каждой строки, что должно предотвратить интернирование; это ничего не меняет. Это что-то еще, чем интернирование?

Ответ 1

Python может "ставить" короткие строки; хранит их в специальном кеше и повторно использует строковые объекты из этого кеша.

При сравнении строк сначала проверяется, является ли он одним и тем же указателем (например, интернированная строка):

if (a == b) {
    switch (op) {
    case Py_EQ:case Py_LE:case Py_GE:
        result = Py_True;
        goto out;
// ...

Только если это сравнение указателей не выполняется, оно использует проверку размера и memcmp для сравнения строк.

Интерполяция обычно выполняется только для идентификаторов (имена функций, аргументы, атрибуты и т.д.), однако не для строковых значений, созданных во время выполнения.

Другим возможным виновником являются строковые константы; строковые литералы, используемые в коде, хранятся в качестве констант во время компиляции и повторно используются повсюду; снова создается только один объект, а тесты идентичности выполняются быстрее.

Для строковых объектов, которые не являются одинаковыми, тесты Python для равной длины, равные первым символам, затем используют функцию memcmp() для внутренних строк C. Если ваши строки не интернированы или иным образом повторно используют одни и те же объекты, все другие характеристики скорости опускаются до функции memcmp().

Ответ 2

Я просто делаю дикие догадки, но вы спросили "что может", а не то, что здесь имеет место:

Размер строки кэша ЦП составляет 64 байта, а более длинные строки - кэш.
Python может хранить строки из 64 байтов в одном виде структуры и более длинные строки в более сложной структуре.
Связано с последним: оно может содержать нулевые строки в массив из 64 байтов и может использовать очень быстрые векторные инструкции SSE2 для соответствия двум строкам.