udoprog / fixed-map Goto Github PK

Hi and thanks for this crate it's perfect for my use case :)
There's a minor issue originating from clippy on some nightly only.

error: non-local `impl` definition, they should be avoided as they go against expectation
  --> sys\src\interop\locale.rs:15:5
   |
15 |     Key,
   |     ^^^
   |
   = help: move this `impl` block outside the of the current constant `__IMPL_KEY_FOR_Locale`
   = note: an `impl` definition is non-local if it is nested inside an item and may impact type checking outside of that item. This can be the case if neither the trait or the self type are at the same nesting level as the `impl`
   = note: one exception to the rule are anon-const (`const _: () = { ... }`) at top-level module and anon-const at the same nesting as the trait or type
   = note: this lint may become deny-by-default in the edition 2024 and higher, see the tracking issue <https://github.com/rust-lang/rust/issues/120363>
   = note: the derive macro `Key` may come from an old version of the `fixed_map_derive` crate, try updating your dependency with `cargo update -p fixed_map_derive`
   = note: `-D non-local-definitions` implied by `-D warnings`
   = help: to override `-D warnings` add `#[allow(non_local_definitions)]`
   = note: this error originates in the derive macro `Key` (in Nightly builds, run with -Z macro-backtrace for more info)

error: could not compile `audioware-sys` (lib) due to 1 previous error
error: Recipe `qa` failed on line 92 with exit code 1

A quick fix suggested by clippy would be to add #[allow(non_local_definitions)] on Key generated impl block (see logs).

It's very trivial and non-blocking, but going around it in my codebase requires pinning nightly version in each and every commands, which is a bit cumbersome.

Hi,
Recently rust decided to not support old linux kernel, this happened in 1.64.0 thus there is now technically 2 versions of rust:
1.63 and lower : support linux 2.6.32+ (glibc 2.11 and later)
1.64 and upper : support linux 3.2+ (glibc 2.17 and later)

If your crate needs new feature such as GAT then it's fine to set the MSRV to something high, however in #13 I fail to see why this was done, for instance your crate compile fine on 1.63.0.

If you can make a statement either saying that you would only support rolling MSRV and thus not support older rust release then it's fine but if you think that you will not need newer features then setting rustc-version to something lower would be better (https://doc.rust-lang.org/cargo/reference/manifest.html#the-rust-version-field).

nvm, I had the wrong version, your crate do use GATs

With benches introduced in #33 I've noticed that the abstracted entry API is slower than doing the equivalent over an array:

entry/fixed/32          time:   [6.9914 ns 6.9959 ns 7.0010 ns]
entry/array/32          time:   [213.54 ps 214.13 ps 214.75 ps]

To run a bench, I used use: cargo bench -- entry/fixed/32 and cargo bench -- entry/array/32.

The slowdown increases with time, at 4 elements it's the same but increases after it (so it's probably inline hinting which is not firing properly):

entry/fixed/4           time:   [209.29 ps 210.74 ps 212.19 ps]
entry/fixed/8           time:   [3.9445 ns 3.9611 ns 3.9782 ns]
entry/fixed/16          time:   [4.5784 ns 4.6329 ns 4.7035 ns]
entry/fixed/32          time:   [6.7929 ns 6.8126 ns 6.8305 ns]

This isn't unexpected, we had a similar issue due to inability to inline code before which was addressed in #23 and subsequent PRs. It would be nice to investigate if something similar is possible with the entry API.

CC: @pitaj if you're curious to investigate as well.

Love the work you've done on this crate. Have you thought about implementing the entry api for the map? I find it very useful and would like to use it with your crate.

Here's a link to the entry type if you aren't familiar https://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html

Wanted to request a little more documentation on this point.

Based on the array explanation, it's not clear why a second hash map is required. For instance, if you're just using a C style enum as keys, does the hash brown map come into play? And what are the performance implications when it does come into play?

Thanks

• FromIterator so it's collectable
• IntoIterator so you can use it in for loops and whatnot

See comment.

This primarily stems from how the ordering implementation for Option is derived:

#[derive(PartialEq, PartialOrd)]
enum Foo {
    First,
    Second,
}

fn main() {
    assert!(Foo::First < Foo::Second);
    assert!([Some(Foo::First), None] > [None, Some(Foo::Second)]);
}

Without such a definition, some form of wrapper would be needed to change how ordering is done. But any such abstractions also cause issues with potential optimization opportunities.

However it's done, it will become part of the public API of this crate.

I suggest renaming the map in each of these names to dynamic instead. This would avoid confusion around other Map stuff in the library.

Other options:

• hashbrown
• anycopy

