CRC in Ada?

CRC in Ada?

[Dr. John B. Matthews]

Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
PAL and several other archives without luck. Any help appreciated.

Thanks,

John
----------------------------------------------------------------
John B. Matthews, M.D.
jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
"Whom the gods would destroy, they first invite to program in C"

Re: CRC in Ada?

[David Brown]

jmatthews@nova.wright.edu (Dr. John B. Matthews) writes:

> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
> PAL and several other archives without luck. Any help appreciated.

I threw this together the other day.  I declare this code to be public
domain.  Please give it a try, but I offer no guarantees that this
works.

David Brown
dbrown@vigra.com

----------------------------------------------------------------------
package Data is

   type Byte is mod 2 ** 8;
   for Byte'Size use 8;

   type Byte_Array is array (Positive range <>) of Byte;

end Data;
----------------------------------------------------------------------
with Data;
use  Data;

package Crc16 is

   type U16 is mod 2 ** 16;

   procedure Update (Crc  : in out U16;
                     Data : in     Byte_Array);

end Crc16;
----------------------------------------------------------------------
package body Crc16 is

   type U16_Array is array (Byte) of U16;

   -- The generated lookup table.
   Table : U16_Array;

   procedure Update (Crc  : in out U16;
                     Data : in     Byte_Array) is
   begin
      for I in Data'Range loop
         Crc := (Crc / 16#100#) xor Table (Byte (Crc) xor Data (I));
      end loop;
   end Update;

   -- Generate the lookup table.
   procedure Generate is
      P : constant := 16#8408#;
      V : U16;
   begin
      for B in Byte loop
         V := U16 (B);
         for I in 1 .. 8 loop
            if (V and 1) = 0 then
               V := V / 2;
            else
               V := (V / 2) xor P;
            end if;
         end loop;

         Table (B) := V;
      end loop;
   end Generate;

begin
   Generate;
end Crc16;
----------------------------------------------------------------------

Re: CRC in Ada?

[Tom Moran]

The recent SIGADA publication had a 16 bit CRC article.  But it ran
around a loop, a bit at a time, which is perhaps OK if your CPU power
greatly exceeds your comm bandwidth. There are table lookup CRCs that
run fast.

Re: CRC in Ada?

[Jon S Anthony]

In article <331bf6ce.2832564@news.logica.co.uk> garriga@logica.com (Stephen Garriga) writes:

> I had to do an 8 bit CRC a couple of years ago on a DEC Alpha running
> OSF 3.2c & DEC Ada.
> 
>  _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. 

That sounds very odd.  Did you use very different implementation
styles?  For example, maybe use unconstrained types in the Ada or some
such?  In general I would think a similar implementation style here
would yield basically the same "efficiency" result.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[Robert Dewar]

Jon Anthony asks

<<That sounds very odd.  Did you use very different implementation
styles?  For example, maybe use unconstrained types in the Ada or some
such?  In general I would think a similar implementation style here
would yield basically the same "efficiency" result.>>

One possibility is that the implementation was relying on doing rotates,
and there certainly is no easy portable efficient way of doing that
in Ada 83 (although for my taste I prefer to use table lookup for
computing CRC's and avoid the bit rotation stuff.

Re: CRC in Ada?

[Stephen Garriga]

On 2 Mar 97 22:06:52 EST, jmatthews@nova.wright.edu (Dr. John B.
Matthews) wrote:

>Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
>PAL and several other archives without luck. Any help appreciated.
{sig snip}

Not the program you wanted, just a comment:

I had to do an 8 bit CRC a couple of years ago on a DEC Alpha running
OSF 3.2c & DEC Ada.

 _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. 

Steve Garriga                         garriga@logica.com                 
   type OPINION is access PERSONAL_THOUGHTS_AND_BIAS; 
   OPINION_STATED : new OPINION := not LOGICA.OPINION;
Logica UK Ltd.   +44 171 637 9111   http://www.logica.com

Re: CRC in Ada?

[Tom Moran]

> I found (exactly the same algorithm)
> implemented in C took an order of magnitude seconds less to execute
> than the Ada equivalent. 
  Was this a byte (or word) lookup or a bit shifting bit-at-a-time
algorithm?  Ada 83 wasn't real handy with bit shifting.

Re: CRC in Ada?

[Stephen Garriga]

On Tue, 04 Mar 1997 08:55:34 -0800, Tom Moran <tmoran@bix.com> wrote:

>> I found (exactly the same algorithm)
>> implemented in C took an order of magnitude seconds less to execute
>> than the Ada equivalent. 
>  Was this a byte (or word) lookup or a bit shifting bit-at-a-time
>algorithm?  Ada 83 wasn't real handy with bit shifting.
I am not 100% sure but I think it was a straight forward XOR
algorithm. The problem was not with the actual calculation, but
with the I/O the implementation on the DEC at the time was terrible.
Even reading blocks of data into memory was slower than reading a byte
at a time using C stdio! (There is a LOT of code between a
sequential_io.read and the actual O/S call and significanly less using
the C libs) Also the io routines did not always correctly detect end
of file and I was having to spot it by trapping exceptions.
We took a pragmatic approach, wrote a few interfaces to the C libs, a
few simple C functions and lived it.

Steve Garriga                         garriga@logica.com                 
   type OPINION is access PERSONAL_THOUGHTS_AND_BIAS; 
   OPINION_STATED : new OPINION := not LOGICA.OPINION;
Logica UK Ltd.   +44 171 637 9111   http://www.logica.com

Re: CRC in Ada?

[Matthew Heaney]

In article <331bf6ce.2832564@news.logica.co.uk>, garriga@logica.com
(Stephen Garriga) 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. 

Once again it is necessary to clarify things with respect to languages and
efficiency.

First, performance is a characteristic of _implementations_, not of
_languages_.  So let's not be making bold intimations that Ada the language
is somehow slower than C.

Second, one of the things many Ada programmers don't realize is that strong
typing can _increase_ the efficiency because it gives the compiler more
semantic information on which to base optimizations.  (For example, using a
subtype for an array index value can turn off checks that would otherwise
be necessary to detect index constraint errors when dereferencing an
array.)

So show me this algorithm that "is exactly the same" and I'll tell you why
it runs more slowly.

matt

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: CRC in Ada?

[Robert Dewar]

<< _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.

In any case, using any decent Ada 95 compiler, this should not be an issue,
if you code using the same approach and general abstraction level in the
C code and in the Ada code. Indeed, the availability of packed arrays in
Ada (but not in C) may allow you to raise the semantic level of the Ada
code without penalty (but this is not necessarily the case,, just a
possibility).

Re: CRC in Ada?

[Stephen Garriga]

On 4 Mar 1997 16:01:48 -0500, dewar@merv.cs.nyu.edu (Robert Dewar)
wrote:
{quote snip}
>
>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.
My comment was just a warning!
I was not saying C was a better language, merely that in certain
situations one has to be pragmatic. On certain platforms, certain
operations are fast in C and dogs in Ada.
>
>In any case, using any decent Ada 95 compiler, this should not be an issue,
This assumes you can use Ada95 or have compiler choice. In the UK at
least, our customers are still insisting on Ada(83) or specific vendor
implementations.
>if you code using the same approach and general abstraction level in the
>C code and in the Ada code. Indeed, the availability of packed arrays in
>Ada (but not in C) may allow you to raise the semantic level of the Ada
>code without penalty (but this is not necessarily the case,, just a
>possibility).
>
FYI the specific problem I encountered was generating a CRC for a
file. The performance problem was entirely due to poor performance by
the Ada I/O routines. (There were other problems like failure to
identify end of file situations too). DEC Ada & OS/F 3.2c
Steve Garriga                         garriga@logica.com                 
   type OPINION is access PERSONAL_THOUGHTS_AND_BIAS; 
   OPINION_STATED : new OPINION := not LOGICA.OPINION;
Logica UK Ltd.   +44 171 637 9111   http://www.logica.com

Re: CRC in Ada?

[Michael & Amy Hartsough]

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

Re: CRC in Ada?

[Robert Dewar]

<<It took my Ada CRC32 18 minutes to calculate the checksum for a 65K file! It too
k
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 d
isk!>>

It would be interesting to see how you coded this up, surely you did not
use Text_IO for the I/O (as I say, I have almost never seen people use
Text_IO for such tasks, it is not designed for that kind of use, and
using it for this purpose is inadvisable). Whether or not the difference
you saw is due to poor performance of the I/O packages, or poor choice
of how to use them is hard to say.

It is always possible to match C++ performance in Ada if you are using
a reasonable compiler (GNAT is one, but there are certainly others),
and if you know what you are doing.

Often differences in speed come from poor implementation, it is true (this
can happen either on the C++ or Ada side, I have run into a number of
really horrible performance problems in compilers for all sorts of
languafges), but more usually comes from coding in a way that seems
equivalent, but is not.

For instance, you may often find that the Ada libraries have additional
overhead from being task safe. Very often C runtimes are not task safe
(this might account for example for malloc being faster than new -- in
such a case recoding malloc as new is NOT an accurate translation -- what
you need to do if you want a tasking unsafe allocator is to program one
yourself, easily done.

Similarly the I/O packages of C and Ada are very different.

When you write an applicatoin in Ada, you obviously reuse existing
libraries as much as you can. Thanks to the unmatched capabilities
of Ada 95 in interfacing to other languages, it is almost as easy
to use libraries in other languages as those in Ada 95 (try using
COBOL libraries from C in a portable manner for example -- can't be 
done). 

If you want to do I/O, you have a wide variety of packages available,
some in Ada, some in C, and, don't forget this possibility if you
are interested in high level efficient indexed file access, some in
COBOL. Often all you need for such interface is a simple pragma Import.
Perhaps, e.g. in the case of COBOL, you need a few simple glue functions.

In the context of writing a large application, such interfaces are isolated
to small numbers of packages, and as I have said before, it seems an
advantage, not a disadvantage that Ada can so easily interface to other
languages. Indeed, what on earth would be the point in dfuplicating something
in Ada that is already available in other standard libraries?

Text_IO is convenient for small scale or occasional use for small amounts
of formatted output (compare it to ACCEPT and DISPLAY use in COBOL). It is
not the appropriate interface for large scale I/O where performance is
critical.

One other thing here is that I generally find that when people recode a
piece of code written in language X into language Y, they often do a much
worse job than if they wrote a new program from scratch in Y. It is much
too easy to copy inappropriate approaches and design from the other
implementation. It would be an interesting experiment to code up something
like the CRC efficiently in Ada, which of course can be done, and then
have it translated to C++. For example, if one used packed arrays in Ada,
you can often get some very efficient code that does not map nicely into
C++ at all. The proper approach for recoding this in C++ is to redesign
the data structures, but it would be a path of lesser resistance to emulate
the packed stuff inefficiently in C.

(not that it could not be emulated efficiently, but that is more work!)

Re: CRC in Ada?

[Michael & Amy Hartsough]

Robert Dewar wrote:
> 
> <<It took my Ada CRC32 18 minutes to calculate the checksum for a 65K file! It too
> k
> 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 d
> isk!>>
> 
> It would be interesting to see how you coded this up, surely you did not
> use Text_IO for the I/O (as I say, I have almost never seen people use

I instantiated Sequential I/O with an unsigned 8-bit type.

> One other thing here is that I generally find that when people recode a
> piece of code written in language X into language Y, they often do a much
> worse job than if they wrote a new program from scratch in Y. It is much
> too easy to copy inappropriate approaches and design from the other
> implementation. It would be an interesting experiment to code up something
> like the CRC efficiently in Ada, which of course can be done, and then
> have it translated to C++. For example, if one used packed arrays in Ada,
> you can often get some very efficient code that does not map nicely into
> C++ at all. The proper approach for recoding this in C++ is to redesign
> the data structures, but it would be a path of lesser resistance to emulate
> the packed stuff inefficiently in C.

In this particular case I don't think you'd see a great deal of difference.
There's some anding and xoring, a table look up and the 8-bit shift right and
that's about it (the code's at work, I'm at home now). So you're basically
about as close to machine code as you can get with a HOL.

If you don't include the file access time, the Ada and C++ execution times were
nearly identical.

Later,
	Michael

Re: CRC in Ada?

[Robert Dewar]

Michael said

<<I instantiated Sequential I/O with an unsigned 8-bit type>>

OUCH! Sequential_IO is intended to be used for logical record I/O. 
I can see that one might be tempted to write non-portable code that
(mis)used Sequential_IO in this manner in Ada 83 if you felt compelled
to use the Ada 83 IO packages, instead of the more obvious choice of
using C packages for a case like this (Ada 83 really lacked stream io,
and in a case like this, which is obviously a case for stream io, the
proper response in my view is to interface to C, rather than misuse
the Ada packages).

Why non-portable? Well there is absolutely *no* guarantee that this
isntantiation will have anything to do with reading single bytes. It
would be perfectly reasonable (indeed it is even somewhat encouraged
by the RM) to prepend type information to each record so that type
checking can be done on input.

In Ada 95, if you want to use the Ada packages, you of course use 
Stream_IO, and not Sequential_IO for this purpose. It is absolutely
no surprise that you get a huge difference between C and Ada if
you code this way. Sequential_IO has no analog in C, it is at a much
higher semantic level that the C routines. It is not at all surprising
that you would see the peformance difference, and it says nothing
about Ada-vs-C performance. 

Re: CRC in Ada?

[Michael & Amy Hartsough]

Robert Dewar wrote:
> Michael said
> <<I instantiated Sequential I/O with an unsigned 8-bit type>>
> 
> OUCH! Sequential_IO is intended to be used for logical record I/O.
> I can see that one might be tempted to write non-portable code that
> (mis)used Sequential_IO in this manner in Ada 83 if you felt compelled
> to use the Ada 83 IO packages, instead of the more obvious choice of
> using C packages for a case like this (Ada 83 really lacked stream io,
> and in a case like this, which is obviously a case for stream io, the
> proper response in my view is to interface to C, rather than misuse
> the Ada packages).

I had been directed to implement CRC32 in Ada 83, and test its output against
the output of a C++ version of the algorithm. As soon as testing was completed
the CRC32 code (sans file I/O) was lifted out of the test program and inserted
into an existing embedded application that reads data from a PCMCIA card.

So yes, I DID feel compelled to use an Ada 83 I/O package. I don't think my
employer would have much appreciated my spending half a day chasing down
some C file I/O routines to improve the throughput of my test program.

> It is not at all surprising
> that you would see the peformance difference, and it says nothing
> about Ada-vs-C performance.

Certainly not Ada versus C, but definitely one compiler versus another compiler.
Pick your I/O package and your language, and 18 minutes versus 27 seconds to read
the same file certainly tells you something. HIS compiler (which happens to be
C++) has buffered file I/O. MY compiler (which happens to be Ada 83) does not
buffer file I/O.

	Michael

Re: CRC in Ada?

[Robert Dewar]

Michael said

<<So yes, I DID feel compelled to use an Ada 83 I/O package. I don't think my
  employer would have much appreciated my spending half a day chasing down
  some C file I/O routines to improve the throughput of my test program.>>

No, you felt compelled to *misuse* an Ada 83 I/O package and write highly
non-portable code that relied on the inner workings of sequential_io in
your particular implementation. OK, if you lacked the knowledge to write
the trivial pragma Import for the appropriate C routine (I assume this
if it would have taken you half a day), then you may have been stuck, and
generating this solution may have been the best you could do.

But it was NOT the right solution in Ada, since it did not meet the spec
of the problem except by accident. You cannot expect to do everything in
Ada. Suppose I tell you to write an Ada program that plays a tune on the
speaker.

You have around a C callable routine called Play_Tune that does exactly
what you want, but instead you write a hairy piece of Ada that uses
address clauses to directly address the memory mapped IO port for the
speaker, and write loops with the right frequencies to play the tune.

Your solution is all Ada. Is it therefore superior? no it is perfectly
horrible, and we assume no one would make such a mistake. But your approach
was a (much less obvious and not nearly so horrible) example of the same
mistake.

The fact of the matter is that there WAS no suitable routine in the Ada 83
IO library to solve your problem, just as there is no Play_Note routine.
When you have this situation, then you use pragma Interface, that is what
it is for!

Now in Ada 95, we have Stream_IO which is suitable for solving your problem,
and comparisons of comaprable code using Stream_IO with corresponding C code
are much more meaningful, but it still may be appropriate to use pragma
Interface.

In London a couple of years ago, I gave a talk "Sleeping with the Enemy",
and the theme was that the attitude that C and C++ and ??? are horrible
languages and that you must never go near them is a counter productive
one for Ada programmers. On the contrary, there is lots of useful stuff
there, and a competent Ada programmer knows when and how to take advantage
of it. Note that of course the C or C++ programmer who has a similar
view of Ada (horrible language, don't want to go near it, don't know,
don't want to know) is similarly hobbling themselves.


<<Certainly not Ada versus C, but definitely
  one compiler versus another compiler.
  Pick your I/O package and your language, and 18 minutes versus 27
  seconds to read
  the same file certainly tells you something. HIS compiler (which happens to be
  C++) has buffered file I/O. MY compiler (which happens to be Ada 83) does not
  buffer file I/O>>.

Nope. That misses the point again, you are not comparing one compiler with
another, but rather two completely different solutions, one using a library
routine appropriate to the job, with another solution using an entirely
inappropriate library routine. It would not surprise me at all if the
difference you see, a factor of 30, has nothing at all to do with buffering,
but rather is a natural consequence of the implementation approach for
sequential_IO, which is undoubtedly written to be reasonable for correct
use of the package, and which may well be slow for this clear misuse.

Just to get a bit of a feel for what I mean by sequential_IO being at
a different level of abstraction from the C getchar, look at the following
little bit of code in GNAT's Ada.Sequential_IO.Read:

      --  For non-definite type or type with discriminants, read size and
      --  raise Program_Error if it is larger than the size of the item.

      if not Element_Type'Definite
        or else Element_Type'Has_Discriminants
      then
         FIO.Read_Buf

Now, given a macro substitution approach to generics, it is likely that
this code is optimized away, but in a shared generic approach, it is 
likely to be a real test, and it is certainly a test that would not 
conceivably be present in the C routine.

Does this mean that sequentio_Io is less efficient than the C routine,
no! It means that they are doing different kinds of things. 

If someone compares the peformance of log in C and sqrt in Ada and
tries to draw conclusions about the efficiency of languages, libraries
or compilers from such a comparison, we would immediately see it as
absurd. Comparing getchar in C with sequential_IO.get in Ada is only
slightly less absurd!

Re: CRC in Ada?

[Michael & Amy Hartsough]

Robert Dewar wrote:
> No, you felt compelled to *misuse* an Ada 83 I/O package and write highly

I totally disagree with your use of the term "misuse" here. The only other
Ada 83 I/O package that can possibly be used to read a binary file is Direct I/O. 
You "use" what you have available.

> OK, if you lacked the knowledge to write
> the trivial pragma Import for the appropriate C routine (I assume this
> if it would have taken you half a day), then you may have been stuck, and
> generating this solution may have been the best you could do.

And of course THIS statement is TOTALLY off-base. I was writing import
pragmas for FORTRAN routines back in the 80s.

What WOULD have taken a half a day was locating the desired C routines,
locating a C compiler (no, there are no C compilers on our LAN. I work for
a Dod Contractor, and because of THE mandate, there's no reason to have C
compilers lying around), then compiling the routines to get the .obj files,
then searching through my Ada compiler's documentation to figure out how
to link those .obj files into my Ada executable.

You see, I HAVE written import pragmas.  ;^)

> But it was NOT the right solution in Ada, since it did not meet the spec
> of the problem except by accident.

The "spec" of the problem was to implement CRC32 in Ada 83. All other
considerations were secondary. One of those secondary considerations was
to read bytes from a file. Using Sequential_IO was the ONLY solution
in Ada. True, I COULD have gone out of my way to code up some overblown
contrivance that would have provided more efficient file I/O (and appeased
Robert Dewar), but as this was essentially throwaway code (the file I/O
portion), it would have been a complete waste of my time.

> You cannot expect to do everything in Ada.

That's an easy thing to say if you're not developing software for the DoD.
My manager HATES writing waivers.

And besides, I DO expect to do everything in Ada.

> Suppose I tell you to write an Ada program that plays a tune on the
> speaker.
>
> You have around a C callable routine called Play_Tune that does exactly
> what you want, but instead you write a hairy piece of Ada that uses
> address clauses to directly address the memory mapped IO port for the
> speaker, and write loops with the right frequencies to play the tune.

The fallacy of your argument (in this case) is that you assume
that I have these C routines lying around, as well as a C compiler I
can compile them with. I don't. I would have to go far out of my
way to acquire these things. Maybe things are different in commercial
shops and ivory towers...

Anyway, this sounds like a lot of fun. I've written similar routines to
drive a videodisc player from a PC. These weren't so horrible. Besides,
once I write them, I have them forever. No need to carry around the excess
baggage of a bunch of C routines and their .obj files, or having to
remember to include them in my link command.

And, since we ARE talking about Ada 83 here, not all Ada 83 compilers are
compatible with all C compilers. If I change Ada 83 compilers, I may well have
to change C compilers too. Where's my portability now? If I had a 100% Ada
solution, I might have a good shot at portability. But now you're telling me
I have to have cross-language portability as well. Now, I really don't know
C all that well, but I have heard reports that it's not particularly
noted for its portability.

> It would not surprise me at all if the
> difference you see, a factor of 30, has nothing at all to do with buffering,
> but rather is a natural consequence of the implementation approach for
> sequential_IO, which is undoubtedly written to be reasonable for correct
> use of the package, and which may well be slow for this clear misuse.

My vendor stated that sequential_io flushes the read buffer prior to each
read. So regardless of whether I was reading bytes or reading records, it
would have been extremely slow.

> Just to get a bit of a feel for what I mean by sequential_IO being at
> a different level of abstraction from the C getchar
> :
> : snip snip
> :
> Does this mean that sequentio_Io is less efficient than the C routine,
> no! It means that they are doing different kinds of things.

No need to explain. This is understood. I was not surprised that there
was a difference in the execution speed. I WAS surprised by the
magnitude of the difference.

It should not take 20 minutes to read an 8mb file on a 166MHz pentium PC.
Even if one IS "misusing" sequential_io!

Later,
	Michael

Re: CRC in Ada?

[Robert Dewar]

i<<I totally disagree with your use of the term "misuse" here. The only other
Ada 83 I/O package that can possibly be used to read a binary file is Direct I/O
>>

Nope, Direct_IO is also unsuitable for simulating stream_io in Ada 83 in a
portable manner.

As for writing waivers, no one ever rqeuired a waiver for using pragma
Interface to interface to existing libraries, especially ANSI C libraries,
the idea is absurd. Yes, I know, some procurement people do absurd
things.

Your "use" of sequential_io was still inappropriate, because you were
writing highly non-portable code, which might even have broken using
the next version of the sam e compiler, let alone a different compiler.

Re: Sequential IO on OpenVMS (was: CRC in Ada?)

[Ken Garlington]

Robert Dewar wrote:
> 
> i<<I totally disagree with your use of the term "misuse" here. The only other
> Ada 83 I/O package that can possibly be used to read a binary file is Direct I/O
> >>
> 
> Nope, Direct_IO is also unsuitable for simulating stream_io in Ada 83 in a
> portable manner.
> 
> As for writing waivers, no one ever rqeuired a waiver for using pragma
> Interface to interface to existing libraries, especially ANSI C libraries,
> the idea is absurd. 

Actually, yes they do, if the library becomes delivered as part of the
total
system. (And to answer the obvious follow-up question, yes I have
processed
waivers for assembly routines contained within the Ada run-time!)

The real question is: "So you have to write a waiver. So what?"

> Yes, I know, some procurement people do absurd
> things.
> 
> Your "use" of sequential_io was still inappropriate, because you were
> writing highly non-portable code, which might even have broken using
> the next version of the sam e compiler, let alone a different compiler.

By the way, on a related topic: On VAX/OpenVMS systems, the end-of-file
marker
is embedded within the file header. Even for sequential, fixed-length
record files, the EOF can be placed in the middle of a record
(effectively
truncating it). I have recently come to discover that doing Sequential
IO
on such files has what I consider to be a strange outcome: the truncated
record is read normally, and so "garbage" values past the end of the
file
are processed. On the next record read, END_ERROR is raised. Does the
GNAT implementation for Alpha/OpenVMS mimic this philosophy, as opposed
to
(for example) raising DATA_ERROR on the truncated record? Because of
this problem, we have had to switch to "C" I/O for these files... 

--
LMTAS - The Fighter Enterprise - "Our Brand Means Quality"
For job listings, other info: http://www.lmtas.com or
http://www.lmco.com

Re: Sequential IO on OpenVMS (was: CRC in Ada?)

[Larry Kilgallen]

In article <3336DC57.25DB@lmtas.lmco.com>, Ken Garlington <GarlingtonKE@lmtas.lmco.com> writes:

> By the way, on a related topic: On VAX/OpenVMS systems, the end-of-file
> marker
> is embedded within the file header. Even for sequential, fixed-length
> record files, the EOF can be placed in the middle of a record
> (effectively
> truncating it).

Such a file is certainly an illegal file according to RMS rules.
The program which wrote it needs to be fixed.  Potentially the
system services used by that program need to be fixed by DEC.
The possibility of such an illegal file exists, since the
various file header bit fields have undefined consequences in
certain combinations (and since we are not dealing with the
Ada standard I feel free to intermix terms like "undefined",
"illegal", "bogus" and "wrong" :-).

I certainly believe that it might exist, and for another kind of
file which breaks RMS rules, look to VMS executable images.

Larry Kilgallen

Re: CRC in Ada?

[Mark & Zurima McKinney]

Michael Hartsough Wrote

>It should not take 20 minutes to read an 8mb file on a 166MHz pentium >PC.
>Even if one IS "misusing" sequential_io!

I agree. I have worked with several implementations of Ada on several
computers. I've run across the same problem. What you're dealing with is
a correct but inefficient implementation of sequential_io. In one case I
had access to the source of sequential_io, copied it, renamed the
package buffered_sequential_io added buffering and used it. Later I
ported that sytem to another machine using an Alsys product that allowed
the programmer to pass buffering information in the form parameter. 

....
   package Char_io is new Sequential_io (Character);
....
   Char_Io.Create(Char_File, Char_io.In_File, "Filename", "Buffer_Size
=> 4096");
   -- On Alsys this also works for text_io a lager buffer size will
probable improve performance

Not completely portable but extreemly effective. We had a 300 MB file
that could be read in 1 minute vs the C compiler in 2 Min. Using the
Alsys PC compiler I could read the same file in approximatly 6 Minutes
using a 90 mz pentium. 

IMHO Stream_Io may be more appropriate if available. If not
sequential_io is a logical choice unfortunately you have a correct but
inefficient implementation to use.

 
Mark McKinney

Re: CRC in Ada?

[Robert Dewar]

i<<IMHO Stream_Io may be more appropriate if available. If not
sequential_io is a logical choice unfortunately you have a correct but
inefficient implementation to use.>>

Logical is not quite the word I would use, since logic says that there
is no reason to expect that it would work at all, since the RM neither
states, nor even implies that it will work. Indeed by pointing out that
type checking *may* be done, the RM puts you on notice that it may well
not work.

Pragmatically, if, for some reason, you think it is better to write
dubious non-portable Ada code, as opposed to portable code that uses
pragma interface to an ANSI C routine, then it may be the case in Ada 83
that sequential_io is your only choice, but logical, I think not!

Also, note that in your hacking of the sequential IO package, you may
well have introduced tasking non-safety. Any time you add more state
(in this case the buffer and its pointers), you risk task safety,
and you need to at least think about this as an issue.

Re: CRC in Ada?

[Tom Moran]

> *misuse* an Ada 83 I/O package and write highly
> non-portable code that relied on the inner workings of sequential_io 
Wow, I'm sure glad I didn't know when I started trying Ada that you
couldn't read a sequential file of fixed length records with the thing
called "Sequential_IO"!  I would have dropped it and stayed with
something reasonable, like C.   @.@

Re: CRC in Ada?

[Robert Dewar]

Tom Moran says

<<Wow, I'm sure glad I didn't know when I started trying Ada that you
couldn't read a sequential file of fixed length records with the thing
called "Sequential_IO"!  I would have dropped it and stayed with
something reasonable, like C.   @.@>>

Well it's just possible that other people than Tom Moran have manbaged
to misread what i read :-)

so here is a further explanation.

Of course you can use Ada to read and write a file that is logically
organized as a sequential file of records, and that is exactly what
Sequential_IO does.

HOWEVER, the level of abstraction in C is quite different from that in 
Ada. In C, you know how the IO operations you write are reflected at the
fundamental level of the sequential butes of a file (of course this
low level understanding breaks down badly when you have more sophisticated
file systems like that on the IBM mainframes or VMS, but C folks generally
don't like such systems anyway ("if I can't read it with C, it must be broke")
so that doesn't matter to most C programmers.

The Sequential_IO, Text_IO and Direct_IO packages of Ada are at a significantly
higher semantic level. You have NO guarantees, none at all, of how the logical
structures they implement map down to the file level. You do have a guarantee
that the same code will operate in the same abstract manner regardlless of
the structure of the underlying file system, and, unlike the C programmer
who sits scratching their head wondering how C stream IO maps into BSAM
or ISAM file structures, the Ada programmer knows that their program will
run fine, no matter what the underlying file system looks like.

This has good points and bad points. The good point is this independence
from the underlying file structure, the bad point is this independence from
the underlying file structure!

If the problem is that you want to read existing data encoded in a certain
way (in the case under discussion a stream of bytes represented in a single
stream file), then there is no correct Ada solution using these high level
packages. Yes, you may be able to get something working by depending on
non-guaranteed implementation behavior of your current compiler, but you
are then writing implementation dependent code. 

As to how portable this code really is, who knows? Certainly the Ada
reference manual gives no hint, but sometimes, as many C programmers
know, you can write non-standard code that is in fact quite portable.
Maybe this code is in this category, maybe it is not, who knows. I know
of at least one counterexample where it would not work.

Note that Stream_IO in Ada 95 is not "just another IO package", it is
COMPLETELY different in style, in that, like the C streams package, it
is very low level, and the mapping to the external file is defined.
Stream_IO has the advantage that you really know what the mapping is,
and can base portable code on this knowlegde. Stream_IO has the disadvantage
that it has this low level mapping, and, for examle, I have no guess as
to what Stream_IO would do on top of a BDAM file on a 360 mainframe!

As for the "if I had known that Ada could not do X, I would have switched
to C", either this is entirely non-serious, or if serious, then it seems
odd to me. If you would switch to C on the basis of such a trivial excuse,
why bother to need an excuse at all, why not just use C in the first place?

Re: CRC in Ada?

[Tom Moran]

Sorry, 
> couldn't read a sequential file
should have said "couldn't read an existing sequential file".  Having
learned Ada after leaving school, I was interested in using it in the
real world, not in a classroom excercise.  I assume there are others who
are doing real tasks and might give Ada a try, but not much of one if
Ada appears, rightly or wrongly, highly unsuitable.

> As for the "if I had known that Ada could not do X, I would have switched
> to C", either this is entirely non-serious, or if serious, then it seems
> odd to me. If you would switch to C on the basis of such a trivial excuse,
> why bother to need an excuse at all, why not just use C in the first place?
  Surely an inability to do X in Ada would not be a "trivial excuse" for
not using Ada to do X.  And the fact that X can in fact be done, but
only by avoiding the obvious approaches and using non-portable vendor
specific features, may be a saving grace theoretically, but not if the
customers have already left the store.  (Also, the original comment did
not say 'switch to C', but rather "stayed with ...".)
  
   The point is that you don't get many chances to sell curious non-Ada
programmers on Ada, and it's highly important that their early
experiences are not turn-offs.  Looking at several Ada texts from my
local computer bookstore I see no warning that Sequential_IO may not
work or that it may be extremely slow.  I suggest that any compiler
vendor who hopes to have Ada novices among his customers (ie any vendor
who hopes for a growing market) should make great efforts not to give
nasty surprises.

Portable Code (was: CRC in Ada?)

[Larry Kilgallen]

In article <3335D8F0.106F@bix.com>, Tom Moran <tmoran@bix.com> writes:
> Sorry, 
>> couldn't read a sequential file
> should have said "couldn't read an existing sequential file".  Having
> learned Ada after leaving school, I was interested in using it in the
> real world, not in a classroom excercise.  I assume there are others who
> are doing real tasks and might give Ada a try, but not much of one if
> Ada appears, rightly or wrongly, highly unsuitable.

I think there is a dichotomy of specification standards, in that
those discussing Ada often presume "in a portable fashion" as
being a requirement.  Over and over again I read messages from
C programmers who are shocked that their traditional IO methods
cannot read an "ordinary" VMS file without resorting to particular
OS-specific file opening methods. Discussions in c.l.a tend to
favor consideration of portability _before_ the source code
is first written.  That approach is not appropriate in the C
world, which has a cultural bias toward "knowing" that every
operating system will be "Unix" (whatever that means this month).

For "real-world" problems in Ada based on an existing environment,
it is quite possible to write non-portable code.  Ada is quite fine
for writing bales of code full of calls to highly non-portable VMS
system services.  I bet it works just as with non-portable calls to
OS/2. Consideration of a language should not be biased by the fact
that the problem itself does not admit of a portable solution.

If you think C is better than Ada for portable code, please first
make sure your C program never uses "#if<whatever>" for platform
distinctions.  Otherwise we are not talking about portable source
but rather how the non-portable source is arranged into files.

Larry Kilgallen

Re: CRC in Ada?

[Robert A Duff]

In article <dewar.859141238@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>The Sequential_IO, Text_IO and Direct_IO packages of Ada are at a significantly
>higher semantic level. ...

I won't comment on Sequential_IO and Direct_IO, but surely Text_IO is
intended to produce a format that makes sense to non-Ada programs.  That
is, if I write a file using Text_IO, and I don't do anything funny with
control characters, then I ought to be able to read that file into my
favorite text editor (say, Emacs), and have it make sense.  If the Ada
system is putting weird stuff in the file, which makes this impossible,
then that's a bug, IMHO.  (IMHO, the term "bug" refers to any
wrong/undesirable behavior, whether or not it violates the Ada standard.
That is, the set of possible bugs in an Ada compiler is a superset of
the set of possible vilations of the RM.)

- Bob

Re: CRC in Ada?

[Robert Dewar]

<<I won't comment on Sequential_IO and Direct_IO, but surely Text_IO is
intended to produce a format that makes sense to non-Ada programs.  That
is, if I write a file using Text_IO, and I don't do anything funny with
control characters, then I ought to be able to read that file into my
favorite text editor (say, Emacs), and have it make sense.  If the Ada
system is putting weird stuff in the file, which makes this impossible,
then that's a bug, IMHO.  (IMHO, the term "bug" refers to any
wrong/undesirable behavior, whether or not it violates the Ada standard.
That is, the set of possible bugs in an Ada compiler is a superset of
the set of possible vilations of the RM.)>>

It is hard to know what Text_IO is intended for sometimes, but the page
mark business means that in fact you have to work VERY hard to make
Text_IO files compatible with interactive IO, or compatible with text
editors, probably any file written by Text_IO can be read by an editor,
but the opposite is not always true.

Also, on a system like the Unisys 1100 operating system, the natural
format for Text_IO files would be the normal source format (I forget
what it is called, a while since I worked with it), but there are aspects
to this format that make it incompatible with Text_IO, so it would not
be surprising to find Text_IO using some other weird format not directly
readable by editors.

Sure on a system with no fancy IO, like Unix, you can easily enough
make Text_IO consistent with editors, but in the case of systems with
complex file structures, it is not a all clear that you can expect
ayutomatic compatibilty bnetween text_IO and some arbitrary editors,
indeed on such systems editorsd are not always compatible with one
another (for examle, one might use a quite different file format for
source files, and general ascii files).

Re: CRC in Ada?

[Robert A Duff]

In article <E7K2q1.EDF@world.std.com>,
I wrote:
>That is, the set of possible bugs in an Ada compiler is a superset of
>the set of possible vilations of the RM.)
                     ^^^^^^^^^

Funny typo (does it mean the same thing as "vilifications"?).  I meant
"violations", of course.  ;-)

- Bob

Re: CRC in Ada?

[Larry Kilgallen]

In article <E7K2q1.EDF@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:
> In article <dewar.859141238@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>>The Sequential_IO, Text_IO and Direct_IO packages of Ada are at a significantly
>>higher semantic level. ...
> 
> I won't comment on Sequential_IO and Direct_IO, but surely Text_IO is
> intended to produce a format that makes sense to non-Ada programs.  That
> is, if I write a file using Text_IO, and I don't do anything funny with
> control characters, then I ought to be able to read that file into my
> favorite text editor (say, Emacs), and have it make sense.  If the Ada
> system is putting weird stuff in the file, which makes this impossible,
> then that's a bug, IMHO.  (IMHO, the term "bug" refers to any
> wrong/undesirable behavior, whether or not it violates the Ada standard.
> That is, the set of possible bugs in an Ada compiler is a superset of
> the set of possible vilations of the RM.)

