[Mnet-devel] erasure code optimization project

[Lenny G Arbage]

--- Zooko <zooko at zooko.com> wrote:
> ...
>
> Now do likewise with the other implementation.  Now
> optimize one of 
> them and
> send me the patch!

  Would you be interested in a 10x speed improvement? 
Large-block FECs can really outperform their
counterparts for file-size data.  Comparison of
LDPC/LDGM (found at
http://www.inrialpes.fr/planete/people/roca/mcl/mcl_download.html)
to the Plank encoder/decoder is very encouraging (I
didn't fiddle around with getting the Rizzo code to
compile):

time ~/tmp/ecopt/plankerasureimpl/rs_encode_file r1 84
170 r1.pcoded/x
 
real    0m0.273s
user    0m0.190s
sys     0m0.010s

time ~/client/fileCoder r1 84 170 x
 
real    0m0.025s
user    0m0.010s
sys     0m0.010s

************ ~= 11x faster!  *****************


Decoding is just as dramatic:

time ~/tmp/ecopt/plankerasureimpl/rs_decode_file x >
r1.decoder 2>decoder.log
 
real    0m0.148s
user    0m0.100s
sys     0m0.050s


time ~/client/fileDecoder 84 170 x
recovered file after 110 blocks.
 
real    0m0.011s
user    0m0.010s
sys     0m0.000s

************ ~= 13x faster!  *****************


  Notice that the decode step for LDGP requires
"slightly more than k" blocks to succeed.  I don't
know what the exact bounds for this number are, but I
believe you can make hard guarantees about what this
value would be, with the common case coming in below
this value.  Requiring more than k blocks to
reconstruct is a tradeoff you'd have to consider.  And
anyway, I may not have picked optimal values for the
parameters into the coder/decoder.  There is a paper
at the website that goes into some depth about
"inefficiency," and shows that values of about k*1.05
are achievable.

  The library was built to support reliable multicast
protocols, and thus all the code/samples are socket-
instead of file-based.  I've written a wrapper library
with sample file coder/decoder programs (which I used
to get the above numbers).  If you are interested in
investigating this for Mnet, I'd be happy to check it
into the ecopt repository.


> I intend to do that last step myself, but first I'm
> going to help an 
> Mnet newbie
> set up a private Mnet network, and update the Mnet
> docs so that the 
> next such
> newbie won't need my help.

  Excellent! 
  
  Lenny



		
__________________________________
Do you Yahoo!?
Read only the mail you want - Yahoo! Mail SpamGuard.
http://promotions.yahoo.com/new_mail