bug#14599: An option to make vector allocation aligned

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

Hello,

If you want to access native uniform vectors from c, sometimes you 
really want guarantees about the alignment.

Fortunately the the (byte)vector format and allocation makes that pretty 
easy to implement: just add a little padding between the header and the 
actual data.

So for my own project, this is what I'm doing, and there shouldn't be 
much of a memory impact unless there are tons of small vectors used, 
which isn't very lispy anyway.

This isn't necessarily true for vectors created from pre-existing 
buffers (the take_*vector functions), but there you have control over 
the pointer you pass, so you can make it true if needed.

So if there is interest, maybe this could be integrated into the build 
system as a configuration like this:


--- libguile/bytevectors.c    2013-04-11 02:16:30.000000000 +0200
+++ bytevectors.c    2013-06-12 14:45:16.000000000 +0200
@@ -223,10 +223,18 @@

        c_len = len * (scm_i_array_element_type_sizes[element_type] / 8);

+#ifdef SCM_VECTOR_ALIGN
+      contents = scm_gc_malloc_pointerless (SCM_BYTEVECTOR_HEADER_BYTES 
+ c_len + SCM_VECTOR_ALIGN,
+                        SCM_GC_BYTEVECTOR);
+      ret = PTR2SCM (contents);
+      contents += SCM_BYTEVECTOR_HEADER_BYTES;
+      contents += (addr + (SCM_VECTOR_ALIGN - 1)) & -SCM_VECTOR_ALIGN;
+#else
        contents = scm_gc_malloc_pointerless 
(SCM_BYTEVECTOR_HEADER_BYTES + c_len,
                          SCM_GC_BYTEVECTOR);
        ret = PTR2SCM (contents);
        contents += SCM_BYTEVECTOR_HEADER_BYTES;
+#endif

        SCM_BYTEVECTOR_SET_LENGTH (ret, c_len);
        SCM_BYTEVECTOR_SET_CONTENTS (ret, contents);


It could even be possible to make the alignment a run-time decision, but 
for that the api and read syntax for vectors need to be extended. Which 
could be worthwhile ...

Apart from that, I see there are issues with the native mingw builds 
again, which I haven't noticed earlier since I primarily develop on 
linux, but I can reproduce the problem shown in #14361.


Regards

Jan Schukat

bug#14599: An option to make vector allocation aligned

[Ludovic Courtès]

severity 14599 wishlist
thanks

Hi!

Jan Schukat <shookie@email.de> skribis:

> If you want to access native uniform vectors from c, sometimes you
> really want guarantees about the alignment.

[...]

> This isn't necessarily true for vectors created from pre-existing
> buffers (the take_*vector functions), but there you have control over
> the pointer you pass, so you can make it true if needed.
>
> So if there is interest, maybe this could be integrated into the build
> system as a configuration like this:
>
>
> --- libguile/bytevectors.c    2013-04-11 02:16:30.000000000 +0200
> +++ bytevectors.c    2013-06-12 14:45:16.000000000 +0200
> @@ -223,10 +223,18 @@
>
>        c_len = len * (scm_i_array_element_type_sizes[element_type] / 8);
>
> +#ifdef SCM_VECTOR_ALIGN
> +      contents = scm_gc_malloc_pointerless
> (SCM_BYTEVECTOR_HEADER_BYTES + c_len + SCM_VECTOR_ALIGN,
> +                        SCM_GC_BYTEVECTOR);
> +      ret = PTR2SCM (contents);
> +      contents += SCM_BYTEVECTOR_HEADER_BYTES;
> +      contents += (addr + (SCM_VECTOR_ALIGN - 1)) & -SCM_VECTOR_ALIGN;
> +#else
>        contents = scm_gc_malloc_pointerless
> (SCM_BYTEVECTOR_HEADER_BYTES + c_len,
>                          SCM_GC_BYTEVECTOR);
>        ret = PTR2SCM (contents);
>        contents += SCM_BYTEVECTOR_HEADER_BYTES;
> +#endif
>
>        SCM_BYTEVECTOR_SET_LENGTH (ret, c_len);
>        SCM_BYTEVECTOR_SET_CONTENTS (ret, contents);

I don’t think it should be a compile-time option, because it would be
inflexible and inconvenient.

Instead, I would suggest using the scm_take_ functions if allocating
from C, as you noted.

In Scheme, I came up with the following hack:

--8<---------------cut here---------------start------------->8---
(use-modules (system foreign)
             (rnrs bytevectors)
             (ice-9 match))