Depending on the operating system, it may be possible to write a file
which makes sense to one non-Ada program but not to another. So if we
say that Text_IO output should be readable by "some" non-Ada programs
or "ANSI-standard" non-Ada programs, that still leaves a lot of room
for "bugs" to use your definition.  It is entirely possible to have
two tools both of which are "favorites" which don't handle things in
the same fashion.  Thus one can have a "bug" (as always, seen in the
eye of the user) which Standard Ada (no platform tricks) could not
avoid.

Larry Kilgallen

Re: CRC in Ada?

[Robert A Duff]

In article <1997Mar24.130721.1@eisner>,
Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>Depending on the operating system, it may be possible to write a file
>which makes sense to one non-Ada program but not to another. So if we
>say that Text_IO output should be readable by "some" non-Ada programs
>or "ANSI-standard" non-Ada programs, that still leaves a lot of room
>for "bugs" to use your definition.  It is entirely possible to have
>two tools both of which are "favorites" which don't handle things in
>the same fashion.

Well, sure, but on VMS, I can edit text files using several editors, and
it seems to work, more or less.  Surely, I can expect Ada.Text_IO to
generate files compatible with that mode of operation.  And vice-versa.
I mean, when I edit a file in VMS, I don't give a bunch of
system-dependent mumbo jumbo about what *sort* of text file I want.

>...  Thus one can have a "bug" (as always, seen in the
>eye of the user) which Standard Ada (no platform tricks) could not
>avoid.

I agree that "bug" is in the eye of the beholder.  ;-)  And, sometimes,
it's in the eye of the holder whose *fault* the bug is -- usually, given
two incompatible programs, the second one that one happens to run
across!

- Bob

P.S. I haven't used VMS for several years, but when I did, I used to
edit text files (e.g. source code for a program) sometimes, and despite
the weird file naming conventions, the *contents* of the files were
plain old ascii text.

Re: CRC in Ada?

[Robert I. Eachus]

In article <E7KIv2.CJ2@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

  > Well, sure, but on VMS, I can edit text files using several editors, and
  > it seems to work, more or less.  Surely, I can expect Ada.Text_IO to
  > generate files compatible with that mode of operation.  And vice-versa.
  > I mean, when I edit a file in VMS, I don't give a bunch of
  > system-dependent mumbo jumbo about what *sort* of text file I want.

     You've lead a sheltered life Bob. ;-)  When you go to read that
VMS text file using Ada.Text_IO on a Unix box, good luck.  Similarly,
I thought we have all had to deal with the different end-of-line
conventions on Unix and PCs.

     In Ada 83, the rule was if you wanted to do system dependent
low-level I/O you used a package called, Low_Level_IO.  And I don't
want to hear carping about not all compilers supporting Low_Level_IO.
It was a required package (no longer required in Ada 95) and I know of
several validated compilers with useful implementations of
Low_Level_IO that were available in 1984.

     In Ada 95, streams replace Low_Level_IO as a more portable
low-level I/O interface.  But sometimes you have to go bang bits in
device drivers, and then the meaning of your code is, of necessity,
way outside the language standard.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: CRC in Ada?

[David Emery]

Of course the meaning of "textfile" is OS-dependent.  In the POSIX/Ada
binding, we specify a way to use Text_IO to produce "textfiles" as
defined by POSIX (actually POSIX.2).  But this requres some special
support within the implementation of Text_IO to work around the
conflict between Ada's "page model" for Text_IO files and the Unix
"stream of bytes separated by line-feed model" for text files.

We spent -A LOT- of time in the POSIX/Ada development on this issue;
it was not trivial to solve.  

There's some discussion on this in the POSIX/Ada Rationale, and a more
complete discussion of the alternatives in my POSIX/Ada Tutorial that I've
presented at Tri-Ada, AdaUK and Ada Europe.

				dave

-- 
Note: if email to me bounces, use 'emery@grebyn.com'

Re: CRC in Ada?

[John Apa]

Stephen Garriga wrote:
> 

snip 

>  _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.

Perhaps, but it so happens that I also implemented a crc algorithm in
both c and ada. I found that the ada was slightly faster (sun & i960,
using gnat for both) when running on disk files, and about even when
running against memory sections. Hmm. 

IMVHO: Any broad statement (C faster than Ada, or the converse) will be
found to have counter examples. Results may vary, as has been shown in
this group time and again. Choosing c or ada without looking at the
results from your particular implementations is simply bad engineering.
If you have a good compiler and knowledge of the language, you can write
very good/fast/safe/_understandable_ code. Ada95 has added many features
which will assist in this for a variety of situations and systems.

To those who don't think ada95 is the best thing out there right now,
read the Rationale for this ANSI/ISO/IEC standard. It should change your
mind. You could read the one for c++, but only if you're a physic. ;-)

John

> 
> Steve Garriga                         garriga@logica.com
>    type OPINION is access PERSONAL_THOUGHTS_AND_BIAS;
>    OPINION_STATED : new OPINION := not LOGICA.OPINION;
> Logica UK Ltd.   +44 171 637 9111   http://www.logica.com

-- 
***********************************
That's my opinion, not Honeywell's.
John Thomas Apa
Honeywell Defense Avionics Systems
Albuquerque, New Mexico.
***********************************

Re: CRC in Ada?

[David L Brown]

garriga@logica.com (Stephen Garriga) writes:

>  _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, I tried this.  I wrote a small program to read files and compute
CRC16's on them.  What I found was disheartening.  The CRC code didn't
take very long.  However, the Stream_IO read of the data was very
slow.  I traced it down to doing a call to the C read function for
each byte.

I'm using GNAT 3.09 on Linux (pentium).  Is there anything about the
specification for Stream_IO (or Text_IO for that matter) that is
causing the GNAT runtime to turn off buffering.  This is a real
performance hit, and I have had to revert to calling the C routines
directly when streams would be adequate, if they just weren't so
inefficient.

Dave

Re: CRC in Ada?

[Robert Dewar]

David Brown:

<<Well, I tried this.  I wrote a small program to read files and compute
CRC16's on them.  What I found was disheartening.  The CRC code didn't
take very long.  However, the Stream_IO read of the data was very
slow.  I traced it down to doing a call to the C read function for
each byte>>

  Are you using stream attributes to read into a string. This is a mistake
  that I have seen a number of people make. Why a mistake (if you are 
  worrying about efficiency?) Because Ada semantics require element by
  element processing of arrays (and for a string, the element is a
  character). 

  Instead use Read and Write directly to read and/or write buffers
  of stream elements.

<<I'm using GNAT 3.09 on Linux (pentium).  Is there anything about the
specification for Stream_IO (or Text_IO for that matter) that is
causing the GNAT runtime to turn off buffering.  This is a real
performance hit, and I have had to revert to calling the C routines
directly when streams would be adequate, if they just weren't so
inefficient.>>

  As for buffering, I am not sure what the default is, but you can use
  setvbuf to control buffering (read the section in the GNAT manual about
  getting at the underlying streams).

Re: CRC in Ada?

[Stephen Garriga]

On 04 Mar 1997 14:56:58 -0800, David L Brown <dbrown@ted.vigra.com>
wrote:

>garriga@logica.com (Stephen Garriga) writes:
>
>>  _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, I tried this.  I wrote a small program to read files and compute
>CRC16's on them.  What I found was disheartening.  The CRC code didn't
>take very long.  However, the Stream_IO read of the data was very
>slow.  I traced it down to doing a call to the C read function for
>each byte.
>
>I'm using GNAT 3.09 on Linux (pentium).  Is there anything about the
>specification for Stream_IO (or Text_IO for that matter) that is
>causing the GNAT runtime to turn off buffering.  This is a real
>performance hit, and I have had to revert to calling the C routines
>directly when streams would be adequate, if they just weren't so
>inefficient.
>
>Dave
I was using a DEC Alpha, DEC Ada (83) and OS/F 3.2c!
I didn't the time to investigate too closely, but it looked to me
that, in my case, the I/O was actually implemented as many layers of
generics on top of the low level OS call then specific instantiations.
This remained in place at run time so instead of generating a single
stack frame/procedure call, dozens were done per read! 
Efficiency was weighted over design purity and several such problems
were addressed with small C procedures interfaced to our Ada. 
Steve Garriga                         garriga@logica.com                 
   type OPINION is access PERSONAL_THOUGHTS_AND_BIAS; 
   OPINION_STATED : new OPINION := not LOGICA.OPINION;
