Что такое _md5.md5 и почему hashlib.md5 намного медленнее?

Question

Нашел недокументированное _md5, когда разочаровался медленной реализацией stdlib hashlib.md5.

На MacBook:

>>> timeit hashlib.md5(b"hello world")
597 ns ± 17.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit _md5.md5(b"hello world")
224 ns ± 3.18 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> _md5
<module '_md5' from '/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/lib-dynload/_md5.cpython-37m-darwin.so'>

На коробке Windows:

>>> timeit hashlib.md5(b"stonk overflow")
328 ns ± 21.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit _md5.md5(b"stonk overflow")
110 ns ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> _md5
<module '_md5' (built-in)>

В поле Linux:

>>> timeit hashlib.md5(b"https://adventofcode.com/2016/day/5")
259 ns ± 1.33 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit _md5.md5(b"https://adventofcode.com/2016/day/5")
102 ns ± 0.0576 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> _md5
<module '_md5' from '/usr/local/lib/python3.8/lib-dynload/_md5.cpython-38-x86_64-linux-gnu.so'>

Для хэширования коротких сообщений это намного быстрее. Для длинных сообщений аналогичная производительность.

Почему он скрыт в модуле расширения подчеркивания, и почему эта более быстрая реализация не используется по умолчанию в hashlib? Что такое _md5 модуль и почему у него нет publi c API?

Answer 1

Модули Python publi c обычно делегируют методы скрытому модулю.

Например, полный код модуля collections.abc:

from _collections_abc import *
from _collections_abc import __all__

Функции hashlib создаются динамически :

for __func_name in __always_supported:
    # try them all, some may not work due to the OpenSSL
    # version not supporting that algorithm.
    try:
        globals()[__func_name] = __get_hash(__func_name)

Определение always_supported равно :

__always_supported = ('md5', 'sha1', 'sha224', 'sha256', 'sha384', 'sha512',
                      'blake2b', 'blake2s',
                      'sha3_224', 'sha3_256', 'sha3_384', 'sha3_512',
                      'shake_128', 'shake_256')

И get_hash либо __get_openssl_constructor, либо __get_builtin_constructor:

try:
    import _hashlib
    new = __hash_new
    __get_hash = __get_openssl_constructor
    algorithms_available = algorithms_available.union(
            _hashlib.openssl_md_meth_names)
except ImportError:
    new = __py_new
    __get_hash = __get_builtin_constructor

__get_builtin_constructor является запасным вариантом для (снова) скрытого _hashlib модуля :

def __get_openssl_constructor(name):
    if name in __block_openssl_constructor:
        # Prefer our blake2 and sha3 implementation.
        return __get_builtin_constructor(name)
    try:
        f = getattr(_hashlib, 'openssl_' + name)
        # Allow the C module to raise ValueError.  The function will be
        # defined but the hash not actually available thanks to OpenSSL.
        f()
        # Use the C function directly (very fast)
        return f
    except (AttributeError, ValueError):
        return __get_builtin_constructor(name)

Выше в hashlib код , у вас есть это:

def __get_builtin_constructor(name):
    cache = __builtin_constructor_cache
    ...
    elif name in {'MD5', 'md5'}:
        import _md5
        cache['MD5'] = cache['md5'] = _md5.md5

Но md5 не в __block_openssl_constructor, следовательно, Версия _hashlib/openssl предпочтительнее версии _md5/builtin:

Подтверждение в REPL:

>>> hashlib.md5
<built-in function openssl_md5>
>>> _md5.md5
<built-in function md5>

Эти функции являются различными реализациями алгоритма MD5, и openssl_md5 выполняет вызов к динамической c системной библиотеке. Вот почему у вас есть некоторые изменения производительности. Первая версия определяется в https://github.com/python/cpython/blob/master/Modules/_hashopenssl.c, а другая - в https://github.com/python/cpython/blob/master/Modules/md5module.c, если вы хотите проверить различия.

