Отвечая на твои вопросы:
1 - есть ли что-то быстрее, чем tokio
2 - правильно ли я использую tokio
3 - насколько хорошая с точки зрения производительности идея использовать Arc
4 - можно ли ускорить саму по себе структуру HashMap или только переписывать?
1. В твоём случае лучше взять rayon для параллельной обработки, тк tokio предназначен для асинхронного io.
2. см п1. Как именно ты tokio использовал я не смотрел.
Дмитрий Беляев хорошо ответил по этому поводу
3. Плохая. Лучше взять другую структуру данных
4а. Можно процентов на 30 ускорить HashMap если заранее сделать with_capacity
4б. И в n раз ускорить если сделать несколько HashMap по одному для каждого из N потоков (и передать во владение каждому потоку, чтобы не тратиться на синхронизацию и подсчёт ссылок).
Для большого количества вставок неизвестного количества данных лучше подойдёт BTreeMap
1.
Многопоток тебе тут не поможет (а нет, обманул. Многопоток поможет. А вот async-нет)
2. Ты бенчмаркаешь format!("{}", i)
3. Вообще тебе тут стоит посмотреть на какие-нибудь concurrency-safe lockfree структуры. Например есть достаточно популярный крейт
dashmap который такое предлагает.
UPD: я обманул сам себя. dashmap не lockfree. Под капотом это как раз несколько HashMap, спрятанных за RwLock:
pub struct DashMap
pub struct DashMap<K, V, S = RandomState> {
shift: usize,
shards: Box<[RwLock<HashMap<K, V, S>>]>,
hasher: S,
}
Мои бенчмарки с использованием criterion
Результат:
Обрати внимание, что тесты без format на порядок быстрее проходят.
Но я не уверен, что корректно написал бенчмарк для btree_known_key__3M
hashmap_no_capacity_format_key__3M
time: [1.4810 s 1.5362 s 1.5952 s]
hashmap_set_capacity_format_key__3M
time: [1.0688 s 1.0744 s 1.0804 s]
btree_format_key__3M time: [754.93 ms 843.10 ms 933.95 ms]
vec_set_apacity__3M time: [1.7122 ms 1.7309 ms 1.7655 ms]
dashmap_rayon_format_key__3M
time: [294.76 ms 303.70 ms 316.85 ms]
btree_known_key__3M time: [554.56 ms 556.18 ms 558.41 ms]
Код
use std::{
collections::{BTreeMap, HashMap},
time::Instant,
};
use criterion::{black_box, criterion_group, criterion_main, Criterion};
fn hashmap_no_capacity_format_key(n: usize) -> HashMap<String, usize> {
let mut map = HashMap::new();
for i in 0..n {
let key = format!("key_{i}");
map.insert(key, i);
}
map
}
fn hashmap_set_capacity_format_key(n: usize) -> HashMap<String, usize> {
let mut map = HashMap::with_capacity(n + 1);
for i in 0..n {
let key = format!("key_{i}");
map.insert(key, i);
}
map
}
fn btreemap_format_key(n: usize) -> BTreeMap<String, usize> {
let mut map = BTreeMap::new();
for i in 0..n {
let key = format!("key_{i}");
map.insert(key, i);
}
map
}
fn vec_set_capacity(n: usize) -> Vec<usize> {
let mut vector = Vec::with_capacity(n);
for i in 0..n {
vector.push(i);
}
vector
}
fn btreemap_known_key(keys: impl Iterator<Item = (String, usize)>) -> usize {
let mut map = BTreeMap::new();
for (k, v) in keys {
map.insert(k, v);
}
map.len()
}
fn dashmap_rayon_format_key(n: usize) -> dashmap::DashMap<String, usize> {
use rayon::prelude::*;
let map = dashmap::DashMap::with_capacity(n);
(0..n).into_par_iter().for_each(|i| {
let key = format!("key_{i}");
map.insert(key, i);
});
map
}
fn bench(c: &mut Criterion) {
c.bench_function("hashmap_no_capacity_format_key__3M", |b| {
b.iter(|| hashmap_no_capacity_format_key(black_box(3_000_000)))
});
c.bench_function("hashmap_set_capacity_format_key__3M", |b| {
b.iter(|| hashmap_set_capacity_format_key(black_box(3_000_000)))
});
c.bench_function("btree_format_key__3M", |b| {
b.iter(|| btreemap_format_key(black_box(3_000_000)))
});
c.bench_function("vec_set_apacity__3M", |b| {
b.iter(|| vec_set_capacity(black_box(3_000_000)))
});
c.bench_function("dashmap_rayon_format_key__3M", |b| {
b.iter(|| dashmap_rayon_format_key(black_box(3_000_000)))
});
c.bench_function("btree_known_key__3M", |b| {
b.iter_custom(|times| {
let mut total = vec![];
for _ in 0..times {
let mut keys = Vec::with_capacity(3_000_000);
for i in 0..3_000_000 {
keys.push((format!("key_{i}"), i));
}
let start = Instant::now();
black_box(btreemap_known_key(black_box(keys.drain(..))));
total.push(start.elapsed());
}
total.iter().sum()
});
});
}
criterion_group! {
name = benches;
config = Criterion::default().sample_size(10);
targets = bench
}
criterion_main!(benches);
