[Mono-dev] [PATCH] Rijndael optimization patch

[Sebastien Pouliot]

On Tue, 2006-09-12 at 00:47 +0900, Kazuki Oikawa wrote:
> Hi.
> 
> I optimized Rijndael implementation.

Great job! I see three factors you addressed:

a. you completely unrolled the Rijndael code;

b. you're working on 32 bits integers instead of bytes;

c. you pass the key as a parameter of the encrypt/decrypt methods, which
allows the current Mono JIT to produce better code (compared to using a
field).


(b) and (c) types of optimization are always nice, but (a) also cause
source code, binary code and JIT time increase so it shouldn't be
applied to every algorithms inside corlib [1].

However, just like SHA1 for hash algorithms, Rijndael is probably the
most used symmetric cipher we have (e.g. our SSL code) so it makes sense
to include the fastest implementation directly in corlib.

Just out of curiosity did you do (and keep) any timing between each
optimization ?


[1] The Crimson project will (soon) address this problem.

> Before (Key and block size is 128bit):
>   2.22 MB/sec
> After:
>   21.9 MB/sec
> (ThinkPad T43, Pentium M 2GHz, Windows XP)

Using a custom tool I have [2] to test .net cryptographic implementation
performance I see a factor between 2.85 and 12.99 of speed improvement,
depending on how you factor the key setup time versus the en-de/cryption
(i.e. lots of small encryption with different key versus a large size
encryption with a single key).

[2] this tool, well hopefully a better version of it, will be part of
Crimson.


There are a lot of possibilities to benchmark (3 key size and 3 block
size) but here are the results for the two most useful one (e.g. used
for SSL). Tests were executed with Mono r65135 (i386) using the default
set of optimizations (i.e. what being used by 98% of Mono users).


128 bits key size (128 bits block size)

Iterations	Size		Encryption	Decryption
65536		16		2.85x		3.58x
1024		1024		6.92x		8.31x
1		1048576		10.29		9.14x

256 bits key size (128 bits block size)

Iterations	Size		Encryption	Decryption
32768		32		4.06x		3.51x
1024		1024		8.75x		11.03x
1		1048576		12.99		12.22x

> Please review it.

I still have a few tests and checks to do before it can be committed
into SVN but it looks very good.

> 
> Best regards.
> Kazuki Oikawa

Thanks!
-- 
Sebastien Pouliot  <sebastien at ximian.com>
Blog: http://pages.infinit.net/ctech/