Adoption of the Apache Arrow memory alignment and padding?

[paddyhoran]

Hi,

I'm just trying to get a sense of the level of interest from the ndarray developers regarding adopting the Apache Arrow memory layout and padding.

I have been wanting to build integrations between Arrow and ndarray for some time. Today it should be easy enough to build a zero-copy converter to ndarray types. Arrow has a tensor type and this could be converted (with the optional names for dimensions in Arrow dropped).

However, without guarantees over the memory alignment and padding assumptions you could not go back to Arrow with zero-copy. The easiest way to do this would be for ndarray to use the Arrow functions that allocate memory through the Arrow Buffer type.

Arrow is attempting to make integrations between crates easier, I noticed this issue today. This is the kind of issue we could avoid.

In general, I think that Arrow and ndarray fit together quite nicely where Arrow could provide alot of help processing data and ndarray provides all the algorithms once data is cleaned and in-memory.

I'm not very familiar with the ndarray codebase, if this sounds like a good idea could you point me to where you allocate memory etc. and any other information that might help?

[alippai]

@paddyhoran if this happens would it make sense to use ndarray-stats for Arrow compute kernels? (I hope this is the good name for min, max, sum, count etc functions).

[paddyhoran]

@paddyhoran if this happens would it make sense to use ndarray-stats for Arrow compute kernels?

Yes, perhaps. We started to implement some compute kernels in Arrow and using SIMD,etc. However, the Rust community is relatively small to begin with. ndarray is the most established numerical library in the Rust ecosystem so if we had seemless integration between the two it would have a lot of mutual benefits, for instance:

• people could contribute to ndarray-stats instead of building a stats package that works with Arrow
• ndarray leveraging Arrow to use parquet, Arrow Flight, etc.

There are probably some things that we need to resolve, for instance:

• handling of Nulls, Arrow has a bitmap, does ndarray use a sentinel value?
• Arrow Boolean Arrays are bit packed, ndarray's might not

I think integration between the two could open up a lot of possibilities on both sides but I'm not sure how the ndarray devs feel?

[LukeMathWalker]

Looking at this purely from an ecosystem integration perspective, it would be amazing!
It would make it seamless to interoperate Rust code using ndarray with systems developed in other language ecosystems using Apache Arrow (an ever-growing list as far as I can see, especially in the ML/Big Data space).

