[viff-devel] Multiparty AES in less than 3 seconds per block thanks to Twisted hack

[Martin Geisler]

Martin Geisler <mg at daimi.au.dk> writes:

> I'll try and write a mail to them to explain our problem in more
> detail. Maybe your short patch didn't provide enough information when
> taken out of context.

I've included a larger answer from Jean-Paul Calderone below -- you can
read in context here:

  http://thread.gmane.org/gmane.comp.python.twisted/18029/focus=18089


Jean-Paul Calderone <exarkun at divmod.com> writes:

> On Sat, 07 Mar 2009 19:38:46 +0100, Martin Geisler <mg at daimi.au.dk> wrote:
>> Jean-Paul Calderone <exarkun at divmod.com> writes:
>>
>> Hi,
>>
>> Thanks for the answer. I'm also with the VIFF project and I would
>> like to explain a bit more about the background for the hack by
>> Marcel.
>>
>>> [snip]
>>>
>>> So you're doing a ton of work all at once now and you want to split
>>> up that ton of work into smaller pieces and do it a little at a
>>> time?
>>
>> Sort of. We have overloaded the arithmetic operators in our library,
>> so people will expect to be able to write
>>
>>  # xs and ys are big lists of our objects
>>  dot_product
>>  for (x, y) in zip(xs, ys):
>>    dot_product += x * y
>>
>> Here the multiplications involves network traffic and return
>> Deferreds. We would like the network traffic for the first
>> multiplication to begin immediately, *before* the remaining
>> multiplications are done.
>>
>> Doing all the multiplications up front makes the code block the
>> reactor and uses an awful lot of RAM. If we let each multiplication
>> trigger the sending of its data immediately, and if we process
>> incoming messages along the way, memory can be reclaimed for the
>> earlier multiplications and the above calculation should run in
>> constant memory.
>
> Hm.  I would bet the constant would be pretty high, though.  Things
> will only balance out once the network is keeping up with the local
> for loop.  Actually, I'm not sure why it would be constant at all.
> Won't the local for loop always run much faster than any network
> operations can happen?  In this case, memory usage will go towards
> K(local) * set size - K(remote) * set size, or just O(set size); that
> is to say, linear.
>
>> Sending and processing data in a more even flow makes our benchmark
>> results better and more consistent from one run to the next.
>
> It seems like what you'll really benefit from most is pipelining with
> a maximum pipeline depth that's not too big (so as to conserve memory)
> but not too small (so as to avoid wasting time on network round trip
> time).
>
>>> If that's the case, then you don't need to modify the reactor, you
>>> just need to split up the work your code is going. There are a lot
>>> of techniques for doing this. coiterate and inlineCallbacks are two
>>> solutions which are closest to "cookie cutter" (ie, you have the
>>> least flexibility in deciding how to use them).
>>
>> Right -- we might be able to use these techniques. I haven't looked
>> at coiterate yet. With inlineCallbacks I guess the code would look
>> something like this:
>>
>>  # xs and ys are big lists of our objects
>>  dot_product
>>  for (x, y) in zip(xs, ys):
>>    dot_product += (yield x * y)
>>
>> which is not so bad, expect that it destroys the nice illusion that x
>> and y behave like normal integers even though the multiplication
>> involves network traffic.
>
> Perhaps with coiterate this might look something like...
>
>    def op(xs, ys):
>        dot_product = 0
>        for (x, y) in zip(xs, ys):
>            dot_product += x * y
>            yield
>
>        yield dot_product
>
>    d = coiterate(op(xs, ys))
>
> This is flawed, but maybe it can be fixed.  What's good about it is
> that it doesn't try to drive the reactor re-entrantly. :) It also
> avoids the yield in the += and * operations, which somewhat preserves
> your illusion of normalcy (I'm not saying I like that illusion, but
> I'll leave that aside for now).
>
> What's bad about it is that it still lets the local loop run
> arbitrarily far ahead of the results from the network, giving you
> unbounded memory usage.  To fix that, it should yield a Deferred every
> once in a while.  The reason I leave it flawed here is that it's a
> little tricky to figure out which Deferred to yield.  What would be
> great would be to yield the Deferred for an operation which preceeds
> the most recently executed operation by some number of operations.
> The number of operations by which it preceeds the most recent will be
> your pipeline depth (roughly).  The effect this has on coiterate is to
> cause your local loop to cease to execute until that Deferred has
> fired.  By making it a Deferred for an operation some time /before/
> the most recent operation, you keep the network busy and avoid wasting
> time on round trip times.  Once the Deferred fires, your loop gets run
> a few more times which has the effect of putting more work into the
> pipeline - until you've got enough extra work to keep things from
> stalling again, and then coiterate puts you to sleep for a while
> again.
>
>>> You have a very long, steep, uphill battle to convince me that
>>> adding support for re-entrant iteration is a good idea.
>>
>> One problem I can think of is the memory usage associated with a very
>> deep recursion. Since there is no such thing as tail call
>> optimization in Python, each level in the recursion will hold onto
>> any local variables even though they might not be needed any more.
>>
>> Are there other general problems with having a re-entrant reactor?
>
> One general problem is simply that the reactor is not written with
> this in mind.  So with the current implementation, even including the
> patch Marcel contributed, it doesn't work, period.  When I say
> "doesn't work", I mean that there are cases which will simply result
> in incorrect behavior, though there may be other cases where
> everything does work out as you expect.  Going along with this, it's
> quite a bit harder to test that things work when re-entrancy is
> allowed or expected than if it isn't, so even if all of the current
> reactor implementations were made re-entrant, there would likely be a
> higher rate of defects related to this in the future, simply because
> it's harder.
>
> This isn't limited solely to the reactor, either.  A re-entrant
> reactor almost certainly means that application code will be invoked
> re-entrantly.  This is actually the case already, unfortunately, and
> it is a bit of an open question as to what should be done about it.  A
> very common bug I find (and write! :() in Twisted applications is
> failure to handle various forms of re-entrancy correctly.  This is an
> existing issue with Twisted, not related to this proposed change, but
> making this change would only make the problem worse and essentially
> destroy and hope for ever making it better.
>
> Actually, that general problem is so general that I can't really think
> of any others to discuss, so I'll leave it at that for now. :) If you
> want, I can probably share some specific examples of how re-entrancy
> leads to surprising bugs in unexpected places (probably from real
> programs, too :/).
>
> Jean-Paul


-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20090307/5f1778d1/attachment.pgp>