🚀 go-pugleaf

Marco van de Voort (Marco.van.de.Voort@p18.f402.n284.z2.fidonet.org) wrote:

>Some things can't be done easily in Modula-2 (or TurboPascal or Basic)

>An example : try mirroring a BITSET of an arbritary size.

>        11001 becomes 10011.
>       110101 becomes 101011. etc.

That's an interesting example, because it comes up in connection
with implementing things like the Fast Fourier Transform.  The way
it arises - I imagine that Marco already knows this, but some
other readers might not - is that at certain points in the
calculation you have to rearrange an array such that, for all j,
A[j] has to be swapped with A[BitReverse(j)], where BitReverse(.)
is the transformation Marco mentions above.

Back when I was a novice programmer (1968), I had to implement
an FFT (in Fortran), and I came to the conclusion that two
short routines really had to be done in assembly language, for
efficiency.  One of them was the bit reversal operation, and
the other was the calculation of base 2 logarithms.  For this
I needed advice on how to use an unfamiliar assembly language,
and the response I got from the local experts was "well, we try
to discourage people from using assembly language".  I went ahead
with it anyway.  My final FFT implementation did work, although
the efficiency was not as good as I had expected.

This year I had to implement an FFT all over again, after 27
years of not having looked at the problem.  As it happened I
still had my old project report including things like the
results of timing tests, but the original source code was lost,
so I had to re-start the job from scratch.

This time around, with the benefit of greater experience, I
started with the attitude of "first get the algorithm working,
and only later look at the fine-tuning efficiency issues".
So I wrote the bit-reversal part in Modula-2, with the thought
that maybe later I would translate it into assembly language.
As the work progressed, I came to notice two things:
 (a) the bit-reversal calculation was not the main bottleneck
     in terms of speed.  Speeding up this part of the calculation
     had negligible effect on the overall speed, because the
     slow part was somewhere else.
 (b) the question "how do you reverse a bit string?" was not, in
     any case, the important question.  The real problem was
     "how do you shuffle an array into the desired order?"
     Doing it in terms of bit-reversing subscripts was one
     solution, but it was not the only possible solution.

By thinking a little harder about point (b), I came up with
a re-ordering algorithm which was significantly faster than the
obvious algorithm, and which incidentally did not require any
bit-reversal calculations.  In other words, the bit-reversal
problem simply went away, and I ended up not using any assembly
code at all.  If I had started thinking in terms of assembly
language - or any other methods of fine-tuning the code - I
would not have found the better algorithm.  By concentrating on
a high-level view of the problem, I came up with a very major
speed improvement rather than a small speed improvement.

(I would not have thought of that better algorithm in 1968, for
several reasons.  One of the reasons is that it required me to
think in terms of recursion, and Fortran discourages you from
thinking recursively.)

I'm not trying here to negate Marco's original point.  There may
well be applications where the bit-reversal problem is a
significant bottleneck, and in such cases an assembly language
solution will certainly beat a solution in any high-level
language, because no compiler is smart enough to work out things
like tricks you can do with the carry bit.  But it does take
a lot of experience to isolate the bottlenecks and to judge when
assembly language is worth using.  It's not too hard to teach a
student - at about second or third year level - the techniques
of "how do I do this in assembly language?"  It's very much harder
to answer questions of the form "Is it worth doing any of this in
assembly language; and, if so, which parts?"  The average programmer
will get WORSE efficiency, rather than better, by using assembly
language.  The small local gains will be negated by more serious
larger-scale losses.

I use assembly language myself in some situations - but only
when I'm very sure that it's needed.

This thread was started by someone who is probably a novice
programmer.  I think the right answer to a novice is to advise
that assembly language approaches never be used.  Student
programmers need to learn about machine and assembly languages
at some stage, but I think it should be done with the attitude
of "You're doing this subject so that you can learn about
machine architecture; it's not our goal to use assembly language
to speed up the code."  Much later in their careers they'll
develop the judgment needed to know when assembly language solutions
are appropriate.

On a completely different topic: in another posting, Marco
commented on the expression "not being able to see the wood for
the trees".  Yes, this is a well-known expression in the
English language; I didn't pick it up from Dutch.  (Ik kan
geen nederlands spreken.)  If it also occurs in Dutch, then I
guess it must be a very old expression that existed in the
common ancestor of the two languages.  Can anyone tell me
whether the expression also exists in German - or, for that
matter, in any other language?

--
Peter Moylan                       peter@ee.newcastle.edu.au
                           file://ee.newcastle.edu.au/pub/www/Moylan.html