Skip to content

No_std feature switch #238

Closed
jonimake wants to merge 6 commits intopetgraph:masterfrom
jonimake:no_std
Closed

No_std feature switch #238
jonimake wants to merge 6 commits intopetgraph:masterfrom
jonimake:no_std

Conversation

@jonimake
Copy link

@jonimake jonimake commented Feb 1, 2019

Using this feature switch will also turn on alloc feature switch which
is used to determine if the collections used in the library should be
imported from the alloc library or not.

Most notable change in no_std is that instead of a HashMap and Set
a BTreeMap and Set are used.

Benchmarks

Standard

running 6 tests
test bench_praust_mst          ... bench:         446 ns/iter (+/- 19)
test full_iso_bench            ... bench:       1,758 ns/iter (+/- 75)
test petersen_iso_bench        ... bench:       1,332 ns/iter (+/- 103)
test petersen_undir_iso_bench  ... bench:         977 ns/iter (+/- 42)
test praust_dir_no_iso_bench   ... bench:   1,115,236 ns/iter (+/- 89,176)
test praust_undir_no_iso_bench ... bench:   1,116,010 ns/iter (+/- 90,303)

test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured; 0 filtered out

     Running target/release/deps/ograph-0a0ed0f5ec42a012

running 3 tests
test bench_add_edge ... bench:         489 ns/iter (+/- 13)
test bench_inser    ... bench:           4 ns/iter (+/- 1)
test bench_remove   ... bench:         221 ns/iter (+/- 13)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out

     Running target/release/deps/stable_graph-5231646bce1ffe18

running 12 tests
test full_edges_default        ... bench:          10 ns/iter (+/- 0)
test full_edges_in             ... bench:          11 ns/iter (+/- 0)
test full_edges_out            ... bench:          10 ns/iter (+/- 0)
test graph_map                 ... bench:         272 ns/iter (+/- 13)
test neighbors_default         ... bench:           6 ns/iter (+/- 0)
test neighbors_in              ... bench:          10 ns/iter (+/- 0)
test neighbors_out             ... bench:           8 ns/iter (+/- 1)
test sccs_graph                ... bench:       3,119 ns/iter (+/- 246)
test sccs_stable_graph         ... bench:       3,221 ns/iter (+/- 230)
test stable_graph_map          ... bench:         389 ns/iter (+/- 36)
test stable_graph_retain_edges ... bench:         415 ns/iter (+/- 17)
test stable_graph_retain_nodes ... bench:          63 ns/iter (+/- 3)

test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out

No_std

running 6 tests
test bench_praust_mst          ... bench:         460 ns/iter (+/- 34)
test full_iso_bench            ... bench:       1,801 ns/iter (+/- 196)
test petersen_iso_bench        ... bench:       1,414 ns/iter (+/- 71)
test petersen_undir_iso_bench  ... bench:       1,032 ns/iter (+/- 68)
test praust_dir_no_iso_bench   ... bench:   1,178,403 ns/iter (+/- 75,966)
test praust_undir_no_iso_bench ... bench:   1,126,183 ns/iter (+/- 32,324)

test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured; 0 filtered out

     Running target/release/deps/ograph-d02ac07c0a8c3a51

running 3 tests
test bench_add_edge ... bench:         512 ns/iter (+/- 52)
test bench_inser    ... bench:           4 ns/iter (+/- 0)
test bench_remove   ... bench:         237 ns/iter (+/- 9)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out

     Running target/release/deps/stable_graph-10f377a07b8dfc8a

running 12 tests
test full_edges_default        ... bench:          10 ns/iter (+/- 0)
test full_edges_in             ... bench:          10 ns/iter (+/- 0)
test full_edges_out            ... bench:          10 ns/iter (+/- 0)
test graph_map                 ... bench:         254 ns/iter (+/- 9)
test neighbors_default         ... bench:           6 ns/iter (+/- 0)
test neighbors_in              ... bench:          10 ns/iter (+/- 0)
test neighbors_out             ... bench:           8 ns/iter (+/- 1)
test sccs_graph                ... bench:       2,971 ns/iter (+/- 285)
test sccs_stable_graph         ... bench:       3,127 ns/iter (+/- 410)
test stable_graph_map          ... bench:         377 ns/iter (+/- 46)
test stable_graph_retain_edges ... bench:         405 ns/iter (+/- 12)
test stable_graph_retain_nodes ... bench:          61 ns/iter (+/- 3)

test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out

@jonimake
Copy link
Author

jonimake commented Feb 1, 2019

@jonimake
Copy link
Author

I just realized that fixedbitset uses std also so I made a pull request for adding no_std support to it here: petgraph/fixedbitset#31

@bluss
Copy link
Member

bluss commented Sep 1, 2019

Hi, what's the goal and motivation of this change? What's the new thing we can do with this, and are there alternative ways of achieving it?

Copy link
Member

@bluss bluss left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It would be good to have the motivations & goals part filled out. I think petgraph can not accept losing HashMap, so this approach does not seem viable to me. If we want to have certain functionality available in no_std environments, there may be other approaches.

@jonimake
Copy link
Author

jonimake commented Sep 5, 2019

The original reason for doing this was because of a commercial project that used petgraph for handling graphs that were central to the the application. One of the requirements was that the binary had to run on embedded devices as well as on normal operating systems. Hence the need for no_std support.

I too think that it would be best if HashMap was available in alloc::collections. Maybe this PR should wait for when/if this one is merged? rust-lang/rust#56192

@bluss
Copy link
Member

bluss commented Sep 5, 2019

It does make me realize how useful indexmap on no std would be, too

@jonimake
Copy link
Author

After pondering this for a while, maybe it would be best if I changed the implementation to use the hashbrown crate https://github.com/rust-lang/hashbrown ? It supports no_std and it should be virtually the same std lib hashmap.

@jmcomets
Copy link
Collaborator

jmcomets commented Sep 10, 2019

I had a look at switching out the underlying map from IndexMap to a standard HashMap. There are a few issues.

Can be re-implemented, but there are performance considerations:

Cannot be implemented without IndexMap:

We could do some cfg attribute magic to use hashbrown with no_std, but that seems like working around the actual problem by introducing unneeded complexity. Personally I think it'd be worth it for indexmap to work on no_std, but I don't know how much of a headache that is.

@bluss
Copy link
Member

bluss commented Sep 10, 2019

One could jettison graphmap if we don't have std. That datastructure needs a lot of love (we have a rewrite issue #208). Note, we have a fruitful WIP on making indexmap no-std.

@bluss
Copy link
Member

bluss commented Oct 6, 2019

Also not having noticed that before now, the usual solution is a default feature named "std". cargo features must be additive, we can't have a cfg flag that takes something away.

@bluss bluss mentioned this pull request Oct 6, 2019
@jmcomets jmcomets mentioned this pull request Jan 29, 2020
@jmcomets
Copy link
Collaborator

@jonimake I've rebased this PR over master. There were quite a few changes, so you might want to reset your branch on my branch's head.

Since it's been a while since you opened this PR, I can close this one and take over if you like.

@jonimake
Copy link
Author

Right I reset my branch to that and it seems to compile fine on my end, travis seems to be quite broken though. No idea about that.

@jmcomets
Copy link
Collaborator

Yeah I just had a look & it seems to be the --no-default-features that I forgot to pass on its own. The .travis.yml has the full command-line that is run. Here's the diff to get things working:

