udoprog / fixed-map Goto Github PK
View Code? Open in Web Editor NEWA map implementation that relies on fixed-size storage derived by a procedural macro
License: Apache License 2.0
A map implementation that relies on fixed-size storage derived by a procedural macro
License: Apache License 2.0
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
andcargo 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 collect
ableIntoIterator
so you can use it in for loops and whatnotSee 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:
fixed-map/tests/derive_tests.rs
Line 1 in 62ea950
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:
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,
}
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)
.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.