Logica UK Ltd.   +44 171 637 9111   http://www.logica.com

Re: CRC in Ada?

[Larry Kilgallen]

In article <331d3cf9.1190126@news.logica.co.uk>, garriga@logica.com (Stephen Garriga) writes:

> I was using a DEC Alpha, DEC Ada (83) and OS/F 3.2c!
> I didn't the time to investigate too closely, but it looked to me
> that, in my case, the I/O was actually implemented as many layers of
> generics on top of the low level OS call then specific instantiations.
> This remained in place at run time so instead of generating a single
> stack frame/procedure call, dozens were done per read! 
> Efficiency was weighted over design purity and several such problems
> were addressed with small C procedures interfaced to our Ada. 

If I were looking for maximum speed in Assembly Language, I would
minimize the total number of reads done, to a single read if possible.
This should be true for any language.

On VMS, the fact that C programs imported from Unix tend to do a
lot of single character I/O has forced the DEC C team to build in
many little tricks to support an inherently inefficient programming
technique.

For Ada, I would guess that implementors have not counted on
people using C-like programming constructs (vs. doing large
buffer reads as suggested earlier in this thread).

It is certainly possible to build an Ada environment optimized for
single-character reads, but that would not seem to be a priority
for most Ada compiler customers.

Larry Kilgallen

Re: CRC in Ada?

[Robert A Duff]

In article <1997Mar5.083233.1@eisner>,
Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>For Ada, I would guess that implementors have not counted on
>people using C-like programming constructs (vs. doing large
>buffer reads as suggested earlier in this thread).
>
>It is certainly possible to build an Ada environment optimized for
>single-character reads, but that would not seem to be a priority
>for most Ada compiler customers.

I think I disagree.  Buffering should be the job of the OS and/or
standard libraries.  Not every program.

I'm not sure why reading a file character-by-character is "C-like".
It seems like the natural way to write lots of programs, in any
language.  The underlying language and OS should ensure that it can be
done efficiently (by making the "give-me-a-char" routine read from a
buffer whenever appropriate).

- Bob

Re: CRC in Ada?

[Larry Kilgallen]

In article <E6Kxux.FL9@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:
> In article <1997Mar5.083233.1@eisner>,
> Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>>For Ada, I would guess that implementors have not counted on
>>people using C-like programming constructs (vs. doing large
>>buffer reads as suggested earlier in this thread).
>>
>>It is certainly possible to build an Ada environment optimized for
>>single-character reads, but that would not seem to be a priority
>>for most Ada compiler customers.
> 
> I think I disagree.  Buffering should be the job of the OS and/or
> standard libraries.  Not every program.

While theoretical computing and Alan Turing may be centered on
the equivalence and correctness of programs, in the real world
performance is also a consideration.  Just as those using intense
computation will be concerned about the efficiency of their
algorithms, those accessing large databases will take care
regarding order-of-access so as not to go skipping over the
whole thing when some locality-of-reference would yield better
performance.  Those reading sequentially from disk should
likewise concern themselves with performance, and 512 calls
to even the lightest-weight library is too much if a single
call would do.  For the stated problem (CRC) reading large
blocks is a clear win.

> I'm not sure why reading a file character-by-character is "C-like".
> It seems like the natural way to write lots of programs, in any
> language.  The underlying language and OS should ensure that it can be
> done efficiently (by making the "give-me-a-char" routine read from a
> buffer whenever appropriate).

In my experience it is generally C programmers who make this mistake.
Perhaps it because many of them come from a Unix background where there
is no strong sense of a "record".  On the other hand, it may just be
that there are so many C programmers that statistically speaking most
of the mistakes made will be made by a C programmer.

Larry Kilgallen

Re: CRC in Ada?

[Fergus Henderson]

kilgallen@eisner.decus.org (Larry Kilgallen) writes:

>bobduff@world.std.com (Robert A Duff) writes:
>> 
>> I think I disagree.  Buffering should be the job of the OS and/or
>> standard libraries.  Not every program.
>
>While theoretical computing and Alan Turing may be centered on
>the equivalence and correctness of programs, in the real world
>performance is also a consideration.

Sure.  That's why buffering is needed.  But buffering  should be the
job of the OS and/or standard libraries.

>Just as those using intense
>computation will be concerned about the efficiency of their
>algorithms, those accessing large databases will take care
>regarding order-of-access so as not to go skipping over the
>whole thing when some locality-of-reference would yield better
>performance. 

Sure.  No disagreement here.

>Those reading sequentially from disk should
>likewise concern themselves with performance, and 512 calls
>to even the lightest-weight library is too much if a single
>call would do.

Nonsense, if the calls are inlined, and the compiler does a good
job of optimization, there is no reason why the cost need be too much.

>For the stated problem (CRC) reading large
>blocks is a clear win.

Yes, but that is true for just about all performance-intensive stream
I/O tasks.  That's why it makes sense for this to be done by the
standard library and/or OS.

>> I'm not sure why reading a file character-by-character is "C-like".
>> It seems like the natural way to write lots of programs, in any
>> language.  The underlying language and OS should ensure that it can be
>> done efficiently (by making the "give-me-a-char" routine read from a
>> buffer whenever appropriate).
>
>In my experience it is generally C programmers who make this mistake.

Why is it a mistake?

If the implementation implements it efficiently, as it should,
I don't see any reason to regard using such a mechanism as a mistake.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: CRC in Ada?

[Larry Kilgallen]

In article <5fmo1k$adm@mulga.cs.mu.OZ.AU>, fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
> kilgallen@eisner.decus.org (Larry Kilgallen) writes:
> 
>>bobduff@world.std.com (Robert A Duff) writes:

>>> I'm not sure why reading a file character-by-character is "C-like".
>>> It seems like the natural way to write lots of programs, in any
>>> language.  The underlying language and OS should ensure that it can be
>>> done efficiently (by making the "give-me-a-char" routine read from a
>>> buffer whenever appropriate).
>>
>>In my experience it is generally C programmers who make this mistake.
> 
> Why is it a mistake?
> 
> If the implementation implements it efficiently, as it should,
> I don't see any reason to regard using such a mechanism as a mistake.

If a programmer _assumes_ that such a construct will be efficient,
when in fact it is _not_ efficient within a particular environment,
it is a mistake from a performance perspective.

I have run into programmers making this mistake over and over again.
In recent years their immediate response has been "Gee, it runs fast
on Unix", but in prior years their response was "Gee, it runs fast
on MVS".  Obviously it is only the recent history where the C language
is involved, but the current generation seems much more surprised than
their MVS-centric predecessors.

An analogy would be developers who find their MS-DOS game cannot
write directly to the screen under Windows NT.  That is a bit
rougher, as one has to start from scratch explaining the difference
between an operating system and a run-time library :-)

Larry Kilgallen

Re: CRC in Ada?

[Robert A Duff]

In article <1997Mar6.114441.1@eisner>,
Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>If a programmer _assumes_ that such a construct will be efficient,
>when in fact it is _not_ efficient within a particular environment,
>it is a mistake from a performance perspective.

OK, but where do you draw the line?  Suppose I'm trying to write
portable software.  I measure the performance on my current
OS/compiler/libraries, and it's fine.  Can I assume that it will still
perform as expected on any other platform?

There don't seem to be any performance requirements in most standards.
E.g. an Ada compiler that implements assignment of integers by first
copying each bit one-by-one, and then doing 10,000 no-op instructions is
perfectly valid, according to the RM.  But when I write code, I assume
that (32-bit) integer assignment, on a 100MHz machine, takes something
like 1/(10**8) seconds, give or take.  Assuming I don't get a cache miss
or page fault.  I assume it's not quadratic in the size of the variable
name, or some such oddity.

Why should I not assume that a get-character-from-file operation takes
more than a few instructions, on average?  I know how to implement such
an operation, and it's not hard.  If it turns out that some OS does it
slowly, then I feel righteous in blaming the OS.  (Of course, from a
practical point of view, if that OS is popular, then I'll have to live
with its limitations.)

Remember this [sub]thread started with the claim that VMS folks had to
go to a lot of trouble to support those "evil" C programmers who wanted
to do char-by-char input.  My response is: Good, somebody forced them to
do what they should do -- namely, implement char-by-char input
efficiently.

>I have run into programmers making this mistake over and over again.
>In recent years their immediate response has been "Gee, it runs fast
>on Unix", but in prior years their response was "Gee, it runs fast
>on MVS".  Obviously it is only the recent history where the C language
>is involved, but the current generation seems much more surprised than
>their MVS-centric predecessors.

Seems pretty reasonable to me: if Unix or MVS can do it fast, why can't
whatever-OS-we're talking about do it fast?  If not, it seems like the
fault of the OS, or the standard libraries implementation.

>An analogy would be developers who find their MS-DOS game cannot
>write directly to the screen under Windows NT.  That is a bit
>rougher, as one has to start from scratch explaining the difference
>between an operating system and a run-time library :-)

I don't buy the analogy.  If OS X can do some operation fast, and OS Y
does it much slower, then that's the fault of OS Y.  (Assuming both OS's
are real operating systems -- that is, provide protection of address
spaces and so forth.)  The write-directly-to-screen thing is different
-- as you say, one needs to explain the difference between MS-DOS and an
operating system.

- Bob

Re: CRC in Ada?

[Robert Dewar]

iRobert Duff says

<<OK, but where do you draw the line?  Suppose I'm trying to write
portable software.  I measure the performance on my current
OS/compiler/libraries, and it's fine.  Can I assume that it will still
perform as expected on any other platform?
>>

No, you can't, but you are expected to have a good feel for what is
efficient and what is not efficient over a wide range of platforms if
you are trying to write portable code that is efficient. This is one
of the skills that is required for writing such code. Yes, it is VERY
hard to acquire this skill and the knowledge base required to support it!!

Re: CRC in Ada?

[Larry Kilgallen]

In article <E6n850.3Ct@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:
> In article <1997Mar6.114441.1@eisner>,
> Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>>If a programmer _assumes_ that such a construct will be efficient,
>>when in fact it is _not_ efficient within a particular environment,
>>it is a mistake from a performance perspective.
> 
> OK, but where do you draw the line?  Suppose I'm trying to write
> portable software.  I measure the performance on my current
> OS/compiler/libraries, and it's fine.  Can I assume that it will still
> perform as expected on any other platform?

Starting with something which performs well in at least one environment
is certainly a bare minimum.  I happen to think there is a need to plan
for revisiting performance when switching environments.

> Why should I not assume that a get-character-from-file operation takes
> more than a few instructions, on average?  I know how to implement such
> an operation, and it's not hard.  If it turns out that some OS does it
> slowly, then I feel righteous in blaming the OS.  (Of course, from a
> practical point of view, if that OS is popular, then I'll have to live
> with its limitations.)

Why should finding a record with particular contents in the middle of
a file take a long time?  There are books about how to write indexed
file systems, but some operating systems skipped that part of what I
am accustomed to relying upon.  I don't include that to start a
feature war, but to introduce the next question:  How hard is it to
get-character-from-file when the file has all that baggage used to
find records with with particular contents ? DEC compilers run
more slowly when fed such a file, because it is beyond the ability
programmed into their map-it-into-memory trick.

What you (or I) see as limitations in a particular selection of
compiler/os/library may be exactly what someone else needs to do
their job.

> Remember this [sub]thread started with the claim that VMS folks had to
> go to a lot of trouble to support those "evil" C programmers who wanted
> to do char-by-char input.  My response is: Good, somebody forced them to
> do what they should do -- namely, implement char-by-char input
> efficiently.

While I understand that is your view on what they should do, not all
will share it. The last time I needed to do character-at-a-time IO was
to emulate an editor which required a termination character on input
_unless_ the first character was one particular alphabetic character
(which had no special meaning in other than the first position).  I
have been faced with a different set of projects than you, but I have
my own list of things that "any environment ought to do properly" such
as file versioning :-).

>>I have run into programmers making this mistake over and over again.
>>In recent years their immediate response has been "Gee, it runs fast
>>on Unix", but in prior years their response was "Gee, it runs fast
>>on MVS".  Obviously it is only the recent history where the C language
>>is involved, but the current generation seems much more surprised than
>>their MVS-centric predecessors.
> 
> Seems pretty reasonable to me: if Unix or MVS can do it fast, why can't
> whatever-OS-we're talking about do it fast?  If not, it seems like the
> fault of the OS, or the standard libraries implementation.

Sorry if I was unclear, but Unix and MVS could not do the _same_thing_
fast.  The only commonality was that people coming from Unix and
people coming from MVS both assumed that the new operating system
would have the same performance characteristics as the one they are
coming from.  Now obviously it is impossible for the target operating
system to fully mimic the behaviour of both Unix and MVS at the same
time to make both camps happy.

Larry Kilgallen

Re: CRC in Ada?

[Robert A Duff]

In article <1997Mar7.090814.1@eisner>,
Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>Why should finding a record with particular contents in the middle of
>a file take a long time?  There are books about how to write indexed
>file systems, but some operating systems skipped that part of what I
>am accustomed to relying upon. ...

Good point, I admit.

>have been faced with a different set of projects than you, but I have
>my own list of things that "any environment ought to do properly" such
>as file versioning :-).

That one's on my list, too.  :-)

- Bob

Re: CRC in Ada?

[Tom Moran]

The original message in this thread did not say "reading a file a
character at a time is slow", but rather that doing it in Ada was an
order of magnitude slower than doing it in C, on the same OS and
hardware.  Since there is no other way strictly in Ada to read a file
which is too large for memory and whose size is a prime number, this is
unfortunate.  And saying Ada 95 can do it by calling a C function, is
less than a strong endorsement of Ada.

Re: CRC in Ada?

[Robert Dewar]

Larry says

<<As for a C implementation being better than an Ada implementation
at single character reads, I imagine there must be another language
characteristics where Ada has some advantage or other.>>

The comparison between C and Ada here is apples-oranges. Text_IO.Get
has far more elaborate semantics than getchar, so you cannot compare
the two. This is a common effect (see another example below). If you
want the simple minded semantics of getchar, then this is trivially
programmed in Ada (the GNAT package GNAT.IO is a much closer approximation
to the C level semantics).

Another interesting case of this is a timing comparison that Bob Klungle
sent me comparing the use of the official log and the log in the
"secret" package Aux. The log in Aux is a direct call to C, the log
in Ada has rather different semantics, as you can see from its coding:

   function Log (X : Float_Type'Base) return Float_Type'Base is
   begin
      if X < 0.0 then
         raise Argument_Error;

      elsif X = 0.0 then
         raise Constraint_Error;

      elsif X = 1.0 then
         return 0.0;
      end if;

      return Float_Type'Base (Aux.Log (Double (X)));
   end Log;

Those extra tests, required by Ada semantics, end up making the use of
the Ada log function very much slower (almost a factor of two in Bob's tests)
which is a bit worrisome -- safety and accuracy are not free :-)

Re: CRC in Ada?

[Geert Bosch]

Robert Dewar (dewar@merv.cs.nyu.edu) wrote:
   Another interesting case of this is a timing comparison that Bob Klungle
   sent me comparing the use of the official log and the log in the
   "secret" package Aux. The log in Aux is a direct call to C, the log
   in Ada has rather different semantics, as you can see from its coding:

But what surprises me is that in cases where the argument is *known*
to be larger than 1.0 the checks are still being made. Normally I would
use a subtype Positive_Float for values which should be positive in a
calculation. This will give a good compiler the opportunity to omit the
extra comparisons in the Ada code.

Sadly enough GNAT is not (yet) such a good compiler in this respect.
In fact GNAT should be able to generate faster code for invocations of
the log function for such arguments, since it can inline the function
to *only* contain the log instruction. 

There are many real-world examples where optimizations like these
can make a difference of a factor 3 and more, so I guess these 
optimizations satisfy Robert Dewars criterea.

Also the requirement to return 0.0 when the argument is 1.0 doesn't need
to generate extra code, since the check could be changed in Accurate_Log_1
and then X = 1.0, and the boolean value Accurate_Log_1 can be determined
at compile time. 
(To be honest, this might not be possible for platforms where 
the program may run on different numeric processors. In this case
the check must be done at elaboration time which leaves in the
boolean check.)

Regards,
   Geert

Re: CRC in Ada?

[Robert Dewar]

<<<<But what surprises me is that in cases where the argument is *known*
to be larger than 1.0 the checks are still being made. Normally I would
use a subtype Positive_Float for values which should be positive in a
calculation. This will give a good compiler the opportunity to omit the
extra comparisons in the Ada code.

Sadly enough GNAT is not (yet) such a good compiler in this respect.
In fact GNAT should be able to generate faster code for invocations of
the log function for such arguments, since it can inline the function
to *only* contain the log instruction.

There are many real-world examples where optimizations like these
can make a difference of a factor 3 and more, so I guess these
optimizations satisfy Robert Dewars criterea.>>


That's a pretty marginal optimization. Maybe Geert makes subtypes
Positive_Float, but of all the code we ever had submitted to us,
no one ever bothered to do this, they just used Float.

Still it can go on the list, it's way down there in priority though,
there are MANY more important optimizations ahead of it!

Note of course that Geert's optimization is only possible in any
case if the log function is inlined.

(i.e. if you compile with -gnatn or -gnatN)

So I don't think this is so sad! My experience, as I mentioned before
is that people are always worrying about individual optimizations, but
these individual worries often correspond to optimizations that end
up being disappointing. This particular one is likely to be disappointing
because most people will use plain float as the type anyway.

I do agree that it is surprising how much extra time these comparisons
add (that of course is HIGHLY target dependent, so the other thing to
think about in getting enthusiastic about this optimization is to
find out how much it will help on various targets).

Note that anyone really worried about this problem can trivially call
the C log function directly anyway (not unreasonable, since it is a way
of clearly documenting that you don't need the Ada semantics)

Incidentally, the reason that optimizations like this are not so easy
is that gcc does not know about subranges, since C doe not know enough
about subranges. So gcc does not know about optimziat9ions. The optimization
under discussion here is of course one that has no conceivable analog in
C or C++ (I guess the "sadly enough GNAT is not such a good compiler" gets
translated into "sadly C and C++ are not such good languages" :-)

It's always hard to get very worked up over optimizations for numerical
code that could not be done in Fortran or C compilers. 

The first item of business is to get the Ada code to be fully comparable
to Fortran code, which is a tall order already! Then we can worry about
refinements like this which make carefully written Ada code faster
than Fortran!

Note in particular that right now, the most significant optimization issue
for GNAT numerical code has to do with handling of unconstrained arrays,
which, on certain targets, is still non-ooptimal.

Re: CRC in Ada?

[Mats Weber]

> I do agree that it is surprising how much extra time these comparisons
> add (that of course is HIGHLY target dependent, so the other thing to
> think about in getting enthusiastic about this optimization is to
> find out how much it will help on various targets).

I think that if the C library functions are good enough for C and
FORTRAN people, they should be good enough for Ada people also, without
adding these comparisons. Who wants to write algorithms that depend on
the sine function with cycle => 90.0 (which is a model number) returning
exactly 1.0, and other such particular cases ? Floating point is
approximate by nature.

This is another instance (the other being simple text IO, see other
threads going on) where Ada is by nature less effective than C, and the
sad thing is that it is not in the language itself but in standard
libraries that are over-featurized: who needs column and line numbers,
and a log function that is guaranteed to return exactly 0.0 when called
with exactly 1.0. I think such special needs are better addressed by
explicit coding: use an explicit line counter for that seldom occasion
where you need line numbers, or put the test for = 1.0 before you call
Log when you really need it to be a special case.

It would be nice if there was a version of the numerics packages with
direct calls to the library and comparisons only for the cases where an
exception must be raised (such as Log of a negative value).

One way to achieve this would be to have two versions of the elementary
functions:

Ada.Numerics.Generic_Elementary_Functions and
Ada.Numerics.Pedantic.Generic_Elementary_Functions :-)

or an installation option for the compiler.

Re: CRC in Ada?

[Robert Dewar]

Mats says

<<This is another instance (the other being simple text IO, see other
threads going on) where Ada is by nature less effective than C, and the
sad thing is that it is not in the language itself but in standard
libraries that are over-featurized: who needs column and line numbers,
and a log function that is guaranteed to return exactly 0.0 when called
with exactly 1.0. I think such special needs are better addressed by
explicit coding: use an explicit line counter for that seldom occasion
where you need line numbers, or put the test for = 1.0 before you call
Log when you really need it to be a special case.

Robert replies:

It would be nice if there was a version of the numerics packages with
direct calls to the library and comparisons only for the cases where an
exception must be raised (such as Log of a negative value).>>

Actually this is catered for in the Ada 95 RM already. Accuracy requirements
must only be met if the numerics annex is supported, and it is perfectly
reasonable to have two versoins of the libraries, one for strict accuracy
and one where accuracy is not required.

It's something we might do for GNAT at some time. Right now, our customers
have much different concerns about performance, so worrying about elementary
function performance is not high on our lists (when it comes to optimizations
we are very much influenced by customer requirements [of the real kind, not
of the subjunctive "well maybe you would have more customers if xxx" kind :-)]

I would NOT be in favor of having a version that did not raise proper
exceptions as required in the RM, this is asking for portability problems.

Ada is unusual in specifying the accuracy semantics of floating-point in
general. This does cause some extra overhead which may be annoying to
those who want fast answers and don't care if they are accurate, so you
may lose some users there, but on the other hand, for those who DO want
to write reliable portable numeric code, Ada offers great advantages.

You can partly have your cake and eat it if the compioler supports the
strict and non-strict modes separately, but not completely!

As for the discussion of Text_IO, it is hard for me to believe that people
use Text_IO for anything other than very casual I/O. For example, it would
not have occurred to us to use Text_IO in the implementation of GNAT
itself (and we would not be using getchar if it was written in C). I really
have not seen the performance of Text_IO be a significant issue in real
large projects.

As I have said previously, I see no reason for not borrowing things from C
if it makes sense. I know that there are two possible reactions to this

  a) UGGGH! borrowing from C, what a horrible idea, GASP, SPLUTTER!

  b) well if you have to import getchar, you might as well write your
        whole million line application in C

