On Sat, 11 Jun 2022 at 07:09, Sumanth Rajkumar <rajkumar.suma...@gmail.com>
wrote:
> Hi Alex and Gilles,
>
> For the complex functional interfaces, we have so far been working on
> different options but all operate on single complex numbers one at a
> time...
>
> Instead can we design around Functional Interfaces that work on List/Arrays
> instead?
>
An interesting approach. IIUC this approach is to allow parallel
optimisation. So the question is what computations would be performed in
parallel on a large set of numbers? I am wondering if all the ISO c99
functions would ever be used in this way. And if they are, how well they
would optimise given the high number of branch statements in many of the
functions to handle edge cases. The optimisation is performing:
for i in range:
x(i) = f(x(i))
So you have to provide a function to operate on a number to obtain another
number. How is this coded in the Java Vector API for simd support?
Would a single layer of abstraction mapping a double[] (in the list) to
ComplexNumber (for the function input) and back (from the function output)
impact performance?
<-- SNIP -->
>
> Interface ComplexDoubleArray{
>
> DoubleStream realAndImgPairs (int index, int length)
>
> <-- SNIP -->
A stream would have to have the pair of [real, imag] as the unit that the
stream operates on. It cannot be a (possibly interleaved) stream of each
part otherwise no function can operate on the whole complex number. Any API
would require:
Stream<T> stream(int index, int length)
with T the type of the complex number.
...
>
> }
>
> @FunctionalInterface
> Interface ComplexDoubleUnaryOperator{
>
> void apply(ComplexDoubleArray input, ComplexDoubleArray output, int
> inputoffset, int outputoffset, int length);
>
> }
>
> This has following advantages
>
> 1) iterating implementations over lists will now be in the complex function
> instead of ComplexList data structures allowing for different
> implementations. For example we could have multi threaded java.util.stream
> based operation on lists and single threaded cursor while loop based
> implementation as suggested before by Alex.
>
Thinking about streams...
For multi-threaded stream based operation this would:
- Create the stream with a start and end point
- Create a custom Spliterator holding the range limits
- Allow division of the Spliterator which handles dividing the range until
no more divisions are required (max threads reached)
Thus the final unit to operate on is an unknown range (this is known to the
Spliterator) of numbers. The unit for the functional interface is then
ComplexDoubleArray:
interface ComplexDoubleArray {
Stream<ComplexDoubleArray> stream(int start, int length);
}
ComplexDoubleArray a;
// Will use the Java 8 ForkJoinPool.commonPool() for parallel execution
a.stream(start, length).parallel().forEach(x -> ComplexFunctions.conj(x,
x));
class ComplexFunctions {
static void conj(ComplexDoubleArray in, ComplexDoubleArray out);
}
So for streams the operations are required to operate on a range that is
unknown. Internally the method must then have a way to access each entry of
the ComplexDoubleArray, which is effectively a List<Complex>.subList(...).
Did you envision a different implementation?
> 2) it will be required to take advantage of simd parallelism as discussed
> before. For example conjugate operation on Complex list (double[] of real
> and imaginary pairs) would be vector multiplication with array [
> 1,-1,1-1,..]
>
> If functional interface enforce operation on one complex number at a time,
> we might not be able take advantage of simd optimizations?
>
IIUC the Java vector API is for multiplications, additions, and other
arithmetic on primitives. The API is not finalised but it appears to have
support for pow and sqrt elementary functions. So this would not allow full
support for the ISO c99 elementary functions in Complex. Also the API
requires a primitive array to be converted to a Vector species and operated
on.
So perhaps to support this only requires that any list of complex numbers
can return the real and imaginary parts:
interface ComplexList {
void getReal(int start, int length, double[] dest);
void getImaginary(int start, int length, double[] dest);
// set methods
}
Then the functions can be written to extract the parts from the list,
operate on them using the Java vector API and return them to the list.
These functions would have an advantage on simple primitive operations. But
any functions that require conditional logic may not be optimised (this is
not clear from the examples I found). So for instance the multiplication of
two complex numbers performed using:
(a + i b)(c + i d) = (ac - bd) + i (ad + bc)
final double ac = a * c;
final double bd = b * d;
final double ad = a * d;
final double bc = b * c;
double x = ac - bd;
double y = ad + bc;
The result x and y are then checked for NaN and suitable infinities
recovered which requires a lot of logic. This logic may have to be moved
out of the vector optimised loop and performed after on the result arrays.
>
> 3) operation on single complex number is now just operation on list/array
> of size 1. We can make existing Complex class implement ComplexDoubleArray
> interface
>
Currently the abstraction to an array does not seem like an approach that
fits all requirements. It may be that the api should operate on some type
of ComplexNumber unit and have a separate support for operating on vector
arrays within the limitations of the Java Vector API.
Alex
