Interesting performance quirk. - ADA

Robert A Duff wrote:

> You should also...

Thanks for all the great suggestions. I have made a note of them for
future reference. And yes, I definitely intend to practice with gprof.
It looks useful.

Thanks also for your words of encouragement. Unfortunately progress on
this project tends to be spotty because I can only work on it here and
there between my "real" work. However, if I find out anything else
interesting or have any more questions I'll definitely post.

Peter

Peter C. Chapin wrote:
>
> Well, I have unit tests for my code that are based on the Blowfish test
> vectors on Schneier's page. My code passes those cases, so the
> encryption results are apparently what Schneier thinks they should be. I
> can only assume that OpenSSL can also pass those test cases (didn't try it).

That's an assumption you ought to test. OpenSSL might be very fast because it's
wrong.

Doesn't seem likely, though.

--
Jeff Carter
"Now look, Col. Batguano, if that really is your name."
Dr. Strangelove
31

On 29 Okt., 00:22, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:
> Besides that, I was wondering if by any chance you were using one 32-
> bit and one 64-bit operating system; if so, which one is Linux and
> which one is Windows?

And maybe check if there is a difference in static/dynamic linking...

The VM might do some JIT-optimizations on the binaries executing. You
could try running some Linux Live-CD with same GNAT version.

Peter C. Chapin wrote:

> I tried running gprof over my code to see what I could learn, but I
> don't know how to use that tool very well yet so I didn't learn much. I
> discovered that a certain procedure is called a HUGE number of times,
> but that's not unexpected considering where it's used. It's a small
> procedure so I might try inlining it.

I'd also recomend valgrind with, e.g., kcachegrind to visualize the results. It might be easier to get into than gprof, and doesn't require special parameters to build the executable.

Ludovic Brenta wrote:

> I believe OpenSSL uses hand-written and carefully optimised assembly
> for its inner loops.

That's interesting. It would help to explain the speed difference...
although as I said I'm sure I can do better, at least a little better,
with the compiled Ada than I am currently.

In any event I don't want to "resort" to assembly language or to
removing the Ada mandated checks (at least not in the final version). My
assumption is the the sort of person who would be interested in using a
crypto library in Ada would have that interest precisely because of the
safety afforded by the Ada language. This is why I'm content with the
library being a bit slower than the competitors that are throwing safety
to the wind by, for example, using assembly language.

Considering that cryptography is, almost by definition, used in security
sensitive programs it seems like issues of safety and correctness should
take priority over raw efficiency. Fast is good, of course, but it's
even more important to be both right and secure. Hence Ada and not C
(and definitely not assembly language).

> Besides that, I was wondering if by any chance you were using one 32-
> bit and one 64-bit operating system; if so, which one is Linux and
> which one is Windows?

No, they are both 32-bit systems. The Linux VM is on the same hardware
as the Windows system.

Peter

On Oct 29, 9:59 am, "Peter C. Chapin" <pcc482...@gmail.com> wrote:
> In any event I don't want to "resort" to assembly language or to
> removing the Ada mandated checks (at least not in the final version).

With a bit of care a lot of checks can be avoided or removed by the
compiler. A fairly common example of this wrt loops is:

type Array_Index_Type is range ...;
type Array_Type is array (Array_Index_Type) of ...;

procedure Example (A : Array_Type) is
begin
for I in Array_Index_Type loop
-- Do something with array I - a check is often included
end loop;
end Example;

is better written as:

procedure Example (A : Array_Type) is
begin
for I in A'Range loop
-- Do something with array I - no need for a check
end loop;
end Example;

I'm not a language lawyer, so I can't tell if that's compiler
inefficiencies or what the language requires but this was certainly
the behaviour of several compilers I've used***.

Cheers
-- Martin

*** I haven't checked this recently!!! :-)

In
news:4904516f$0$28741$4d3efbfe@news.sover.net
on October 26th, 2008, Peter C. Chapin submitted:
|------------------------------------------------------------------------|
|"[..] |
| |
|I am also planning to write a similar program in C using OpenSSL's |
|Blowfish implementation. I want to get a point of comparison to see if |
|my implementation has "reasonable" performance or not (here I'm assuming|
|that OpenSSL is reasonable). I'm curious now if the C/OpenSSL version |
|will also demonstrate this same performance quirk." |
|------------------------------------------------------------------------|

I had intended to reply with a claim that any language would be sped
up in the emulated system, however instead in
news:4906f908$0$5781$4d3efbfe@news.sover.net
on Tue, 28 Oct 2008, Peter C. Chapin submitted:
|------------------------------------------------------------------------|
|"[..] |
| |
|In further developments... |
| |
|I wrote a version of the benchmark program in C that uses OpenSSL's |
|Blowfish implementation. The program is the "same" in that it creates |
|the same amount of data and processes it in the same way. The only |
|significant difference is that it calls into OpenSSL. It's quite a bit |
|faster. Right now I get |
| |
|Windows XP Laptop (GNAT GPL 2008 for the Ada, Cygwin gcc for the C) |
|----- |
|My Library => 11 MB/s (with -O2 option and no debugging support) |
|OpenSSL => 65 MB/s (Wow!) |
| |
|SUSE Linux in a VM on the same box |
|----- |
|My Library => 25 MB/s (odd) |
|OpenSSL => 65 MB/s (now this makes sense at least) |
| |
|[..]" |
|------------------------------------------------------------------------|

Earlier this year I had used QEMU on Windows (possibly not Windows XP)
to have a GNU/Linux distribution (possibly RedHat) emulated. I ran a
Bourne shell script or a Bourne Again SHell script in the emulated
system which made thousands of fairly short I/O transactions. The
emulated system including its pretend harddisk were kept small enough
(no more than a few hundred megabytes) to be kept solely in the real
physical primary memory instead of relying on virtual memory.

It was faster than running the same script on Cygwin on the same
machine. (The throughput of my shell script was faster in the emulated
system, whereas the human user interface of the emulated system was
dominated by how quickly it starts to respond instead of throughput,
and suffered from sluggish latencies.) Conversely, on
WWW.Debian.org/intro/why_debian
it was claimed:
!-------------------------------------------------------------------!
!"If you are not already a GNU/Linux user, you may also enjoy the !
!following benefits: !
! !
![..] !
!Fast and easy on memory !
! Other operating systems may be as fast in one or two areas, but!
! being based on GNU/Linux, Debian is lean and mean. Windows !
! software run from GNU/Linux using an emulator sometimes runs !
! faster than when run in the native environment. !
![..]" !
!-------------------------------------------------------------------!
That Debian webpage lacks important information for a fair comparison
with Windows.

However, I do not know why Peter C. Chapin's Ada code is sped up but
OpenSSL is not.

Yours sincerely,
Colin Paul Gloster

* Peter C. Chapin:

> I don't really have a question or a problem with any of this, but I
> found it curious and I thought I'd post in case someone had some useful
> insight into what might be going on.

Is memory allocation or finalization involved in an inner loop?
It might also help to compare -gnatdg output or assembly (-S).

Florian Weimer wrote:

> Is memory allocation or finalization involved in an inner loop?
> It might also help to compare -gnatdg output or assembly (-S).

No, the inner loop is pretty much plain computation. The array over
which I work is dynamically allocated, however. So I suppose the Ada
version is doing checks to make sure the access value that points at the
array isn't null, whereas the C version is probably not doing that. I'm
not sure how much of an effect those null checks would have, though.
Blowfish's uses 16 "rounds" on each block so depending on where the
checks are done they could be lost in the overhead of the algorithm...
or not.

As Martin said in another post, I understand that by making some
adjustments to the code one can often coax the compiler to skip checks
that are actually unnecessary without violating the semantics of Ada. I
will definitely have to look into that. Thanks for your suggests above
for getting further information. I would definitely like to understand
*why* the code is slow before spending too much time try to fix it. I've
optimized code before (not Ada code) and I know that just guessing about
the problem often doesn't work well.

Peter