Тогда почему _md5.md5 функция определена, но никогда не использовалась? Я предполагаю, что идея состоит в том, чтобы гарантировать, что некоторые алгоритмы всегда доступны, даже если openssl отсутствует:

Конструкторами для алгоритмов ha sh, которые всегда присутствуют в этом модуле, являются sha1 (), sha224 (), sha256 (), sha384 (), sha512 (), blake2b () и blake2s (). (https://docs.python.org/3/library/hashlib.html)

Answer 2

Til Python 2. 5 , хеши и дайджесты были реализованы в своих собственных модулях (например, [Python 2.Docs]: md5 - MD5 алгоритм дайджеста сообщений ).
Начиная с v2.5 , [Python 2.6.Docs]: hashlib - добавлены защищенные хэши и дайджесты сообщений . Его целью было:

1. Предложить единый метод доступа к хешам / дайджестам (через их имя)
2. Переключить ( по умолчанию ) на внешнюю криптографию провайдера (кажется логичным шагом делегировать какую-то сущность, специализирующуюся в этой области, так как поддержание всех этих алгоритмов может быть излишним). В то время OpenSSL был лучшим выбором: достаточно зрелым, известным и совместимым (было множество похожих Java провайдеров, но они были довольно бесполезны)

В качестве побочного эффекта # 2. реализации Python были скрыты от публикуемого c API (переименовал их: _md5 , _sha1 , _sha256 , _sha512 , и добавлены последние: _blake2 _sha3 ), поскольку избыточность часто создает путаницу.
Но еще одним побочным эффектом была _hashlib.so зависимость от OpenSSL libcrypto * .so (это Nix (по крайней мере Lnx ), специфицирующий c, Win , статус c libeay32.lib был связан в _hashlib.pyd , а также _ssl.pyd (что я считаю хромым), до v3. 7 + , где OpenSSL .dll s являются частью установки Python).
Вероятно, на 90 +% машин все было гладко, так как OpenSSL был / установлен по умолчанию, но для тех, где это не так, многие вещи могут сломаться потому что, например, hashlib импортируется многими модулями (одним из таких примеров является random , который сам импортируется многими другими), поэтому тривиальные части кода, которые не связаны с все, чтобы криптография (по крайней мере, не в 1 ^ST зрение) перестанет работать . Вот почему старые реализации сохраняются (но, опять же, они являются только запасными вариантами, поскольку OpenSSL версии поддерживаются / должны поддерживаться лучше).

[cfati@cfati-ubtu16x64-0:~/Work/Dev/StackOverflow/q059955854]> ~/sopr.sh
*** Set shorter prompt to better fit when pasted in StackOverflow (or other) pages ***

[064bit-prompt]> python3 -c "import sys, hashlib as hl, _md5, ssl;print(\"{0:}\n{1:}\n{2:}\n{3:}\".format(sys.version, _md5, hl._hashlib, ssl.OPENSSL_VERSION))"
3.5.2 (default, Oct  8 2019, 13:06:37)
[GCC 5.4.0 20160609]
<module '_md5' (built-in)>
<module '_hashlib' from '/usr/lib/python3.5/lib-dynload/_hashlib.cpython-35m-x86_64-linux-gnu.so'>
OpenSSL 1.0.2g  1 Mar 2016
[064bit-prompt]>
[064bit-prompt]> ldd /usr/lib/python3.5/lib-dynload/_hashlib.cpython-35m-x86_64-linux-gnu.so
        linux-vdso.so.1 =>  (0x00007fffa7d0b000)
        libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f50d9e4d000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f50d9a83000)
        libcrypto.so.1.0.0 => /lib/x86_64-linux-gnu/libcrypto.so.1.0.0 (0x00007f50d963e000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f50da271000)
        libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f50d943a000)
