[mnet-devel] Re: [mnet-cvs]terminology doc (icepick could double-check)

[Zooko]

> No, I think this would work great.  I *sorta* understand the algo behind
> (going read the paper again), but there is no reason I can think of that
> this wouldn't work.
> 
> Could you describe the trick?

Well, as I mentioned in another e-mail, the current system is probably 
better!  It's probably better to wait 1 or 2 seconds while generating a share, 
then publish that share, and so forth, instead of waiting a few dozen seconds 
to generate all the shares, then you have to store them all while publishing.

But anyway, here is my idea.

There is code in Rizzo's fec.c, which takes "source packets" and generates 
"output packets".  Inside of that code, it uses a black box which does 
mathematical magic on "source bytes" and generates "output bytes".  I intend 
to leave that inner mathematical black box firmly closed, because I do not 
understand the thing that lives inside of it, but open the outer "packetizing" 
code and change its behavior.

So assume that we have the inner black box, which operates not on packets, but 
on bytes.  The inner black box takes, for example, 128 input bytes, and 
generates 128 output bytes.  They have the magical property that if you select 
any 128 out of the whole 256, then you can reconstruct the original 128 input 
bytes.

How is the larger notion of a "packet", which Mnet calls a "share", built out 
of the smaller notion of bytes?  Here is my current understanding of how fec.c 
does this:

To generate the first byte of the first output packet, read in all 128 of the 
first bytes of the 128 input packets, and generate that byte.  Then generate 
the second byte of the first output packet by reading in all 128 of the second 
bytes of the 128 input packets, etc.  After you've generated all the bytes of 
the first output packet, you return that output packet to the caller, who will 
probably then request that you start working on the second output packet.

To generate the first byte of the second output packet, read in all 128 of the 
first bytes of the 128 input packets...

Here is how I propose to speed it up, at the cost of having to generate the 
output packets all-at-once rather than one-at-a-time:

Read in all 128 of the first bytes of the 128 input packets, and generate the 
first byte of the first output packet, the first byte of the second output 
packet, etc., until you've generated all 128 of the first bytes of the 128 
output packets.  Now you never need to read in the first bytes of the input 
packets again.

Hm.  There's even a *further* time/space tradeoff that *might* help (or might 
hurt) on top of this one.  That is to bundle up the 128 first bytes of the 
input packets into sequential memory so that reading in the first one also 
fetches the next 63 of them all the way into the L1 cache.

--Z

P.S.  Before anyone actually spent time on this hack, they should double-check 
my understanding of how the "collect bytes into packets" algorithm works.

P.P.S.  Again I re-iterate that I don't think this is needed for Mnet, and 
*perhaps* not even for HiveCache, but it is fun so I'm continuing to think 
about it.  I want to practice this level of optimization.



-------------------------------------------------------
This SF.Net email sponsored by: Free pre-built ASP.NET sites including
Data Reports, E-commerce, Portals, and Forums are available now.
Download today and enter to win an XBOX or Visual Studio .NET.
http://aspnet.click-url.com/go/psa00100003ave/direct;at.aspnet_072303_01/01
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel