Re: Complex numbers in the library

[Mike Griebling <grieblm@trt.allied.com>]

> Hi all!
> 
> - Functional, i.e. PROCEDURE sin(x: COMPLEX): COMPLEX;
>   - Advantages: Mathematical notation should be much easier to use.
>   - Disadvantages: Allocates a number on the heap with every invocation,
> which      is essentially a side effect and which would be extremely
> inefficient, both
>     in time and in heap fragmentation; also has space overhead for both the
> record header and the pointer. Overcoming these would require some rather 
>     difficult heap object lifetime analysis and a more advanced collector.

I agree that there is a definite overhead here but before we throw out this
implementation or replace it with alternatives perhaps we could implement an
efficient module which allows reuse of smaller records without requiring the
garbage collector.  I'm proposing something like a QuickHeap module which
keeps track of many fixed-size, small blocks very efficiently.  Of course,
to make all this work, we will have to disallow assignments of COMPLEX
numbers (this was always the case with this COMPLEX set of modules).

As well, before we go crazy, perhaps we should run some benchmarks on the
existing module and get some figures.  Of course, the current o2c compiler
will be much slower than the final optimizing compiler and Boehm's garbage
collector is probably also much slower than the final one will be.  Then,
perhaps an experimental implementation of the QuickHeap module could be
implemented and comparative benchmarks run.

I personally prefer leaving the implementation details of the COMPLEX numbers
within the module and hiding implementation details from users.  So, if arrays
of complex numbers are important, they should be defined in the same module(s).
This may point out a weakness of Oberon-2 in not giving structural visibility
to children of a module's data type while still hiding the details from users.
 
> - Procedural, i.e. PROCEDURE sin(x: COMPLEXDesc; VAR ret: COMPLEXDesc);
>   - Advantages: Greater space efficiency, allows the programmer to choose 
>     whether or not to heap-allocate the numbers. This style allows you to use 
>     arrays of COMPLEXDesc records when doing matrix/vector work. Such arrays 
>     have been typically implemented with one type header for the array and one
>     for _all_ of the elements. If the elements had to be allocated individually,
>     there would be a space overhead of the pointer and a type header for _each_
>     element. This would get very big, very quick, and become very fragmented.
>   - Disadvantages: Using this notation would not be as easy for the programmer.
>     The users of this library would have to allocate the space for the numbers
>     themselves, and manage all of the temporaries. Many mathematicians would
>     like to avoid having to do this because it confuses the algorithms with
>     implementation details. 

I've used this notation in the past and it is a real pain.  Definitely not
recommended.  The array issue really is also not a user concern.  The user
should not be building their own arrays -- instead a COMPLEXVECTOR type should
be defined which the user can manipulate via exported functions.

> - Recycling Functional, i.e. PROCEDURE sin(x, ret: COMPLEX): COMPLEX;
>   The second parameter is either given a pointer to a preallocated COMPLEXDesc
>   that can be reused, or NIL. The result is returned from the function, either 
>   the recycled record or a newly allocated one with new values filling it.
>   - Advantages: Can be used in a functional style with only minor wierdness 
>     (none in a language with optional parameters, but that's another matter :).
>     If we are careful to minimize aliasing effects in the implementation, this
>     notation can be used to speed calculation dramatically and cut down on heap
>     fragmentation. The programmer that uses these functions can allocate one or
>     two temporaries early on, and these temporaries can be reused over and over
>     again. The compiler and collector would have fewer objects to do lifetime
>     analysis with. If the programmer doesn't want to go through the trouble of 
>     allocating temporaries, this notation has the same characteristics of the
>     first notation (you always have had to choose to recycle :).
>   - Disadvantages: This still has that space and time overhead of heap objects,
>     and doesn't strictly follow the math notation. The programmer has to do a
>     little work to speed things up that would be done by the compiler with the 
>     procedural notation.

Personally I don't like this approach since it invites a whole lot of problems
when programmers make mistakes about aliasing variables accidentally.  I *know*
someone will do this and they will spend a long time trying to trace down why
their mathematical calculations are coming out wrong.  I think it's better to
keep implementation details private (ie., whether someone is reusing the
data records or not).

> Complex math is currently implemented with the functional notation in the
> library. Here's my proposal for how the library could be implemented:
> 
> - Modules LowComplexMath and LowLongComplexMath, done in the Procedural style,
>   and exporting the COMPLEX and COMPLEXDesc types.
> - Modules ComplexMath and LongComplexMath, done in the Recycling Functional
>   style, implemented using the Low* modules, and exporting aliases to the Low*
>   types as their own.
> - Other modules yet to be determined that do math on arrays of COMPLEXDesc, 
>   using the Low* modules to do their dirty work.
> 
> This arrangement would allow you to do math in the functional style where it
> matters, i.e. with individual complex numbers, but would still allow you to
> use the procedural style where you really need to minimize overhead, i.e.
> when you are working with arrays or other large quantities of numbers.

I personally don't like this approach since it opens up the COMPLEX type to the
user who should remain ignorant of its contents.  A COMPLEX number should be
a monolithic type and no one should be able to get at the implementation
details -- that would just be inviting unwarranted dependencies on how the
COMPLEX numbers are implemented.
 
> So what do you think?
> Brian Hawley
> bhawley@luc.edu

Perhaps some experimentation with the existing implementation might be fruitful
before we change this module.  Your performance concerns seem to be foremost in
your mind and maybe there are other ways of addressing this issue such as with
an optimized small-block allocator/deallocator.

In reviewing the COMPLEX module(s) I did notice that there don't exist any COMPLEX
constructors (i.e., the CMPLX function should have been exported).  What is also
missing is an "assign" or "copy" function.

I'll make these changes and reupload the new modules.
 

Regards,
	Michael
--------------------------------------------------------------
Michael Griebling, P. Eng.		mgriebling@bix.com
Computer Inspirations			grieblm@trt.allied.com