(define (memalign len alignment)
  (let* ((b (make-bytevector (+ len alignment)))
         (p (bytevector->pointer b))
         (a (pointer-address p)))
    (match (modulo a alignment)
      (0 b)
      (padding
       (let ((p (make-pointer (+ a (- alignment padding)))))
         ;; XXX: Keep a weak reference to B or it can be collected
         ;; behind our back.
         (pointer->bytevector p len))))))
--8<---------------cut here---------------end--------------->8---

Not particularly elegant, but it does the job.  ;-)

Do you think there’s additional support that should be provided?

Thanks,
Ludo’.

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

On 06/12/2013 04:59 PM, Ludovic Courtès wrote:
> Instead, I would suggest using the scm_take_ functions if allocating
> from C, as you noted.

The whole point of me doing this is so I can use lisp files to define aligned data (and using lisp as a flexible text data format that can be compiled is the primary reason I use guile).

So either I make normal vectors aligned, or I define a whole new set of datatypes of aligned vectors with their own read syntax.

The former I just did today, the latter would take me probably a quite a bit of time to do properly. So, I'm gonna keep using my compile time option for now, and probably write a module of aligned vectors at some point in the future when I have more of an understanding what exactly the requirements for something like this would be.

Jan

bug#14599: An option to make vector allocation aligned

[Andy Wingo]

On Wed 12 Jun 2013 15:37, Jan Schukat <shookie@email.de> writes:

> If you want to access native uniform vectors from c, sometimes you
> really want guarantees about the alignment.

16 bytes I guess?  Guile's uniforms are 8-byte-aligned by default, as
you probably know.

Just wondering if there is a better default.

> +#ifdef SCM_VECTOR_ALIGN
> +      contents = scm_gc_malloc_pointerless (SCM_BYTEVECTOR_HEADER_BYTES
> + c_len + SCM_VECTOR_ALIGN,
> +                        SCM_GC_BYTEVECTOR);
> +      ret = PTR2SCM (contents);
> +      contents += SCM_BYTEVECTOR_HEADER_BYTES;
> +      contents += (addr + (SCM_VECTOR_ALIGN - 1)) & -SCM_VECTOR_ALIGN;
> +#else
>        contents = scm_gc_malloc_pointerless (SCM_BYTEVECTOR_HEADER_BYTES
> + c_len,
>                          SCM_GC_BYTEVECTOR);
>        ret = PTR2SCM (contents);
>        contents += SCM_BYTEVECTOR_HEADER_BYTES;
> +#endif

This is somewhat dangerous, as you could lose the pointer to the start,
and then the contents get collected.

I guess this can be fixed in master, if you set the "holder" field on a
bytevector to the actual memory that you allocate.

Andy
-- 
http://wingolog.org/

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

Thought a bit about it, and it would really be nice to have an aligned 
uniform vector API.

ATM all are 8 byte aligned, so you probably would want also to be able 
to have at least 16 and 32 byte alignment (intel's AVX has 256bit 
registers that better work aligned).
But even 64 and and more could be useful for cache line alignment, 
although that would require this to be a separate alignment, because the 
benefits of cache line alignment are kind of defeated if the header is 
in a different cache line.

So I guess just one alignment, namely that of the first element is 
feasible without wasting whole cache lines. If you really need that you 
can still use the take_*vector functions, and it's pretty rare to do 
such things anyway. But being able to control the alignment of the first 
element allows you to properly use simd instructions on those vectors.

You don't even really need any more space to store alignment 
information, since that can be directly inferred from the bytevector 
content pointer, although the bytevector flags still have more than 
enough space to store it.

Extending the programming api to support this is a bit more tricky. I 
guess most straightforward and backward compatible would be to just at a 
set of make-aligned-*vector and aligned-*vector and *->aligned-*vector 
functions and their scm_* versions with an additional alignment 
parameter. Optional alignment parameters on the old functions could be 
nice too, but I guess that is just asking for compatibility trouble.

The other question is the read syntax (one of the primary reasons I'm 
doing all this). If alignment is something that should be preserved in 
the permanent representation, you also need to store it in the flags, 
since the content pointer can be aligned by coincidence. I haven't 
looked at the compiling of bytevectors yet, to see if alignment can be 
handled easily there.

As for the text representation, I think the simplest way is to add 
another reserved character with the alignment number that works for 
uniform vectors and arrays like #vu8>8(1 2 3 4 5 6) to have the first 
element at 8byte alignment (right now the allocation pretty much ensures 
4 byte alignment of the first element on 32 bit machines and 8 byte at 
64bit machines, because gc_malloc returns 8byte aligned blocks, but the 
array starts at cell word 3. Any 64 bit type vector like double and long 
is already guaranteed to be misaligned on 32 bit platforms. Which would 
be even more unfortunate on linux x32 abi systems that uses efficient 64 
bit ints with 32 bit pointers, but cell size is determined by pointer size.

Or to construct simd 4 element arrays #2f32:2:4>16((1 2 3 4)(1 2 3 4)). 
Maybe even have a default alignment of 16 when you just use > without a 
number so #2f32:2:4>((1 2 3 4)(1 2 3 4)) is the same thing. Or even more 
convenient #m128((1 2 3 4)(1.0 1.0 1.0 1.0) (2.0 2.0)) where you can 
freely mix the underlying types and the size of the elements is inferred 
by the amount of them in each group.


So if there is interest for something like this in the main guile, I 
will make the patches. If not, I'll just stick to my crude hack for now 
and see if I need the full shebang :).


Regards

Jan Schukat


On 06/12/2013 04:59 PM, Ludovic Courtès wrote:
> severity 14599 wishlist
> thanks
>
> Hi!
>
> Jan Schukat <shookie@email.de> skribis:
>
>> If you want to access native uniform vectors from c, sometimes you
>> really want guarantees about the alignment.
> [...]
>
>> This isn't necessarily true for vectors created from pre-existing
>> buffers (the take_*vector functions), but there you have control over
>> the pointer you pass, so you can make it true if needed.
>>
>> So if there is interest, maybe this could be integrated into the build
>> system as a configuration like this:
>>
>>
>> --- libguile/bytevectors.c    2013-04-11 02:16:30.000000000 +0200
>> +++ bytevectors.c    2013-06-12 14:45:16.000000000 +0200
>> @@ -223,10 +223,18 @@
>>
>>         c_len = len * (scm_i_array_element_type_sizes[element_type] / 8);
>>
>> +#ifdef SCM_VECTOR_ALIGN
>> +      contents = scm_gc_malloc_pointerless
>> (SCM_BYTEVECTOR_HEADER_BYTES + c_len + SCM_VECTOR_ALIGN,
>> +                        SCM_GC_BYTEVECTOR);
>> +      ret = PTR2SCM (contents);
>> +      contents += SCM_BYTEVECTOR_HEADER_BYTES;
>> +      contents += (addr + (SCM_VECTOR_ALIGN - 1)) & -SCM_VECTOR_ALIGN;
>> +#else
>>         contents = scm_gc_malloc_pointerless
>> (SCM_BYTEVECTOR_HEADER_BYTES + c_len,
>>                           SCM_GC_BYTEVECTOR);
>>         ret = PTR2SCM (contents);
>>         contents += SCM_BYTEVECTOR_HEADER_BYTES;
>> +#endif
>>
>>         SCM_BYTEVECTOR_SET_LENGTH (ret, c_len);
>>         SCM_BYTEVECTOR_SET_CONTENTS (ret, contents);
> I don’t think it should be a compile-time option, because it would be
> inflexible and inconvenient.
>
> Instead, I would suggest using the scm_take_ functions if allocating
> from C, as you noted.
>
> In Scheme, I came up with the following hack:
>
> --8<---------------cut here---------------start------------->8---
> (use-modules (system foreign)
>               (rnrs bytevectors)
>               (ice-9 match))
>
> (define (memalign len alignment)
>    (let* ((b (make-bytevector (+ len alignment)))
>           (p (bytevector->pointer b))
>           (a (pointer-address p)))
>      (match (modulo a alignment)
>        (0 b)
>        (padding
>         (let ((p (make-pointer (+ a (- alignment padding)))))
>           ;; XXX: Keep a weak reference to B or it can be collected
>           ;; behind our back.
>           (pointer->bytevector p len))))))
> --8<---------------cut here---------------end--------------->8---
>
> Not particularly elegant, but it does the job.  ;-)
>
> Do you think there’s additional support that should be provided?
>
> Thanks,
> Ludo’.

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

Hello again :)


On 06/12/2013 10:37 PM, Andy Wingo wrote:
> On Wed 12 Jun 2013 15:37, Jan Schukat <shookie@email.de> writes:
>
>> If you want to access native uniform vectors from c, sometimes you
>> really want guarantees about the alignment.
> 16 bytes I guess?  Guile's uniforms are 8-byte-aligned by default, as
> you probably know.

Yes, 16 bytes. But more could be useful too. And as I have stated in my 
previous mail, the first element of the vector is guaranteed to be 4 
byte aligned on 32 bit machines, because it starts directly after the 3 
word header, which is allocated at 8 byte boundaries. And yes, I have 
tested this, but should be obvious from the code too.