I am afraid I have zero sympathy for either reaction. Neither makes any
sense at all. The first is borne of some over-fanatic Ada orientation,
the second is just a thinly disguised translation of an excuse!

Re: CRC in Ada?

[Dr. John B. Matthews]

In article <33206340.2616@bix.com>, Tom Moran <tmoran@bix.com> writes:
> The original message in this thread did not say "reading a file a
> character at a time is slow", but rather that doing it in Ada was an
> order of magnitude slower than doing it in C, on the same OS and
> hardware.  Since there is no other way strictly in Ada to read a file
> which is too large for memory and whose size is a prime number, this is
> unfortunate.

This can't be right. For example, Streams.Stream_IO.Read lets me
read into a buffer of arbitrary size, and politely tells me if
there's any stray elements in the last chunk.

> And saying Ada 95 can do it by calling a C function, is
> less than a strong endorsement of Ada.

For efficiency, I frequently call OS routines. I rarely know what
language they're written in, although I typically access them
through a language-specific interface. For example, under MacOS, I
use Pascal interfaces and C calling conventions. The ease with which
this can be done seems like a strong endorsement of Ada.

John
----------------------------------------------------------------
John B. Matthews, M.D.
jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
"Whom the gods would destroy, they first invite to program in C"

Re: CRC in Ada?

[Robert Dewar]

Tom Moran says

<<The original message in this thread did not say "reading a file a
character at a time is slow", but rather that doing it in Ada was an
order of magnitude slower than doing it in C, on the same OS and
hardware.  Since there is no other way strictly in Ada to read a file
which is too large for memory and whose size is a prime number, this is
unfortunate.  And saying Ada 95 can do it by calling a C function, is
less than a strong endorsement of Ada.>>

This makes no sense at all. My best guess is that the business about
prime numbers is talking about trying to misuse direct_io to read the
file. 

The proper way to read this file in Ada 95 is to use Stream_IO into
a stream element buffer. The imagined "prime number" restriction
does not exist, and in practice this should be highly efficient.

I am afraid this is just misinformation that comes from misunderstanding.

Re: CRC in Ada?

[Tom Moran]

Robert Dewar says
> This makes no sense at all. My best guess is that the business about
> prime numbers is talking about trying to misuse direct_io to read the
> file. 
> 
> The proper way to read this file in Ada 95 is to use Stream_IO into
> a stream element buffer. The imagined "prime number" restriction
> does not exist, and in practice this should be highly efficient.
> 
> I am afraid this is just misinformation that comes from misunderstanding.
> 
  Yes, you did misunderstand.  The original post implied that the
comparison had taken place several years ago, which implies it was done
in Ada 83, which did not implement Stream_IO.  The only "strictly in
Ada" way to read a file then was via Text, Sequential, or Direct_IO. 
Both Sequential and Direct_IO require fixed size records. (Not strictly
true, but essentially true in practice.  E.g., ActivAda, GNAT, and Janus
will all accept a "(string)" as the parameter to Sequential_IO, but all
three die on trying to actually read a text file in chunks that way.) So
the fixed buffer size, if one did *not* use Text_IO, would have to be a
divisor of the total file size.  If the file size is a prime number,
it's divisors are itself and one.  One takes us back to the original
byte-at-a-time that was 10x slower in Ada than C.  If the whole file is
small enough to fit in memory, then we could use a single fixed size
record holding the entire file.  If this doesn't fit in memory then that
option is not available, and byte-at-a-time is the only way, strictly in
Ada, to do the job.  Yes, it can be done by calling the OS or a C
function, and I'm sure everyone has done this.  But it doesn't make Ada
look particularly good to say "Oh yes, you can do it in Ada; just don't
use the Ada IO packages".

Re: CRC in Ada?

[Robert Dewar]

Tom Moran said

<<  Yes, you did misunderstand.  The original post implied that the
comparison had taken place several years ago, which implies it was done
in Ada 83, which did not implement Stream_IO.  The only "strictly in
Ada" way to read a file then was via Text, Sequential, or Direct_IO.
Both Sequential and Direct_IO require fixed size records. (Not strictly
true, but essentially true in practice.  E.g., ActivAda, GNAT, and Janus
will all accept a "(string)" as the parameter to Sequential_IO, but all
three die on trying to actually read a text file in chunks that way.) So
the fixed buffer size, if one did *not* use Text_IO, would have to be a
divisor of the total file size.  If the file size is a prime number,>>

Actually this is wrong, you cannot even assume that Direct_IO will work
even if the file size is comfortably divisible by a convenient record
size. There is nothing to suggest that the mapping of Direct_IO files
is direct at the byte level, and for example, it would be perfectly
reasonable to have a control byte that showed whether a record was
present, or even a tag to verify the type of the data from run to run.

But in any case, from a language design point of view, this is of
archeological interest only, since one would not consider using 
Direct_IO for this purpose in Ada 95 anyway. If you are trying to
solve this problem with an old Ada 83 compiler, certainly the best
thing is to interface to C.

Unlike Tom (and some others), it never worries me to interface to C where
that is appropriate (or to interface to any other language). The idea that
everything must be done in Ada, and it is a terrible thing to use any
other language seems peculiar to me, and is something that is better left
on the dust heap of Ada relics. I realize that there are Ada fanatics who
feel very differently (though from his posts I would not have thought of
Tom as one), but to me Ada is a tool to be used in the most effective
way possible, and if the most effective way in some particular instance
is to interface to C, that's no problem -- why else have we put such
effort into designing this interface to C portably and effectively (it
certainly *is* more of a problem if you are in C or C++ and have to
interface portably to, e.g. COBOL or Fortran, since it cannot be done
in a portable manner).

Re: CRC in Ada?

[Jim Balter]

Larry Kilgallen wrote:

> Why should finding a record with particular contents in the middle of
> a file take a long time?  There are books about how to write indexed
> file systems, but some operating systems skipped that part of what I
> am accustomed to relying upon.  I don't include that to start a
> feature war, but to introduce the next question:  How hard is it to
> get-character-from-file when the file has all that baggage used to
> find records with with particular contents ? DEC compilers run
> more slowly when fed such a file, because it is beyond the ability
> programmed into their map-it-into-memory trick.

How does one write a series of 3 megabyte text lines to a
record-oriented filesystem that was only designed with 16-bit record
lengths?

Putting record indexing into the filesystem is putting it at the wrong
level of abstraction.  Commercial databases are written on UNIX
systems by doing direct I/O to disk devices or partitions.  The OS
vendor cannot write an indexed system general enough to provide the
extremes of performance needed by such databases, which comes back to
your own performance point, but from the right direction.  Buffered
stream I/O is a simple and common function that any system can provide. 
Programs that have more demanding requirements
can provide their own indexing mechanisms or utilize libraries built
on top of primitive streams.  This really is straightforward modern
systems design.

> What you (or I) see as limitations in a particular selection of
> compiler/os/library may be exactly what someone else needs to do
> their job.

The question is, which is the primitive on top of which the other
can be built?

> > Remember this [sub]thread started with the claim that VMS folks had to
> > go to a lot of trouble to support those "evil" C programmers who wanted
> > to do char-by-char input.  My response is: Good, somebody forced them to
> > do what they should do -- namely, implement char-by-char input
> > efficiently.
> 
> While I understand that is your view on what they should do, not all
> will share it. The last time I needed to do character-at-a-time IO was
> to emulate an editor which required a termination character on input
> _unless_ the first character was one particular alphabetic character
> (which had no special meaning in other than the first position).

That you haven't had much need for efficient char-by-char input cannot
possibly be an argument that it shouldn't be provided.

> I
> have been faced with a different set of projects than you, but I have
> my own list of things that "any environment ought to do properly" such
> as file versioning :-).

File versioning can be built on top of an unstructured name system
such as unix's, and programs such as emacs do so.  OTOH, VMS and
DOS/Windows [...]xxxxx.yyy;nnn type stuff is a straightjacket.
 
> >>I have run into programmers making this mistake over and over again.
> >>In recent years their immediate response has been "Gee, it runs fast
> >>on Unix", but in prior years their response was "Gee, it runs fast
> >>on MVS".  Obviously it is only the recent history where the C language
> >>is involved, but the current generation seems much more surprised than
> >>their MVS-centric predecessors.
> >
> > Seems pretty reasonable to me: if Unix or MVS can do it fast, why can't
> > whatever-OS-we're talking about do it fast?  If not, it seems like the
> > fault of the OS, or the standard libraries implementation.
> 
> Sorry if I was unclear, but Unix and MVS could not do the _same_thing_
> fast.  The only commonality was that people coming from Unix and
> people coming from MVS both assumed that the new operating system
> would have the same performance characteristics as the one they are
> coming from.  Now obviously it is impossible for the target operating
> system to fully mimic the behaviour of both Unix and MVS at the same
> time to make both camps happy.

Certainly not if the OS "primitives" are not sufficiently primitive.

--
<J Q B>

Re: CRC in Ada?

[Jim Balter]

Larry Kilgallen wrote:

> If a programmer _assumes_ that such a construct will be efficient,
> when in fact it is _not_ efficient within a particular environment,
> it is a mistake from a performance perspective.

This same argument was used to justify assembly language programming
for decades.

A programmer should assume that her tools are not broken, and that
she is not dealing with an anomalous case with unusually poor
performance, until and unless project requirements and empirical
measurements indicate otherwise.

> I have run into programmers making this mistake over and over again.
> In recent years their immediate response has been "Gee, it runs fast
> on Unix", but in prior years their response was "Gee, it runs fast
> on MVS".  Obviously it is only the recent history where the C language
> is involved, but the current generation seems much more surprised than
> their MVS-centric predecessors.
> 
> An analogy would be developers who find their MS-DOS game cannot
> write directly to the screen under Windows NT.  That is a bit
> rougher, as one has to start from scratch explaining the difference
> between an operating system and a run-time library :-)

You are arguing against yourself.  Putting screen I/O optimizations
into the lower system or library layers instead of embedding them into
every application is precisely the path for avoiding this sort of
problem.  It is your "optimized" application that will fail miserably in
many environments, whereas my application that assumes an efficient
underlying buffering mechanism (or an optimizing compiler instead
of "clever" assembly code, or an abstract BLT operation that may well
be implemented in hardware instead of hand coding, or threads that
may be run in parallel processors instead of hand coded scheduling)
will run well in any environment that provides one, which means in
today's practice all of them.  And an API is an API is an API; the line
between the OS and the run-time library has been quite blurred with
developments such as microkernels and dynamically linked libraries.
Welcome to the modern age.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Fergus asks

<<>In my experience it is generally C programmers who make this mistake.

Why is it a mistake?>>

Tell you what Fergus, do a whole lot of timing tests comparing reading
character by character and reading large blocks, and come back and tell
us if it did not tell you the answer to that questin :-)

Re: CRC in Ada?

[Robert A Duff]

In article <1997Mar5.131846.1@eisner>,
Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
>While theoretical computing and Alan Turing may be centered on
>the equivalence and correctness of programs, in the real world
>performance is also a consideration.  Just as those using intense
>computation will be concerned about the efficiency of their
>algorithms, those accessing large databases will take care
>regarding order-of-access so as not to go skipping over the
>whole thing when some locality-of-reference would yield better
>performance.  Those reading sequentially from disk should
>likewise concern themselves with performance, and 512 calls
>to even the lightest-weight library is too much if a single
>call would do.  For the stated problem (CRC) reading large
>blocks is a clear win.

Agreed, but that's what inlining is for.  All I was saying is that there
should be a standard package that does efficient I/O, with buffering,
and of course you want to inline a call that just bumps a pointer and
grabs a character out of a buffer (except in the rare case where the
buffer is exhausted).  Unfortunately, Text_IO has an awful lot of
nearly-useless cruft in it.  But why can't Stream_IO fit the bill here?

>> I'm not sure why reading a file character-by-character is "C-like".
>> It seems like the natural way to write lots of programs, in any
>> language.  The underlying language and OS should ensure that it can be
>> done efficiently (by making the "give-me-a-char" routine read from a
>> buffer whenever appropriate).

And I should have added, "and by making that thing inline-able".
Actually, I suppose the OS has little to do with it -- obviously you
can't afford to do a system call (i.e. enter supervisor mode) on every
character.

>In my experience it is generally C programmers who make this mistake.
>Perhaps it because many of them come from a Unix background where there
>is no strong sense of a "record".  On the other hand, it may just be
>that there are so many C programmers that statistically speaking most
>of the mistakes made will be made by a C programmer.

I still don't think it's a "mistake" to expect buffering to be done by
standard packages, rather than by every user's program.  I mean, you
have to tell the thing that you're planning to read sequentially through
the file, but beyond that, the application program shouldn't have to
worry about it.

(When I programmed on VAX/VMS, I was appalled at the complexity of the
Record Management Services.  I still don't know why all that complexity
is necessary, as compared to the Unix notion that a file is a sequence
of bytes.  But I could be wrong -- I write compilers, mostly, which
don't need "fancy" I/O facilities.)

Note that Ada compilers don't typically use Text_IO to read the source
code!  ;-)

- Bob

Re: CRC in Ada?

[Robert Dewar]

Larry Kilgallen <kilgallen@eisner.decus.org> wrote:

<<While theoretical computing and Alan Turing may be centered on
the equivalence and correctness of programs, in the real world
performance is also a consideration.>>

  This shows a big misunderstanding of the theory of correctness. If
  performance is part of the requirement, it must be part of the
  specification, and thus part of the criterion for correctness. This
  is not to say it is easy to prove correctness for such specifications,
  it is indeed hard. But there is a lot of work of value here, which
  I recommend Larry investigate before dismissing it in such a 
  cavalier manner :-)

Re: CRC in Ada?

[Robert Dewar]

Bob Duff said

