Re: [viff-devel] Some profiling results

2008-09-24 Thread Mikkel Krøigård
Citat Martin Geisler [EMAIL PROTECTED]:

 In both plots we see that the first multiplication takes very long, it
 is sort of waiting on the other multiplications. I think this is
 because we're not yielding to the reactor when we start all the
 multiplications.

 This also means that no network communication is started for the first
 multiplication until after all multiplications have been scheduled --
 this is actually not what we want...

 Here are the plots, please let me know what you think of this.

At a glance, it does look like the timing is being done correctly. Right now I
can only confirm that there's definitely something funny going on in those
plots.


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] Some profiling results

2008-09-24 Thread Martin Geisler
[EMAIL PROTECTED] writes:

 Hi Martin,

 I have a couple of stupid questions:

 Quoting Martin Geisler [EMAIL PROTECTED]:

 I've attached two plots, one for 1000 multiplications and one for
 4000. Each plot has the multiplication-number on the x-axis and the
 time for that multiplication on the y-axis.

 If you have done 1000, resp. 4000 mult's, why do the x-axes start at
 2000, reps. 8000?

Ah, good question: the numbers are taken from the current program
counter at the time when the multiplication is scheduled. And it turns
out to start at about 2n since we start by doing 2n shamir secret
sharings to get n pairs.

 And if you have measured time for individual multiplications, why
 are the numbers on the y-axis smaller in the 1000 multiplication
 case? Shouldn't they take about the same amount of time in both
 cases?

Yes, that was what I expected too! I would at least expect the final
multiplications to take about equally long, even if the first one are
waiting longer when doing 4000 multiplications.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://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] What to benchmark

2008-09-24 Thread ivan
Quoting Martin Geisler [EMAIL PROTECTED]:

  Note that I am not saying we are in that situation, in fact I don't
  think so - but I am saying that it is important to find out ASAP!

 Agreed! I would be very happy to hear suggestions as to how we can
 measure things in VIFF and/or Twisted.

Well, it seems to me it makes sense to split the time spent in 3 classes
1) necessary local computing (such as arithmetic on shares, computing PRF's
etc.)
2) idle time, while waiting for messages from the others
3) anything else

and the most basic information we want is how large these three are relative to
each other.

I think there was earlier some version where arithmetic was done by calling some
external C code. From that I am guessing that it is feasible to make a version
where all or most of the stuff in 1) is done by calling specific functions we
can name and track rather than using the internal Python arithmetic, for
instance. In such a version, it should be possible to find out
how much time is spent on 1). If this gets much slower than the normal version,
we are in trouble and then I don't know what to do.
2) I suppose can be measured by hooking into the event loop of Twisted

Exercise: if you can measure 1) and 2), how do you measure 3)?  :-)

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] What to benchmark

2008-09-24 Thread Mikkel Krøigård
Citat [EMAIL PROTECTED]:

 I think there was earlier some version where arithmetic was done by calling
 some
 external C code.
We are easily able to switch between gmpy (which is implemented in C) and Python
arithmetic, if that's what you mean.

I remember trying out how to implement Python modules in C, and you needed to
define special functions that map to C functions. Presumably there is something
of the same kind going on inside gmpy that we can measure separately from the
rest of the Python code. I am not familiar with the profilers though, and I
could be wrong.

 Exercise: if you can measure 1) and 2), how do you measure 3)?  :-)
That's one tough equation.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] Some profiling results

2008-09-24 Thread Martin Geisler
Martin Geisler [EMAIL PROTECTED] writes:

 Hi everybody,

 I have done some testing and come up with some strange numbers. I
 measured the time each individual multiplication takes by storing a
 timestamp when the multiplication is scheduled, and another when it
 finishes.

Here is another plot which also shows when each multiplication is
started and how long it takes.

attachment: duration-4000.png
-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://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] What to benchmark

2008-09-24 Thread Martin Geisler
[EMAIL PROTECTED] writes:

 I think there was earlier some version where arithmetic was done by
 calling some external C code. From that I am guessing that it is
 feasible to make a version where all or most of the stuff in 1) is
 done by calling specific functions we can name and track rather than
 using the internal Python arithmetic, for instance. In such a
 version, it should be possible to find out how much time is spent on
 1). If this gets much slower than the normal version, we are in
 trouble and then I don't know what to do.