>
> Just wondering if there is a better default.
>
>> +#ifdef SCM_VECTOR_ALIGN
>> +      contents = scm_gc_malloc_pointerless (SCM_BYTEVECTOR_HEADER_BYTES
>> + c_len + SCM_VECTOR_ALIGN,
>> +                        SCM_GC_BYTEVECTOR);
>> +      ret = PTR2SCM (contents);
>> +      contents += SCM_BYTEVECTOR_HEADER_BYTES;
>> +      contents += (addr + (SCM_VECTOR_ALIGN - 1)) & -SCM_VECTOR_ALIGN;
>> +#else
>>         contents = scm_gc_malloc_pointerless (SCM_BYTEVECTOR_HEADER_BYTES
>> + c_len,
>>                           SCM_GC_BYTEVECTOR);
>>         ret = PTR2SCM (contents);
>>         contents += SCM_BYTEVECTOR_HEADER_BYTES;
>> +#endif
> This is somewhat dangerous, as you could lose the pointer to the start,
> and then the contents get collected.
>
> I guess this can be fixed in master, if you set the "holder" field on a
> bytevector to the actual memory that you allocate.
>

Don't really understand the danger here, isn't this allocated as a whole 
block and only collected as a whole block too? What am I missing?

Having the arrays aligned according to their type by default could be a 
nice option, i.e. a word of padding for long and doubles on 32 bit 
machines, and then also introducing a new 16byte simd128 and 32 byte 
simd256 type id and their respective creation functions.


Regards

Jan Schukat

bug#14599: An option to make vector allocation aligned

[Ludovic Courtès]

Hi,

Thanks for sharing your thoughts on this!

Jan Schukat <shookie@email.de> skribis:

> Extending the programming api to support this is a bit more tricky. I
> guess most straightforward and backward compatible would be to just at
> a set of make-aligned-*vector and aligned-*vector and
> *->aligned-*vector functions and their scm_* versions with an
> additional alignment parameter. Optional alignment parameters on the
> old functions could be nice too, but I guess that is just asking for
> compatibility trouble.

What about something like ‘make-aligned-bytevector’?  This should be
enough, since bytevectors can be accessed through the SRFI-4 API (info
"(guile) Bytevectors as Uniform Arrays").  (And it can already be
implemented in Scheme, as I showed previously.)

> The other question is the read syntax (one of the primary reasons I'm
> doing all this). If alignment is something that should be preserved in
> the permanent representation, you also need to store it in the flags,
> since the content pointer can be aligned by coincidence. I haven't
> looked at the compiling of bytevectors yet, to see if alignment can be
> handled easily there.

I agree that we’d need some sort of annotation to specify the alignment
of literals, but adding read syntax for that scares me somewhat.  What
do people think?

On the compilation side, I think alignment will be more easily handled
in 2.2 (current ‘master’), which uses ELF (think of GCC’s ‘alignment’
attribute.)

None of this really seems doable in the 2.0 stable series.  So for now
you’d have to resort to one of the options discussed.

WDYT?

Thanks,
Ludo’.

bug#14599: An option to make vector allocation aligned

[Daniel Hartwig]

On 13 June 2013 21:31, Ludovic Courtès <ludo@gnu.org> wrote:
> Jan Schukat <shookie@email.de> skribis:
>> The other question is the read syntax (one of the primary reasons I'm
>> doing all this). If alignment is something that should be preserved in
>> the permanent representation, you also need to store it in the flags,
>> since the content pointer can be aligned by coincidence. I haven't
>> looked at the compiling of bytevectors yet, to see if alignment can be
>> handled easily there.
>
> I agree that we’d need some sort of annotation to specify the alignment
> of literals, but adding read syntax for that scares me somewhat.  What
> do people think?

I agree.  The read syntax for vector-ish types in guile is already
large enough.  If alignment is important then use a procedural
constructor and query.

Alignment information not need to be printed with the default
representation (read syntax), we dont also print the storage address,
etc..

Regards

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

On 06/14/2013 03:33 AM, Daniel Hartwig wrote:
> On 13 June 2013 21:31, Ludovic Courtès <ludo@gnu.org> wrote:
>> Jan Schukat <shookie@email.de> skribis:
>>> The other question is the read syntax (one of the primary reasons I'm
>>> doing all this). If alignment is something that should be preserved in
>>> the permanent representation, you also need to store it in the flags,
>>> since the content pointer can be aligned by coincidence. I haven't
>>> looked at the compiling of bytevectors yet, to see if alignment can be
>>> handled easily there.
>> I agree that we’d need some sort of annotation to specify the alignment
>> of literals, but adding read syntax for that scares me somewhat.  What
>> do people think?
> I agree.  The read syntax for vector-ish types in guile is already
> large enough.  If alignment is important then use a procedural
> constructor and query.
>
> Alignment information not need to be printed with the default
> representation (read syntax), we dont also print the storage address,
> etc..
>
> Regards
  The more I think about it and hear what you have to say, the more I 