<<(When I programmed on VAX/VMS, I was appalled at the complexity of the
Record Management Services.  I still don't know why all that complexity
is necessary, as compared to the Unix notion that a file is a sequence
of bytes.  But I could be wrong -- I write compilers, mostly, which
don't need "fancy" I/O facilities.)>>

Well this is an old discussion, the trouble in Unix is that there are
no standardized file formats for simple things like indexed sequential
files, and indeed, until recently, Unices have paid little attention
to I/O efficiency. If you spend 90% of your time running Syncsort on
mainframes, it is quite important to be able to describe the layout
of your file data precisely, including its positioning on external
devices (just to take one example of appalling complexity). 

Yes, compiler writers don't need much in the way of I/O support, that's
true, but I don't think you can extend this experience very far. In
practice VMS is very successful in a segment of the market where Unix
has been quite unsuccessful, and the RMS facilities are one important
component in this success.

Re: CRC in Ada?

[Robert Dewar]

Bob Duff said

<<Agreed, but that's what inlining is for.  All I was saying is that there
should be a standard package that does efficient I/O, with buffering,
and of course you want to inline a call that just bumps a pointer and
grabs a character out of a buffer (except in the rare case where the
buffer is exhausted).  Unfortunately, Text_IO has an awful lot of
nearly-useless cruft in it.  But why can't Stream_IO fit the bill here?>>

  It can, but be careful. If you write String'Input, then not only do you
  get the overhead of going character by character, unless a lot of
  special optimization is at work, but you also get the general inefficiency
  of dealing with unconstrained variable length objects, which usually
  involves at least one extra copy. The character by character reads come
  from the fact that this is the semantics of String'Input. yes, it could
  indeed be optimized (in the normal case, where a user level attribute is
  not supplied for type character), but you cannot count on that.

  More likely to be efficient is using Read and Write directly on
  buffers of stream elements.

  Indeed it is perfectly easy, and probably safest to do your own
  buffering in many cases (the same advice applies to C, it may be
  efficient to do indidvidual getchar's, but it may also be a disaster
  from an efficiency point of view.

Re: CRC in Ada?

[Dr. John B. Matthews]

In article <dewar.857652688@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>   More likely to be efficient is using Read and Write directly on
>   buffers of stream elements.

Yes. In the code below I tried to compare Sequential_IO to Stream_IO
for the two extremes of one-at-a-time vs all-at-once (imagining
a buffered approach to fall between). In the one-at-a-time
procedures, I assumed knowledge of the file's length instead of
calling the relevant End_Of_File predicate; in the all-at-once
procedures, I looped through the resulting buffer.

For Sequential_IO, all-at-once is clearly faster than
one-at-a-time. Stream_IO is more interesting: In Stream_All1,
String'Read is actually slower than looping with Character'Read, as
the former calls Character'Read in a loop, checking for EOF as it
goes. The fastest approach seems to be to read the stream elements
directly, as in Stream_All2.

John
----------------------------------------------------------------
John B. Matthews, M.D.
jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
"Whom the gods would destroy, they first invite to program in C"
------------------------------------------------------------------
--|
--| iotest: time IO
--|
--| Author: John B. Matthews, Wright State University
--| Last Modified: March 8, 1997
--|
------------------------------------------------------------------
-- results of 6 runs on a 451239 byte file:
-- ave.     std.dev.
-- 1.00278  0.03391  sequential, one character at a time.
-- 0.72499  0.02679  sequential, entire file.
-- 1.26389  0.01146  stream, one character at a time.
-- 1.41389  0.09738  stream, entire file 1.
-- 0.65113  0.08572  stream, entire file 2.
------------------------------------------------------------------
-- build: gnatmake iotest -largs -Xlstack=500000 (or so)

with Ada.Command_Line;
with Ada.Sequential_IO;
with Ada.Streams.Stream_IO;
with Ada.Text_IO;
with Calendar; use type Calendar.Time;

procedure IOTest is

   package CLI renames Ada.Command_Line;
   package Text_IO renames Ada.Text_IO;
   package Fixed_IO is new Ada.Text_IO.Fixed_IO (Duration);

   Length : Natural;
   Start, Stop : Calendar.Time;
   
   -- Determine the size (in bytes) of the file, Name.
   function File_Size (Name : in String) return Natural is
      package SIO renames Ada.Streams.Stream_IO;
      F : SIO.File_Type;
      Size : Natural;
   begin
      SIO.Open (F, SIO.In_File, Name);
      Size := Integer (SIO.Size(F));
      SIO.Close (F);
      return Size;
   end File_Size;

   procedure Sequential_One (Name : String; Length : Natural) is
      package SIO is new Ada.Sequential_IO (Character);
      F : SIO.File_Type;
      C : Character;
   begin
      SIO.Open (F, SIO.In_File, Name);
      for i in 1 .. Length loop
         SIO.Read (F, C);
      end loop;
      SIO.Close (F);
   end Sequential_One;

   procedure Sequential_All (Name : String; Length : Natural) is
      subtype Data is String (1 .. Length);
      package SIO is new Ada.Sequential_IO (Data);
      F : SIO.File_Type;
      S : Data;
      C : Character;
   begin
      SIO.Open (F, SIO.In_File, Name);
      SIO.Read (F, S);
      for i in 1 .. Length loop
          C := S (i);
      end loop;
      SIO.Close (F);
   end Sequential_All;

   procedure Stream_One (Name : String; Length : Natural) is
      package SIO renames Ada.Streams.Stream_IO;
      F : SIO.File_Type;
      S : SIO.Stream_Access;
      C : Character;
   begin
      SIO.Open (F, SIO.In_File, Name);
      S := SIO.Stream (F);
      for i in 1 .. Length loop
         Character'Read (S, C);
      end loop;
      SIO.Close (F);
   end Stream_One;

   procedure Stream_All1 (Name : String; Length : Natural) is
      subtype Data is String (1 .. Length);
      package SIO renames Ada.Streams.Stream_IO;
      F : SIO.File_Type;
      S : Data;
      C : Character;
   begin
      SIO.Open (F, SIO.In_File, Name);
      Data'Read (SIO.Stream (F), S);
      for i in 1 .. Length loop
          C := S (i);
      end loop;
      SIO.Close (F);
   end Stream_All1;

   procedure Stream_All2 (Name : String; Length : Natural) is
      subtype Data is String (1 .. Length);
      package SIO renames Ada.Streams.Stream_IO;
      F : SIO.File_Type;
      S : Ada.Streams.Stream_Element_Array
             (1 .. Ada.Streams.Stream_Element_Offset(Length));
      L : Ada.Streams.Stream_Element_Offset;
      C : Ada.Streams.Stream_Element;
   begin
      SIO.Open (F, SIO.In_File, Name);
      SIO.Read (F, S, L);
      for i in 1 .. L loop
          C := S (i);
      end loop;
      SIO.Close (F);
   end Stream_All2;

begin

   if CLI.Argument_Count = 1 then
   
      Length := File_Size (CLI.Argument (1));

      Start := Calendar.Clock;
      Sequential_One (CLI.Argument (1), Length);
      Stop := Calendar.Clock;
      Fixed_IO.Put (Stop - Start, 0, 5);
      Text_IO.Put_Line (" sequential, one character at a time.");

      Start := Calendar.Clock;
      Sequential_All (CLI.Argument (1), Length);
      Stop := Calendar.Clock;
      Fixed_IO.Put (Stop - Start, 0, 5);
      Text_IO.Put_Line (" sequential, entire file." );

      Start := Calendar.Clock;
      Stream_One (CLI.Argument (1), Length);
      Stop := Calendar.Clock;
      Fixed_IO.Put (Stop - Start, 0, 5);
      Text_IO.Put_Line (" stream, one character at a time.");

      Start := Calendar.Clock;
      Stream_All1 (CLI.Argument (1), Length);
      Stop := Calendar.Clock;
      Fixed_IO.Put (Stop - Start, 0, 5);
      Text_IO.Put_Line (" stream, entire file 1.");

      Start := Calendar.Clock;
      Stream_All2 (CLI.Argument (1), Length);
      Stop := Calendar.Clock;
      Fixed_IO.Put (Stop - Start, 0, 5);
      Text_IO.Put_Line (" stream, entire file 2.");

   else
      Text_IO.Put_Line ("Usage: iotest <filename>");
   end if;

end IOTest;

Re: CRC in Ada?

[Larry Kilgallen]

In article <E6Lpv3.AoL@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:
> In article <1997Mar5.131846.1@eisner>,
> Larry Kilgallen <kilgallen@eisner.decus.org> wrote:

>>In my experience it is generally C programmers who make this mistake.
>>Perhaps it because many of them come from a Unix background where there
>>is no strong sense of a "record".  On the other hand, it may just be
>>that there are so many C programmers that statistically speaking most
>>of the mistakes made will be made by a C programmer.
> 
> I still don't think it's a "mistake" to expect buffering to be done by
> standard packages, rather than by every user's program.  I mean, you
> have to tell the thing that you're planning to read sequentially through
> the file, but beyond that, the application program shouldn't have to
> worry about it.

If one were to espouse the Unix paridigm of "stream of bytes",
it seems to me the logical representation of that is an array
(at least for files less than 1 GB if you do not have 64-bit
addressing). For large (compared to resources made available
by the operating system) file IO mechanisms such as provided
with Ada are needed.

> (When I programmed on VAX/VMS, I was appalled at the complexity of the
> Record Management Services.  I still don't know why all that complexity
> is necessary, as compared to the Unix notion that a file is a sequence
> of bytes.  But I could be wrong -- I write compilers, mostly, which
> don't need "fancy" I/O facilities.)

But there are more people writing financial software (in general)
than writing compilers.  I write some programs were that record
stuff is crucial and some where it is skipped.

> Note that Ada compilers don't typically use Text_IO to read the source
> code!  ;-)

And typical VMS compilers (meaning those from DEC) don't use RMS to
read those characters either.  They map the files into their virtual
address space and compile directly out of memory.  (Of course they
have alternate strategies for rare special cases such as compiling
from a magnetic tape or compiling from the keyboard).  This is
perilously close to the "stream of bytes is an array" approach.

But compiler writers do this with a full understanding of the
performance characteristics of their environment.  It is impossible
to write a program which performs well on all operating systems without
taking into account the varying characteristics of the operating systems.
The variable block-size disks used on MVS provide a swift example
where generality does not cut the mustard.

Larry Kilgallen

Re: CRC in Ada?

[Tarjei Jensen]

>In article <33206340.2616@bix.com> Tom Moran <tmoran@bix.com> writes:
>
>   The original message in this thread did not say "reading a file a
>   character at a time is slow", but rather that doing it in Ada was an
>   order of magnitude slower than doing it in C, on the same OS and
>   hardware.  Since there is no other way strictly in Ada to read a file
>   which is too large for memory and whose size is a prime number, this is
>   unfortunate.  And saying Ada 95 can do it by calling a C function, is
>   less than a strong endorsement of Ada.
>

The usual explanation is that the C standard library buffers I/O while many
other languages does not have that requirement. If Ada required that the
stream I/O libraries had to support buffering then Ada would probably be as
fast as C for single character I/O.

The slowness of Ada is probably because each read triggers an system call which
reads a single character.

Good example: use Turbo Pascal under MSDOS and experiment with the buffer size
for the same program. Differences are dramatic.


Greetings,
-- 
// Tarjei T. Jensen 
//    tarjeij@ulrik.uio.no || fax +47 51664292  || voice +47 51 85 87 39
//   Support you local rescue centre: GET LOST!
// Working, but not speaking for the Norwegian Hydrographic Service.

Re: CRC in Ada?

[Robert Dewar]

Tarjei said

<<The usual explanation is that the C standard library buffers I/O while many
other languages does not have that requirement. If Ada required that the
stream I/O libraries had to support buffering then Ada would probably be as
fast as C for single character I/O.

The slowness of Ada is probably because each read triggers an system call which
reads a single character.>>

"If Ada required that the stream I/O libraries had to support buffering"

That is not the issue at all. The issue is that if you use String'Read
instead of reading into a buffer, the semantics pretty much imply character
by character reads, since such stream attribtues are by default executed
element wise. Yes, a compiler could optimize this, but is unlikely to.
The proper way to do fast stream_io is to read and write buffers of
stream elemkents.

Re: CRC in Ada?

[Graham Hughes]

-----BEGIN PGP SIGNED MESSAGE-----

dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>That is not the issue at all. The issue is that if you use String'Read
>instead of reading into a buffer, the semantics pretty much imply character
>by character reads, since such stream attribtues are by default executed
>element wise. Yes, a compiler could optimize this, but is unlikely to.
>The proper way to do fast stream_io is to read and write buffers of
>stream elemkents.

Perhaps.  But the beauty of the C and other approaches is that I don't
have to write the buffer explicitly, and thus have to debug it.  I *can*
read character by character if I want to, and often I do; socket
programming is a perfect example.  But the rest of the time, I don't
want to worry about it, and don't have to.

Perhaps you feel that Unbounded_String is an abomination, because `the
proper way' to do arbitrary length strings is to do it yourself?
- -- 
Graham Hughes    http://A-abe.resnet.ucsb.edu/~graham/ -- MIME & PGP mail OK.
   PGP Key fingerprint = E9 B7 5F A0 F8 88 9E 1E  7C 62 D9 88 E1 03 29 5B

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMyRu6SqNPSINiVE5AQH1igP/Twwim+fN+z59CCTsa+tQXyff/mvyLkEc
d97WaqyWJqpRpgQjTL86VfJnrkKGMitwajheMKqCDbEBFoDcCS6QnA5H1bUNgjPY
tcWIxxNQczCJf85ZLPpq96zdhSUQ8f9oJJPvo2RuuigIiTLp+i0wkSgtLAl/JEsK
kKUa5eEWAfw=
=52Ex
-----END PGP SIGNATURE-----

Re: CRC in Ada?

[Robert Dewar]

Graham says

<<Perhaps.  But the beauty of the C and other approaches is that I don't
have to write the buffer explicitly, and thus have to debug it.  I *can*
read character by character if I want to, and often I do; socket
programming is a perfect example.  But the rest of the time, I don't
want to worry about it, and don't have to.>>

Sure you can read character by character, but you are paying a considerable
price, even in C, for doing so!

Re: CRC in Ada?

[Graham Hughes]

-----BEGIN PGP SIGNED MESSAGE-----

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Sure you can read character by character, but you are paying a considerable
>price, even in C, for doing so!

Actually:  virtually none.

Now, any stdio library can do this any way it damn well pleases, but the
*usual* way to implement the buffers is this:

If you request a character to be read, it feeds you the next character
in the buffer.  If there isn't a next character in the buffer, it reads
in BUFSIZ elements and tries again.  If it can't read any elements in,
then it returns EOF.

This is simplified somewhat, as ungetc() has to work across buffers, and
standard input is usually line buffered if it comes in from a tty (which
is handled largely by reading in as much as possible, getting an EOF,
and trying again later; see glibc).

Now, since BUFSIZ is 1024 bytes on my computer, this is in fact quite
efficient.  The actual BUFSIZ varies from compiler to compiler and
platform to platform, much as stdio itself does.

I don't see why this is so hard to do in Ada.  It's the most used
library in C (even hello world programs call printf()).

Oh, and as has been said earlier; with setvbuf, I can make the stream
buffer any way I want.
- -- 
Graham Hughes    http://A-abe.resnet.ucsb.edu/~graham/ -- MIME & PGP mail OK.
   PGP Key fingerprint = E9 B7 5F A0 F8 88 9E 1E  7C 62 D9 88 E1 03 29 5B


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMyXTnCqNPSINiVE5AQEIHgP8C/daYdavY71nD4+/OiMVyhff2Cspbd0Q
ip7yB+q7ATJEs9WyJU4id5oYxxDtEq3rD7pWQwkDYIuyIX22/cB4EgMkw40ubFFF
NRClDGq8MhMsmm4q1KHBr0goR8t73wta/0H/zJw1VulRG+OqgfQ7zipL2/9r8jrY
K+JV6wLBCQY=
=PZp9
-----END PGP SIGNATURE-----

Re: CRC in Ada?

[Robert Dewar]

Graham says

<<>Sure you can read character by character, but you are paying a considerable
>price, even in C, for doing so!

Actually:  virtually none.>>

Well words like considerable and virtually are not very quantitative. 
There definitely is a price in going character by character (even Balter
thinks this extra price might be dominant in something like "cat").

Every system where I have measured the effect (e.g. the difference in 
a compiler that reads large blocks, or does character by character reads,
I have seen enough difference to be worth the effort of doing IO in blocks.
This is especially true if you can put a sentinel at the end of the block
that will naturally be detected by your processing, e.g. an end-of-file
mark of some kind in the compiler case, so that you can then process
character by character with out a test for buffer exhaustion (once you
commit to using getchar, you do of course have a test on each character
read for buffer exhuastion, because at that level it is not under
your control). 

GNAT actually works exactly this way, it reads the entire source with
a single read, and then puts an end of file sentinel at the end of the
source. This provides noticable speed up over character by character
processing.

Re: CRC in Ada?

[Robert Dewar]

iTarjei said

<<The usual explanation is that the C standard library buffers I/O while many
other languages does not have that requirement. If Ada required that the
stream I/O libraries had to support buffering then Ada would probably be as
fast as C for single character I/O.>>

One more comment here: in GNAT, the I/O sits on top of the C standard
library stream I/O, you get whatever that layer gives you, so from the
point of view of system level access, the situation in GNAT is identical
to that in C. See GNAT reference manual for further details.

Re: CRC in Ada?

[David Brown]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> The proper way to read this file in Ada 95 is to use Stream_IO into
> a stream element buffer. The imagined "prime number" restriction
> does not exist, and in practice this should be highly efficient.

Ok, so I am reading the file data into a stream element buffer
(Stream_Element_Array).  My file, however, really consists of some
small objects (16 bit signed integers).  What is the "proper" way to
get these integers out of this buffer?  I want there to be as little
copying of these numbers as possible.  Here are some solutions I've
come up with:

1.  Have code to extract and insert my objects out of a stream element
    array.  These routines could be inlined and the access would end
    up fast.  However, they would be cumbersome to call because the
    item wouldn't quite be an array.

2.  Use for Foo'Address clauses or address to access conversions to
    alias an array of my data on top of the stream element buffer.
    Aside from the general feeling of grossness about this, I have
    heard mentioned on this group that this is not the proper way of
    aliasing two data items.  Is there a "proper" way of doing this?

3.  Use Ada.Storage_IO to convert the buffer into a buffer of my
    data.  This will cause a copy.

4.  Just do my I/O by calling my underlying operating system calls.
    This would probably be most efficient.  With the GNAT runtime, the
    stream IO read and write just call fread which on my OS doesn't do
    a copy if the buffer is large enough.  In other words, if I could
    somehow avoid the copy in Ada, the Stream IO code would be
    efficient enough.

Dave Brown
dbrown@vigra.com

Re: CRC in Ada?

[Robert Dewar]

Dave Brown says

<<Ok, so I am reading the file data into a stream element buffer
(Stream_Element_Array).  My file, however, really consists of some
small objects (16 bit signed integers).  What is the "proper" way to
get these integers out of this buffer?  I want there to be as little
copying of these numbers as possible.  Here are some solutions I've
come up with:>>

Well first, as you go on to mention, you may well find that it is
efficient enough to use the stream attributes directly in the first
place.

If not, I would still use Stream_Attributes as the mechanism, but
write your own to access the buffer efficiently.

Re: CRC in Ada?

[Mark & Zurima McKinney]

Use an address clause for and object of the compatible type with and the
address of the buffer.

Re: CRC in Ada?

[Robert I. Eachus]

In article <dewar.858095506@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

  > That's a pretty marginal optimization. Maybe Geert makes subtypes
  > Positive_Float, but of all the code we ever had submitted to us,
  > no one ever bothered to do this, they just used Float.

  > Still it can go on the list, it's way down there in priority though,
  > there are MANY more important optimizations ahead of it!

   Let me put an optimization way ahead of it on the list and see if
anyone is interested...

   The easiest way of dealing with the A.5.1(37-42) requirements in a
portable manner is the one currently taken by GNAT--explicit code.
However, most of these requirements will be met by any IEEE conforming
implementation.  So it should be possible to have two versions of the
elementary functions packages, one which assumes good underlying math
libraries, and one which does not.

   Note that the hard work here can be done completely separately from
other compiler maintenance and enhancement activities.  It involves
writing some test code and running it on a lot of different
platforms. (The way I envision this is a set of alternate bodies, and
a test program which validates the elisions.  Of course, the ultimate
would be a test program that generated a tailored version of the
bodies which matched the particular hardware.)

   
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.858096166@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Graham says

   <<Perhaps.  But the beauty of the C and other approaches is that I don't
   have to write the buffer explicitly, and thus have to debug it.  I *can*
   read character by character if I want to, and often I do; socket
   programming is a perfect example.  But the rest of the time, I don't
   want to worry about it, and don't have to.>>

   Sure you can read character by character, but you are paying a considerable
   price, even in C, for doing so!

If you actually want to do something with your char instead of just
reading it, it is usually negligible.

Re: CRC in Ada?

[Jon S Anthony]

In article <5g4k31$g54$1@A-abe.resnet.ucsb.edu> Graham Hughes <graham.hughes@resnet.ucsb.edu> writes:

> Now, any stdio library can do this any way it damn well pleases, but the
> *usual* way to implement the buffers is this:
> 
> If you request a character to be read, it feeds you the next character
> in the buffer.  If there isn't a next character in the buffer, it reads
> in BUFSIZ elements and tries again.  If it can't read any elements in,
> then it returns EOF.
...
> Now, since BUFSIZ is 1024 bytes on my computer, this is in fact quite
> efficient.  The actual BUFSIZ varies from compiler to compiler and
> platform to platform, much as stdio itself does.
> 
> I don't see why this is so hard to do in Ada.  It's the most used
> library in C (even hello world programs call printf()).

It's not.  It's easy.  But you might not get that from the way this
thread has progressed.  As Robert pointed out back at the start (and a
couple of times since), use Read and Write directly on buffers of
stream elements _instead_ of the attributes String'Read and
String'Write.  The latter require character by character processing
(per RM element by element processing of arrays in streams).

OK, so clearly the Read/Write for streams into buffers will be very
efficient and you can then chop this at your leisure.  But there are a
still a few issues in all this.

First, for GNAT String'Read/Write should boil down to a getc/putc or
some such C read/write, so any extra overhead here (beyond what you
have in C) should not be due to any buffering aspects whatsover.  They
will be due to call overhead on the C IO function.  The claim that
started this twist in the thread here, was that this overhead made the
IO "very slow".  I guess the problem is with "very".  3 times slower?
4 times?  What?  And are these examples of "very slow"?  Perhaps.
Regular ol' getchar, of course, can avoid this call overhead - though
I suppose it may not: thread safety issues anyone?

Second, while 13.13.2(9) sez that for composites (including arrays)
the associated Read and Write attributes call the Read/Write
attributes for each _component_, I don't see why this can't be one of
those cases where "as if semantics" apply.  For example, for one
dimensional arrays, just read the thing as if you called Read/Write
for each element.

Third, since you can specify stream oriented attributes ('Read 'Write)
for any type with an attribute definition clause, you can always just
change the "efficiency" behavior of String'Read/Write to be just like
getchar's by inlining a version which does what getchar does.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[Robert Dewar]

Jon says

<<Second, while 13.13.2(9) sez that for composites (including arrays)
the associated Read and Write attributes call the Read/Write
attributes for each _component_, I don't see why this can't be one of
those cases where "as if semantics" apply.  For example, for one
dimensional arrays, just read the thing as if you called Read/Write
for each element.>>

Sure, this is a possible optimization, but not such a simple one. For one
thing, we deliberately introduce another level of abstraction in GNAT,
namely the system.stream_attributes package in s-stratt.ads. This is provided
so that it is possible to substitute alternative semantics for stream
handling for primitive elements, and for example GLADE takes advantage
of this to substitute XDR (target independent) semantics.

Now it would be easy enough to at least provide an extra entry point for
string processing in system.stream_attributes for the special case of
string (and maybe wide_string), so that the front end could still do
the optimization, but this would not generalize to all arrays, and in
any case, the generalization to all arrays is not always possible,
it can be derailed by alignment considerations, or by packing, or
by the specification of component size.

Note that the additional layer here does not introduce extra call overhead
since it can be inlined, but it does make it virtually impossible using the
current interface, to specialize the case of stream attributes on strings.

As I say, the interface can easily be change. Handling stream_io more
efficiently on strings has been down on our list of possible optimziations
for a long time, but it's not particularly high priority -- so far it
has not been a significant performance issue for any of our customers!

Robert Dewar
Ada Core Technologies

P.S. I strongly encourage people to do profiling on their applications.
Nothing like finding out what *actually* takes the time, as opposed to
guessing at what might be critical optimizations!

Much the most convincing kind of input here is profiles from a real
application, not one construted to make the point, that show that
x% of time is spent in string stream attributes, where x is high enougj
to worry about.

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:

> Much the most convincing kind of input here is profiles from a real
> application, not one construted to make the point, that show that
> x% of time is spent in string stream attributes, where x is high                                                    ^^^^^^^^^^^^^^^
enougj
^^^^^^
> to worry about.
  ^^^^^^^^^^^^^^

Now there's something to agree on.
--
<J Q B>

Re: CRC in Ada?

[Jon S Anthony]

In article <dewar.858263011@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Now it would be easy enough to at least provide an extra entry point for
> string processing in system.stream_attributes for the special case of
> string (and maybe wide_string), so that the front end could still do
> the optimization, but this would not generalize to all arrays, and in
> any case, the generalization to all arrays is not always possible,
> it can be derailed by alignment considerations, or by packing, or
> by the specification of component size.

It is even worse than you suggest for arrays "in general".  They could
be composed of elements whose type is user defined and which have
their own specialized 'Read and 'Write.  There's no way to handle this
sort of thing in general except to just call the things element by
element.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[Dr. John B. Matthews]

Thanks to everyone who responded to my query about performing a
Cyclic Redundancy Check (CRC) in Ada.

David L Brown supplied an economical implementation using a 256 byte
lookup table, which I've incorporated in the code below.

Several correspondents expressed concern about efficient ways of
accessing a file to calculate it's CRC. Although systems vary and
there's no substitute for profiling actual code, much empirical
evidence suggests that it's often faster to process large blocks off
data rather than one element at a time. The familiar trade-off
between time and space dictates how big a block to process.

As suggested by Robert Dewar and others, Ada.Stream.Stream_IO.Read
provides a convenient, efficient way to read blocks of arbirary
size. In particular, the Read procedure reports the index of the
last buffer element read, thus allowing an arbitrary buffer size.

John
----------------------------------------------------------------
John B. Matthews, M.D.
jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
"Whom the gods would destroy, they first invite to program in C"

------------------------------------------------------------------
--|
--| CRC: Calculate 16 bit Cyclic Redunancy Check
--|
--| Author: John B. Matthews, Wright State University
--| Last Modified: March 15, 1997
--|
------------------------------------------------------------------
-- build: gnatmake crc

with Ada.Command_Line;
with Ada.Streams.Stream_IO; use type Ada.Streams.Stream_Element;
with Ada.Text_IO;

procedure CRC is

   package CLI renames Ada.Command_Line;
   package Text_IO renames Ada.Text_IO;
   package Stream_IO renames Ada.Streams.Stream_IO;

   -- assumes System.Storage_Unit is 8 bits/byte.
   subtype Byte is Ada.Streams.Stream_Element;
   subtype Byte_Array is Ada.Streams.Stream_Element_Array;
   subtype Byte_Index is Ada.Streams.Stream_Element_Offset;
   type Word is mod 2 ** 16; for Word'Size use 16;
   type Word_Array is array (Byte) of Word;

   Data  : Byte_Array (1 .. 8192); -- an 8K buffer
   File  : Stream_IO.File_Type;
   Last  : Byte_Index;
   Table : Word_Array;
   Check : Word := 0;

   --
   -- Generate the lookup table. Adapted from an
   -- implementation by David L Brown, comp.lang.ada
   --
   procedure Generate (P : in Word := 16#8408#) is
      V : Word;
   begin
      for B in Byte loop
         V := Word (B);
         for I in 1 .. 8 loop
            if (V and 1) = 0 then
               V := V / 2;
            else
               V := (V / 2) xor P;
            end if;
         end loop;
         Table (B) := V;
      end loop;
   end Generate;

   --
   -- Update the CRC value to account for Data.
   -- Implemented by David L Brown, comp.lang.ada
   --
   procedure Update (CRC : in out Word; Data : in Byte_Array) is
   begin
      for I in Data'Range loop
         CRC := (CRC / 16#100#) xor Table (Byte (CRC) xor Data (I));
      end loop;
   end Update;

begin

   if CLI.Argument_Count > 0 then
      Generate; -- the table
      for I in 1 .. CLI.Argument_Count loop
   
         Stream_IO.Open (File, Stream_IO.In_File, CLI.Argument(I));
         while not Stream_IO.End_Of_File (File) loop
            Stream_IO.Read (File, Data, Last);
            Update (Check, Data (Data'First .. Last));
         end loop;
         Stream_IO.Close (File);
   
         Text_IO.Put_Line (CLI.Argument(I) & Word'Image (Check));
      end loop;

   else
      Text_IO.Put_Line ("Usage: crc <filename>");
   end if;

end CRC;

Re: CRC in Ada?

[Robert Dewar]

Jon said

<<It is even worse than you suggest for arrays "in general".  They could
be composed of elements whose type is user defined and which have
their own specialized 'Read and 'Write.  There's no way to handle this
sort of thing in general except to just call the things element by
element.>.

Well of course, but the compiler knows perfectly well when this is the case,
and tthere is nothing bad about repeated calls to the user routine if that
is what the user as explicitly requested!

On the other hand, this does not stand in the way at all from optimizaing
certain cases where the user has NOT specialized things this way.

Of course, as always, the existence of the general case tends to mean that
the optimized case gets put aside (consider the influence on Fortran
compilers of the fact that format strings *may* be dynamic -- for a long
time the result was that Fortran runtimes treated all format strings as

dynamic.

Re: CRC in Ada?

[Jon S Anthony]

In article <dewar.858439200@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Jon said
> 
> <<It is even worse than you suggest for arrays "in general".  They could
> be composed of elements whose type is user defined and which have
> their own specialized 'Read and 'Write.  There's no way to handle this
> sort of thing in general except to just call the things element by
> element.>.
> 
> Well of course, but the compiler knows perfectly well when this is the case,

Well, of course I agree with this - it's the reason I suggested the
"as if" optimization in the first place.


> On the other hand, this does not stand in the way at all from optimizaing
> certain cases where the user has NOT specialized things this way.

Absolutely.  And that is why I suggested it.


> Of course, as always, the existence of the general case tends to mean that
> the optimized case gets put aside (consider the influence on Fortran
> compilers of the fact that format strings *may* be dynamic -- for a long
> time the result was that Fortran runtimes treated all format strings as

Agreed.  Picking certain "strategic" special cases to optimize can
work near miracles in practice!

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <E6Lpv3.AoL@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

<stuff deleted>

   I still don't think it's a "mistake" to expect buffering to be done by
   standard packages, rather than by every user's program.  I mean, you
   have to tell the thing that you're planning to read sequentially through
   the file, but beyond that, the application program shouldn't have to
   worry about it.

   (When I programmed on VAX/VMS, I was appalled at the complexity of the
   Record Management Services.  I still don't know why all that complexity
   is necessary, as compared to the Unix notion that a file is a sequence
   of bytes.  But I could be wrong -- I write compilers, mostly, which
   don't need "fancy" I/O facilities.)

Nor do data base management systems. If you use something like the
RMS, your DBMS is probably not going to be very portable, and it is
not very likeley that the RMS idea of what properties and physical
layout a record should have matches the DBMS's ideas. I could make
similar complaints about the crazy idea of building so-called
"reliable" network protocols without regard to the rest of the system
(like TCP/IP), but I'll stop here.

The basic problem is that designers of services like file systems and
network protocols must assume soemthing about their clients. Often
that assumption is wrong, in which case the value of the service is
rather dubious. It is NOT easy to build complex mechanisms which must
be useable in a variety of contexts.

   Note that Ada compilers don't typically use Text_IO to read the source
   code!  ;-)

   - Bob

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.857652688@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Bob Duff said

   <<Agreed, but that's what inlining is for.  All I was saying is that there
   should be a standard package that does efficient I/O, with buffering,
   and of course you want to inline a call that just bumps a pointer and
   grabs a character out of a buffer (except in the rare case where the
   buffer is exhausted).  Unfortunately, Text_IO has an awful lot of
   nearly-useless cruft in it.  But why can't Stream_IO fit the bill here?>>

     It can, but be careful. If you write String'Input, then not only do you
     get the overhead of going character by character, unless a lot of
     special optimization is at work, but you also get the general inefficiency
     of dealing with unconstrained variable length objects, which usually
     involves at least one extra copy. The character by character reads come
     from the fact that this is the semantics of String'Input. yes, it could
     indeed be optimized (in the normal case, where a user level attribute is
     not supplied for type character), but you cannot count on that.

     More likely to be efficient is using Read and Write directly on
     buffers of stream elements.

     Indeed it is perfectly easy, and probably safest to do your own
     buffering in many cases (the same advice applies to C, it may be
     efficient to do indidvidual getchar's, but it may also be a disaster
     from an efficiency point of view.

It may certainly be less effective, but I cannot think of any
implementation where it would be a disaster. The C single char IO
operations are not complicated, and have very little overhead. What
makes you think otherwise?

Re: CRC in Ada?

[Robert Dewar]

TD/DELAB (?) said

<<It may certainly be less effective, but I cannot think of any
implementation where it would be a disaster. The C single char IO
operations are not complicated, and have very little overhead. What
makes you think otherwise?
>>

I'll tell you what. Go measure the relative speed of reading a 1 meg
file a character at a time, vs using read to read the entire 1 meg at
a time. Do this measurement on at least six different systems. Come
back here with the results and we will discuss them!

Re: CRC in Ada?

[Robert A Duff]

In article <dewar.857749952@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>I'll tell you what. Go measure the relative speed of reading a 1 meg
>file a character at a time, vs using read to read the entire 1 meg at
>a time. Do this measurement on at least six different systems. Come
>back here with the results and we will discuss them!

I think the presumption is that the program needs to look at each
character, one at a time.  So to make it a fair test, you need to loop
through all the characters and do something with them.  Preferably
something that will prevent optimizing away the whole loop (like add
them up and print out the result at the end).  The first program should
read a character at a time, and do something.  The second should read
into a giant buffer, and *then* loop through it doing (the same)
something.

- Bob

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> TD/DELAB (?) said
> 
> <<It may certainly be less effective, but I cannot think of any
> implementation where it would be a disaster. The C single char IO
> operations are not complicated, and have very little overhead. What
> makes you think otherwise?
> >>
> 
> I'll tell you what. Go measure the relative speed of reading a 1 meg
> file a character at a time, vs using read to read the entire 1 meg at
> a time. Do this measurement on at least six different systems. Come
> back here with the results and we will discuss them!

Instead of being stupid about it, how about just looking at the
getchar macro, which is virtually the same on every single system?
I've done this repeatedly over the last nearly 20 years on many many
systems.  There is a small overhead per byte due to the getchar
macro, which is reduced with good optimizing compilers and good
caching hardware.  For the inner loop of "cat", the getchar cost
predominates.  For anything else, it doesn't.  This is basic
algorithmic analysis, which you can find good references for in your
local library, if you ever bother to head in that direction.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim Balter said

<<Instead of being stupid about it, how about just looking at the
getchar macro, which is virtually the same on every single system?
I've done this repeatedly over the last nearly 20 years on many many
systems.  There is a small overhead per byte due to the getchar
macro, which is reduced with good optimizing compilers and good
caching hardware.  For the inner loop of "cat", the getchar cost
predominates.  For anything else, it doesn't.  This is basic
algorithmic analysis, which you can find good references for in your
local library, if you ever bother to head in that direction.>>

(replying to me)

Very curious, your post EXACTLY agrees with my point, which is that
there is extra overhead, even in C in going character by character, 
and you even go so far as to say (further than I went) that there
can be programs in which this effect is dominant.

Well of course your claim that ONLY cat can see this effect is 
over-headed hyperbole, but there is a real difference, and for
example, in many of the compilers I have written in C, I have
found that the overall compilation time is noticably affected by
the choice of reading character by character or reading blocks.
A character read is going to do at least one pipe-line breaking
test (or one should say potentially pipe-line breaking test),
and it is not going to be free.

That was my point, and you seem to completely agree, and I really
don't see what algorithmic analysis has to do with the situation,
since we are talking O(N) in any case, i.e. we are discussing
constants, not algorithmic complexities

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim Balter said
> 
> <<Instead of being stupid about it, how about just looking at the
> getchar macro, which is virtually the same on every single system?
> I've done this repeatedly over the last nearly 20 years on many many
> systems.  There is a small overhead per byte due to the getchar
> macro, which is reduced with good optimizing compilers and good
> caching hardware.  For the inner loop of "cat", the getchar cost
> predominates.  For anything else, it doesn't.  This is basic
> algorithmic analysis, which you can find good references for in your
> local library, if you ever bother to head in that direction.>>
> 
> (replying to me)
> 
> Very curious, your post EXACTLY agrees with my point, which is that
> there is extra overhead, even in C in going character by character,
> and you even go so far as to say (further than I went) that there
> can be programs in which this effect is dominant.

It take an unusual degree of intellectual dishonesty to misrepresent
one's own point.  No more talk here of extra system calls,
buffering not being mandated, or the need to go out and empirically
check 6 implementations.

> Well of course your claim that ONLY cat can see this effect is
> over-headed hyperbole,

It would be if I claimed that; the only claim was about predominance,
i.e., the major factor in the cost.

> but there is a real difference, and for
> example, in many of the compilers I have written in C, I have
> found that the overall compilation time is noticably affected by
> the choice of reading character by character or reading blocks.
> A character read is going to do at least one pipe-line breaking
> test (or one should say potentially pipe-line breaking test),
> and it is not going to be free.

The point is and has been a radical overstatement of the cost,
as though it is just the luck of the draw whether a getchar
call might do an extra system call, and you have to go out and
empirically check 6 different systems to find out.  Of course

if (c = (--n < 0? fetch() : *p++)) == EOF break;

is potentially more costly than

if (i == n) break; c = buf[i++];

but it is not the sort of "mistake" to code this way that some have
made it out to be.  The hyperbole is on the other side.

> That was my point, and you seem to completely agree, and I really
> don't see what algorithmic analysis has to do with the situation,
> since we are talking O(N) in any case, i.e. we are discussing
> constants, not algorithmic complexities

The magnitude of constants is part of algorithmic analysis.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim said

<<It take an unusual degree of intellectual dishonesty to misrepresent
one's own point.  No more talk here of extra system calls,
buffering not being mandated, or the need to go out and empirically
check 6 implementations.>>

No, sorry, you are confused, go back and check the thread, I never said
that there were extra system calls, that was someone else with whom I
disagreed!

As for buffering being mandated, I am not quite sure what you are talking
about here. As I noted, GNAT I/O is constructed directly on top of 
C Stream I/O, so it inherits the same default buffering behavior (and
the same ability to control buffering, see the GNAT RM for details).

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim said
> 
> <<It take an unusual degree of intellectual dishonesty to misrepresent
> one's own point.  No more talk here of extra system calls,
> buffering not being mandated, or the need to go out and empirically
> check 6 implementations.>>
> 
> No, sorry, you are confused, go back and check the thread, I never said
> that there were extra system calls, that was someone else with whom I
> disagreed!

I have already quoted you as saying that a single I/O call per block
by the *C library* (not a comment about ADA) is not guaranteed.
 
> As for buffering being mandated, I am not quite sure what you are talking
> about here.

Sorry to here that you are having so much trouble following the thread.

--
<J Q B>

Re: CRC in Ada?

[Richard A. O'Keefe]

Jim Balter <jqb@netcom.com> writes:
>I have already quoted you as saying that a single I/O call per block
>by the *C library* (not a comment about ADA) is not guaranteed.

I have the C standard and the POSIX standard, and for the life of me
I cannot find in either document _any_ guarantee about how many system
calls or even how many read() calls will be done for fread() or any
other C stdio input function call.  In fact, it is quite easy to set
up a situation where there _is_ and _has to be_ a read() call for
every character transferred.
-- 
Will maintain COBOL for money.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: CRC in Ada?

[Jim Balter]

Richard A. O'Keefe wrote:
> 
> Jim Balter <jqb@netcom.com> writes:
> >I have already quoted you as saying that a single I/O call per block
> >by the *C library* (not a comment about ADA) is not guaranteed.
> 
> I have the C standard and the POSIX standard, and for the life of me
> I cannot find in either document _any_ guarantee about how many system
> calls or even how many read() calls will be done for fread() or any
> other C stdio input function call.

"When a stream is /fully buffered/, characters are intended to be
transmitted to or from the host environment as a block when a buffer
is filled".

Someone who does design and planning based upon a theoretical
possibility that some implementation will ignore that intent
just doesn't know what they are doing, profession-wise.

> In fact, it is quite easy to set
> up a situation where there _is_ and _has to be_ a read() call for
> every character transferred.

Which is totally irrelevant to the question of whether it is a
"mistake" to do char-at-time processing.  If one sets up such a
situation then presumably one wants that situation.

--
<J Q B>

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <1997Mar5.131846.1@eisner> kilgallen@eisner.decus.org (Larry Kilgallen) writes:

   In article <E6Kxux.FL9@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:
   > In article <1997Mar5.083233.1@eisner>,
   > Larry Kilgallen <kilgallen@eisner.decus.org> wrote:
   >>For Ada, I would guess that implementors have not counted on
   >>people using C-like programming constructs (vs. doing large
   >>buffer reads as suggested earlier in this thread).
   >>
   >>It is certainly possible to build an Ada environment optimized for
   >>single-character reads, but that would not seem to be a priority
   >>for most Ada compiler customers.
   > 
   > I think I disagree.  Buffering should be the job of the OS and/or
   > standard libraries.  Not every program.

   While theoretical computing and Alan Turing may be centered on
   the equivalence and correctness of programs, in the real world
   performance is also a consideration.  Just as those using intense
   computation will be concerned about the efficiency of their
   algorithms, those accessing large databases will take care
   regarding order-of-access so as not to go skipping over the
   whole thing when some locality-of-reference would yield better
   performance.  Those reading sequentially from disk should
   likewise concern themselves with performance, and 512 calls
   to even the lightest-weight library is too much if a single
   call would do.  For the stated problem (CRC) reading large
   blocks is a clear win.

I think you are missing something here. Altough in Unix it IS possible
to do reads of arbitrary length, the standard IO library of C
definitely does IO in blocks. The getc/putc functions are
usually implemented as macros, which just manipulate the buffer. Of
course it is possible to do it faster yourself, but the interface is
both efficient and simple to use. If you want to, you can even set the
buffer size.

You may judge for yourself:

#define	getc(p)		(--(p)->_cnt < 0 ? __filbuf(p) : (int)*(p)->_ptr++)
#define	putc(x, p)	(--(p)->_cnt < 0 ? __flsbuf((unsigned char) (x), (p)) \

				: (int)(*(p)->_ptr++ = (x)))


   > I'm not sure why reading a file character-by-character is "C-like".
   > It seems like the natural way to write lots of programs, in any
   > language.  The underlying language and OS should ensure that it can be
   > done efficiently (by making the "give-me-a-char" routine read from a
   > buffer whenever appropriate).

   In my experience it is generally C programmers who make this mistake.
   Perhaps it because many of them come from a Unix background where there
   is no strong sense of a "record".  On the other hand, it may just be
   that there are so many C programmers that statistically speaking most
   of the mistakes made will be made by a C programmer.

   Larry Kilgallen

It should be no harder to implement the putc/getc funtions on any
other OS which allows you to do character IO in blocks, than it is in Unix.

It may be a mistake in some cases, but talking about "this mistake" is
a vast oversimplification. Surely, there is nothing conceptually wrong
with having a set of single character IO operations like putc, getc,
and ungetc?


Ole-Hj. Kristensen

Re: CRC in Ada?

[Graham Hughes]

-----BEGIN PGP SIGNED MESSAGE-----

ohk@edeber.tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:
>It may be a mistake in some cases, but talking about "this mistake" is
>a vast oversimplification. Surely, there is nothing conceptually wrong
>with having a set of single character IO operations like putc, getc,
>and ungetc?

One important point here, in agreement with what you say: for a lot of
stuff (e.g., about 80% of the stuff I program routinely), text I/O is a
major portion of the code.  Things like scanners, editors, filters, and
others all require a good I/O interface, but also are most convenient
when read a character at a time.

When the standard libraries do buffering automatically, we win.
Low-level escapes like read() and write() could be retained, but having
fread() and cousins as a part of the library means that I don't have to
go implementing a buffering routine every time I want to do something
trivial.  If somebody wants buffering off, then let them, but most
programs will want buffering.

Personally, if I'm going to have to work around GNAT not having I/O
buffering, I'm probably going to write it in Icon, Perl, C, C++,
Python, or any of a hundred other languages that do this for me.  My
time is better spent coding, not writing buffers, and I'm going to have
to write buffers just for the sake of program speed.
- -- 
Graham Hughes (graham.hughes@resnet.ucsb.edu)
http://A-abe.resnet.ucsb.edu/~graham/ -- MIME & PGP mail OK.
"Never attribute to malice that which can be adequately explained by 
	stupidity." -- Hanlon's Razor

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMx6guiqNPSINiVE5AQEzyAP8DAbVaLEW7JFj6awX57mJQkvv7GAXruzY
0tiZRiEClTQaDCiyileSlxpXLXW07fR5XZiGiblwOy5WHK3QX+f6RJ+KbEEYL1pS
2UzEiUxwMX8L3i1nzVi/02Re40bFFWA0AlrI6fp/EK1JP8qg07V7b/bBOUYfj1gp
mA1DiGSqs8E=
=gKP9
-----END PGP SIGNATURE-----

Re: CRC in Ada?

[Robert Dewar]

Graham says

<<Personally, if I'm going to have to work around GNAT not having I/O
buffering, I'm probably going to write it in Icon, Perl, C, C++>>

Uh? GNAT uses exactly C stream semantics to read, it will be buffered
or unbuffered depending on whether the C streams are buffered or unbuffered
by default. As with C, setvbuf (I think I remember the name right) can e
used to control buffering.

More significant is that the Text_IO semantics has a lot of junk, like
column, line and page counting, which can introduce fundamental unwelcome
overhead.

If this is a problem, then of course it is perfectly easy to use the
C routines directly from Ada, or even GNAT.IO if you are using GNAT.

I recommend that people read the section on implementation of Text_IO
in the GNAT manual, which gives the EXACT correspondence between Ada
Text_IO and C stream IO.

Re: CRC in Ada?

[Larry Kilgallen]

In article <OHK.97Mar6080224@edeber.tfdt-o.nta.no>, ohk@edeber.tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:

> In article <1997Mar5.131846.1@eisner> kilgallen@eisner.decus.org (Larry Kilgallen) writes:

>    performance.  Those reading sequentially from disk should
>    likewise concern themselves with performance, and 512 calls
>    to even the lightest-weight library is too much if a single
>    call would do.  For the stated problem (CRC) reading large
>    blocks is a clear win.
> 
> I think you are missing something here. Altough in Unix it IS possible
> to do reads of arbitrary length, the standard IO library of C
> definitely does IO in blocks. The getc/putc functions are
> usually implemented as macros, which just manipulate the buffer. Of

And relying on performance characteristics of a particular implementation
which are not mandated from implementation to implementation brings
problems.  (Perhaps this implementation technique _is_ mandated,
but it is not something I would know.)

>    > I'm not sure why reading a file character-by-character is "C-like".
>    > It seems like the natural way to write lots of programs, in any
>    > language.  The underlying language and OS should ensure that it can be
>    > done efficiently (by making the "give-me-a-char" routine read from a
>    > buffer whenever appropriate).
> 
>    In my experience it is generally C programmers who make this mistake.
>    Perhaps it because many of them come from a Unix background where there
>    is no strong sense of a "record".  On the other hand, it may just be
>    that there are so many C programmers that statistically speaking most
>    of the mistakes made will be made by a C programmer.

> It should be no harder to implement the putc/getc funtions on any
> other OS which allows you to do character IO in blocks, than it is in Unix.

And any vendor in the non-Unix space can choose to emulate as many
Unix characteristics as they choose, including performance-related
ones or not.

> It may be a mistake in some cases, but talking about "this mistake" is
> a vast oversimplification. Surely, there is nothing conceptually wrong
> with having a set of single character IO operations like putc, getc,
> and ungetc?

It is a mistake to assume performance semantics (if that is the term)
which are not present in the target environment.

Don't get me wrong, I think there are many instances for non-portable
code in the world. However just because something written in Ada (or
C) will compile and get the right answer in another environment, that
does not mean it is portable from the standpoint of the end user who
must wait for the results.

Larry Kilgallen

Re: CRC in Ada?

[Robert Dewar]

OUe-Hjalmar says

> I think you are missing something here. Altough in Unix it IS possible
> to do reads of arbitrary length, the standard IO library of C
> definitely does IO in blocks. The getc/putc functions are
> usually implemented as macros, which just manipulate the buffer. Of


You cannot make such statements (the standard IO lbrary of C definitely
does IO in blocks). The standard speaks only of interfaces, not of
implementation, there is nothing in the standardized interface that requires
IO to be done in blocks. This may be an implementation characterstic of some
or even most or even all current implementations, but it is NOT a fundamental
property of the standard IO library.

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.857693222@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Fergus asks

   <<>In my experience it is generally C programmers who make this mistake.

   Why is it a mistake?>>

   Tell you what Fergus, do a whole lot of timing tests comparing reading
   character by character and reading large blocks, and come back and tell
   us if it did not tell you the answer to that questin :-)

OK, I'll bite:

The following two simple programs have been tested on a 24443068 byte
file, both compiled wit -O7 on the Centerline C compiler:

#include <stdio.h>

main() {
   setvbuf(stdin,0,_IOFBF,4096);
   int c,total=0;
   while ((c = getc(stdin)) != EOF) total++;
   printf("total %d\n",total);
}

Average results obtained with time:
2.28u 0.28s 0:02.66 96.2%

char buf[4096];

main() {
   int c,n,total=0;
   while ((n = read(0,buf,sizeof(buf))) > 0) {
      int i;
      for (i = 0; i < n; i++) {
         c = buf[i];
         total++;
      }
   }
   printf("total %d\n",total);
}

Average results obtained with time:
0.12u 0.29s 0:00.41 100.0%


As you can see, the time used by the OS is pretty much the same in
both cases. 

It is somewhat surprising that the difference between the user CPU
times is so large, but I'm more surprised by the speed of the second
version than by the slowness of the first.

Depending on what your program is really going to do with the 24443068
bytes, the 2.5 seconds spent in the C standard IO library may or may
not be significant....

Re: CRC in Ada?

[Robert Dewar]

Fergus said

<<It is somewhat surprising that the difference between the user CPU
times is so large, but I'm more surprised by the speed of the second
version than by the slowness of the first.>>

Well it does not surprise me, and I don't really understand why it
surprises you. I would expect a large difference here, and indeed
it is what we see!

Just shows that measurements can be a useful substitute for guesswork,
though measurements have the weakness of being system specific, so
nothing really substitutes for a lot of experience on a lot of difrerent
machiens!

Re: CRC in Ada?

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Fergus said
>
><<It is somewhat surprising that the difference between the user CPU
>times is so large, but I'm more surprised by the speed of the second
>version than by the slowness of the first.>>

Those weren't my words.  You are quoting ohk@edeber.tfdt-o.nta.no
("Ole-Hjalmar Kristensen FOU.TD/DELAB"), not me.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Fergus said
> 
> <<It is somewhat surprising that the difference between the user CPU
> times is so large, but I'm more surprised by the speed of the second
> version than by the slowness of the first.>>
> 
> Well it does not surprise me, and I don't really understand why it
> surprises you. I would expect a large difference here, and indeed
> it is what we see!
> 
> Just shows that measurements can be a useful substitute for guesswork,
> though measurements have the weakness of being system specific, so
> nothing really substitutes for a lot of experience on a lot of difrerent
> machiens!

These measurements are totally misleading, and their use and
interpretation show a total *lack* of experience.  If the tests are
coded properly so that the buffer accesses aren't optimized out of
existence, you will see about a 3:1 difference in user cpu time between
the getchar version and the read version, solely as a consequence of the
getchar macro requiring more instructions.  Exactly the same number of
system calls are made, as anyone who attempts to *understand* the
issue instead of indulging in silly sophistry will know.  If you then
do, say, 20 instructions worth of processing per character, the ratio
is 23:21.  *Big* difference, like you'd expect.  Feh.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim Balter quoted me and replied

<<These measurements are totally misleading, and their use and
interpretation show a total *lack* of experience.  If the tests are
coded properly so that the buffer accesses aren't optimized out of
existence, you will see about a 3:1 difference in user cpu time between
the getchar version and the read version, solely as a consequence of the
getchar macro requiring more instructions.  Exactly the same number of
system calls are made, as anyone who attempts to *understand* the
issue instead of indulging in silly sophistry will know.  If you then
do, say, 20 instructions worth of processing per character, the ratio
is 23:21.  *Big* difference, like you'd expect.  Feh.>>

Well if there is one thing I am certainly not guilty of, it is lack of
experience :-)

But actually Jim, you have your quotes confused. I never said there
were a different number of systems calls, of course not! I said exactly
the opposite.

I am not quite sure what you mean by the measurements being misleading,
they are measuring exactly what they purport to be measuring. It is
possible to draw incorrect conclusions from these measurements, but
they only mislead those who wish to be mislead!

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:

> I am not quite sure what you mean by the measurements being misleading,
> they are measuring exactly what they purport to be measuring. It is
> possible to draw incorrect conclusions from these measurements, but
> they only mislead those who wish to be mislead!

Robert Dewar is apparently so afraid of seeing certain inputs
that he has blocked mail from me.  This immediately after misreading
a note from me pointing out that he had taken Ole-Hjalmar Kristensen's
measurements as valid because they showed what he wanted them to show
(even though important code in an inner loop may have been optimized
out) as instead claiming that *he*, Dewar, had taken the measurements,
and thereupon interpreting me as being unable to follow a newsgroup
thread.  Of course, I made no such mistake as thinking that Dewar
had taken the measurement.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim Balter said

<<Robert Dewar is apparently so afraid of seeing certain inputs
that he has blocked mail from me>>

A curious misinterpretation, but just for the record, Mr. Balter's
arguments descended into a string of obsecnities, and at that point
I concluded that I had better things to do with my time (I do have
a rather large number of email messages to deal with that are somewhat
more informative and useful :-) 

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim Balter said
> 
> <<Robert Dewar is apparently so afraid of seeing certain inputs
> that he has blocked mail from me>>
> 
> A curious misinterpretation, but just for the record, Mr. Balter's
> arguments descended into a string of obsecnities, and at that point
> I concluded that I had better things to do with my time (I do have
> a rather large number of email messages to deal with that are somewhat
> more informative and useful :-)

My comments were in response to Dewar calling me a child and pompously
referring to his teaching of courses as some sort of
argument from authority rather than answering my substantive points.

--
<J Q B>

Re: CRC in Ada?

[Samuel Mize]

" When you said what I said you said said what you said what I
" said said, you said what you said said said what ....

Take it to alt.flame, you guys.  The grownups are using comp.lang.ada.

If anyone here gives a rat's ash what was actually said, he/she can
go to the archives or DejaNews and read the thread itself.

If you want to appear intelligent and professional, post useful
information and/or ask technical questions.  If someone appears
confused, courteously ask for clarification instead of saying "HA!
you fool!"  If someone seems less than civil, ignore that person.

If you want to look like a petty cretin, argue about the meaning of
old messages, as if there were One Right True Reading of the Text
and you own it.

Followups.
Samuel Mize

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim Balter quoted me and replied
> 
> <<These measurements are totally misleading, and their use and
> interpretation show a total *lack* of experience.  If the tests are
> coded properly so that the buffer accesses aren't optimized out of
> existence, you will see about a 3:1 difference in user cpu time between
> the getchar version and the read version, solely as a consequence of the
> getchar macro requiring more instructions.  Exactly the same number of
> system calls are made, as anyone who attempts to *understand* the
> issue instead of indulging in silly sophistry will know.  If you then
> do, say, 20 instructions worth of processing per character, the ratio
> is 23:21.  *Big* difference, like you'd expect.  Feh.>>
> 
> Well if there is one thing I am certainly not guilty of, it is lack of
> experience :-)
> 
> But actually Jim, you have your quotes confused. I never said there
> were a different number of systems calls, of course not! I said exactly
> the opposite.

"You cannot make such statements (the standard IO lbrary of C definitely
does IO in blocks). The standard speaks only of interfaces, not of
implementation, there is nothing in the standardized interface that
requires
IO to be done in blocks. This may be an implementation characterstic of
some
or even most or even all current implementations, but it is NOT a
fundamental
property of the standard IO library.
"

And there has been other material in which you have implied that
multiple system calls might be involved.

> I am not quite sure what you mean by the measurements being misleading,
> they are measuring exactly what they purport to be measuring. It is
> possible to draw incorrect conclusions from these measurements, but
> they only mislead those who wish to be mislead!

What a foolish thing to say.  Take a course in philosophy of science.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim Balter said

<<And there has been other material in which you have implied that
multiple system calls might be involved.>>

Just so this is crystal clear at this stage, at least to other readers
than Jim, I definitely did NOT imply that there are multiple system calls.
It maybe that Jim does not know Ada 95 very well, and that is how he got
confused.

What I did say was that if you use String'Output and String'Input, the
RM strongly implies character by character reads, since stream I/O is
defined as being component wise. But of course this does not result in
a system call per character, at least not in a reasonable implementation.
For example in GNAT, this translates eventually into a normal C stream
operation, which will typically be buffered.

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim Balter said
> 
> <<And there has been other material in which you have implied that
> multiple system calls might be involved.>>
> 
> Just so this is crystal clear at this stage, at least to other readers
> than Jim, I definitely did NOT imply that there are multiple system calls.
> It maybe that Jim does not know Ada 95 very well, and that is how he got
> confused.

I gave a quote, which you have deliberately deleted, that made it
clear that you had implied that the *C language* getchar macro
might cause extra system calls to be made.  And it is the "mistake"
of using getchar in C that has been at issue, so it seems that you
are having considerable trouble following the thread.

--
<J Q B>

Re: CRC in Ada?

[David Brown]

ohk@edeber.tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:

> char buf[4096];
> 
> main() {
>    int c,n,total=0;
>    while ((n = read(0,buf,sizeof(buf))) > 0) {
>       int i;
>       for (i = 0; i < n; i++) {
>          c = buf[i];
>          total++;
>       }
>    }
>    printf("total %d\n",total);
> }
> 
> Average results obtained with time:
> 0.12u 0.29s 0:00.41 100.0%
> 
> It is somewhat surprising that the difference between the user CPU
> times is so large, but I'm more surprised by the speed of the second
> version than by the slowness of the first.

I suspect that most of the inner loop is being optimized out.  Since
you don't actually do anything with 'c', it probably is never actually
used.  The buffer is probably never accessed.  A slightly better test
would be to compute a simple checksum or something.

Dave Brown
dbrown@vigra.com

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <1997Mar6.091150.1@eisner> kilgallen@eisner.decus.org (Larry Kilgallen) writes:

   In article <OHK.97Mar6080224@edeber.tfdt-o.nta.no>, ohk@edeber.tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:

   > In article <1997Mar5.131846.1@eisner> kilgallen@eisner.decus.org (Larry Kilgallen) writes:

   >    performance.  Those reading sequentially from disk should
   >    likewise concern themselves with performance, and 512 calls
   >    to even the lightest-weight library is too much if a single
   >    call would do.  For the stated problem (CRC) reading large
   >    blocks is a clear win.
   > 
   > I think you are missing something here. Altough in Unix it IS possible
   > to do reads of arbitrary length, the standard IO library of C
   > definitely does IO in blocks. The getc/putc functions are
   > usually implemented as macros, which just manipulate the buffer. Of

   And relying on performance characteristics of a particular implementation
   which are not mandated from implementation to implementation brings
   problems.  (Perhaps this implementation technique _is_ mandated,
   but it is not something I would know.)

No, it is not mandated, but every implementation I have ever seen,
has done it that way. NB, this has NOTHING to do with Unix, but with
the C standard IO library. And of course, you are right, language and
libraray specifications do not in general say anything about
performance. You cannot count on block IO being efficient either, but
I'll agree it's a good bet :-)

   >    > I'm not sure why reading a file character-by-character is "C-like".
   >    > It seems like the natural way to write lots of programs, in any
   >    > language.  The underlying language and OS should ensure that it can be
   >    > done efficiently (by making the "give-me-a-char" routine read from a
   >    > buffer whenever appropriate).
   > 
   >    In my experience it is generally C programmers who make this mistake.
   >    Perhaps it because many of them come from a Unix background where there
   >    is no strong sense of a "record".  On the other hand, it may just be
   >    that there are so many C programmers that statistically speaking most
   >    of the mistakes made will be made by a C programmer.

   > It should be no harder to implement the putc/getc funtions on any
   > other OS which allows you to do character IO in blocks, than it is in Unix.

   And any vendor in the non-Unix space can choose to emulate as many
   Unix characteristics as they choose, including performance-related
   ones or not.

Again, the C standard IO library has nothing to do with Unix. The
question is whether the vendor has implemnted this library efficiently
or not, based on the mechanisms available in the OS.

   > It may be a mistake in some cases, but talking about "this mistake" is
   > a vast oversimplification. Surely, there is nothing conceptually wrong
   > with having a set of single character IO operations like putc, getc,
   > and ungetc?

   It is a mistake to assume performance semantics (if that is the term)
   which are not present in the target environment.

I agree 100%. Which means that you have to run your program and
profile it anyway.

   Don't get me wrong, I think there are many instances for non-portable
   code in the world. However just because something written in Ada (or
   C) will compile and get the right answer in another environment, that
   does not mean it is portable from the standpoint of the end user who
   must wait for the results.

   Larry Kilgallen

There is no such thing as portable, high-performance, code which does
IO :-)

Ole-Hj. Kristensen

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.857911919@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   OUe-Hjalmar says

   > I think you are missing something here. Altough in Unix it IS possible
   > to do reads of arbitrary length, the standard IO library of C
   > definitely does IO in blocks. The getc/putc functions are
   > usually implemented as macros, which just manipulate the buffer. Of


   You cannot make such statements (the standard IO lbrary of C definitely
   does IO in blocks). The standard speaks only of interfaces, not of
   implementation, there is nothing in the standardized interface that requires
   IO to be done in blocks. This may be an implementation characterstic of some
   or even most or even all current implementations, but it is NOT a fundamental
   property of the standard IO library.

Yes, of course you are right. I plead guilty of using imprecise language.

But I still would say that this is the only reasonable implementation,
especially as functions to explicitly control the buffering and flush
the buffer is part of the specification.  You could just as well argue
that if you use the write system call, you have no guarantee that the
OS does not actually write a single byte at a time to the disk...
Maybe the standards should say something about the precise semantics
at this level as well.

Anyway, you seem to have missed my point, which is that as all the
Unix standard IO libraries I am aware og does block IO anyway, it
would not be any harder to implement such a library on any other OS
which have block IO but not single char IO as part of the system
calls.
The flexibility of the Unix read and write calls is not needed by the
usual implementations of the C standard IO library.

Ole-Hj. Kristensen

Re: CRC in Ada?

[Robert Dewar]

Ole-HJ said

<<But I still would say that this is the only reasonable implementation,
especially as functions to explicitly control the buffering and flush
the buffer is part of the specification.>>

YOu have lost me here, what do you mean when you say that functions to
explicitly control the buffering are part of the speciication. Yes
there is flush, but that's it ...

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Ole-HJ said
> 
> <<But I still would say that this is the only reasonable implementation,
> especially as functions to explicitly control the buffering and flush
> the buffer is part of the specification.>>
> 
> YOu have lost me here, what do you mean when you say that functions to
> explicitly control the buffering are part of the speciication. Yes
> there is flush, but that's it ...

No, there is no flush, but there is fflush, and setbuf, setvbuf, _IOFBF,
_IOLBF, _IONBF, and BUFSIZ are all part of the specification; it really
helps if one limits one's authoritative claims to what one actually
knows something about.  While it is true that an ANSI C
stdio implementation can send bytes by bicycle courier, "quality of
implementation" mandates against it.  Byte-at-a-time C (or in fact
POSIX, and thus ADA, given a binding) programs perform well portably, a
fact that no amount of sophistry can cancel.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Ole-HJ said

<<No, there is no flush, but there is fflush, and setbuf, setvbuf>>

Ah, I was confused by your original post, I did not think you were talking
about C there, but about Ada.

Byte at a time procesing will always be slower than reading blocks. This
is true in C as well as Ada.

Given comparable I/O packages, C and Ada are not significantly different
here.

It is true that Text_IO has a lot of extra baggage that makes doing
Get(char) slower than getchar in C, these swimply are not comparble
operations.

Because of this extra baggage, put there quite deliberately of course,
most big Ada programs concerned with efficiency do NOT use Text_IO.

It is perfectly possible to do character by character IO using
streams in Ada, by reading one character at a time. This certainly
does introduce an extra overhead of call levels, but it does not
result in a system call per character, as some have suggested.

If you want something equivalent to the macroized get_char, that is
trivially easily programmed in C on top of stream_IO, perhaps it is
a good idea for a standard package -- any student could write it
in a few minutes, so it is not exactly rocket science!

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:

> If you want something equivalent to the macroized get_char, that is
> trivially easily programmed in C on top of stream_IO, perhaps it is
> a good idea for a standard package

Since that was the original point, this whole discussion has been
much ado about nothing.

--
<J Q B>

Re: CRC in Ada?

[Robert Dewar]

Jim said

<<> If you want something equivalent to the macroized get_char, that is
> trivially easily programmed in C on top of stream_IO, perhaps it is
> a good idea for a standard package

Since that was the original point, this whole discussion has been
much ado about nothing.
>>

Actually I mistyped here, what I meant to say was "easily programmed
in Ada on top of [Ada] Stream_IO", and that is what would be a good idea
for a standard package.

One problem in using C I/O routines directly is that they are often
not properly thread safe, whereas you can count on Stream_IO being
thread safe, which is why it is safer to build on top of the existing
Ada packages.

Re: CRC in Ada?

[Jim Balter]

Robert Dewar wrote:
> 
> Jim said
> 
> <<> If you want something equivalent to the macroized get_char, that is
> > trivially easily programmed in C on top of stream_IO, perhaps it is
> > a good idea for a standard package
> 
> Since that was the original point, this whole discussion has been
> much ado about nothing.
> >>
> 
> Actually I mistyped here, what I meant to say was "easily programmed
> in Ada on top of [Ada] Stream_IO", and that is what would be a good idea
> for a standard package.

That's what I took you to mean (i.e., I misread you and thereby
read you properly).

--
<J Q B>

Re: CRC in Ada?

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Ole-HJ said
>
><<But I still would say that this is the only reasonable implementation,
>especially as functions to explicitly control the buffering and flush
>the buffer is part of the specification.>>
>
>YOu have lost me here, what do you mean when you say that functions to
>explicitly control the buffering are part of the speciication. Yes
>there is flush, but that's it ...

What about setvbuf()?

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.857750112@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:


   Fergus said

   <<It is somewhat surprising that the difference between the user CPU
   times is so large, but I'm more surprised by the speed of the second
   version than by the slowness of the first.>>

   Well it does not surprise me, and I don't really understand why it
   surprises you. I would expect a large difference here, and indeed
   it is what we see!

   Just shows that measurements can be a useful substitute for guesswork,
   though measurements have the weakness of being system specific, so
   nothing really substitutes for a lot of experience on a lot of difrerent
   machiens!

He didn't say it, I did. 

So tell me, why would you expect a large difference?
I would expect the optimizer to recognize that both (&_iob[0])->_cnt
and (&_iob[0])->_ptr are constant expressions, so that the two loops
differ mainly in using indirect or direct addressing.
Bu I suppose Im'm expecting too much from optimizers.

Here is a version of the first program after it has passed through
cpp:

main() {
   setvbuf((&_iob[0]),0,0000,4096);
   int c,total=0;
   while ((c = (--((&_iob[0]))->_cnt < 0 ? __filbuf((&_iob[0])) : (int)*((&_iob[0]))->_ptr++)) != (-1)) total++;
   printf("total %d\n",total);
}

And the second:

main() {
   int c,n,total=0;
   while ((n = read(0,buf,sizeof(buf))) > 0) {
      int i;
      for (i = 0; i < n; i++) {
         c = buf[i];
         total++;
      }
   }
   printf("total %d\n",total);
}

Ole-Hj. Kristensen

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.858014326@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Ole-HJ said

   <<But I still would say that this is the only reasonable implementation,
   especially as functions to explicitly control the buffering and flush
   the buffer is part of the specification.>>

   YOu have lost me here, what do you mean when you say that functions to
   explicitly control the buffering are part of the speciication. Yes
   there is flush, but that's it ...


There are the functions  fflush,setbuf, setvbuf and the constants  _IOFBF,
_IOLBF, _IONBF, and BUFSIZ. Look them up if you aren't familiar with
stdio.

Btw., I admire your urge to reduce the bandwidth by only quoting
selected parts of messages, but on the other hand, you constantly run
the risk of looking like a smartass who likes quoting people out of context.

Ole-Hj. Kristensen

Re: CRC in Ada?

[Jim Balter]

Ole-Hjalmar Kristensen FOU.TD/DELAB wrote:

> Actually, I don't think he claimed to have done the measurements
> himself.

No, he didn't, nor did I say that he did.  I said that he had
misread something I said to him as a claim by me that he had done
these measurements.  He then claimed that (which was his own misreading
of something I said) showed that I couldn't follow a newsgroup thread.

> But just some comments about doing invalid measurements and being
> unable to interpret the results :-)
> 
> I did the measurements mainly to show that the amount of work being
> done by system calls was exactly the same in both cases, and that is
> why the setvbuf call was made to ensure that the buffer size was the
> same in both cases. I didn't particulary care about the code in the
> inner loop being optimized away, because as you have said yourself,
> as soon as you start doing something interesting with the char, the
> difference is pretty unimportant. I only expressed a mild surprise
> that not more of the getchar macro had been optimzed away as well.

With getchar, the stdin ptr and cnt must be updated to accurately
reflect the amount of data scanned, and many compilers will generate
code that does the compare to EOF whether the char came from filbuf
or from *ptr++, even though the latter isn't necessary.  In the read()
loop, the buffer need not be touched at all if the data isn't actually
used.
 
> Btw., I've re-run the program with a simple checksum computation in the
> innner loop, and the ratio is now 4 to 1. Still a bit more difference
> than I would have thought, but pipelining effects may have something
> to do with it, as Dewar pointed out.

The compiled code may well not be moving stdin._ptr and
stdin._cnt into registers.  You would have to carefully evaluate
the actual compiled code for both the getchar and read() cases to
determine the precise overhead for getchar.  It may even get down to
zero (within the loop; there would still be constant overhead) with
certain compilers and processors.  Of course, it won't get down below
zero, unless the read() loop is really badly coded.
But it is easy to write read() loops that mishandle some cases,
such as a search for a two-character sequence that straddles a buffer
boundary, so loose talk about "mistakes" should be avoided.

My own measurements gave  a getchar cost of 100 nanoseconds
per byte on a Pentium 166, rather a small fraction of the total cost,
but I didn't run a lot of cases or examine the generated code to be
sure I wasn't seeing some artifact, so my experience leads me not
to jump to conclusions about such numbers.  And of course all these
measurements are *CPU* time, not elapsed time, and totally
exclude physical I/O time.

--
<J Q B>

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <33263B09.6285@netcom.com> Jim Balter <jqb@netcom.com> writes:

   Robert Dewar wrote:

   > I am not quite sure what you mean by the measurements being misleading,
   > they are measuring exactly what they purport to be measuring. It is
   > possible to draw incorrect conclusions from these measurements, but
   > they only mislead those who wish to be mislead!

   Robert Dewar is apparently so afraid of seeing certain inputs
   that he has blocked mail from me.  This immediately after misreading
   a note from me pointing out that he had taken Ole-Hjalmar Kristensen's
   measurements as valid because they showed what he wanted them to show
   (even though important code in an inner loop may have been optimized
   out) as instead claiming that *he*, Dewar, had taken the measurements,
   and thereupon interpreting me as being unable to follow a newsgroup
   thread.  Of course, I made no such mistake as thinking that Dewar
   had taken the measurement.

   --
   <J Q B>

Actually, I don't think he claimed to have done the measurements
himself. 

But just some comments about doing invalid measurements and being
unable to interpret the results :-)

I did the measurements mainly to show that the amount of work being
done by system calls was exactly the same in both cases, and that is
why the setvbuf call was made to ensure that the buffer size was the
same in both cases. I didn't particulary care about the code in the
inner loop being optimized away, because as you have said yourself,
as soon as you start doing something interesting with the char, the
difference is pretty unimportant. I only expressed a mild surprise
that not more of the getchar macro had been optimzed away as well.

Btw., I've re-run the program with a simple checksum computation in the
innner loop, and the ratio is now 4 to 1. Still a bit more difference
than I would have thought, but pipelining effects may have something
to do with it, as Dewar pointed out.

Re: CRC in Ada?

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.858138084@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Jim Balter said

   <<And there has been other material in which you have implied that
   multiple system calls might be involved.>>

But Jim Balter also said the following:

<Start quote of Jim Balter>
Robert Dewar wrote:
> 
> Jim Balter quoted me and replied
> 
> <<These measurements are totally misleading, and their use and
> interpretation show a total *lack* of experience.  If the tests are
> coded properly so that the buffer accesses aren't optimized out of
> existence, you will see about a 3:1 difference in user cpu time between
> the getchar version and the read version, solely as a consequence of the
> getchar macro requiring more instructions.  Exactly the same number of
> system calls are made, as anyone who attempts to *understand* the
> issue instead of indulging in silly sophistry will know.  If you then
> do, say, 20 instructions worth of processing per character, the ratio
> is 23:21.  *Big* difference, like you'd expect.  Feh.>>
> 
> Well if there is one thing I am certainly not guilty of, it is lack of
> experience :-)
> 
> But actually Jim, you have your quotes confused. I never said there
> were a different number of systems calls, of course not! I said exactly
> the opposite.

"You cannot make such statements (the standard IO lbrary of C definitely
does IO in blocks). The standard speaks only of interfaces, not of
implementation, there is nothing in the standardized interface that
requires
IO to be done in blocks. This may be an implementation characterstic of
some
or even most or even all current implementations, but it is NOT a
fundamental
property of the standard IO library.
"

<stuff deleted>
<end quote>

   Just so this is crystal clear at this stage, at least to other readers
   than Jim, I definitely did NOT imply that there are multiple system calls.
   It maybe that Jim does not know Ada 95 very well, and that is how he got
   confused.

And the above quote from Jim Balter makes it crystal clear that we
were talking about the C standard IO library, not Ada 95. It seems
that you are deliberately trying to confuse things here.

   What I did say was that if you use String'Output and String'Input, the
   RM strongly implies character by character reads, since stream I/O is
   defined as being component wise. But of course this does not result in
   a system call per character, at least not in a reasonable implementation.
   For example in GNAT, this translates eventually into a normal C stream
   operation, which will typically be buffered.

Yes, you did say that, but that has nothing to do with the post you
replied to.

Re: CRC in Ada?

[David C. Hoos, Sr.]

This is a multi-part message in MIME format.

------=_NextPart_000_01BC292F.C954A260
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Here is an implementation of a 16-bit CRC in both C and Ada.  The C code is
perhaps ten years old, and is from an implementation of Xmodem.  The Ada
code was translated from that.

The test driver tests both the  C code (as an imported set of functions),
and the Ada code.

The form of the test driver is not suitable for performance testing, as the
CRC generation is swamped by the file reads.  I'd like to modify this in
the next couple of days so as to be able to compare the speeds of the two
implementations.  The test driver does serve to demonstrate the equivalence
of the two implementations, though.

The generating polynomial is one frequently used (x1021), but the value can
be changed as one likes.

-- 
David C. Hoos, Sr.,
http://www.dbhwww.com
http://www.ada95.com

Dr. John B. Matthews <jmatthews@nova.wright.edu> wrote in article
<1997Mar2.220652@nova.wright.edu>...
> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
> PAL and several other archives without luck. Any help appreciated.
> 
> Thanks,
> 
> John
> ----------------------------------------------------------------
> John B. Matthews, M.D.
> jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
> "Whom the gods would destroy, they first invite to program in C"
> 
> 
------=_NextPart_000_01BC292F.C954A260
Content-Type: application/octet-stream; name="crc.c"
Content-Transfer-Encoding: 7bit
Content-Description: crc.c (C source code file)
Content-Disposition: attachment; filename="crc.c"

/* crc.c */

#include "crc.h"

#define POLY 0x1021

static unsigned short CRCtable[256];

/* calculate CRC table entry */

unsigned short CalcTable(data,genpoly,accum)
unsigned short data;
unsigned short genpoly;
unsigned short accum;
{static int i;
 data <<= 8;
 for(i=8;i>0;i--)
         {
          if((data^accum) & 0x8000) accum = (accum << 1) ^ genpoly;
          else accum <<= 1;
          data <<= 1;
         }
 return(accum);
}

/* initialize CRC table */

void InitCRC(void)
{int i;
 for(i=0;i<256;i++) CRCtable[i] = CalcTable(i,POLY,0);
}

/* compute updated CRC */

unsigned short UpdateCRC(crc,byte)
unsigned short crc;
unsigned char  byte;
{
 return( (crc << 8) ^ CRCtable[ (crc >> 8) ^ byte ] );
}

------=_NextPart_000_01BC292F.C954A260
Content-Type: application/octet-stream; name="crc.h"
Content-Transfer-Encoding: 7bit
Content-Description: crc.h (C Header File)
Content-Disposition: attachment; filename="crc.h"

void InitCRC(void);
unsigned short UpdateCRC(unsigned short,unsigned char);

------=_NextPart_000_01BC292F.C954A260
Content-Type: application/octet-stream; name="crc_pkg.adb"
Content-Transfer-Encoding: 7bit
Content-Description: crc_pkg.adb (ObjectAda File)
Content-Disposition: attachment; filename="crc_pkg.adb"

package body CRC_pkg is
  type Lookup_Table_Type is
    array (Interfaces.Unsigned_8) of Interfaces.Unsigned_16;
  Lookup_Table : Lookup_Table_Type;
  procedure Update
      (The_CRC_Value : in out Interfaces.Unsigned_16;
       With_The_Byte : in     Interfaces.Unsigned_8) is
    use Interfaces;
  begin
    The_CRC_Value := Shift_Left 
	     (Value  => The_CRC_Value,
	      Amount => 8) xor Lookup_Table 
	(Interfaces.Unsigned_8 (Shift_Right
	 (Value  => The_CRC_Value,
	  Amount => 8)) xor With_The_Byte);
  end Update;

begin -- CRC package initialization
  declare
    function Lookup_Table_Entry
	(For_The_Index      : in Interfaces.Unsigned_8;
	 And_The_Polynomial : in Interfaces.Unsigned_16)
	 return Interfaces.Unsigned_16 is
      use Interfaces;
      Temporary_Data        : Interfaces.Unsigned_16 := Shift_Left
	  (Value  => Interfaces.Unsigned_16 (For_The_Index),
	   Amount => 8);
      Temporary_Accumulator : Interfaces.Unsigned_16 := 0; 
    begin
      for I in reverse 1 .. 8 loop
	if ((Temporary_Data xor Temporary_Accumulator) and 
	    16#8000#) > 0 then
	  Temporary_Accumulator := Shift_Left 
	      (Value => Temporary_Accumulator, 
	       Amount => 1) xor And_The_Polynomial;
	else
	  Temporary_Accumulator := Shift_Left
	      (Value  => Temporary_Accumulator,
	       Amount => 1);
	end if;
	Temporary_Data := Shift_Left
	    (Value  => Temporary_Data,
	     Amount => 1);
      end loop;
      return Temporary_Accumulator;
    end Lookup_Table_Entry;
  begin
    for I in Lookup_Table'Range loop
      Lookup_Table (I) := Lookup_Table_Entry 
	  (For_The_Index => I,
	   And_The_Polynomial => Polynomial);
    end loop;
  end;
end CRC_pkg;


------=_NextPart_000_01BC292F.C954A260
Content-Type: application/octet-stream; name="crc_pkg.ads"
Content-Transfer-Encoding: 7bit
Content-Description: crc_pkg.ads (ObjectAda File)
Content-Disposition: attachment; filename="crc_pkg.ads"

with Interfaces;

package CRC_pkg is

  use type Interfaces.Unsigned_8;
  use type Interfaces.Unsigned_16;
  Polynomial : constant Interfaces.Unsigned_16 := 16#1021#;

  procedure Update
      (The_CRC_Value : in out Interfaces.Unsigned_16;
       With_The_Byte : in     Interfaces.Unsigned_8);

end CRC_pkg;

------=_NextPart_000_01BC292F.C954A260
Content-Type: application/octet-stream; name="test_crc.adb"
Content-Transfer-Encoding: quoted-printable
Content-Description: test_crc.adb (ObjectAda File)
Content-Disposition: attachment; filename="test_crc.adb"

with Ada.Command_Line;
with Ada.Sequential_IO;
with Ada.Text_IO;
with CRC_pkg;
with Interfaces.C;
procedure Test_CRC is
  package C renames Interfaces.C;
  package Command_Line renames Ada.Command_Line;
  package Text_IO renames Ada.Text_IO;
  use type C.Unsigned_Char;
  use type C.Unsigned_Short;
  procedure Init_CRC;
  function Updated_CRC=20
      (Previous_CRC_Accumulation : C.Unsigned_Short;
       Current_Byte		 : C.Unsigned_char)
       return C.Unsigned_Short;
  pragma Import (C, Init_CRC, "InitCRC");
  pragma Import (C, Updated_CRC, "UpdateCRC");
  pragma Linker_Options ("crc.o");
  Current_CRC_Accumulation : C.Unsigned_Short;
  package Unsigned_Short_IO is new Ada.Text_IO.Modular_IO =
(C.Unsigned_Short);
  package Unsigned_Char_IO is new Ada.Sequential_IO (C.Unsigned_Char);
  The_File : Unsigned_Char_IO.File_Type;
  The_Unsigned_Char : C.Unsigned_Char;
begin
  Text_Io.Put_Line (Integer'Image (C.Unsigned_Char'Size));
  Text_Io.Put_Line ("16-bit CRCs (x1021) by file:");
  Text_Io.Put_Line ("(Using imported C subprograms)");
  Init_CRC;
  for F in 1 .. Command_Line.Argument_Count loop
    Text_IO.Put=20
	("File """ &
	 Command_Line.Argument (F));
    begin
      Unsigned_Char_IO.Open
	  (File =3D> The_File,
	   Name =3D> Command_Line.Argument (F),
	   Mode =3D> Unsigned_Char_IO.In_File);
    exception
       when Text_Io.Name_Error =3D>
	 Text_IO.Put_Line (""": -- NOT FOUND!");
    end;
    if Unsigned_Char_IO.Is_Open (The_File) then
      Current_CRC_Accumulation :=3D 0;
      while not Unsigned_Char_IO.End_Of_File (The_File) loop
	Unsigned_Char_IO.Read=20
	    (Item =3D> The_Unsigned_Char,
	     File =3D> The_File);
	Current_CRC_Accumulation :=3D Updated_CRC
	    (Previous_CRC_Accumulation =3D> Current_CRC_Accumulation,
	     Current_Byte              =3D> The_Unsigned_Char);
      end loop;
      Unsigned_Char_IO.Close (The_File);
      Text_IO.Put (""":");
      Unsigned_Short_IO.Put
	  (Item  =3D> Current_CRC_Accumulation,
	   Width =3D> 10,
	   Base  =3D> 16);
      Text_IO.New_Line;
    end if;
  end loop;
 =20
  Text_Io.Put_Line ("(Using Ada subprogram)");
  for F in 1 .. Command_Line.Argument_Count loop
    Text_IO.Put=20
	("File """ &
	 Command_Line.Argument (F));
    begin
      Unsigned_Char_IO.Open
	  (File =3D> The_File,
	   Name =3D> Command_Line.Argument (F),
	   Mode =3D> Unsigned_Char_IO.In_File);
    exception
       when Text_Io.Name_Error =3D>
	 Text_IO.Put_Line (""": -- NOT FOUND!");
    end;
    if Unsigned_Char_IO.Is_Open (The_File) then
      Current_CRC_Accumulation :=3D 0;
      while not Unsigned_Char_IO.End_Of_File (The_File) loop
	Unsigned_Char_IO.Read=20
	    (Item =3D> The_Unsigned_Char,
	     File =3D> The_File);
	CRC_Pkg.Update
	    (The_Crc_Value =3D> Interfaces.Unsigned_16 =
(Current_CRC_Accumulation),
	     With_The_Byte =3D> Interfaces.Unsigned_8 (The_Unsigned_Char));
      end loop;
      Unsigned_Char_IO.Close (The_File);
      Text_IO.Put (""":");
      Unsigned_Short_IO.Put
	  (Item  =3D> Current_CRC_Accumulation,
	   Width =3D> 10,
	   Base  =3D> 16);
      Text_IO.New_Line;
    end if;
  end loop;
 =20
end Test_CRC;

------=_NextPart_000_01BC292F.C954A260--

Re: CRC in Ada?

[Laurent Pautet]

>>>>> "John" == John B Matthews <jmatthews@nova.wright.edu> writes:

John> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked
John> the PAL and several other archives without luck. Any help
John> appreciated.

I looked at this a while ago. I remember that there is such a piece of
code in the PAL, it is called occ (compression algorithm).

Is Ada absolutly needed here ? You can interface with existing
software. Recently, we added compression filtering to GLADE and we
reused the Z library. I am almost sure that there is a CRC code in
this library.

-- 
-- Laurent

Re: CRC in Ada?

[Jon S Anthony]

In article <dewar.857612984@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Jon Anthony asks
> 
> <<That sounds very odd.  Did you use very different implementation
> styles?  For example, maybe use unconstrained types in the Ada or some
> such?  In general I would think a similar implementation style here
> would yield basically the same "efficiency" result.>>
> 
> One possibility is that the implementation was relying on doing rotates,
> and there certainly is no easy portable efficient way of doing that
> in Ada 83 (although for my taste I prefer to use table lookup for
> computing CRC's and avoid the bit rotation stuff.

Right.  That's a good example of the sort of thing I was fishing for,
but I guess it really had to do with the IO involved...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[david]

On Sunday, March 2, 1997 3:00:00 AM UTC-5, Dr. John B. Matthews wrote:
> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
> PAL and several other archives without luck. Any help appreciated.
> 
> Thanks,
> 
> John
> ----------------------------------------------------------------
> John B. Matthews, M.D.
> jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
> "Whom the gods would destroy, they first invite to program in C"

I had to write a crc library in Ada back in 2004.  But I can't post it.  Sorry.

Re: CRC in Ada?

[Adam Beneschan]

On Thursday, November 14, 2013 9:39:54 AM UTC-8, david wrote:
> On Sunday, March 2, 1997 3:00:00 AM UTC-5, Dr. John B. Matthews wrote:
> 
> > Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
> > PAL and several other archives without luck. Any help appreciated.
> 
> > Thanks,
> 
> > John

> I had to write a crc library in Ada back in 2004.  But I can't post it.  Sorry.

What a bummer!  He waited sixteen and a half years for you to help him, only to find out that you couldn't post your answer.  Sort of reminds me of how the people waiting for Deep Thought's answer must have felt ...  :) :) :)

                                  -- Adam

Re: CRC in Ada?

[tmoran]

On a Walnut Creek CD ROM dated 11/1997 I see "crcada95.ada"
  --| AUTHOR          -- Dr. Guido DUERINCKX, 1996-1997                         |--
  --| PROBLEM SUBJECT -- Implementation of the POSIX/UNIX95 CRC algorithm.      |--
I trust the OP (March 2, 1997) has already found it or another.  ;)

Re: CRC in Ada?

[Dmitry A. Kazakov]

On Thu, 14 Nov 2013 09:39:54 -0800 (PST), david wrote:

> On Sunday, March 2, 1997 3:00:00 AM UTC-5, Dr. John B. Matthews wrote:
>> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
>> PAL and several other archives without luck. Any help appreciated.

From simple components:

http://www.dmitry-kazakov.de/ada/components.htm

   function Fletcher_16
            (  Data : Stream_Element_Array;
               Last : Stream_Element_Offset
            )  return Stream_Element_Array is
      Sum_1 : Unsigned_16 := 16#FF#;
      Sum_2 : Unsigned_16 := 16#FF#;
      Index : Stream_Element_Offset := Data'First;
   begin
      for Major in 1..(Last - Data'First + 1) / 21 loop
         for Index in Major * 21 - 20..Major * 21 loop
            Sum_1 := Sum_1 + Unsigned_16 (Data (Index));
            Sum_2 := Sum_2 + Sum_1;
         end loop;
         Sum_1 := (Sum_1 and 16#FF#) + Sum_1 / 2**8;
         Sum_2 := (Sum_2 and 16#FF#) + Sum_2 / 2**8;
      end loop;
      Sum_1 := (Sum_1 and 16#FF#) + Sum_1 / 2**8;
      Sum_2 := (Sum_2 and 16#FF#) + Sum_2 / 2**8;
      return
      (  1 => Stream_Element (Sum_1 and 16#FF#),
         2 => Stream_Element (Sum_2 and 16#FF#)
      );
   end Fletcher_16;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: CRC in Ada?

[John B. Matthews]

On 11/14/13, 12:39 PM, david wrote:
> On Sunday, March 2, 1997 3:00:00 AM UTC-5, Dr. John B. Matthews wrote:
>> Hi! Can anyone point me to 16-bit CRC code in Ada? I've checked the
>> PAL and several other archives without luck. Any help appreciated.
>> [...]
> I had to write a crc library in Ada back in 2004. But I can't post it. Sorry.
>

Gratefully, I acknowledge receiving many helpful replies in the original
thread, cited here for reference:

<https://groups.google.com/d/msg/comp.lang.ada/nIbrE905UGY/ZRCFlQbP2r4J>

John
-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: CRC in Ada?

[tmoran]

> it never worries me to interface to C where that is appropriate
 Me neither.  But it does worry me if interfacing to C is appropriate
too often.
 Multi-language projects are more work to maintain.  C (or special OS
calls) are less portable.  It's hard to argue strongly for Ada while
also saying "except for the parts Ada can't do well" (even if that
really means except for the parts this particular Ada compiler doesn't
do well).  And consider the start of this discussion:  someone
translated a small program from C to Ada and found it ten times
slower.  I don't know what happened in that particular case, but often
that sort of thing results not in investigation of how to get around
the weak points of the Ada compiler/library, but rather in non-use of
Ada because "Ada is ten times slower".
  There should be *very* few cases where C is the more appropriate
language.

Re: CRC in Ada?

[Robert Dewar]

tmoran said

<< Multi-language projects are more work to maintain.  C (or special OS
calls) are less portable.  It's hard to argue strongly for Ada while
also saying "except for the parts Ada can't do well" (even if that
really means except for the parts this particular Ada compiler doesn't
do well).  And consider the start of this discussion:  someone
translated a small program from C to Ada and found it ten times
slower.  I don't know what happened in that particular case, but often
that sort of thing results not in investigation of how to get around
the weak points of the Ada compiler/library, but rather in non-use of
Ada because "Ada is ten times slower".>>

First, it simply is not the case that using some interfaced C functions
makes projects harder to maintain. That seems pure FUD to me. Almost
every big Ada program I have worked on has odd bits of interfaced
stuff around (after all the reason we worked so hard on improving the
functionality and portability of language interfacing features in Ada
95 was precisely that this is a perfectly reasonable way to structure
programs. At some level nearly any big program will be multi-language
since at some level it will use bindings that interface to foreign
languages and systems.

As for the 10x faster, it is also easy to find examples where a small
Ada program recoded in C in a casual manner runs 10 times slower in C.
Anyone who makes language decisions based on uncritical analysis of
isolated data points of this kind without investigating the source
of the difference is either incompetent, or looking for an excuse to
make a decision that they wanted to make for other reasons anyway.

Re: CRC in Ada?

[Tom Moran]

> As for the 10x faster, it is also easy to find examples where a small
> Ada program recoded in C in a casual manner runs 10 times slower in C.
  Could folks who've had this happen, or the other way, please give us
some counts on the frequency of such occurrences?  I must admit I
suspect there are many more cases where a tiny program 'recoded from C
to Ada in a casual manner' is slower in Ada than the opposite.  But
perhaps those are just the ones I remember.

> Anyone who makes language decisions based on uncritical analysis of
> isolated data points of this kind without investigating the source
> of the difference is either incompetent, or looking for an excuse to
> make a decision that they wanted to make for other reasons anyway.
  But it would be nice if they weren't handed an excuse easily.

Re: CRC in Ada?

[Joakim Olsson]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote in article
<dewar.858314609@merv>...
> tmoran said
> 
> 
> As for the 10x faster, it is also easy to find examples where a small
> Ada program recoded in C in a casual manner runs 10 times slower in C.
> Anyone who makes language decisions based on uncritical analysis of
> isolated data points of this kind without investigating the source
> of the difference is either incompetent, or looking for an excuse to
> make a decision that they wanted to make for other reasons anyway.
> 
I Just wanna agree with you Robert,

and some comments...

I have been programming Ada now for 6 years and I've never seen a Ada
program being slower than C, not large programs anyway (maybe in the early
years on PC).
Maybe it was slow in the early years but know it's great.
You also get a good code that does'nt CRASH all the time because you did'nt
thought of... what's it called... pointer and other C-trash.

/jake

Re: CRC in Ada?

[Tom Moran]

> Anyone who makes language decisions based on uncritical analysis of
> isolated data points of this kind without investigating the source
> of the difference is either incompetent, or looking for an excuse to
> make a decision that they wanted to make for other reasons anyway.
> 
  This really marks the crux of our disagreement.  To me the point is
not "he chose not-Ada unfairly" but rather "he chose not-Ada".

  I certainly agree that choosing a language based on a single test with
a tiny program would be most unwise.  But there are people who do it. 
I'd rather have those people choose Ada than choose against Ada.  Not
only would that give hope that their wisdom might be increased, it would
also make their software, which I might someday depend on, work better.
  Both the design and the implementation of Ada must take marketing into
account - or else.  For example, suppose Ada 0X had a postfix ++
operator, analogous to C's, but guaranteed task safe, and to guarantee
this some compiler generated RTS tasking calls.  X++ on such a system
might well take quite a bit longer than X++ on C, but it would be safer.
A sophisticated Ada programmer would know not to use X++ unless he
actually needed it, but someone transliterating a little C program just
to try out the trial version Ada compiler they had just downloaded would
likely use X++, be horrified by the program's slowness, and drop all
notion of using Ada.  I would call that a bad outcome and would find
little solace in calling such a person incompetent.

Re: CRC in Ada?

[Jon S Anthony]

In article <5g98ai$gqi@news2.delphi.com> tmoran@bix.com writes:


> calls) are less portable.  It's hard to argue strongly for Ada while
> also saying "except for the parts Ada can't do well" (even if that

I know what you are trying to get at here.  But the odd thing is, this
sort of thing is true of anything (in this context: PL), so why isn't
it hard to argue for, say, C while also saying "except for the parts C
can't do well".  Like nearly _all_ the aspects of any major piece of
software - not some of the low level bit twiddly stuff on some
platforms.


> translated a small program from C to Ada and found it ten times
> slower.  I don't know what happened in that particular case, but often
> that sort of thing results not in investigation of how to get around
> the weak points of the Ada compiler/library, but rather in non-use of
> Ada because "Ada is ten times slower".

Yes, that's the sort of myopia that does abound.  But, why only here?
After all, there are a lot of stories that I know of personally where
the gist is something like: "Yeah, we used C for this large piece of
work which needed to run on many platforms.  We had tons of your
typical SIGSEGV problems and memory leaks up the wazoo. And to make
the code portable we had a nightmare with all the #ifdefs in the
source.  But we basically got it done and now we're looking at doing
something similar for this other project."

Why wasn't the reaction, "This experience has led us to reject out of
hand the use of C again for nearly all the major work on this new
project.  Certain bits will be more appropriate in C, but most of it
will be in X.  Quite frankly, the idea of using C here would make us
all want to head for the hills as fast as possible."

>   There should be *very* few cases where C is the more appropriate
> language.

There *are* very few *places* (areas, kind of work, what-have-you)
where C is the more appropriate language.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: CRC in Ada?

[Richard A. O'Keefe]

tmoran@bix.com writes:
>> it never worries me to interface to C where that is appropriate
> Me neither.  But it does worry me if interfacing to C is appropriate
>too often.

Aren't we in danger of forgetting the POSIX binding for Ada?
If C can do IO efficiently on UNIX, it's because it can do system calls.
THERE IS NO REASON TO EXPECT C IO TO BE EFFICIENT ON OTHER SYSTEMS, and
in fact it often _isn't_ efficient.  One of the last things I did for
Quintus, whose Prolog system was layered on top of C stdio, was to
design a new IO interface that could be efficiently layered directly
on top of QSAM or RMS or UNIX system calls, without incurring the
overheads of going through getc() and its close relatives.  Ada
stream-IO buffers look amazingly familiar...

-- 
Will maintain COBOL for money.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.