Re: [viff-devel] Mystery of the quadratic running time solved?
Hi Ivan, I just wanted to say that I think it would be great if you would implement a version of your proposed two-threaded solution. I do not have a firm grasp of all the programming details, but it does seem that the overall idea is converging, and that some time soon the best way to judge the idea is to go ahead and do it. OK, i will start doing it next Monday. Note that Alexandra is committed to using a non-trivial amount of resources on developing VIFF and related software. Although this may not mean that lots of man-hours are available just now, it might be possible that they could help you. It may also be more efficient that one guy does it in the first iteration, I'll leave this up to you. Since it doesn't seem that complicated to me, I will try it on my own first. But I keep that in mind for the case that I'm wrong. Note that myself, Martin and Jakob will not be at the meeting Thursday. Maybe we should postpone the meeting until next week? Me neither, I'm on holidays until the weekend. Therefore, I would agree to postpone the meeting. Best regards, Marcel ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel, I just wanted to say that I think it would be great if you would implement a version of your proposed two-threaded solution. I do not have a firm grasp of all the programming details, but it does seem that the overall idea is converging, and that some time soon the best way to judge the idea is to go ahead and do it. Note that Alexandra is committed to using a non-trivial amount of resources on developing VIFF and related software. Although this may not mean that lots of man-hours are available just now, it might be possible that they could help you. It may also be more efficient that one guy does it in the first iteration, I'll leave this up to you. Note that myself, Martin and Jakob will not be at the meeting Thursday. Maybe we should postpone the meeting until next week? regards, Ivan ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
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. I'm not sure but LoopingCall._reschedule() looks more like it schedules the calls at certain tick, not as soon as possible after the interval is elapsed. This might not cost too much time but still doesn't feel very elegant. Furthermore, setting the interval very low leads to high CPU usage when waiting. Again, this is not too bad but not elegant either. The same applies if using reactor.callLater() directly. A looping call is just a higher level wraper for doing def reschedule(func): func() reactor.callLater(interval, reschedule, func) reschedule(func) It will execute the function when the (now + interval) time has been reached and when the control flow returns to the reactor's event loop. We probably wont need the extra logic in a looping call, so we can just let the function reschedule itself like above. That's what I meant with calling reactor.callLater() directly. If we do this with an interval of 0, then the function will be called on each iteration through the reactor's event loop -- just like your loopCall I believe? Not exactly because it also sets the timeout of the select call to 0 leading to 100% CPU usage while when we are waiting. 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? At this time, we shouldn't call the callbacks because we might recurse into selectreactor.doSelect(). However, we want to know which deferreds are ready so we can call deferred.callback() later. Uhh, this sounds a bit dangerous -- do we know exactly which Deferreds we can invoke callback on and which we cannot? As I remember, we invoke callback in a couple of other locations, is that safe? Yes, it is safe because the callback is called only once. When the data arrives, the Deferreds are paused, appended to the queue, and the callback is called. The Deferres in the queue are unpaused and removed in process_deferred_queue(). As far as I know you can pause and unpause Deferreds as you like. 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). But map() still would need O(n) time because that is the nature of calling a function n times, isn't it? Maybe the function calls are optimized but the code in the function still is called n times. Each pop(0) call is an O(n) operation, so we get O(n^2) here -- it is an expensive way to loop through a list. And now that I look at it, using map will still unpause the Deferreds in the order as you added them. OK, I wasn't aware that pop(0) is O(n), but I still think that the complexities should be added resulting in running time O(n) again. Using a linked list would be more reasonable, of course. The difference is then that anything added to the queue as a result of the unpause calls will be processed the next time the code is called. Yes, and the Deferreds in the queue previously would wait. I considered it to be more safe if the Deferreds are processed in the order they arrive. 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. 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? We actually call it recursively but it should be reentrant if it's not called from doIteration(). doIteration() is a the same as select.doSelect(), which certainly is not reentrant. We however call it from the loop call (process_deferred_queue()) after doIterate(). Calling reactor.iterate() is not enough because it doesn't call process_deferred_queue(). So if we call reactor.iterate and then runtime.process_deferred_queue as reactor.callLater(0, reactor.iterate) reactor.callLater(0, runtime.process_deferred_queue) we should be fine? They would then both run one after another just as soon as the event loop is rea
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller writes: >> You're talking about this two-threaded solution as if it is something >> that exists and will solve all our problems... > > No, for now, it's just an imagination in my mind, a proposal for the > next meeting, and a strong feeling that it's the right way to do it. Yeah, I think it would help too. >> But I still haven't seen it, and I would like to see how you can >> cleanly seperate the work of the two threads. I'm afraid that the >> threads will be alternating between working and waiting on the other >> thread in such a way that we could just as well use one thread. > > My idea is that the Twisted main loop runs in one thread and most of > the VIFF code in the other. The Twisted thread only waits for I/O and > the VIFF thread only waits if there is no work to be done. It's funny -- then we'll have sort of two event loops. > If the group decides to give this idea a try, I would be happy to > implement it. I would claim that it can be done in one or two weeks. So you'll have something when I get back from PKC? :) Seriously, I think you're right, the code is fairly well partitioned already, so we should be able to make this change without too much trouble. >> Also, threading in Python is unfortunately not optimal :-( The Python >> VM will use a single thread to execute the bytecode, even when using >> multiple thread in Python. It is only if the threads do things >> blocking for I/O that you will see a performance increase by using >> multiple threads. > > I'm aware that Python only runs on one CPU, a friend pointed that out > to me today. However, the Twisted thread mentioned above would block > on I/O. Right, that should help us! Janus has been looking more into Python threads, so be sure to discuss it with him too. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpNe3r9JiJcA.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
You're talking about this two-threaded solution as if it is something that exists and will solve all our problems... No, for now, it's just an imagination in my mind, a proposal for the next meeting, and a strong feeling that it's the right way to do it. But I still haven't seen it, and I would like to see how you can cleanly seperate the work of the two threads. I'm afraid that the threads will be alternating between working and waiting on the other thread in such a way that we could just as well use one thread. My idea is that the Twisted main loop runs in one thread and most of the VIFF code in the other. The Twisted thread only waits for I/O and the VIFF thread only waits if there is no work to be done. If the group decides to give this idea a try, I would be happy to implement it. I would claim that it can be done in one or two weeks. Also, threading in Python is unfortunately not optimal :-( The Python VM will use a single thread to execute the bytecode, even when using multiple thread in Python. It is only if the threads do things blocking for I/O that you will see a performance increase by using multiple threads. I'm aware that Python only runs on one CPU, a friend pointed that out to me today. However, the Twisted thread mentioned above would block on I/O. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller writes: Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) >>> That is not the only problem. To free the memory of the shares and to >>> send out further shares, also the incoming shares must be processed as >>> soon as possible. This is even trickier because incoming shares might >>> trigger code that calls functions sending out data, which activates >>> the Twisted reactor again and therefore leads to a possibly too deep >>> recursion. I think I have a solution for that, it just wasn't >>> necessary to implement it for now because the hack worked anyway. >> >> I guess we could simply not recurse if the recursion depth is too big? >> >> At some point we have to let the recursive calls finish in order to let >> the local variables and stack frames be garbage collected. > > Yes, but If we just stop recursing at a certain level, we might just > stay at that level for a longer time. That is also not optimal. In my > opinion, another point for the two-threaded solution. You're talking about this two-threaded solution as if it is something that exists and will solve all our problems... But I still haven't seen it, and I would like to see how you can cleanly seperate the work of the two threads. I'm afraid that the threads will be alternating between working and waiting on the other thread in such a way that we could just as well use one thread. Also, threading in Python is unfortunately not optimal :-( The Python VM will use a single thread to execute the bytecode, even when using multiple thread in Python. It is only if the threads do things blocking for I/O that you will see a performance increase by using multiple threads. Please see these links for some discussion on this so-called Global Interpreter Lock (GIL): http://www.artima.com/weblogs/viewpost.jsp?thread=214235 http://www.python.org/doc/faq/library/#can-t-we-get-rid-of-the-global-interpreter-lock -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpsk7RDTH9ae.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reactor again and therefore leads to a possibly too deep recursion. I think I have a solution for that, it just wasn't necessary to implement it for now because the hack worked anyway. I guess we could simply not recurse if the recursion depth is too big? At some point we have to let the recursive calls finish in order to let the local variables and stack frames be garbage collected. Yes, but If we just stop recursing at a certain level, we might just stay at that level for a longer time. That is also not optimal. In my opinion, another point for the two-threaded solution. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller writes: >> 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. > > I'm not sure but LoopingCall._reschedule() looks more like it > schedules the calls at certain tick, not as soon as possible after the > interval is elapsed. This might not cost too much time but still > doesn't feel very elegant. Furthermore, setting the interval very low > leads to high CPU usage when waiting. Again, this is not too bad but > not elegant either. The same applies if using reactor.callLater() > directly. A looping call is just a higher level wraper for doing def reschedule(func): func() reactor.callLater(interval, reschedule, func) reschedule(func) It will execute the function when the (now + interval) time has been reached and when the control flow returns to the reactor's event loop. We probably wont need the extra logic in a looping call, so we can just let the function reschedule itself like above. If we do this with an interval of 0, then the function will be called on each iteration through the reactor's event loop -- just like your loopCall I believe? > Of course, we can avoid hacking the Twisted code by extending it > within VIFF. Still, I'm in favor of the two-threaded solution because > it's more elegant, doesn't have the danger of recursing too deep, and, > in my opinion, it should be feasible. I have not yet seen the two-threaded approach -- do you have a patch? >>> 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? > > At this time, we shouldn't call the callbacks because we might recurse > into selectreactor.doSelect(). However, we want to know which > deferreds are ready so we can call deferred.callback() later. Uhh, this sounds a bit dangerous -- do we know exactly which Deferreds we can invoke callback on and which we cannot? As I remember, we invoke callback in a couple of other locations, is that safe? >> 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). > > But map() still would need O(n) time because that is the nature of > calling a function n times, isn't it? Maybe the function calls are > optimized but the code in the function still is called n times. Each pop(0) call is an O(n) operation, so we get O(n^2) here -- it is an expensive way to loop through a list. And now that I look at it, using map will still unpause the Deferreds in the order as you added them. The difference is then that anything added to the queue as a result of the unpause calls will be processed the next time the code is called. >> 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. >> >> 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? > > We actually call it recursively but it should be reentrant if it's not > called from doIteration(). doIteration() is a the same as > select.doSelect(), which certainly is not reentrant. We however call > it from the loop call (process_deferred_queue()) after doIterate(). > > Calling reactor.iterate() is not enough because it doesn't call > process_deferred_queue(). So if we call reactor.iterate and then runtime.process_deferred_queue as reactor.callLater(0, reactor.iterate) reactor.callLater(0, runtime.process_deferred_queue) we should be fine? They would then both run one after another just as soon as the event loop is reached. My goal is to violate as few Twisted docstrings as possible :-) And to use the tools provided by Twisted as much as possible. I would also like to hear what the Twisted guys have to say about calling reactor.iterate like this, it would be nice if they could say that it *is* infact safe to do it like this. > The prin
Re: [viff-devel] Mystery of the quadratic running time solved?
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 :-)
You're welcome. :-)
--- /usr/lib/python2.5/site-packages/twisted/internet/base.py 2008-07-29
22:13:54.0 +0200
+++ internet/base.py2009-02-20 12:27:42.0 +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
...
Yes, exactly.
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.
I'm not sure but LoopingCall._reschedule() looks more like it schedules
the calls at certain tick, not as soon as possible after the interval is
elapsed. This might not cost too much time but still doesn't feel very
elegant. Furthermore, setting the interval very low leads to high CPU
usage when waiting. Again, this is not too bad but not elegant either.
The same applies if using reactor.callLater() directly.
Of course, we can avoid hacking the Twisted code by extending it within
VIFF. Still, I'm in favor of the two-threaded solution because it's more
elegant, doesn't have the danger of recursing too deep, and, in my
opinion, it should be feasible.
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?
At this time, we shouldn't call the callbacks because we might recurse
into selectreactor.doSelect(). However, we want to know which deferreds
are ready so we can call deferred.callback() later.
+#: Activation depth counter
+self.depth_counter = 0
This is for keeping track of the recursion depth in the future?
Yes. It was used in some debug output earlier but I removed it to
simplify the patch.
+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?
Yes. I'm not sure whether this is really necessary but it seems just
cleaner because the callback of the some deferred might do a lot of
computations and recurse, which unnecessarily extends the lifetime of
the remaining deferreds.
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).
But map() still would need O(n) time because that is the nature of
calling a function n times, isn't it? Maybe the function calls are
optimized but the code in the function still is called n times.
+def activate_reactor(self):
+self.activation_counter += 1
+
+# setting the number to n makes the reactor called
Re: [viff-devel] Mystery of the quadratic running time solved?
That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reactor again and therefore leads to a possibly too deep recursion. I think I have a solution for that, it just wasn't necessary to implement it for now because the hack worked anyway. Ah, but the numbers I had been shown did not indicate we were anywhere near running out of memory. That's not to say memory isn't important (it certainly will be in cases with huge amounts of operations), I just didn't think it had anything to do with our specific test cases for the paper. Sorry, maybe I expressed myself not clear enough: We are not running out of memory, we are too slow because there are delays due to the control flow. I think that higher memory usage is just a side effect. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller writes: >> Indeed we did not know (well I didn't) back then that the data was >> not sent immediately by Twisted, and I was starting to think >> yesterday whether the hack would make a difference. Lucky for us, it >> apparently does :) > > That is not the only problem. To free the memory of the shares and to > send out further shares, also the incoming shares must be processed as > soon as possible. This is even trickier because incoming shares might > trigger code that calls functions sending out data, which activates > the Twisted reactor again and therefore leads to a possibly too deep > recursion. I think I have a solution for that, it just wasn't > necessary to implement it for now because the hack worked anyway. I guess we could simply not recurse if the recursion depth is too big? At some point we have to let the recursive calls finish in order to let the local variables and stack frames be garbage collected. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpp6C0lL7dUL.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller 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.0 +0200
> +++ internet/base.py 2009-02-20 12:27:42.0 +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
Re: [viff-devel] Mystery of the quadratic running time solved?
Citat af Marcel Keller : Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reactor again and therefore leads to a possibly too deep recursion. I think I have a solution for that, it just wasn't necessary to implement it for now because the hack worked anyway. Ah, but the numbers I had been shown did not indicate we were anywhere near running out of memory. That's not to say memory isn't important (it certainly will be in cases with huge amounts of operations), I just didn't think it had anything to do with our specific test cases for the paper. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reactor again and therefore leads to a possibly too deep recursion. I think I have a solution for that, it just wasn't necessary to implement it for now because the hack worked anyway. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Citat af Ivan Bjerre Damgård : Very interesting! So if things are as they seem here, the explanation for the strange behavior would be that the precomputing phase, being more involved than the online phase, is punished by Twisted (when unhacked). And this is of course not included in the analysis in the paper. Yes. Very interesting, and nice work Marcel. Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) regards, Ivan Quoting Marcel Keller : 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 The preprocessing time now seems to be linear whereas the online time is slightly increased. I didn't benchmark bigger thresholds because it's difficult enough find 13 camels which are not hard ridden yet. I think I also fixed the increased online time, but I couldn't test the fix thoroughly because the active adversaries continuously change the corrupted camels. 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 Best regards, Marcel ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Very interesting! So if things are as they seem here, the explanation for the strange behavior would be that the precomputing phase, being more involved than the online phase, is punished by Twisted (when unhacked). And this is of course not included in the analysis in the paper. regards, Ivan Quoting Marcel Keller : 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 The preprocessing time now seems to be linear whereas the online time is slightly increased. I didn't benchmark bigger thresholds because it's difficult enough find 13 camels which are not hard ridden yet. I think I also fixed the increased online time, but I couldn't test the fix thoroughly because the active adversaries continuously change the corrupted camels. 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 Best regards, Marcel ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Mystery of the quadratic running time solved?
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
The preprocessing time now seems to be linear whereas the online time is
slightly increased. I didn't benchmark bigger thresholds because it's
difficult enough find 13 camels which are not hard ridden yet. I think I
also fixed the increased online time, but I couldn't test the fix
thoroughly because the active adversaries continuously change the
corrupted camels.
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
Best regards,
Marcel
--- /usr/lib/python2.5/site-packages/twisted/internet/base.py 2008-07-29 22:13:54.0 +0200
+++ internet/base.py 2009-02-20 12:27:42.0 +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()
diff -r e2759515f57f viff/active.py
--- a/viff/active.py Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/active.py Fri Mar 06 13:43:14 2009 +0100
@@ -69,6 +69,9 @@
for protocol in self.protocols.itervalues():
protocol.sendData(pc, data_type, message)
+# do actual communication
+self.activate_reactor()
+
def echo_received(message, peer_id):
# This is called when we receive an echo message. It
# updates the echo count for the message and enters the
@@ -132,6 +135,8 @@
d_send = Deferred().addCallback(send_received)
self._expect_data(sender, "send", d_send)
+# do actual communication
+self.activate_reactor()
return result
@@ -260,6 +265,9 @@
# first T shares.
return rvec[:T]
+# do actual communication
+self.activate_reactor()
+
result = gather_shares(svec[T:])
self.schedule_callback(result, exchange)
return result
@@ -360,6 +368,9 @@
# first T shares.
return (rvec1[:T], rvec2[:T])
+# do actual communication
+self.activate_reactor()
+
result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
self.schedule_callback(result, exchange)
return result
diff -r e2759515f57f viff/passive.py
--- a/viff/passive.py Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/passive.py Fri Mar 06 13:43:14 2009 +0100
@@ -104,6 +104,10 @@
result = share.clone()
self.schedule_callback(result, exchange)
+
+# do actual communication
+self.activate_reactor()
+
if self.id in receivers:
return result
@@ -209,6 +213,10 @@
result = gather_shares([share_a, share_b])
result.addCallback(lambda (a, b): a * b)
self.schedule_callback(result, share_recombine)
+
+# do actual communication
+self.activate_reactor()
+
return result
def pow(self, share, exponent):
@@ -484,6 +492,9 @@
else:
results.append(self._expect_share(peer_id, field))
+# do actual communication
+self.activate_reactor()
+
# Unpack a singleton list.
if len(results) == 1:
return results[0]
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:
