no_std for ndarray

[bluss]

Using std gives us the following features:

• std::arch and target feature detection for seamless simd
• .

Having optional no_std support would give us these tangible benefits:

• .

I have created this issue so that the pros and cons of no_std can be explained. As of this writing, using no_std does not seem to be attractive.

As usual, all new features are to be used because of what gain they give us, not to score points. Formulate goal & gain before implementing.

[LukeMathWalker]

I guess the no_std game is more about enabling the usage of ndarray in no_std context than any tangible benefit to the library itself in terms of functionality.
Being quite ignorant when it comes to no_std environments (e.g. embedded), I'd be curious to understand:

• what is the current situation in terms of math libraries?
• is there any interest in using something similar to ndarray?
• would stack-allocated arrays be more desirable, given the device constraints?

[bluss]

We need formulation of the tangible benefits when it comes to usage of ndarray in no_std context. Not just interest, what it enables.

Also to make a feature highlight so that we don't miss this ndarray is already plenty useful outside of dynamically allocated arrays. Using ArrayView/Mut::from on a reference to array, or slice is the starting point to use ndarray functionality with any data.

There are examples where we use slices of arrays:

• https://docs.rs/ndarray/0.12.1/ndarray/type.ArrayView.html#method.from_shape
• https://docs.rs/ndarray/0.12.1/ndarray/fn.aview1.html
• https://docs.rs/ndarray/0.12.1/ndarray/fn.aview_mut2.html

And hopefully other places.

I think it's cool - you can have arrayviews of any storage you have - and a very big set of tools is available with that, all the traversal methods, arithmetic operators like +=, and Zip, even rayon-parallelized.

A point of precision is that we don't need to talk about stack-allocated, but inline storage. Just like ArrayVec, it's not a "stack allocated" vector. It has its storage inline, and Rust allows you to decide what to do with it. If you have a struct like this: Foo { a: ArrayVec, b: ArrayVec, c: ArrayVec }, then Box<Foo> is certainly not stack allocated, but the storage of the vectors are neatly packed in Foo next to each other, inline in Foo.

[jturner314]

Fwiw, adding (optional) no_std support to ndarray is pretty much just a matter of changing use statements from std to core/alloc, with the following exceptions:

• matrixmultiply (a required dependency of ndarray) currently doesn't support no_std. (WIP) Add no_std support bluss/matrixmultiply#46 is a work-in-progress PR to resolve this.

• The Float trait from num-traits isn't currently available in no_std environments. Hopefully, that'll be resolved soon with Revive Float+Real in no_std thanks to libm rust-num/num-traits#99.

So once those things are resolved, adding no_std support should be straightforward. There'll be only marginal additional complexity if we start using explicit SIMD. (In no_std, we have to rely on compile-time feature detection; the is_x86_feature_detected macro isn't available.)

I do think ndarray could be useful in embedded contexts, even without an allocator. With an allocator, it would be possible to use the full functionality of ndarray.

[vadixidav]

@bluss It looks like all the road blocks are now out of the way to make this possible. If nobody else volunteers to do this then I can do it.

[bluss]

Nobody has answered my question of what the benefit of doing it is 😅

[vadixidav]

@bluss The Rust CV project is interested on many levels in being able to run computer vision algorithms on embedded chips within robots. We currently have two crates (akaze and ndarray-vision) which utilize ndarray to perform some basic array routines. We are looking to get no_std support to support embedded Rust for robotics and aviation. This is why some of us are looking to get ndarray to support no_std, as we are unable to use it in crates that run on embedded, and we also cannot run some crates now that were significantly easier to write with ndarray to embedded.

By adding no_std support to ndarray we would be able to use it extensively in Rust CV for many types of problems, but primarily image processing and optimizers that are needed for the feature extraction and 3d reconstruction processes in vSLAM, SfM, and camera calibration. We currently use nalgebra pretty heavily, but there are some scenarios where ndarray is a better fit for the problem due to its slicing operations, negative strides, etc.

[bluss]

Thanks for filling in.

If possible, I've always favoured the "extern crate core as std" solution, since it makes the code across the crate the easiest to read and causes the least amount of churn, not sure if it's applicable here.

[vadixidav]

Thanks for filling in.

If possible, I've always favoured the "extern crate core as std" solution, since it makes the code across the crate the easiest to read and causes the least amount of churn, not sure if it's applicable here.

I hadn't thought to do that, but perhaps we can make that work. I think there are some minor differences though, but I will keep that in mind. I take it that you are okay with adding no_std support then, so I will start working on that 👍.

[bluss]

Arrayvec does it like that. Of course everything that's not in core (so between std and core) needs to be handled separately.

https://docs.rs/arrayvec/0.5.2/src/arrayvec/lib.rs.html#34-35

[SparrowLii]

（Hope it helps）
I traversed the .rs files in the project and found the following dependency on std：

These places use alloc::slice
	src/impl_views/conversions.rs:10
	src/iterators/mod.rs:29
	src/data_repr.rs:5
	src/free_fuctions.rs:10
	src/impl_methods.rs:10

These places use alloc::sync::Arc
	src/data_traits.rs:14
	src/lib.rs:118

These places use std::os::raw::c_int(Just type renaming)
	src/linalg/impl_linalg.rs:21 

These places use std::error::Error(impl Error for ShapeError)
	src/error.rs:9

And others:
	test/iteration uses std::panic::catch_unwindnd
	test/array.rs uses std::panic::catch_unwindnd
	test/array.rs:1065 uses alloc::collection and rc
	test/dimension.rs:229 uses alloc::collection
	test/par_azip.rs:7 uses std/sync

Other places can be solved by replacing "std" with "core". like this and this

[jplatte]

@bluss I'd be interested in implementing this. I haven't seen extern crate core as std; before, and since some places will have to be rewritten to use alloc rather than std anyway, in addition to there probably being a bunch of churn because there is no prelude for #[no_std], I'd personally favor referring to libcore as core, not std to avoid confusion from the rename. WDYT?

[vadixidav]

@jplatte We might all want to sync up this weekend. It looks like we have three people interested in contributing to this PR. It might be that less people actually do it, but we may as well just quickly chat about it. @SparrowLii has already started looking at it.

[bluss]

For some reason, github has opened a discussion feature so I enabled it- here: #860

I don't necessarily want discussions to be here on github - they can be anywhere :) Over there I've mentioned the two more specific places I know - matrix and discord, are there more?

[jplatte]

@SparrowLii has already started looking at it.

Right, I thought they shared their findings here so somebody else can do the grunt work. If somebody else wants to do that, that's fine by me 👍🏼

[bluss]

@jplatte There's a prelude still, the core prelude. I like using "core as std".

In #708 (comment) @vadixidav was the first person to say they wanted to do it.

[vadixidav]

I am totally on board with @jplatte working on it if you want to do that. If not, I offered myself up to do it, which I can work on tomorrow. I will check out the discussion board thing, haven't used that feature before.

[SparrowLii]

Have joined the sci-and-ai channel and matrix. I personally think "use core as std" is cool, but it may make people confused about the difference between core and std, especially for beginners

[vadixidav]

So, I left some extensive commentary in #science-and-ai on the Rust community Discord. I analyzed the dependencies to see what the impact of switching to no_std would be.

@bluss you may need to weigh in on whether a breaking release is justified or not. I have explained what the workarounds would be to make a non-breaking release below. Nonetheless, downstream users with default-features = false on ndarray are potentially broken by this change either way, so we would have to accept that on top of everything listed below.

Here are my findings:

num-integer = "0.1.39" 🟢

We have to add default-features = false. This should not create a breaking change because we only use functions from it and they aren't publicly exposed. Public API is unaffected.

num-traits = "0.2" 🔴

We have to add default-features = false.

Most of the time the traits are merely used, which is an implementation detail. However, we do expose num-traits in the public API (a quick rg):

src/numeric/impl_numeric.rs
9:use num_traits::{self, Float, FromPrimitive, Zero};
35:        A: Clone + Add<Output = A> + num_traits::Zero,
85:        A: Clone + Add<Output = A> + num_traits::Zero,
101:        A: Clone + Mul<Output = A> + num_traits::One,

One and Zero are still implemented the same with or without std. This is no issue.

Another case is the use of the Float trait:

pub trait NdFloat:
    Float
    + AddAssign
    ...
{
}

I investigated the float trait:

/// Generic trait for floating point numbers
///
/// This trait is only available with the `std` feature, or with the `libm` feature otherwise.
#[cfg(any(feature = "std", feature = "libm"))]
pub trait Float: Num + Copy + NumCast + PartialOrd + Neg<Output = Self> {
    ...
}

The Float trait is not present on no_std. The num-traits crate has a convenient solution for this in most cases:

/// Generic trait for floating point numbers that works with `no_std`.
///
/// This trait implements a subset of the `Float` trait.
pub trait FloatCore: Num + NumCast + Neg<Output = Self> + PartialOrd + Copy {
    ...
}

However, this is actually not a complete solution. Float does not require that FloatCore be implemented. This means that some type A could implement Float but not FloatCore. This would mean we have a breaking change. This could not be remedied by a change in num-traits because that would also be a breaking change and force us to make a breaking release in kind. Therefore, we either must accept that its incredibly unlikely someone is implementing the Float trait themselves and potentially break them downstream with a non-breaking release, or we must make a breaking release to convey this change.

We also cannot work around this by using a different trait depending on if we are no_std or std because of the rules for features. Notably, a separate dependency could upgrade ndarray to std and then cause the consumer's code to fail due to ndarray when that other dependency is added.

My recommendation for this would be to break versions and only utilize FloatCore, which is present in std and no_std. I don't see a way around this (feel free to point out any workaround). The alternative would be to accept that some code might be broken even with a semantically compatible release, given that the number of people with this issue is small.

num-complex = "0.2" 🟢

We have to add default-features = false for this, but the only thing used from it is Complex, which does not require std.

There is, however, this one subtle difference:

        #[cfg(feature = "std")]
        // Currently, we can only apply width using an intermediate `String` (and thus `std`)
        fn fmt_complex(f: &mut fmt::Formatter<'_>, complex: fmt::Arguments<'_>) -> fmt::Result {
            use std::string::ToString;
            if let Some(width) = f.width() {
                write!(f, "{0: >1$}", complex.to_string(), width)
            } else {
                write!(f, "{}", complex)
            }
        }

        #[cfg(not(feature = "std"))]
        fn fmt_complex(f: &mut fmt::Formatter<'_>, complex: fmt::Arguments<'_>) -> fmt::Result {
            write!(f, "{}", complex)
        }

I think we can be rest assured this one is a non-issue.

rayon = { version = "1.0.3", optional = true } 🟢

rayon has no features and only works in the presence of std. This is to be expected and is a non-issue.

approx = { version = "0.3.2", optional = true } 🟢

approx internally has no difference when std is enabled, aside from to use things from std rather than core, so there is no point to using its std feature. I created an issue to track this behavior here: brendanzab/approx#62.

My suggestion is to just add default-features = false and it should be fine.

cblas-sys = { version = "0.1.4", optional = true, default-features = false } 🟢

We don't need to worry about this one because the default features are off and its optional, so if it requires an OS then that is on the user to deal with.

blas-src = { version = "0.2.0", optional = true, default-features = false } 🟢

This one is the same as the previous.

matrixmultiply = { version = "0.2.0" } 🟢

Only functions are used from matrixmultiply, so we can simply change this to default-features = false.

serde = { version = "1.0", optional = true } 🟡