[064bit-prompt]>
[064bit-prompt]> openssl version -a
OpenSSL 1.0.2g  1 Mar 2016
built on: reproducible build, date unspecified
platform: debian-amd64
options:  bn(64,64) rc4(16x,int) des(idx,cisc,16,int) blowfish(idx)
compiler: cc -I. -I.. -I../include  -fPIC -DOPENSSL_PIC -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -g -O2 -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM -DECP_NISTZ256_ASM
OPENSSLDIR: "/usr/lib/ssl"
[064bit-prompt]>
[064bit-prompt]> python3 -c "import _md5, hashlib as hl;print(_md5.md5(b\"A\").hexdigest(), hl.md5(b\"A\").hexdigest())"
7fc56270e7a70fa81a5935b72eacbe29 7fc56270e7a70fa81a5935b72eacbe29

Согласно [Python 3.Docs]: hashlib. gorithms_guaranteed :

Набор, содержащий имена алгоритмов ha sh, гарантированно поддерживаемых этот модуль на всех платформах. Обратите внимание, что «md5» находится в этом списке, несмотря на то, что некоторые вышестоящие поставщики предлагают странную «FIPS-совместимую» сборку Python, которая исключает ее.

Ниже приведен пример пользовательского Python 2.7 установка (которую я собрал довольно давно go, стоит упомянуть, что он динамически связывается с OpenSSL .dll s):

e:\Work\Dev\StackOverflow\q059955854>sopr.bat
*** Set shorter prompt to better fit when pasted in StackOverflow (or other) pages ***

[prompt]> "F:\Install\pc064\HPE\OPSWpython\2.7.10__00\python.exe" -c "import sys, ssl;print(\"{0:}\n{1:}\".format(sys.version, ssl.OPENSSL_VERSION))"
2.7.10 (default, Mar  8 2016, 15:02:46) [MSC v.1600 64 bit (AMD64)]
OpenSSL 1.0.2j-fips  26 Sep 2016

[prompt]> "F:\Install\pc064\HPE\OPSWpython\2.7.10__00\python.exe" -c "import hashlib as hl;print(hl.md5(\"A\").hexdigest())"
7fc56270e7a70fa81a5935b72eacbe29

[prompt]> "F:\Install\pc064\HPE\OPSWpython\2.7.10__00\python.exe" -c "import ssl;ssl.FIPS_mode_set(True);import hashlib as hl;print(hl.md5(\"A\").hexdigest())"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
ValueError: error:060A80A3:digital envelope routines:FIPS_DIGESTINIT:disabled for fips

Что касается вопроса о скорости, я могу только предположить:

• Python реализация была (очевидно) написана специально для Python, что означает, что он «более оптимизирован» (да, это грамматически неверно) для Python, чем универсальная c версия, и также находится в python*. So (или сам исполняемый файл python)
• Реализация OpenSSL находится в libcrypto * .so , и к нему обращается оболочка _hashlib.so , которая выполняет обратное преобразование типов Python ( PyObject *) ) и OpenSSL ( EVP_MD_CTX *)

Учитывая вышеизложенное, будет иметь смысл, что первый будет (немного) быстрее ( по крайней мере для небольших сообщений, где издержки (вызов функции и другие базовые операции Python) занимают значительный процент от общего времени по сравнению с самим хэшированием). Есть и другие факторы, которые следует учитывать (например, * были ли использованы OpenSSL ускорения ассемблера).

---

Обновление # 0

Ниже приведены некоторые мои собственные тесты.

code00.py :

#!/usr/bin/env python

import sys
from hashlib import md5 as md5_openssl
from _md5 import md5 as md5_builtin
import timeit


def main(*argv):
    base_text = b"A"
    number = 1000000
    print("timeit attempts number: {0:d}".format(number))
    #x = []
    #y = {}
    for count in range(0, 16):
        factor = 2 ** count
        text = base_text * factor
        globals_dict = {"text": text}
        #x.append(factor)
        print("\nUsing a {0:8d} (2 ** {1:2d}) bytes message".format(len(text), count))
        for func in [
            md5_openssl,
            md5_builtin,
        ]:
            globals_dict["md5"] = func

            t = timeit.timeit(stmt="md5(text)", globals=globals_dict, number=number)
            print("    {0:12s} took: {1:11.6f} seconds".format(func.__name__, t))
            #y.setdefault(func.__name__, []).append(t)
    #print(x, y)