diff --git a/src/simple_paths.rs b/src/simple_paths.rs
index 7f49b3b..6843588 100644
--- a/src/simple_paths.rs
+++ b/src/simple_paths.rs
@@ -98,7 +98,7 @@ mod test {
     use core::iter::FromIterator;
 
     #[cfg(not(feature = "alloc"))]
-    use std::{collections::HashSet, iter::FromIterator};
+    use std::{collections::HashSet};
 
     #[cfg(feature = "alloc")]
     use alloc::{collections::BTreeSet as HashSet, vec::Vec};
@@ -107,6 +107,9 @@ mod test {
 
     use crate::prelude::DiGraph;
 
+    #[cfg(not(feature = "no_std"))]
+    use crate::dot::Dot;
+
     use super::all_simple_paths;
 
     #[test]

@jmcomets
Copy link
Collaborator

jmcomets commented Jan 29, 2020

While the changes here could still use some refactoring, I think we only need to flip no_std to an std flag to keep things additive (should be enabled by default), before this can be merged. I'm not sure what the comment from @bluss concerning the approach w.r.t HashMap meant, though.

@jonimake
Copy link
Author

So to sum it up:

  • Add an std feature that's enabled by default
  • Change code so that all #[cfg(not(feature = "no_std"))] etc instead say #[cfg(feature = "std")]

Did I understand that right? What about the alloc feature switch? Should I just remove it and just import stuff from alloc if the std feature isn't enabled?

@jonimake
Copy link
Author

jonimake commented Feb 4, 2020

Looks like the failing travis test fails due to the all part in cargo test ${ALL:---all}. What's the use case for that? Is it even needed?

Edit: Looks like it's the same as --workspace when running cargo test

@XVilka
Copy link
Member

XVilka commented May 15, 2020

Could you please rebase this one? I think it will be very cool addition to the future 0.6 release.

mitchmindtree added a commit to mitchmindtree/dasp that referenced this pull request Jul 14, 2020
This adds a new crate for working with dynamic audio graphs.

From the new docs:

> `dasp_graph` is targeted towards users who require an efficient yet
> flexible and dynamically configurable audio graph. Use cases might
> include virtual mixers, digital audio workstations, game audio systems,
> virtual modular synthesizers and related usecases.

This work has been a long-time coming and is the result of many
discussions in the rust audio community and many lessons learned over
the last few years of working with rust and audio. In particular:

- the development of and reflection on [dsp-chain](https://crates.io/crates/dsp-chain) and its shortcomings.
- The (reasonable) limitations of [dasp_signal](https://crates.io/crates/dasp_signal) when dynamically configuring graphs.
- Discussion on the design of audio graphs with @raphlinus at RustAudio/dsp-chain#141.
- The development of the [spatial audio server](https://github.com/museumsvictoria/spatial_audio_server).
- A recent email discussion with Sami Perttu on DASP and audio graphs.

`dasp_graph` is of course not a one-size-fits-all solution. Instead, it
is designed specifically to work well alongside (and fill a gap within)
the rest of the `dasp` crate ecosystem. Please refer to the "Comparing
`dasp_signal`" section of the `dasp_graph` root documentation for a more
detailed overview of the design choices between the two, what
applications each are best suited toward and how the two best
interoperate together.

A small suite of node implementations are provided out of the box
including a `Delay`, `Sum`, `Pass`, `GraphNode` and `BoxedNode`, all of
which can be enabled/disabled via their associated features.

Following this, I have some ideas for adding an optional `sync` module
to the crate, aimed at controlling and monitoring a dasp graph and it's
nodes from a separate thread (i.e. for convenient use alongside a GUI)
in a non-dynamically-allocating, non-blocking manner. The work so far
has been performed with these plans in mind. The ideas are for the most
part based on the discussion at RustAudio/dsp-chain#141.

Also, `no_std` support for `dasp_graph` is currently blocked on petgraph
support for `no_std`. A PR is open for adding `no_std` support at
petgraph/petgraph#238. In the meantime, the `std` feature must be
enabled to use the new `dasp::graph` module. This is also noted in the
updated docs.

For more information about the crate and inner workings feel free to
read through the new `dasp_graph` docs. I'm yet to add examples, but
hopefully the added tests can give a good idea of how to use the crate
in the meantime.
@zendurix
Copy link

I was planning on implementing no_std myself, but I have found this.
Does this PR works fine for no_std? If so why isn't it merged?
If have tested it and it seems to builds in both std and no_std.
If there are still some bugs I can try to help.

@zendurix
Copy link

Using this feature switch will also turn on alloc feature switch which
is used to determine if the collections used in the library should be
imported from the alloc library or not.

Most notable change in no_std is that instead of a HashMap and Set
a BTreeMap and Set are used.

Other squashed changes:
- Added cfg_attr for switching on nightly alloc feature
- Added nightly travis test with no_std feature enabled
- Fixed travis.yml syntax
- Use fixedbitset with no_std feature in no_std mode
- Run cargo fmt
@XVilka

This comment has been minimized.

@zendurix
Copy link

I have started to rewrite it from the beggining for 'no_std'.
Do you have any tips what to use in "no_std" instead of std::collections::hash_map::RandomState in thoose structs:
pub struct IndexMap<K, V, S = RandomState> { core: IndexMapCore<K, V>, hash_builder: S, }

pub struct IndexSet<T, S = RandomState> { map: IndexMap<T, (), S>, }
I have almoust fully implement it, but I still have problem with this.

@XVilka
Copy link
Member

XVilka commented Aug 26, 2020

@zendurix
Copy link

@XVilka I haven't thought that it might be in other mod than hash_map . Thanks

@zendurix
Copy link

I have updated it, and now it passes no_std check (https://github.com/mystor/cargo-no-std-check)

zendurix@ef0eded
should i make new PR?

@XVilka
Copy link
Member

XVilka commented Aug 26, 2020

@zendurix please do

@zendurix
Copy link

@XVilka #370

@ABorgna ABorgna modified the milestones: 0.6, 0.7 Jul 4, 2021
@chaosprint
Copy link

Hi, is there any update on this? Thanks!

@indietyp indietyp added the 0.9.0-fixed Issue fixed in 0.9.0 label Oct 23, 2023
@indietyp
Copy link
Member

0.7.0 will have no-std support, until this version has landed I will keep this PR open.

github-merge-queue bot pushed a commit that referenced this pull request Mar 21, 2025
# Objective

- Alternative to #238
- Alternative to #370
- Implements Item 6 from #551

## Solution

- Promoted `hashbrown` to a direct dependency (currently transient
through `indexmap`)
- Added a new `std` feature, and included it in all features which rely
on `std` for documentation purposes.
- Added new CI task to ensure `no_std` support works (using
`wasm32v1-none` as an example `no_std` target)
- Added several lints which help minimise `std` usage
- Adjusted certain public APIs to allow passing a `S: BuildHasher`
instead of implicitly relying on `std::hash::RandomState` when the `std`
feature is disabled

---

## Notes

I know this has been attempted several times before and delayed due to a
desire to refactor the crate _first_ before adding this functionality.
Delays in adding `no_std` support forced Bevy to drop `petgraph` from
its core crates, relying on a specialised alternative. We'd love to keep
using `petgraph`, but `no_std` support is now a requirement going
forward. This will also come up with `wgpu` which is _also_ pursuing
`no_std` support [here](gfx-rs/wgpu#6826).

---

BREAKING CHANGE:

Petgraph previously assumed the usage of `std::hash::RandomState` as the
hashing implementation across its codebase. In `no_std`, this is not
possible. To minimise friction for libraries supporting both `std` and
`no_std` with Petgraph, I have made the following changes to the public
API:

### `petgraph::algo::simple_paths::all_simple_paths`

This function now has a 3rd generic parameter `S` which controls the
hashing implementation used. Because `all_simple_paths` is a function it
cannot have default generic parameters, so users must specify the hasher
themselves.

```rust
// Before
let foo = all_simple_paths(/* ... */);

// After
let foo = all_simple_paths::<_, _, std::hash::RandomState>(/* ... */);
```

### Switched from `std::collections::{HashMap, HashSet}` to
`hashbrown::{HashMap, HashSet}`

To support `no_std`, we cannot use the standard library's
implementations of `HashMap` or `HashSet`. Methods and types previously
referencing those collections from `std` will now reference them from
`hashbrown`. Note that `hashbrown` was already a dependency of Petgraph,
so no change in audit requirements.

### Added Hashing Parameter

The following types have had a new generic parameter `S` added to
specify the hashing implementation. Note that when `std` is enabled,
these will all default to `std::hash::RandomState`, as before.

- `UnGraphMap`
- `DiGraphMap`
- `MatrixGraph`
- `DiMatrix`
- `UnMatrix`
- `NodeIdentifiers`
- `NodeReferences`

Note that for `MatrixGraph`, `DiMatrix`, `UnMatrix` the new `S`
parameter is in the 3rd position (all others have `S` in the last
position). The reason is `S` has a default parameter with `std` enabled,
but is required with `std` disabled. This means it must be the last
_required_ parameter.

```rust
// Before
let foo: MatrixGraph<Foo, Bar, Directed, Option<Bar>, DefaultIx>;

// After
let foo: MatrixGraph<Foo, Bar, std::hash::RandomState, Directed, Option<Bar>, DefaultIx>;
```

Also note that because `Default` can now be implemented for multiple
versions of the above types (generic over the hasher), you may need to
either specify the hasher, or explicitly declare it as default (with the
`std` feature enabled):

```rust
// Note that N and E are inferred by code below.
// Before
let foo = UnMatrix::default();

// After (Explicitly infer N and E, but use defaults otherwise)
let foo = UnMatrix::<_, _>::default();
```

### `default-features = false` MSRV is 1.81

If you don't enable the `std` feature, the MSRV increases to 1.81, when
`core::error::Error` was stabilised. To preserve the original MSRV of
1.64, just enable the `std` feature.
@starovoid starovoid removed this from the 0.8 milestone Mar 26, 2025
@RaoulLuque
Copy link
Member

The PR #747 seems to have introduced the same behaviour. Thus I'll nominate this as to be closed :)

@RaoulLuque RaoulLuque added S-nominated-to-close Status: A contributor thinks this PR or issue should be closed out and removed 0.9.0-fixed Issue fixed in 0.9.0 labels Jun 21, 2025
@starovoid
Copy link
Collaborator

Support for no_std has been added in #747, so it's really time to close this PR.

@starovoid starovoid closed this Jun 22, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

S-nominated-to-close Status: A contributor thinks this PR or issue should be closed out

Projects

None yet

Development

Successfully merging this pull request may close these issues.

10 participants