Kerl operations are pretty slow

[scottbelden]

I was trying to figure out why get_account_data sometimes takes seemingly forever. For example, take the following script:

from iota import Iota
import time

seed = 'A' * 81

api = Iota('http://astra2261.startdedicated.net:14265', seed)

start = time.time()
api.get_account_data()
print(f'total time: {time.time() - start}')

This took me 87.39378452301025 seconds to run.

I started profiling and noticed that one of the reasons is that that seed has a lot of addresses that have been used, and generating those addresses is not particularly fast. For example, here's another script that will generate 10 addresses:

from iota import Iota
import time
from iota.commands.extended.utils import iter_used_addresses
from iota.crypto.addresses import AddressGenerator

seed = 'A' * 81

api = Iota('http://foo.bar:14265', seed)
adapter = api.adapter

start = time.time()
addresses = []
for addy in AddressGenerator(api.seed).create_iterator(0):
    addresses.append(addy)
    if len(addresses) == 10:
        break
print(addresses)
print(f'total time: {time.time() - start}')

It takes me 4.875983476638794 seconds to just generate those addresses.

It seems a lot of the time is spent in iota/crypto/kerl/conv.py doing the conversion from bytes to trits and trits to bytes. I played with re-working these functions to use cython and am getting some promising results. My hacking around so far is here (forgive the ugliness, it definitely needs polishing; I just wanted to see if I could get it working).

If I run the same scripts using the cython version as it is (and it could definitely be improved some), I got a time of 2.0970706939697266 to create the 10 addresses (less than half the time of the python version) and 68.44585180282593 to do get_account_data (about 20 seconds faster).

I might try to write a cython extension that can be installed (similar to how the curl extension is installed) that would provide the speedups for the kerl module. Obviously it would need extensive testing, but fortunately some test vectors already exist so with that and tests to compare it to the python version it should be possible to show that it produces equivalent outputs for a given input.

Would you be open to something like that?

[todofixthis]

Hey Scott! Great observations, thanks for investigating this!

Using C extensions to speed up the crypto functionality is awesome, and we already have a precedent for that.

Using Cython is an interesting approach. I must confess; I've never used it before. Is this something that will work "out of the box", or will users have to install Cython before they can pip install pyota?

Is it possible to make this an optional install (e.g., pip install pyota[ccurl,ckerl])?

[scottbelden]

Users do not have to have cython installed if the c files are generated and packaged up on pypi. This is what we do on fastavro and what I would plan to do. They would of course need a compiler if compiled wheels aren't provided (as with any c extension AFAIK).

And yes, I think an optional install as you mentioned would make sense.

[microtransactions]

@scottbelden I know this might be an older post, but thank you for the C rework of this file! I'm doing a password recovery now and it is indeed much much faster at generating addresses. I didn't do a benchmark yet but from the console output I'm seeing is working blazing fast. I would say it's lighter on the CPU temps but heavier on RAM usage at about 40x increase.

[scottbelden]

Thanks! I haven't looked at this in years but it's good to hear that at least some people have found it useful. It was a fun experience while implementing the changes.

[microtransactions]

After some headscratching regarding the huge memory leak, I've added this instruction free(bytesArray) at line 196. From my limited understanding the memory was not being freed up at the end of the function. Works great now with no issues.