ExactSizeIterator
impl<K, V, const N: usize, S> SmolMap<K, V, N, S>
where
K: Eq + Hash,
S: BuildHasher,
{
/// # Panics
/// If length == N
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
assert_ne!(self.len, N);
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx = 0;
loop {
let idx_mod: usize = (start_idx + iter_idx * iter_idx) % self.storage.len();
if self.storage[idx_mod].0 {
if unsafe { self.storage[idx_mod].1.assume_init_ref() }
.0
.eq(&key)
{
let new_val = MaybeUninit::new((key, value));
let old_val = std::mem::replace(&mut self.storage[idx_mod].1, new_val);
return Some(unsafe { old_val.assume_init().1 });
}
} else {
let new_val = MaybeUninit::new((key, value));
self.storage[idx_mod].0 = true;
self.storage[idx_mod].1 = new_val;
self.len += 1;
return None;
}
iter_idx += 1;
}
}
}
behold my possibly unsafe and possibly wrong quadratic probing insertion#[derive(Debug)]
pub struct SmolMap<K, V, const N: usize, S = RandomState> {
storage: [(bool, MaybeUninit<(K, V)>); N],
len: usize,
state: S,
}
(bool, T)
→ Option<T>
Option<T>
is literally (bool, MaybeUninit<T>)
^^ pub fn new(hasher: S) -> Self {
let data = std::array::from_fn(|_| (false, MaybeUninit::uninit()));
Self {
storage: data,
len: 0,
state: hasher,
}
}
pub const fn new(hasher: S) -> Self {
Self {
storage: unsafe {
MaybeUninit::uninit().assume_init()
},
tags: [false; N],
len: 0,
state: hasher,
}
}
/// # Panics
/// If length == N
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
assert_ne!(self.len, N);
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx = 0;
loop {
let idx_mod: usize = (start_idx + iter_idx * iter_idx) % self.storage.len();
if self.tags[idx_mod] {
if unsafe { self.storage[idx_mod].assume_init_ref() }
.0
.eq(&key)
{
let new_val = MaybeUninit::new((key, value));
let old_val = std::mem::replace(&mut self.storage[idx_mod], new_val);
return Some(unsafe { old_val.assume_init().1 });
}
} else {
let new_val = MaybeUninit::new((key, value));
self.tags[idx_mod] = true;
self.storage[idx_mod] = new_val;
self.len += 1;
return None;
}
iter_idx += 1;
}
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx = 0;
while iter_idx < N {
let idx_mod: usize = (start_idx + iter_idx) % self.storage.len();
if self.tags[idx_mod] {
if unsafe { self.storage[idx_mod].assume_init_ref() }
.0
.eq(&key)
{
let new_val = MaybeUninit::new((key, value));
let old_val = std::mem::replace(&mut self.storage[idx_mod], new_val);
return Some(unsafe { old_val.assume_init().1 });
}
} else {
let new_val = MaybeUninit::new((key, value));
self.tags[idx_mod] = true;
self.storage[idx_mod] = new_val;
self.len += 1;
return None;
}
iter_idx += 1;
}
panic!("no slot could be found")
}
std::map
in C++BTreeMap
in rust<
relation on the key typesmolmap get 1000 time: [7.6065 ns 7.6679 ns 7.7887 ns]
Found 10 outliers among 100 measurements (10.00%)
5 (5.00%) high mild
5 (5.00%) high severe
hashmap get 1000 time: [8.9185 ns 8.9328 ns 8.9479 ns]
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high severe
The implementation of the Rust abstract machine - miri - stops execution of Rust programs when they exhibit undefined behavior.
C, C++, etc. don't even have implementations of their abstract machines. They don't have one existing as a goal. And they are happy to make certain operations exhibit undefined behavior even if that implies that it would make an implementation of the abstract machine that traps impossible.
This is why even if you were to combine valgrind with address sanitizer, memory sanitizer, thread sanitizer, undefined-behavior-sanitizer, and other existing C and C++ tools, there is still a lot of classes of undefined behavior that these tools can't detect.
That's fine in C and C++, but not fine in Rust. In Rust, if we add a new type of undefined behavior, the constraint is that it should be (demonstrably) possible to extend miri to detect it, such that if a user doesn't know whether some program exhibits undefined behavior for some inputs, they can just run it under miri, and miri will precisely pinpoint which part of their code exhibited undefined behavior and why, and how their program execution got there.
thread 'main' panicked at 'unsupported Miri functionality: can't call foreign function `GFp_cpuid_setup` on OS `linux`', /home/jupeyy/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ring-0.16.20/src/cpu.rs:46:21
i depend on unsupported feature ;~;thread 'main' panicked at 'unsupported Miri functionality: can't call foreign function `GFp_cpuid_setup` on OS `linux`', /home/jupeyy/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ring-0.16.20/src/cpu.rs:46:21
i depend on unsupported feature ;~; struct Test;
impl Test {
fn a(&mut self) -> &() {
&()
}
}
fn compile(t: &mut Test) -> &() {
let b = t.a();
if false {
return b;
}
t.a()
}
not compile due to lifetimes. But when removing the if false { return b; }
it does compile error[E0499]: cannot borrow `*t` as mutable more than once at a time
--> src/main.rs:14:5
|
9 | fn compile(t: &mut Test) -> &() {
| - let's call the lifetime of this reference `'1`
10 | let b = t.a();
| ----- first mutable borrow occurs here
11 | if false {
12 | return b;
| - returning this value requires that `*t` is borrowed for `'1`
13 | }
14 | t.a()
| ^^^^^ second mutable borrow occurs here
struct Test(());
impl Test {
fn a(&mut self) -> &() {
&self.0
}
}
fn compile(t: &mut Test) -> &() {
{
let b = t.a();
if false {
return b;
}
}
t.a()
}
struct Test(());
impl Test {
fn a(&mut self) -> &() {
&self.0
}
}
fn compile(t: &mut Test) -> &() {
{
let b = t.a();
if false {
return b;
}
}
t.a()
}
struct Test(());
impl Test {
fn a(&mut self) -> &() {
&self.0
}
}
fn compile(t: &mut Test) -> &() {
{
let b = t.a();
if false {
return b;
}
}
t.a()
}
say_self
or echo
depending on availability etc