Implement Reflect method

[pinpox]

For various mathematical applications it would be useful to have a reflection method that mirrors the array around a given axis.

For a 2D example:

1 2 3
4 5 6
7 8 9

reflected around the Y-axis, this should result in:

3 2 1
6 5 4 
9 8 7

I'm trying to implement this for n-dimensional objects. The operation is simple: leave all indices as they are, except the ones of the given axis which equal (size at that axis)-(original position)

For a 2D matrix that could be implemented as:

func (a *Array64) ReflectX() {
	tmp := a.C()
	for x := 0; x < int(a.shape[0]; x++ {
	        for y := 0; y < int(a.shape[1]; y++ {
		        val := a.Get( x,y)
		        tmp.Set( a.shape[0] - x ,y )
	        }
        }
	a = tmp
}

func (a *Array64) ReflectY() {
	tmp := a.C()
	for x := 0; x < int(a.shape[0]; x++ {
	        for y := 0; y < int(a.shape[1]; y++ {
		        val := a.Get( x,y)
		       tmp.Set(x,  a.shape[1] - y  )
	        }
        }
	a = tmp
}

Since I can't make a method for every axis (unknown number of axis), I need a general method that takes the axis to flip around as parameter. Also I can't add a nested for loop for every axis, since I don't know how many there are.

// Reflect mirrors the array at around a given axis
func (a *Array64) Reflect(axis int) {

        if len(a.shape) < axis {
                /*handle error, invalid axis */
        }

	tmp := a.C()

	for i := 0; i < int(a.shape[axis]); i++ {
		val := a.Get(/*other axis before*/, i, /*other axis following*/)
		tmp.Set(val, /*other axis before*/, a.shape[axis] - i /*other axis following*/)
	}

	a = tmp
}

I have trouble filling in the blanks (see comments in code above). How do I go about implementing this?
More generally: How do I loop through all axis with indexes?

[Kunde21]

This might be connected to the other problem I've been trying to solve: Slicing and views.

An idea that came up in conversation was changing the structure of the Array64 (and ArrayB) structs to include an offset and allow negative strides. That way the (a *Array64) Reflect(axis int) *Array64 could just change the offset and stride for that axis, without the expensive copying.

ex:

ype Array64 struct {
	shape        []uint64
	strides      []int64
	offset       []int64
	data         []float64
	err          error
	debug, stack string
}

This would require a bunch of re-working for validation and accessing in other methods, but the basis of indexing would become:

func (a *Array64) at(index []uint64) float64 {
	var idx uint64
	for i, v := range index {
		idx += a.offset[i] + v * a.strides[i+1]
	}
	return a.data[idx]
}

I'm not sure how big of an impact it would have on the collapse (fold) method, either. That's a big, complex method, but important for a lot of other functionality. I just haven't had the time to sit down and sketch it out. It seems like a sizable, but necessary, undertaking. There's still no clear plan for slicing, either. The idea I had was:

type SliceIndx struct{
	axis, start, end, stride int
}
func (a *Array64) Slice( indices SliceIndx...) *Array64

It seems verbose, but I haven't seen a better way to do it that avoids a single method call per axis.

[pinpox]

That sounds interesting! is this planned to be implemented anytime soon? If so do you need help somewhere?

In the meanwhile I found a way to traverse a multidimensional array with recursion. I assume the method you outlined above would be a lot faster though.

[pinpox]

Sorry for double commenting:

I started to implement the new structure you proposed for Array64.

type Array64 struct {
	shape        []uint64
	strides      []int64
	offset       []int64
	data         []float64
	err          error
	debug, stack string
}

Throughout the whole code I have to insert a lot of casts from uint64() to int64() and vice versa.
I did some reading on int vs int64 vs uint64.

Here is a comment from stackoverflow on the performance of the different data types:

int and uint are only 64-bit on 64-bit architectures. On 32-bit architectures they are 32 bits.
The general answer is that, unless you need a certain precision, sticking with datatypes that are the same size as a word on the current architecture (e.g. 32 bits on a 32-bit architecture) is typically slightly more efficient.

(https://stackoverflow.com/questions/16427416/what-are-the-advantages-of-the-general-types-int-uint-over-specific-types-i)

Unless there is a specific reason not to do so I would propose to change the structure to:

type Array64 struct {
	shape        []int
	strides      []int
	offset       []int
	data         []float64
	err          error
	debug, stack string
}

Sure, a negative shape doesn't make much sense, but that could be checked on creation of the array with a simple if-statement to throw an error on negative shapes. The code would become much more readable and easier to maintain. Also it seems that it would not change the performance or even benefit it .

Let me know what you think. I'll be submitting a pull request in case you are interested to merge it.

EDIT: What would the Reflect() method look like after these changes, does it just negate the stride like this?

//Reflect reflects the array around a given axis
func (a *Array64) Reflect(axis int) {
	a.strides[axis-1] = -a.strides[axis-1]
}

[Kunde21]

This is a good first step in getting offsets incorporated. All indexing into the data slice will need to be re-evaluated to get that built in, though. None of the assembly code assumes an offset or negative strides, so we'll need to build the go code in numgo/internal for Proof of Concept and figure out if adding that to the assembly is viable.

Once that is done, Reflect would look like:

func (a *Array64) Reflect(axis int) *Array64 {
    if a.validx(axis) { // Validate inputs & check errors }
    a.strides[axis] = -a.strides[axis]
    a.offset[axis-1] = a.shape[axis-1]-1
    return a
}

[pinpox]

At the moment, the offset field is just added but doesn't really do anything. The indexing should be pretty much unchanged (tests were still passing). Let's get the casts removed, the code cleaned up then continue on this issue.

I wont be able to help with the assembly codes, I have never worked with that. If you think it is doable in go without loosing performance I'd be happy to implement some of the functions. In that case maybe #5 should be reconsidered.

[Kunde21]

All of the assembly routines have fallback functions in go, because not all environments allow asm (Google App Engine, for one). The noasm build tag forces everything to be built with the native go instead of asm (go build -tags noasm and go test -tags noasm). Once we get the go code updated, optimized, and tested; I can update the assembly.

[pinpox]

Without any changes I can't run the tests. Do I have to tell the build process to use the fallbacks explicetely?
This is my output when runninggo test -tags=noasm .

binaryplease➜github.com/Kunde21/numgo(offset)» go test -tags=noasm .                                                                                                                                     [17:08:32]
# github.com/Kunde21/numgo
./arithmetic_test.go:13: undefined: asm.Sse3Supt
./arithmetic_test.go:13: undefined: asm.AvxSupt
./arithmetic_test.go:13: undefined: asm.FmaSupt
./arithmetic_test.go:13: undefined: asm.Avx2Supt
./arithmetic_test.go:31: undefined: asm.AvxSupt
./arithmetic_test.go:34: undefined: asm.AvxSupt
./arithmetic_test.go:40: undefined: asm.AvxSupt
./arithmetic_test.go:453: undefined: asm.AvxSupt
./arithmetic_test.go:456: undefined: asm.AvxSupt
./arithmetic_test.go:465: undefined: asm.AvxSupt
./arithmetic_test.go:465: too many errors
FAIL	github.com/Kunde21/numgo [build failed]

[Kunde21]

That's my fault. I pushed the changes to fix the noasm builds in commit 0e692b5 today.