GiacomoPope / kyber-py

A pure python implementation of ML-KEM (FIPS 203) and CRYSTALS-Kyber
MIT License
183 stars 44 forks source link

optimise encoding and decoding #76

Closed GiacomoPope closed 1 month ago

GiacomoPope commented 1 month ago

bit operations are slow and big integers are fast because python. About 1.5 - 2x performance increase and simpler functions.

GiacomoPope commented 1 month ago

@tomato42 this breaks because Python 3.9 doesnt support bit_count() -- I can fix this, but I'm not actually super interested in it working for 3.9, is the reason you want to go back to 3.9 because its not end of life?

The 3.9 version of this is bin(x).count("1") which is a pretty ugly hack.

GiacomoPope commented 1 month ago
def bit_count(x):
    """
    Count the number of bits in x

    Method to support old python as `x.bit_count()`
    was released in Python 3.10 and we currently
    support Python 3.9
    """
    try:
        return x.bit_count()
    except AttributeError:
        return bin(x).count("1")

Begrudgingly wrote something stupid for python 3.9

tomato42 commented 1 month ago

@tomato42 this breaks because Python 3.9 doesnt support bit_count() -- I can fix this, but I'm not actually super interested in it working for 3.9, is the reason you want to go back to 3.9 because its not end of life?

The 3.9 version of this is bin(x).count("1") which is a pretty ugly hack.

I need 3.9 because that's the version that will be supported for the lifetime of RHEL-9

tomato42 commented 1 month ago

Begrudgingly wrote something stupid for python 3.9

the downside of that is that it will be very inefficient in 3.9, and we know the problem is with 3.9, so it's better to define a different method conditionally, based on detected python version

GiacomoPope commented 1 month ago

Sure but if we do a conditional check then it means every python version gets the performance hit by having to do a check before the function. I'd rather just make python 3.9 slower (this string counting is already 6x slower than the 3.10 version so the extra try/except is relatively small.

GiacomoPope commented 1 month ago

Also the CI says failure because of the coverage dropping but I thought it was supposed to be taking into account all the tests from 3.9-3.12 -- so shouldn't both branches of this new function be considered?

tomato42 commented 1 month ago

Sure but if we do a conditional check then it means every python version gets the performance hit by having to do a check before the function. I'd rather just make python 3.9 slower (this string counting is already 6x slower than the 3.10 version so the extra try/except is relatively small.

No, that check is executed then only once, at the time the module is loaded, not every time the function is executed

tomato42 commented 1 month ago

Also the CI says failure because of the coverage dropping but I thought it was supposed to be taking into account all the tests from 3.9-3.12 -- so shouldn't both branches of this new function be considered?

that's because you reduced the amount of code, so it increased the fraction of code that is not covered