This one is tricky. The reason is that, should we leave this exactly as is, one cannot use serde on no_std. Suppose that one were to use ndarray/serde as a feature, in that case they would be depending on the std version of serde, which cannot build and run on no_std targets.

Suppose that we added default-features = false, then someone that pulls in ndarray/serde. This would technically bring in serde without the std feature, but this doesn't seem to be an issue. The reason is that while we implement Serialize and Deserialize, no APIs are exported from ndarray. Additionally, we can simply disable serde impls that would require std when the std feature is not enabled. When std is enabled, we should provide the same implementation as today, which doesn't appear, at first glance, to depend on any std behavior of serde, aside from some impls for deserializing Vec, which we can probably work around.

My recommendation is to add default-features = false to this one and to modify any code utilizing the impl of Deserialize for Vec to not use that impl if possible. If this is not possible, then we may need to introduce a secondary feature called serde_std that depends on serde/std.

rawpointer = { version = "0.2" } 🟢

This is already no_std and has no std feature. No change needed.

[bluss]

matrixmultiply should definitely be conditionally using std (enable std when ndarray enables it). And yes, it is a breaking change because we're going to change what ndarray does with its no-default-features.

[vadixidav]

@bluss I just want to clarify that you are okay with making a new breaking release. Is that fine? If so, it seems we can proceed without too much more discussion.

[SparrowLii]

@vadixidav

My recommendation for this would be to break versions and only utilize FloatCore, which is present in std and no_std. I don't see a way around this (feel free to point out any workaround). The alternative would be to accept that some code might be broken even with a semantically compatible release, given that the number of people with this issue is small.

I think it is reasonable to switch to FloatCore in order to achieve no_std, because this is the meaning of FLoatCore. If we want to use the Float feature without activating std, we can use libm crate.

[bluss]

I just want to leave a brief comment, not necessarily a judgement about the actual float trait

I think it is reasonable to switch to FloatCore in order to achieve no_std, because this is the meaning of FLoatCore

This argument doesn't really ring true to me. The main feature of ndarray will continue to be that we use it with std. Having optional no_std is going to be one of the minor features. It's not a super important feature. That means that we need a float trait that maximizes our utility.

[bluss]

This change needs to wait for a breaking release anyway. We should proceed quickly to that - we have breaking changes tagged with the 0.15 milestone already.

[xd009642]

Yeah I agree with @bluss regarding Float and FloatCore, potentially we could also export an NdFloatCore for a more constrained trait for no_std users to mimic what num-traits does.

Searching through the code NdFloat isn't used anywhere in the code apart from tests and is just exported as a public type so we can always cfg it so it's only exported with the std feature without creating a breaking change.

[xd009642]

it looked very quick so I did a slight draft of float changes: #861

It will break tests because the --no-default-features is set. Also, if the other no_std changes are going to be massive I'd prefer to keep things to smaller easier to review PRs instead of one massive change - just for ease of review

[bluss]

Yes, a breaking change is ok since it's needed for this, so that was a bit implicit I guess.

Will you clarify what you want here? I'm expecting that we're going for no_std + alloc (And not a pure "just core" configuration).

[xd009642]

so because others mentioned the FloatCore trait from num-traits instead of Float I created an NdFloatCore which is the same composition of traits just with the proposed replacement, so instead of changing NdFloat we just get a more minimal alternative to it for no_std crates.

As for my PR it's just an attempt to break up the changes for no_std a bit to things which are solved easily or already doable and other things that may take more effort and thought. I agree with the no_std + alloc as that's the impression I got from the previous chat

[vadixidav]

I think no_std + alloc is the right way to go. If we want, we can also add an alloc feature right now that ndarray cannot build without. This would allow us to add a no-alloc version in the future.

[SparrowLii]

Since I replaced the replaceable "std" in the ndarray with "core", should I submit a pr?

[xd009642]

@SparrowLii that sounds good ☺️