[viff-devel] Mystery of the quadratic running time solved?
Martin Geisler
mg at daimi.au.dk
Sat Mar 7 09:46:16 PST 2009
Marcel Keller <mkeller at cs.au.dk> writes:
> Hello friends of VIFF,
>
> I've now run the benchmark of actively secure multiplications with
> hyperinvertible matrices together with my hack. Here are my results
> (column 1 and 2) compared to the results in the paper "Asynchronous
> Multiparty Computation: Theory and Implementation" (column 3 and 4):
>
> (n,t) online preprocessing online preprocessing
> (4,1) 5 18 4 20
> (7,2) 7 30 6 42
> (10,3) 9 43 8 82
> (13,4) 12 56 10 136
Wow, this is nice! I had sort of given up finding the cause of this :-(
Thank you for looking at this, and just in time for my presentation at
PKC in 10 days :-)
> Again, there are two patches in the attachement, and again, the patch
> for VIFF is against the current tip of my repository:
> http://hg.viff.dk/mkeller/rev/e2759515f57f
Cool -- the patches are much less of a hack than I feared... they
actually look quite nice :-)
But I hope it can be done even easier, please see below.
> Best regards,
> Marcel
>
> --- /usr/lib/python2.5/site-packages/twisted/internet/base.py 2008-07-29 22:13:54.000000000 +0200
> +++ internet/base.py 2009-02-20 12:27:42.000000000 +0100
> @@ -1127,17 +1127,32 @@
> self.startRunning(installSignalHandlers=installSignalHandlers)
> self.mainLoop()
>
> +
> + def setLoopCall(self, f, *args, **kw):
> + self.loopCall = (f, args, kw)
> +
> +
> + def myIteration(self, t):
> + # Advance simulation time in delayed event
> + # processors.
> + self.runUntilCurrent()
> +
> + if (t is None):
> + t2 = self.timeout()
> + t = self.running and t2
> +
> + self.doIteration(t)
> +
> + if ("loopCall" in dir(self)):
> + f, args, kw = self.loopCall
> + f(*args, **kw)
> +
>
> def mainLoop(self):
> while self._started:
> try:
> while self._started:
> - # Advance simulation time in delayed event
> - # processors.
> - self.runUntilCurrent()
> - t2 = self.timeout()
> - t = self.running and t2
> - self.doIteration(t)
> + self.myIteration(None)
> except:
> log.msg("Unexpected error in main loop.")
> log.err()
The changes above basically insert a call to self.loopCall after each
doIteration invocation, right?
When the loopCall is process_deferred_queue the main loop becomes:
self.runUntilCurrent()
self.doIteration(t)
runtime.process_deferred_queue
self.runUntilCurrent()
self.doIteration(t)
runtime.process_deferred_queue
...
I think we would get the same result if we started a LoopingCall that
executes process_deferred_queue with an interval of, say, 100 ms:
http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.task.LoopingCall.html
This should work since the runUntilCurrent method runs through the
waiting calls and will trigger our process_deferred_queue method.
And voilá -- no hacking of the Twisted source needed.
> diff -r e2759515f57f viff/runtime.py
> --- a/viff/runtime.py Thu Mar 05 21:02:57 2009 +0100
> +++ b/viff/runtime.py Fri Mar 06 13:43:14 2009 +0100
> @@ -306,6 +306,8 @@
> deferred = deq.popleft()
> if not deq:
> del self.incoming_data[key]
> + # just queue
> + self.factory.runtime.queue_deferred(deferred)
Why is this done?
> deferred.callback(data)
> else:
> deq.append(data)
> @@ -501,6 +503,13 @@
> # communicating with ourselves.
> self.add_player(player, None)
>
> + #: List of paused deferreds
> + self.deferred_queue = []
> + #: Counter for calls of activate_reactor
> + self.activation_counter = 0
> + #: Activation depth counter
> + self.depth_counter = 0
This is for keeping track of the recursion depth in the future?
> + def queue_deferred(self, deferred):
> + deferred.pause()
> + self.deferred_queue.append(deferred)
> +
> + def process_deferred_queue(self):
> + while(self.deferred_queue):
> + deferred = self.deferred_queue.pop(0)
> + deferred.unpause()
Are you doing it this way to ensure that the Deferreds are unpaused in
the same order as they were added to the list?
If that doesn't matter, then I think this would be faster:
queue, self.deferred_queue = self.deferred_queue, []
map(Deferred.unpause, queue)
My idea is that looping over the list with map is faster than repeatedly
popping items from the beginning (an O(n) operation).
> +
> + def activate_reactor(self):
> + self.activation_counter += 1
> +
> + # setting the number to n makes the reactor called
> + # only every n-th time
> + if (self.activation_counter >= 2):
> + self.depth_counter += 1
> + reactor.myIteration(0)
> + self.depth_counter -= 1
> + self.activation_counter = 0
If we remove the myIteration code above, we'll have to move the calls to
reactor.runUntilCurrent and reactor.doIteration here.
A question springs to my mind: calling
reactor.runUntilCurrent()
reactor.doIteration(0)
is the same as calling
reactor.iterate(0)
and the documentation for that method says:
[...] This method is not re-entrant: you must not call it recursively;
in particular, you must not call it while the reactor is running.
http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.interfaces.IReactorCore.html#iterate
How does your code ensure that we only call myIteration when we're not
in a call made by the reactor? And could we simply call reactor.iterate
instead?
--
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/68dc0458/attachment.pgp>
More information about the viff-devel
mailing list