[Monotone-devel] Botan performance issues

[Jack Lloyd]

[CC'ing monotone-devel as this may be of some interest to people on that list]

I've been doing some analysis to try to get a feel for how much performance can
be improved in Botan, particularly in the area public key algorithms. This
summer (largely due to assistance and feedback from a couple of people working
on Monotone) many of the hash functions and symmetric ciphers ended up getting
significantly faster, and I'd like to do the same for the public key algorithms.

I've been running some benchmarks and comparing Botan's RSA/DSA performance
against some other implementations. Specifically, I ran the Botan benchmarks
using the OpenSSL and GNU MP backends; in this way, the only difference is the
very low-level code (the results of which show that there can be major
performance gains without having to modify any but the lowest-level PK
implementation code). I ran the tests using OpenSSL 0.9.8a configured with
no-asm (which I'm taking as "the best you can do in semi-reasonable C"),
OpenSSL 0.9.8a with assembly (the default performance comparison), and GNU MP
4.1.4 (which probably shows something fairly close to the hardware limit). All
three were built as static libraries to free up the PIC register (I ran these
tests using both shared and and static libraries, and using static libs had a
substantial positive impact). The full results are attached.

My performance goal right now is for RSA/DSA/DH using plain out of the box
Botan to be as fast as using Botan with the OpenSSL engine, backing to latest
OpenSSL version configured with no-asm. Right now, we are off that by 15% and
200% typically, and 800+% in some extreme cases.

Here is my initial things-to-do on this project:
  - Check performance of bigint_mul3 (and possibly of bigint_smul,
    bigint_comba[468], and bigint_karat* individually) against OpenSSL's
    BN - if there is a major difference, figure out why

  - Do the same for raw power_mod calls

  - Profile PK operations using both Botan's default engine and the OpenSSL
    engine, and see where we are losing time (using oprofile, cachegrind, or
    some other finely-tuned profiler - I've never gotten particularly useful
    results out of gprof for this).

  - Identify algorithms which may be superior to the ones currently in use
    (Chapter 14 of the Handbook of Applied Cryptography will be a reasonable
    start); implement, test, profile, and benchmark them. Obvious starting
    points are Montgomery multiplication/reduction, floating window
    exponentiation, and optimizations and precomputations for fixed exponents,
    such as addition chains.

  - Try to get the low-level C/C++ to compile to more efficient code (reducing
    temporaries, better use of software pipelining, inlining, etc) on typical
    compilers.

  - Potentially write assembler implementations for common platforms (I'm
    considering this a last resort)

The major reason for this email is that, basically, I could use some help. I've
got a lot of things going on and don't really have time to spend too many hours
each week on Botan. So, if you wish Botan was faster, and a) can help out with
anything above, or have any suggestions/hints/ideas, or b) know of a person or
company who would like to sponsor this work, please drop me an email.

Jack

timings.txt
Description: Text document