Re: CRC in Ada?

[Michael & Amy Hartsough <Hartsough@worldnet.att.net>]

Robert Dewar wrote:
> 
> << _IF_ you are doing the CRC on a file (as I was), I would advise you
> to consider performance. I found (exactly the same algorithm)
> implemented in C took an order of magnitude seconds less to execute
> than the Ada equivalent.>>
> 
> Well of course no one can see what the two pieces of code you compared
> are, since you did not post them, so we cannot tell whether the problem
> came from inappropriate coding choices on your part, or bad code generation
> in the Ada compiler you were using -- it certainly was nothing to do with
> C vs Ada per se as languages.

I recently implemented THE CRC32 algorithm (at least I was told that it was THE
CRC32 algorithm, all I was given as a reference was some C++ code) in Ada (83). Our
Ada application uses a database that's created by a C++ program, and my Ada CRC32 
results of course had to match the C++ CRC32 results.

It took my Ada CRC32 18 minutes to calculate the checksum for a 65K file! It took
the C++ CRC32 27 seconds to checksum the same file! Timings were performed using
the stopwatch function on my Timex. ;^) Why the difference? File I/O. Turns out
all but about 8-9 seconds of those 18 minutes were spent reading from the hard disk!

I was extremely displeased by this, particularly since my C++ compatriot was getting
a big whopping chuckle out of the whole thing! So I contacted my Ada vendor via
email, asking what the deal was. I got a marvelous reply. "In general [red alert!
red alert!], Ada flushes the I/O buffer before every read.". I replied that I
hadn't recalled ever reading that in the Ada LRM anytime in the 10 years I'd been 
using Ada.

So my Ada vendor is now looking into how they may be able to improve file I/O
performance. I suggested a field in the "form" parameter that lets you specify
a buffer size. They even offered to send me some examples of how to implement my
own buffered I/O, but I declined the offer, stating that I recalled doing that
in Turbo Pascal version 1.2 back in the early 80s.

There was something else stated in another message in this thread about bit
shifting being inefficient in Ada. This is NOT the case in my experience.
My implementation of the CRC32 algorithm is a case in point. The algorithm
requires an 8-bit shift right. Since my compiler does not provide a "shift"
routine, I coded the shift as a divide by 256. A check of the disassembled
machine code generated by my Ada compiler confirmed my hunch. Instead of
generating a divide instruction, the compiler was smart enough to recognize
that an 8-bit shift right instruction would produce the same result, and
that's the machine instruction the compiler used.

I could regale you with the tale of how I recoded a poorly coded rotate left
function, cutting 3 minutes out of a 5 minute task, but I think I'll leave that til 
another time! ;^)

Later,
	Michael