When messing around with clippy lints, I found that #![no_std] can be enabled unconditionally in the main crate.
However, when looking for other no_std stuff, I came across the following:

I'm not sure why it's there, but since there is no no_std feature, this essentially has caused those tests to be disabled.
When I removed it, cargo test starts failing with the following message:

fixed-map$ cargo test
   Compiling fixed-map v0.8.0-alpha.2 (/home/peter/Dev/fixed-map)
    Finished test [unoptimized + debuginfo] target(s) in 0.42s
     Running unittests src/lib.rs (target/debug/deps/fixed_map-9035f9f1a380e143)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/derive_tests.rs (target/debug/deps/derive_tests-56212a1e8a4a06f9)

running 4 tests
test test_clone ... ok
test test_debug ... ok
test test_fromiter ... ok
test test_eq ... FAILED

failures:

---- test_eq stdout ----
thread 'test_eq' panicked at 'assertion failed: `(left != right)`
  left: `{First: 42}`,
 right: `{First: 42, Second: 42}`', tests/derive_tests.rs:32:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    test_eq

test result: FAILED. 3 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

error: test failed, to rerun pass `--test derive_tests`

As you can see, it appears that the two sides are, in fact, not equal, but the Eq impl is not returning the correct response.

Or: "Do the iterators really need to copy the keys by default?"

I'm having a bit of trouble creating an implementation for bevy_reflect::Map on a wrapper type around your fixed_map::Map type. The problem stems from the requirement that bevy_reflect::Map::get_at and bevy_reflect::Map::get_at_mut return the key-value pairs as borrowed dyn Reflect trait objects. While this is easy for the values (since they are borrowed anyway), there comes a problem with the keys. Because the keys are given from your iter() and iter_mut() iterators as owned values, this makes it impossible to meet the requirement for the trait.

Due to how trivial it is to acquire an owned key if necessary for a user's use-case (since the keys must implement Copy, simply doing *key in the iterator adaptor is good enough), I propose that the iterator implementations instead return borrows of the keys and leave it to the user to copy them if necessary.

Not sure if this is an issue with rustc/cargo or if there's a way for fixed_map to solve it, but I'm writing a library that uses a fixed map as input. So I want to re-export the Key derive macro for users of my library to use on their own types:

pub use fixed_map::Key;

This works fine and compiles in the library, however, when trying to use the Key derive type in a crate using my library:

63 | #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Key)]
   |                                                                    ^^^ could not find `fixed_map` in the list of imported crates
51 | #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Key)]
   |                                                                    ^^^ not found in `fixed_map::map`

From the sound of it, the error is because the crate using my library doesn't directly use fixed_map as one of it's dependencies? But it seems kinda unfortunate that to use my lib, they also have to explicitly add fixed_map as a dep...

Any ideas if it's possible to get this to work?

These are universally useful for maps:

• contains_key
• is_empty
• len
• retain

When following key:

#[derive(Key)]
enum MyKey {
    First,
    Second,
    Third,
}

Is stored in a Set it is currently backed by a structure like this since it's based on a map storing () values:

struct Storage {
    data: [Option<()>; 3],
}

Which occupies 3 bytes. This could instead be optimized to make use of a bit set (like I do in bittle) who's size depends on the number of variants:

struct SetStorage {
    // can represent 8 distinct values.
    data: u8,
}

Performance Musings

Whether this would be "as good" as a manually implemented bitset is hard to say. It might require additional specialization such as ensuring that MyKey is #[repr(<integer>)] and that each variant specifies a distinct value, such as:

#[derive(Key)]
#[repr(u8)]
#[key(bitset = "u8")]
enum MyKey {
    First = 0b1000,
    Second = 0b0100,
    Third = 0b0010,
}

Without that it might be difficult to ensure that certain operations are optimal, to the same degree as a manual bitset:

let set = 0b1001;

// contains
if set & MyKey::First as u8 != 0 {
    // and so forth.
}

Iteration might be the hardest one to perform with good performance, but in all fairness that is also something which is difficult with a manual bitset. Ensuring some representation and that each variant is reliably specified might mean that it's possible to coerce values into MyKey (unsafely) which wouldn't be easy to do manually.

I'm gathering a list of missing APIs here instead of having them in multiple separate issues.

• FromIterator, IntoIterator (#9) (added in #9).
• Map::contains_key / Set::contains (#10) (added in #22).
• Map::is_empty / Set::is_empty (#10).
• Map::len / Set::len (#10).
• Map::retain / Set::retain (#10) (added in #27).
• Entry api (#5) (added in #31).

Thanks to @msdrigg and @pitaj for the requests!

If you see something you'd like to implement, set up a PR and poke this issue (relates #11).