Sigurd is actually testing this at this very moment (we talked about
it on IRC) and I hope he will give some benchmark results. This is
about using GMPY for field arithmetic:

  http://tracker.viff.dk/issue10

 2) I suppose can be measured by hooking into the event loop of
 Twisted

That was what I described in the mail before -- I saw very few calls
to the select() function, which is the one used in the event loop to
sleep while waiting for data from a set of file descriptors.

 Exercise: if you can measure 1) and 2), how do you measure 3)?  :-)

Hehe :-)

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://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] What to benchmark

2008-09-24 Thread ivan
Quoting Mikkel Krøigård [EMAIL PROTECTED]:

 Citat [EMAIL PROTECTED]:

  I think there was earlier some version where arithmetic was done by calling
  some
  external C code.
 We are easily able to switch between gmpy (which is implemented in C) and
 Python
 arithmetic, if that's what you mean.

Well I guess that's part of what I meant. Certainly, if you can measure how much
time is spent inside the C code, this will say how much raw time is spent on
arithmetic. This assumes, however, that all arithmetic, even down to simple
additions are done this way. Then there are other things, such as computing
PRF's that I suppose is not done using gmp?. This would have to be measured
separately


  Exercise: if you can measure 1) and 2), how do you measure 3)?  :-)
 That's one tough equation.


Many years of experience as a university teacher allows me to ask almost
impossible questions with surprising ease..

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] What to benchmark

2008-09-24 Thread Martin Geisler
Mikkel Krøigård [EMAIL PROTECTED] writes:

 I remember trying out how to implement Python modules in C, and you
 needed to define special functions that map to C functions.
 Presumably there is something of the same kind going on inside gmpy
 that we can measure separately from the rest of the Python code. I
 am not familiar with the profilers though, and I could be wrong.

I've looked at the GMPY code, and it is a fairly straightforward
wrapper for the GMP library, as you describe.

But I don't know if it makes it easier for us to benchmark just
because it is split into its own C code...

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://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] Some profiling results

2008-09-24 Thread ivan
Quoting Martin Geisler [EMAIL PROTECTED]:

 Martin Geisler [EMAIL PROTECTED] writes:

  Hi everybody,
 
  I have done some testing and come up with some strange numbers. I
  measured the time each individual multiplication takes by storing a
  timestamp when the multiplication is scheduled, and another when it
  finishes.

 Here is another plot which also shows when each multiplication is
 started and how long it takes.

I agree with Mikkel that it seems to make sense that it looks this way.
But of course we would have been happier if the first multiplication did
not have to wait for so long. In particular it seems it is waiting longer
the more multiplications you ask for in total, right?
This is certainly something we don't want. I don't nearly enough about
how this works to say what to do about it..

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] What to benchmark

2008-09-24 Thread ivan
Quoting Mikkel Krøigård [EMAIL PROTECTED]:

 Citat Martin Geisler [EMAIL PROTECTED]:

  I've looked at the GMPY code, and it is a fairly straightforward
  wrapper for the GMP library, as you describe.
 
  But I don't know if it makes it easier for us to benchmark just
  because it is split into its own C code...
 I never said it would. If you use this approach, it is easy to see how much
 is
 spent on the dangerous arithmetic, but I guess a profiler could tell you how
 much time Python spends on the functions implementing the operators anyway.

If that's the case, then it doesn't make sense w.r.t. the profiling to
use GMPY. I was assuming the profiler could not give you information that was so
fine-grained.

But at least it is good news that Sigurd saw a speed-up from using C, albeit on
large numbers. It indicates that the raw computing time is not completely
dwarfed by bookkeeping etc.


 It is not completely unimaginable, however, that someone would want to know
 how
 much actually goes on inside gmpy (arithmetic on big numbers, the data) and
 how
 much goes on outside (counting variables, various kinds of overhead).

That someone is me. I think it is important to know what fraction of the time we
spend on computing we HAVE to do.

regards, Ivan
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk