Structure alignment / AVX instructions

[Stephen Gutekanst]

Hi,

I have been playing with plan 9 assembly and Go both out of curiosity and with hope of providing a AVX accelerated vector math package. Right now I am using unaligned AVX instructions and the performance is just a tad better than 6g's generated assembly, I think that if I could use the aligned instructions it might improve performance more. But is it possible to?

The Intel manual I am reading through [1] mentions that the aligned instructions I wish to use require data to be 32-byte aligned, is it possible to achieve this with a Go datatype?:

type Vec64 [4]float64

I know C/C++ compilers offer ways to explicitly align data to n-byte boundaries, and I have read the Go spec[2] on this topic and played with the unsafe package a lot but it seems like there is no way explicitly make a Go datatype 32-byte aligned?

[1] https://software.intel.com/sites/default/files/managed/68/8b/319433-019.pdf

[2] http://golang.org/ref/spec#Size_and_alignment_guarantees

[Kevin Gillette]

Go automatically pads an aligns data on all the currently supported architectures. builtin 32-bit types will by aligned to a multiple of 4 bytes, 64-bit types will be aligned to a multiple of 8-bytes. Structs are aligned such that the alignment requirements of the struct members are met. You can use unsafe.Alignof to see how your types are being aligned.

[Stephen Gutekanst]

Thanks for the prompt response. It seems like I must be misunderstanding something. The spec says:

The following minimal alignment properties are guaranteed:

1. For a variable x of any type: unsafe.Alignof(x) is at least 1.
2. For a variable x of struct type: unsafe.Alignof(x) is the largest of all the values unsafe.Alignof(x.f) for each field f of x, but at least 1.
3. For a variable x of array type: unsafe.Alignof(x) is the same as unsafe.Alignof(x[0]), but at least 1.

For an array type, unsafe.Alignof is the same as the array's first element type, so no explicit alignment of an array is allowed (so I should be using a struct).

2. A struct is always aligned to it's *largest* field's alignment?:

type A struct { 

    A float32

    B complex128

} 

unsafe.Alignof(x.A) == 4 

unsafe.Alignof(x.B) == 8 

Thus: unsafe.Alignof(x) == 8

Which still leaves me asking: how can I achieve 32-byte alignment on a struct? The unsafe package mentions:

Alignof returns the alignment of the value v. It is the maximum value m such that the address of a variable with the type of v will always be zero mod m. If v is of the form structValue.field, it returns the alignment of field f within struct object obj.

The last part here structValue.field returning the alignment of field f within the struct object makes me think that I can add some padding or something manually to a struct to change it's alignment?

type A struct {
_ byte // Padding?
A float32
B float64
}

But alas the same results occur:

unsafe.Alignof(v):  8
unsafe.Alignof(v.A):  4
unsafe.Alignof(v.B):  8

I'm new to data alignment in general and have been profusely reading up on it over the past few days -- so if there is something obvious I am missing go easy on me.

Stephen

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/IfKlAkvvSds/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Follow me on twitter @slimsag.

[Tamás Gulácsi]

Afaik 32byte aligned array's elements are 32byte-aligned, so a []struct{IntVal int64, pad [24]byte} will be ok.

[peterGo]

Stephen,

"I'm new to data alignment in general and have been profusely[sic] reading up on it over the past few days -- so if there is something obvious I am missing go easy on me."

Here's a simple example and description of alignment (padding and packing). Is there anything that you don't understand about the sample output?

package main

import (
    "fmt"
    "unsafe"
)

type A struct {
    _ byte // Padding?

    X float32
    Y float64
}

func main() {
    var a A
    fmt.Printf("A:   %p %d %d\n", &a, unsafe.Alignof(a), uintptr(unsafe.Pointer(&a))%unsafe.Alignof(a))
    fmt.Printf("A.X: %p %d %d\n", &a.X, unsafe.Alignof(a.X), uintptr(unsafe.Pointer(&a.X))%unsafe.Alignof(a.X))
    fmt.Printf("A.Y: %p %d %d\n", &a.Y, unsafe.Alignof(a.Y), uintptr(unsafe.Pointer(&a.Y))%unsafe.Alignof(a.Y))
}

/*
Sample Output:

A:   0xc208000150 8 0
A.X: 0xc208000154 4 0
A.Y: 0xc208000158 8 0
*/

/*
References:

Algorithms and Data Structures
N. Wirth 1985 (Oberon version: August 2004).
http://www.inf.ethz.ch/personal/wirth/AD.pdf

1.6 Representation Of Arrays, Records, And Sets
1.6.1 Representation of Arrays
1.6.2 Representation of Records
*/

http://play.golang.org/p/dM_BEPH5FV

Peter

[Kevin Gillette]

On Sunday, May 25, 2014 12:33:48 AM UTC-6, Stephen Gutekanst wrote:

For an array type, unsafe.Alignof is the same as the array's first element type, so no explicit alignment of an array is allowed (so I should be using a struct).

That's a misread. Arrays in Go (like everything else) are statically typed -- _every_ element in an array/slice is the same type and has the same alignment and sizing characteristics. The spec could just as well have said `unsafe.Alignof(x[1])`. For now, just assume that everything in Go is implicitly aligned to whatever is needed for aligned assembly instructions to "just work" (unless the assembly instructions require 8-byte or larger alignment on a 32-bit system, or 16-byte or larger alignment on a 64-bit system). IIRC, the first element of an array allocation will be aligned to a word boundary regardless of whether the element is smaller than a word. If you're running a *IMD instruction on a subslice of that data which doesn't start at a word-size-multiple (or required-alignment-multiple) offset, then you might have to do some special handling (which consists of using unaligned instructions for the smallest unaligned leading/trailing portion [which is usually 1-7 elements at most], and then aligned instructions for the rest). There are examples of this in the stdlib (look at the "bytes" package's assembly files).

The only way to get misaligned data in Go is to use unsafe.Pointer manipulations, cgo, plan9 C, or assembly to write the data, and there's no guarantees that such misaligned data will be usable by Go once written anyway. By "misaligned", I mean a value in memory that doesn't start at an address which is a multiple of the value's size (e.g. an int16 starting an an odd-numbered address).

Please, you don't need to wrap things in structs to have them aligned. Go does the alignments you need already, and for any type.

The last part here structValue.field returning the alignment of field f within the struct object makes me think that I can add some padding or something manually to a struct to change it's alignment?

type A struct {
_ byte // Padding?
A float32
B float64
}

float32's are aligned by Go to a multiple of 32 bits, and float64's are aligned to a multiple of 64-bits, so what the above struct ends up looking like in memory, at least on a 64-bit system, is:

type A struct {

    _ byte    // bytes [0,1)

              // bytes [1,4) -- padding to align field A

    A float32 // bytes [4,8)

    B float64 // bytes [8,16)

}

In this case, B needs no additional padding because A just happens to end before byte 8. Compare to:

type A struct {

    A float32 // bytes [0,4)

              // bytes [4,8) -- padding to align field B

    B float64 // bytes [8,16)

}

[Stephen Gutekanst]

Afaik 32byte aligned array's elements are 32byte-aligned, so a []struct{IntVal int64, pad [24]byte} will be ok.

Tamás Gulácsi,

That doesn't appear to be true?: http://play.golang.org/p/6ekvvSwkWG

Peter,

Everything you described in your example I do understand, I do appreciate the help a lot though.

Kevin,

Right, I understand that it is not directly related to the first element of the array but the fact that all types in Go are statically typed (all elements of an array must use the same type).

everything in Go is implicitly aligned to whatever is needed for aligned assembly instructions to "just work" (unless the assembly instructions require 8-byte or larger alignment on a 32-bit system, or 16-byte or larger alignment on a 64-bit system)

The assembly instructions I wish to use do require 32-byte alignment, and it's on a 64-bit system (the AVX instructions mentioned in my initial mail).

Right now I am using the equivalent instructions which do not require 32-byte aligned data, and this works. But from what I have read this is slower than using the instructions which require 32-byte aligned data.

you might have to do some special handling (which consists of using unaligned instructions for the smallest unaligned leading/trailing portion [which is usually 1-7 elements at most], and then aligned instructions for the rest). There are examples of this in the stdlib (look at the "bytes" package's assembly files).

I can do this, yeah, and it would certainly make a large difference with larger data sets, but right now my data is *very* small, e.g.:

type Vec64 struct{

        X, Y, Z, W float64

}

At this point I still don't see a way to explicitly a small Go data type like the one mentioned above to 32-bytes without using some padding (although I'm not sure if this will work in all cases).

http://play.golang.org/p/qmftpezySJ

I really appreciate all your time on this,

Stephen

--

You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/IfKlAkvvSds/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Anthony Martin]

Stephen Gutekanst <stephen....@gmail.com> once said:
> [...]

>
> type Vec64 [4]float64
>
> I know C/C++ compilers offer ways to explicitly align data to n-byte
> boundaries, and I have read the Go spec[2] on this topic and played with
> the unsafe package a lot but it seems like there is no way explicitly make
> a Go datatype 32-byte aligned?

How do align something in C? You allocate a buffer with enough
extra space to cover the alignment requirement and then offset
from the beginning of the buffer until the first aligned member.

Something like,

typedef double Vec[4];

char buf[sizeof(Vec)+31];

v = (Vec*)((uintptr_t)(&buf[31]) & ~31);

It's essentially the same process in Go but note that you're
forced to use the unsafe package. Here's one way of doing it:

func aligned(n int) []float64 {
const align = 32 // alignment in bytes

v := make([]float64, n + align/8) // float64s are 8 bytes
for i := range v {
if uintptr(unsafe.Pointer(&v[i])) % align == 0 {
return v[i:]
}
}
panic("could not create aligned []float64")
}

Cheers,
Anthony

[Tamás Gulácsi]

So you want all the elements 32 byte padded, and not just the elements starting from the first - so you need to pad the first element, too:
http://play.golang.org/p/NP6sZrPkdU

Or I still don't understand.