Ответ 1
TL: DR: сравнение срезов - это некоторые служебные данные Python + высоко оптимизированный memcmp (если только обработка UTF-8?). В идеале, используйте срез, чтобы найти первое несоответствие в пределах менее 128 байтов или что-то в этом роде, а затем цикл char за раз.
Или, если это опция и проблема важна, создайте измененную копию оптимизированного asm memcmp, который возвращает позицию первого разницы вместо равного/не равного; он будет работать так же быстро, как один == для всех строк. У Python есть способы вызвать собственные функции C/asm в библиотеках.
Это разочаровывающее ограничение того, что CPU может сделать это невероятно быстро, но Python не позволяет (AFAIK) предоставить вам доступ к оптимизированному циклу сравнения, который сообщает вам позицию несоответствия, а не просто равную/большую/меньшую.
Это абсолютно нормально, что служебные данные интерпретатора доминируют над стоимостью реальной работы в простом цикле Python с CPython. Построение алгоритма из оптимизированных строительных блоков стоит того, даже если это означает выполнение более полной работы. Вот почему NumPy хорош, но чередование по элементам по элементам ужасно. Разница в скорости может быть чем-то вроде 20-100, для CPython и скомпилированного цикла C (asm) для сравнения одного байта за раз (составленные цифры, но, вероятно, с точностью до порядка).
Сравнение блоков памяти для равенства, вероятно, является одним из самых больших несоответствий между циклами Python и работает со всем списком/срезом. Это обычная проблема с высоко оптимизированными решениями (например, большинство реализаций libc (включая OS X) имеют ручной векторизованный asm memcmp с ручным кодированием, который использует SIMD для сравнения 16 или 32 байта параллельно и работает намного быстрее, чем байт -at-time-цикл в C или сборке). Таким образом, существует еще один фактор от 16 до 32 (если пропускная способность памяти не является узким местом), умножая коэффициент разницы в скорости от 20 до 100 между контурами Python и C. Или в зависимости от того, насколько оптимизирован ваш memcmp, возможно, "только" 6 или 8 байтов за цикл.
При использовании данных, горячих в кешках L2 или L1d для буферов среднего размера, разумно ожидать 16 или 32 байта за цикл для memcmp на процессоре Haswell или более позднем. (именование i3/i5/i7 началось с Nehalem; только i5 недостаточно, чтобы рассказать нам о вашем CPU.)
Я не уверен, что вам или вашим обеим сравнениям приходится обрабатывать UTF-8 и проверять классы эквивалентности или различные способы кодирования одного и того же символа. В худшем случае, если ваш цикл Python char -at-a-time должен проверять наличие многобайтовых символов, но ваш анализ фрагментов может просто использовать memcmp.
Написание эффективной версии в Python:
Мы просто полностью боремся с языком, чтобы получить эффективность: ваша проблема почти такая же, как и стандартная библиотечная функция C memcmp, за исключением того, что вы хотите, чтобы позиция первой разницы вместо -/0/+ результат, указывающий, какая строка больше. Цикл поиска идентичен, это просто разница в том, что делает функция после нахождения результата.
Ваш двоичный поиск - это не лучший способ использования быстрого сравнительного строительного блока. У сравнения фрагментов все еще есть стоимость O(n), а не O(1), с гораздо меньшим постоянным коэффициентом. Вы можете и должны избегать повторного сравнения запусков буферов повторно с помощью с помощью срезов для сравнения больших кусков, пока не найдете несоответствие, а затем вернитесь к этому последнему куску с меньшим размером куска.
# I don't actually know Python; consider this pseudo-code
# or leave an edit if I got this wrong :P
chunksize = min(8192, len(smaller))
# possibly round chunksize down to the next lowest power of 2?
start = 0
while start+chunksize < len(smaller):
if smaller[start:start+chunksize] == bigger[start:start+chunksize]:
start += chunksize
else:
if chunksize <= 128:
return char_at_a_time(smaller[start:start+chunksize], bigger[start:start+chunksize])
else:
chunksize /= 8 # from the same start
# TODO: verify this logic for corner cases like string length not a power of 2
# and/or a difference only in the last character: make sure it does check to the end
Я выбрал 8192, потому что ваш CPU имеет кеш-память 32kiB L1d, поэтому общий размер кеша из двух 8-килобайтовых фрагментов составляет 16k, половина вашего L1d. Когда цикл обнаружит несоответствие, он будет повторно проверять последние 8kiB в 1k кусках, и эти сравнения будут перебирать данные, которые все еще горячие в L1d. (Заметим, что если == обнаружено несоответствие, возможно, он коснулся только данных до этой точки, а не всего 8k. Но предварительная выборка HW будет продолжать несколько дальше.)
Коэффициент 8 должен быть хорошим балансом между использованием больших ломтиков для локализации быстро и без необходимости прохождения нескольких проходов по тем же данным. Конечно, это настраиваемый параметр, а также размер блока. Чем больше несоответствие между Python и asm, тем меньше этот фактор должен уменьшить итерации цикла Python.)
Надеемся, что 8k достаточно велико, чтобы скрыть накладные расходы на Python/slice; аппаратная предварительная выборка должна по-прежнему работать во время накладных расходов Python между вызовами memcmp от интерпретатора, поэтому нам не нужна гранулярность, чтобы она была огромной. Но для действительно больших строк, если 8k не насыщает полосу пропускания памяти, то, возможно, сделает ее 64k (ваш кэш L2 равен 256kiB, i5 действительно так говорит).
Как точно memcmp так быстро:
Я запускаю это на Intel Core i5, но я бы предположил, что получаю те же результаты на большинстве современных процессоров.
Даже в C, Почему memcmp намного быстрее, чем проверка цикла? memcmp быстрее, чем цикл сравнения байтов в момент времени, потому что даже компиляторы C не велики в (или полностью неспособны) авто-векторизации поисковых циклов.
Даже без аппаратной поддержки SIMD оптимизированный memcmp может проверять 4 или 8 байтов за раз (размер слова/ширина регистра) даже на простом CPU без 16-байтового или 32-байтового SIMD.
Но большинство современных процессоров и всех x86-64 имеют инструкции SIMD. SSE2 является базовым для x86-64 и доступен как расширение в 32-битном режиме.
SSE2 или AVX2 memcmp могут использовать pcmpeqb/pmovmskb для сравнения параллельно 16 или 32 байта. (Я не буду подробно разбираться в том, как писать memcmp в x86 asm или с помощью C intrinsics. Google это отдельно и/или искать эти инструкции asm в задании набора инструкций x86, например http://felixcloutier.com/x86/index.html. См. также wiki для ссылок asm и производительности. Например Почему Skylake намного лучше, чем Broadwell-E для однопоточной пропускной способности памяти? имеет некоторую информацию об ограничении пропускной способности одноядерной памяти.)
Я нашел старую версию с 2005 года Apple x86-64 memcmp (на языке ассемблера синтаксиса AT & T) в своей сети с открытым исходным кодом сайт. Это определенно может быть лучше; для больших буферов он должен выровнять один указатель источника и использовать только movdqu для другого, позволяя movdqu, затем pcmpeqb с операндом памяти вместо 2x movdqu, даже если строки смещены относительно друг друга. xorl $0xFFFF,%eax/jnz также не является оптимальным для процессоров, где cmp/jcc может использовать плавкий предохранитель, но xor / jcc не может.
Развертывание для проверки всей строки в 64-байтовом кэше сразу также будет скрывать накладные расходы на цикл. (Это та же идея, что и большой кусок, а затем зацикливается на нем, когда вы находите хит). Glibc AVX2- movbe версия делает это с помощью vpand, чтобы совместить результаты сравнения в основном цикле с большим буфером, причем конечный комбайн является vptest, который также устанавливает флаги из результата. (Меньший размер кода, но не менее, чем vpand/vpmovmskb/cmp/jcc, но не имеет недостатков и, возможно, более низкая латентность, чтобы уменьшить отклонения от ветвления - неверно предсказанные на выходе цикла). Glibc выполняет динамическую диспетчеризацию процессора при динамическом времени соединения; он выбирает эту версию для процессоров, которые ее поддерживают.
Надеюсь, Apple memcmp лучше в эти дни; Тем не менее, я не вижу источника для него в самом последнем каталоге Libc. Надеюсь, они отправят во время работы версию AVX2 для Haswell и более поздних процессоров.
Цикл LLoopOverChunks в связанной версии я будет работать только с 1 итерацией (16 байт с каждого входа) на 2,5 цикла на Haswell; 10 скомпилированных доменов. Но это намного быстрее, чем 1 байт за цикл для наивного цикла C, или намного хуже, чем для цикла Python.
Цикл Glibc L(loop_4x_vec): - это 18 совместимых доменов uops и, таким образом, может работать только чуть меньше 32 байт (с каждого входа) за такт, когда данные горячие в кеше L1d. В противном случае это будет узким местом по пропускной способности L2. Это могло бы быть 17 uops, если бы они не использовали дополнительную инструкцию внутри цикла, уменьшающую отдельный счетчик циклов, и вычисляли конечный указатель вне цикла.
Поиск инструкций/горячих точек в собственном коде интерпретатора Python
Как я мог развернуть, чтобы найти инструкции C и инструкции процессора, которые вызывает мой код?
В Linux вы можете запустить perf record python ..., затем perf report -Mintel, чтобы узнать, какие функции CPU затрачивают больше всего времени, и какие инструкции в этих функциях были самыми горячими. Вы получите результаты, подобные тому, что я опубликовал здесь: Почему float() быстрее, чем int()?. (Перейдите к любой функции, чтобы увидеть текущие машинные инструкции, которые были запущены, показаны как язык ассемблера, потому что perf имеет встроенный дизассемблер.)
Для более тонкого представления, которое отображает график вызовов для каждого события, см. linux perf: как интерпретировать и находить горячие точки.
(Когда вы хотите оптимизировать программу, вы хотите знать, какие вызовы функций дороги, поэтому вы можете попытаться избежать их в первую очередь. Профилирование только для "собственного" времени найдет горячие точки, но вы не всегда будут знать, какие разные вызывающие лица вызвали заданный цикл для запуска большей части итераций. См. ответ Майка Данлэйви на этот главный вопрос.)
Но для этого конкретного случая профилирование интерпретатора, использующего версию для сравнения фрагментов над большими строками, должно, мы надеемся, найти цикл memcmp, где я думаю, что он будет тратить большую часть своего времени. (или для версии char -at-a-time найдите код интерпретатора, который "горячий".)
Затем вы можете непосредственно увидеть, какие инструкции asm находятся в цикле. Из имен функций, предполагая, что ваш двоичный код имеет какие-либо символы, вы, вероятно, можете найти источник. Или, если у вас есть версия Python, построенная с информацией об отладке, вы можете напрямую перейти к источнику из профиля. (Не отладка с оптимизацией отключена, просто с полными символами).