if __name__ == "__main__":
    print("Python {0:s} {1:d}bit on {2:s}\n".format(" ".join(item.strip() for item in sys.version.split("\n")), 64 if sys.maxsize > 0x100000000 else 32, sys.platform))
    main(*sys.argv[1:])
    print("\nDone.")

Вывод :

• Win 10 pc064 (работает на ноутбуке Dell Precision 5510 ):

  [prompt]> "e:\Work\Dev\VEnvs\py_pc064_03.07.06_test0\Scripts\python.exe" code00.py
  Python 3.7.6 (tags/v3.7.6:43364a7ae0, Dec 19 2019, 00:42:30) [MSC v.1916 64 bit (AMD64)] 64bit on win32
  
  timeit attempts number: 1000000
  
  Using a        1 (2 **  0) bytes message
      openssl_md5  took:    0.449134 seconds
      md5          took:    0.120021 seconds
  
  Using a        2 (2 **  1) bytes message
      openssl_md5  took:    0.460399 seconds
      md5          took:    0.118555 seconds
  
  Using a        4 (2 **  2) bytes message
      openssl_md5  took:    0.451850 seconds
      md5          took:    0.121166 seconds
  
  Using a        8 (2 **  3) bytes message
      openssl_md5  took:    0.438398 seconds
      md5          took:    0.118127 seconds
  
  Using a       16 (2 **  4) bytes message
      openssl_md5  took:    0.454653 seconds
      md5          took:    0.122818 seconds
  
  Using a       32 (2 **  5) bytes message
      openssl_md5  took:    0.450776 seconds
      md5          took:    0.118594 seconds
  
  Using a       64 (2 **  6) bytes message
      openssl_md5  took:    0.555761 seconds
      md5          took:    0.278812 seconds
  
  Using a      128 (2 **  7) bytes message
      openssl_md5  took:    0.681296 seconds
      md5          took:    0.455921 seconds
  
  Using a      256 (2 **  8) bytes message
      openssl_md5  took:    0.895952 seconds
      md5          took:    0.807457 seconds
  
  Using a      512 (2 **  9) bytes message
      openssl_md5  took:    1.401584 seconds
      md5          took:    1.499279 seconds
  
  Using a     1024 (2 ** 10) bytes message
      openssl_md5  took:    2.360966 seconds
      md5          took:    2.878650 seconds
  
  Using a     2048 (2 ** 11) bytes message
      openssl_md5  took:    4.383245 seconds
      md5          took:    5.655477 seconds
  
  Using a     4096 (2 ** 12) bytes message
      openssl_md5  took:    8.264774 seconds
      md5          took:   10.920909 seconds
  
  Using a     8192 (2 ** 13) bytes message
      openssl_md5  took:   15.521947 seconds
      md5          took:   21.895179 seconds
  
  Using a    16384 (2 ** 14) bytes message
      openssl_md5  took:   29.947287 seconds
      md5          took:   43.198639 seconds
  
  Using a    32768 (2 ** 15) bytes message
      openssl_md5  took:   59.123447 seconds
      md5          took:   86.453821 seconds
  
  Done.
  