From a technical perspective, I am afraid I don't have enough mastery of the nitty-gritty details of ndarray's internal memory representation (or Arrow's 😅) to judge if there might be issues/incompatibilities.
@jturner314 / @bluss are probably the best suited to give a high-level feasibility judgement - I'd be happy to work on this myself if it's indeed viable.

With respect to your questions:

handling of Nulls, Arrow has a bitmap, does ndarray use a sentinel value?

You would generally use Option<T> if you are handling nullable values.

Arrow Boolean Arrays are bit packed, ndarray's might not

I am not aware of any optimization regarding boolean arrays in ndarray.

[andy-thomason]

Hi Everyone, I'm working on dictionary support (categories/factors) for the rust arrow implementation. The simplest thing would be to support bit packed bool vectors in ndarray. These could be zipped with the data vectors. I'm proposing to write iterator support for the arrow arrays in the near future which could include the bitarrays. The trick is to get the loops to vectorise. It would be nice if there was an intrinsic in Rust to assert pointer alignment. There may be such a thing as it does exist in LLVM. Arrow's 8 byte alignment is enough for pretty much every SIMD we are likely to encounter except for power PC. Andy.

…

On Sun, Jan 5, 2020 at 11:21 AM Luca Palmieri ***@***.***> wrote: Looking at this purely from an ecosystem integration perspective, it would be amazing! It would make it seamless to interoperate Rust code using ndarray with systems developed in other language ecosystems using Apache Arrow (an ever-growing list as far as I can see). From a technical perspective, I am afraid I don't have enough mastery of the nitty-gritty details of ndarray's internal memory representation (or Arrow's 😅) to judge if there might be issues/incompatibilities. @jturner314 <https://github.com/jturner314> / @bluss <https://github.com/bluss> are probably the best suited to give a high-level feasibility judgement - I'd be happy to work on this myself if it's indeed viable. With respect to your questions: handling of Nulls, Arrow has a bitmap, does ndarray use a sentinel value? You would generally use Option<T> if you are handling nullable values. Arrow Boolean Arrays are bit packed, ndarray's might not I am not aware of any optimization regarding boolean arrays in ndarray. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#771?email_source=notifications&email_token=AAL36XC6IJ5JHPSINYLFDRTQ4G7CBA5CNFSM4KBPYCSKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEIDUMKI#issuecomment-570902057>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAL36XGMK3HPGSH525S4WCLQ4G7CBANCNFSM4KBPYCSA> .

[alippai]

people could contribute to ndarray-stats instead of building a stats package that works with Arrow

@paddyhoran Exactly this is why I suggested the cross-dependency. While both Rust Arrow and ndarray(-stats) is awesome, they don't have the "critical mass" yet, together they could be much better 🤞

[andy-thomason]

X86 is generally the best of all CPUs for alignment requirements as it will access data on two beats with at any alignment relatively little overhead. The exception may be "exotic" memory, such as GPU buffers and DMA I/O spaces.

ARM can be a little fussy, but generally 4 bytes is good enough. Again, this depends very much on the flavour of ARM CPU and bus. Also the LLVM implementation is super-conservative and generates terrible code. I'm talking to Philippe the next time I'm in Cambridge about this.

PPC is always the hard one as several instructions are needed to make an unaligned load or store.

Worth noting the benefits of non-temporal stores on X86 which significantly improve the store speed which will otherwise become a bottleneck for all vector operations. Hard to achieve in Rust as LLVM is resistant to the concept beyond basic intrinsic support. You need to put a fence at the end of the loop to make it thread safe.

But on the whole 128 or 256 bit alignment is likely to be a win.

[jturner314]

The current format of ndarray's ArrayBase type is provided here. For owned arrays, the data field has type OwnedRepr<A>, which is just a thin wrapper around Vec<A>.

The best resources I've found about the Apache Arrow Tensor format are the following:

• Tensor (Multi-dimensional Array)
• Tensor.fbs
• implementation of conversions between NumPy arrays and Arrow Tensors

From what I can tell, the only restrictions on the memory layout of the data are that:

• The address in bytes of the first element must be a multiple of 64 (i.e. 512-bit alignment).
• All strides must be non-negative.

Given this, creating an ArrayBase from an Arrow tensor should be possible as a zero-copy operation in the case where the strides are a multiple of the element size. (This should be the common case, but the format doesn't appear to require the strides to be a multiple of the element size since they're specified in bytes and not element counts.)

Going the other way (from ArrayBase to an Arrow tensor) is not as straightforward. It looks we need to ensure the alignment of the first element is a multiple of 64 bytes and return an error in the case of negative strides (that's how Python Arrow implementation handles negative strides).

For owned arrays, we could allocate with 64-byte alignment when ndarray is performing the allocation, assuming this change does not have a large performance cost. This won't help when the data is allocated outside of ndarray (e.g. a user converting a Vec to an Array) or after slicing operations (which may make the first element not be 64-byte aligned). I'm surprised not to see any alignment checks in the conversion from a NumPy array to an Arrow tensor. How does the NumPy/Python implementation handle converting NumPy arrays to Arrow tensors in these cases (a NumPy array created from a user-provided buffer which may not be 64-byte aligned or a NumPy array that has been sliced such that the first element is not 64-byte aligned)?

It would also be helpful to have a better understanding of the ownership semantics of the arrow crate's Buffer and MutableBuffer types. (At first glance based on the source code, it looks like they're intended to be analogous to Arc<[T]> and Vec<T>, but the owned field of BufferData on the master branch makes me question this.)

[paddyhoran]

Hi @jturner314,

Thanks for the detailed response.

creating an ArrayBase from an Arrow tensor should be possible as a zero-copy operation in the case where the strides are a multiple of the element size

Yes, I think this scenario should be, relatively, straight forward.

This should be the common case, but the format doesn't appear to require the strides to be a multiple of the element size since they're specified in bytes and not element counts.

AFAIK the strides would always be a multiple of the element size and the use of bytes in the strides is an implementation detail (which could be changed).

Going the other way (from ArrayBase to an Arrow tensor) is not as straightforward. It looks we need to ensure the alignment of the first element is a multiple of 64 bytes and return an error in the case of negative strides (that's how Python Arrow implementation handles negative strides).

Yes, this is where adoption of the Arrow functions that allocate memory would help. If ndarray could be changed to use the functions here then memory would already be aligned and could be passed to Arrow zero-copy. Of course, you can't ensure aligned memory from user input. Alignment would be checked at conversion time. I'm not sure about the numpy case and why we don't check the alignment, I'm not too familiar with the Python implementation. Another consideration is that Arrow pads to 64 bytes, this simplifies some SIMD code, i.e. SIMD can operate on this padded region without worry (initially we should not worry about these details in the Arrow -> ndarray case).

It would also be helpful to have a better understanding of the ownership semantics of the arrow crate's Buffer and MutableBuffer types. (At first glance based on the source code, it looks like they're intended to be analogous to Arc<[T]> and Vec<T>, but the owned field of BufferData on the master branch makes me question this.)

My understanding is as follows:

• MutableBuffer is purely for creating Buffer objects, i.e. in BufferBuilder, and is never used as the buffer backing an array. All data in Arrow is immutable.
• All arrays are backed by the ArrayData type and are reference counted, i.e. operations like slicing update the offset and don't allocate
• the owned field of BufferData was introduced relatively recently and was added to aid in situations where data had been allocated outside of Arrow AFAIK, I need to look into this.

I think I will start small and add an implementation of converting from Arrow tensor to ArrayBase and we can expand from there and work through the details.

[paddyhoran]

One key question is in regard to how ndarray represents null values, i.e. NaN, etc. I'm assuming you use a sentinal value?

[jturner314]

If ndarray could be changed to use the functions here then memory would already be aligned and could be passed to Arrow zero-copy.

My concern is that simply allocating with 64-byte alignment does not ensure that the first element of an array will be 64-byte aligned, due to the possibility of slicing. Consider the following Python example:

import numpy as np


def is_first_elem_64_byte_aligned(array):
    return array.__array_interface__['data'][0] % 64 == 0


aligned = np.zeros(10, dtype=np.uint8)
print(is_first_elem_64_byte_aligned(aligned))

unaligned = aligned[1:]
print(is_first_elem_64_byte_aligned(unaligned))

The example prints

True
False

In other words, the allocation is 64-byte aligned, but the first element of the array unaligned is not 64-byte aligned, which I understand to be a requirement for (zero-copy) creating an Arrow tensor. That's why I'm curious how NumPy handles this, because the same issue would occur for ndarray. (Maybe this is what the offset field of Buffer is for?)

One key question is in regard to how ndarray represents null values, i.e. NaN, etc. I'm assuming you use a sentinal value?

ndarray doesn't have explicit support for null/invalid/missing values. (ndarray doesn't have an equivalent of NumPy's masked arrays feature, which I think is what you're asking about?) For arrays of floating-point (f32/f64), you can use NaN. For any arbitrary type T, you can make the element type of the array be Option<T> so that missing values can be represented as None, although this probably isn't great for performance. For non-floating-point element types, I would think using a separate mask array would provide better performance.

[paddyhoran]

In other words, the allocation is 64-byte aligned, but the first element of the array unaligned is not 64-byte aligned, which I understand to be a requirement for (zero-copy) creating an Arrow tensor. That's why I'm curious how NumPy handles this, because the same issue would occur for ndarray. (Maybe this is what the offset field of Buffer is for?)

I'll need to look into how numpy handles this but yes, this is what offset if for. In this case, the underlying data is aligned but offset is updated. As all data in Arrow is immutable we can share zero copy in this way.

As you mentioned on #776 I think there's not much you can do about alignment of slices and ensuring that the first element is aligned at allocation covers alot of common use cases. Technically, in your numpy example above you could have SIMD operate on the underlying data (without the offset) as it is still aligned and return the result with the offset. This is getting into the weeds though as it depends on the size of the slice relative to the size of the original array and is probably not worth worrying about.

I think you are right about investigating how numpy handles all these concerns. Thanks for all the detailed responses. I won't take anymore of your time, I need to find time to do my own research and open some draft PR's.

Thanks again

[jturner314]

Just one note before you draft a PR -- I'd prefer for ndarray not to have a required dependency on the arrow crate since it includes lots of functionality unnecessary for ndarray. Functions/types for 64-byte aligned allocation should be simple enough to put directly in ndarray instead of using arrow's Buffer. (Prototypes depending on arrow are fine for discussion purposes and performance evaluation, but I don't plan to merge a PR with a required dependency on arrow.) Conversions to and from arrow types can be provided with an optional dependency on arrow.

[paddyhoran]

Yep, makes total sense. Thanks @jturner314