think alignment just needs to be tied to the type of the uniform array. 
Up to float and int 32 arrays nothing will change then. Double and int64 
arrays get one word of padding on 32 bit machines to make them 8 byte 
aligned. And then introduce new type flags m128 and m256 for for simd 
types that are 16 or 32 byte bit aligned, possibly the complex arrays 
too. Since you can interpret uniform arrays as all types of uniform 
array this should solve all alignment problems where needed. The simd 
type arrays must be able to accept and recognize int and float 
immediates though, and you must be able to group them. That's not really 
much new syntax, and won't interfere with the old syntax.

Also, now I lean more towards switching to 2.2 for myself and implement 
it on there, because as Ludovic said, the compiling will possibly 
preserve alignment there better.

Regards

Jan Schukat

bug#14599: An option to make vector allocation aligned

[Ludovic Courtès]

Jan Schukat <shookie@email.de> skribis:

>  The more I think about it and hear what you have to say, the more I
> think alignment just needs to be tied to the type of the uniform
> array.

I think it would be wrong.  An array of floats is an array of floats,
regardless of its alignment.

> Also, now I lean more towards switching to 2.2 for myself and
> implement it on there, because as Ludovic said, the compiling will
> possibly preserve alignment there better.

Well yeah, though you’d still need to come up with an annotation for
that, and I’m not enthusiastic about changing the read syntax for that
purpose.

Now, I think the compiler should support a generic annotation mechanism,
to allow users to specify various things (like ‘declare’ in some
implementations.)  That could be one possible use.

Ludo’.

bug#14599: An option to make vector allocation aligned

[Jan Schukat]

On 06/14/2013 02:21 PM, Ludovic Courtès wrote:
> Jan Schukat <shookie@email.de> skribis:
>
>>   The more I think about it and hear what you have to say, the more I
>> think alignment just needs to be tied to the type of the uniform
>> array.
> I think it would be wrong.  An array of floats is an array of floats,
> regardless of its alignment.

For floats nothing would change anyway. Those are 4byte data types with 
4byte alignment already. As for the larger types, you can still make 
them in any alignment with the take functions. Just the default would 
the optimized one when you add padding, and that's what it should be, 
since the scheme programmer doesn't care about the underlying memory 
layouts as much as the C programmer does. In normal guile uniform vector 
use you are completely oblivious to the underlying vector 
implementation, apart from the performance. In short: an array of floats 
is still an array of floats, and you can create them at any alignment, 
although cumbersomely. But the very point if creating arrays of native 
types is to better use the underlying hardware. And not taking advantage 
of alignment there unless you absolutely can't is negligent at best.
>> Also, now I lean more towards switching to 2.2 for myself and
>> implement it on there, because as Ludovic said, the compiling will
>> possibly preserve alignment there better.
> Well yeah, though you’d still need to come up with an annotation for
> that, and I’m not enthusiastic about changing the read syntax for that
> purpose.

You don't need a special annotation if the default alignment is the 
native alignment of the native type. If you create arrays of native 
types that is what you want in the vast majority of cases. Overriding 
that should be the extra work and forced by external requirements, not 
by internal coincidental implementation details. And the interfaces to 
do that are already there.

I wanna use native SIMD types, which are obviously less portable, but in 
the end where they do exist they are all more or less the same in memory 
layout:  4 32bit ieee floats, 4 32bit ints or 2 ieee doubles, all 
preferably aligned at 128 bit. That's true for sse, altivec and neon on 
x86, power and arm respectively.

I can see why you wouldn't want SIMD types in the core modules. I can 
also see why you wouldn't want to change existing read syntax.

What I can't see is why you wouldn't want native type arrays in native 
alignment by default. There is no downside, and the implementation makes 
doing that trivial.

And having a module of uniform SIMD type arrays/vectors could be very 
valuable. I'll probably do that as an extension then, with a #, reader. 
Would just be a lot of code duplication and less nice.


>
> Now, I think the compiler should support a generic annotation mechanism,
> to allow users to specify various things (like ‘declare’ in some
> implementations.)  That could be one possible use.
>
> Ludo’.

Yes, that would have a lot of utility.

Regards

Jan Schukat