• Ubtu 16 pc064 ( VM в VirtualBox на указанном компьютере):

  [064bit-prompt]> python3 code00.py
  Python 3.5.2 (default, Oct  8 2019, 13:06:37) [GCC 5.4.0 20160609] 64bit on linux
  
  timeit attempts number: 1000000
  
  Using a        1 (2 **  0) bytes message
      openssl_md5  took:    0.246166 seconds
      md5          took:    0.130589 seconds
  
  Using a        2 (2 **  1) bytes message
      openssl_md5  took:    0.251019 seconds
      md5          took:    0.127750 seconds
  
  Using a        4 (2 **  2) bytes message
      openssl_md5  took:    0.257018 seconds
      md5          took:    0.123116 seconds
  
  Using a        8 (2 **  3) bytes message
      openssl_md5  took:    0.245399 seconds
      md5          took:    0.128267 seconds
  
  Using a       16 (2 **  4) bytes message
      openssl_md5  took:    0.251832 seconds
      md5          took:    0.136373 seconds
  
  Using a       32 (2 **  5) bytes message
      openssl_md5  took:    0.248410 seconds
      md5          took:    0.140708 seconds
  
  Using a       64 (2 **  6) bytes message
      openssl_md5  took:    0.361016 seconds
      md5          took:    0.267021 seconds
  
  Using a      128 (2 **  7) bytes message
      openssl_md5  took:    0.478735 seconds
      md5          took:    0.413986 seconds
  
  Using a      256 (2 **  8) bytes message
      openssl_md5  took:    0.707602 seconds
      md5          took:    0.695042 seconds
  
  Using a      512 (2 **  9) bytes message
      openssl_md5  took:    1.216832 seconds
      md5          took:    1.268570 seconds
  
  Using a     1024 (2 ** 10) bytes message
      openssl_md5  took:    2.122014 seconds
      md5          took:    2.429623 seconds
  
  Using a     2048 (2 ** 11) bytes message
      openssl_md5  took:    4.158188 seconds
      md5          took:    4.847686 seconds
  
  Using a     4096 (2 ** 12) bytes message
      openssl_md5  took:    7.839173 seconds
      md5          took:    9.242224 seconds
  
  Using a     8192 (2 ** 13) bytes message
      openssl_md5  took:   15.282232 seconds
      md5          took:   18.368874 seconds
  
  Using a    16384 (2 ** 14) bytes message
      openssl_md5  took:   30.681912 seconds
      md5          took:   36.755073 seconds
  
  Using a    32768 (2 ** 15) bytes message
      openssl_md5  took:   60.230543 seconds
      md5          took:   73.237356 seconds
  
  Done.
  

результат, похоже, совсем не твой. В моем случае:

• Начиная где-то в сообщениях размером [~ 512B .. ~ 1 КБ ], реализация OpenSSL , кажется, выполняет лучше, чем встроенный
• Я знаю, что слишком мало результатов, чтобы претендовать на шаблон, но кажется, что обе реализации кажутся линейно пропорциональными (с точки зрения времени) размеру сообщения (но встроенный наклон кажется быть немного круче - это означает, что в долгосрочной перспективе он будет работать хуже

В заключение, если все ваши сообщения маленькие, а встроенная реализация работает лучше для вас, используйте ее.

---

Обновление # 1

Графическое представление (мне пришлось уменьшить число итераций timeit на порядка величины, так как это займет слишком много времени для больших сообщений):

и масштабирование области, где пересекаются 2 графика:

Answer 3

Моя теория - оглядываться на ошибки. python .org и читать cpython git историю коммитов:

cpython перешли на openssl md5 в 2005 году, потому что это было быстрее, чем встроенная реализация. Они добавили новую встроенную реализацию в 2007 году, которая работает быстрее, чем openssl, но никогда не переключалась обратно. Оба эти изменения были сделаны Грегори П. Смитом.

Вот мое свидетельство.

• В 2005 году Грег создал выпуски bpo"sha и md5. следует использовать OpenSSL, когда это возможно ". Это изменение внесено в этот коммит .
• В 2007 году Грег добавил новый, быстрый модуль md5 в этот коммит .
• _md5 реализация, по-видимому, практически одинакова в Python 3.8 (я смотрю на commit ea316fd21527)

Я думаю, что сопровождающие cpython, вероятно, будут открыты для переключения обратно на _md5 когда это доступно, поскольку больше не правда, что реализация openssl быстрее (и, возможно, не соответствует действительности в течение последних 13 лет).