lasso

一个多线程和单线程的字符串驻留工具，允许以最小的内存占用缓存字符串，并将其与唯一的[键]关联，可随时用于检索。Rodeo提供O(1)复杂度的驻留和解析操作，可转换为RodeoReader以实现无竞争的解析，支持键到字符串和字符串到键的操作。还可以转换为仅支持键到字符串操作的RodeoResolver，以实现最低的内存使用。

我应该使用哪个驻留器？

对于单线程工作负载，建议使用Rodeo，而多线程应用程序应使用ThreadedRodeo。这两种方式是驻留字符串的唯一方法，但大多数应用程序在完成字符串驻留后，需要在RodeoReader和RodeoResolver之间做出选择。如果用户仍需要获取字符串的键，则必须使用RodeoReader（尽管仍可以转换为RodeoResolver）。对于只需要键到字符串解析的用户，RodeoResolver提供无竞争访问，且内存使用量最小。注意，要使用ThreadedRodeo，需要启用multi-threaded功能。

驻留器	线程安全	驻留字符串	字符串到键	键到字符串	无竞争	内存使用
Rodeo	❌	✅	✅	✅	N/A	中等
ThreadedRodeo	✅	✅	✅	✅	❌	最多
RodeoReader	✅	❌	✅	✅	✅	中等
RodeoResolver	✅	❌	❌	✅	✅	最少

Cargo 功能

默认情况下，lasso只有一个依赖项hashbrown，并且只暴露Rodeo。使用Hashbrown是因为标准库的hashmap中的raw_entry API目前还不稳定。原始hashmap API用于哈希表中的自定义哈希，这大大减少了内存使用。要使用ThreadedRodeo，必须启用multi-threaded功能。

• multi-threaded - 启用ThreadedRodeo，用于多线程任务的驻留器
• ahasher - 使用ahash的RandomState作为默认哈希器
• no-std - 为Rodeo和ThreadedRodeo启用no_std + alloc支持
  • 自动启用以下必需功能：
    • ahasher - no_std哈希函数
• serialize - 为所有Spur类型和所有驻留器实现Serialize和Deserialize
• inline-more - 用#[inline]注释外部API

示例：使用Rodeo

use lasso::Rodeo;

let mut rodeo = Rodeo::default();
let key = rodeo.get_or_intern("Hello, world!");

// 轻松检索键的值并查找值的键
assert_eq!("Hello, world!", rodeo.resolve(&key));
assert_eq!(Some(key), rodeo.get("Hello, world!"));

// 再次驻留相同的字符串将产生相同的键
let key2 = rodeo.get_or_intern("Hello, world!");

assert_eq!(key, key2);

示例：使用ThreadedRodeo

use lasso::ThreadedRodeo;
use std::{thread, sync::Arc};

let rodeo = Arc::new(ThreadedRodeo::default());
let key = rodeo.get_or_intern("Hello, world!");

// 轻松检索键的值并查找值的键
assert_eq!("Hello, world!", rodeo.resolve(&key));
assert_eq!(Some(key), rodeo.get("Hello, world!"));

// 再次驻留相同的字符串将产生相同的键
let key2 = rodeo.get_or_intern("Hello, world!");

assert_eq!(key, key2);

// ThreadedRodeo可以在线程间共享
let moved = Arc::clone(&rodeo);
let hello = thread::spawn(move || {
    assert_eq!("Hello, world!", moved.resolve(&key));
    moved.get_or_intern("Hello from the thread!")
})
.join()
.unwrap();

assert_eq!("Hello, world!", rodeo.resolve(&key));
assert_eq!("Hello from the thread!", rodeo.resolve(&hello));

示例：创建RodeoReader

use lasso::Rodeo;

// Rodeo和ThreadedRodeo在这里可以互换
let mut rodeo = Rodeo::default();

let key = rodeo.get_or_intern("Hello, world!");
assert_eq!("Hello, world!", rodeo.resolve(&key));

let reader = rodeo.into_reader();

// Reader保留了父对象的所有字符串
assert_eq!("Hello, world!", reader.resolve(&key));
assert_eq!(Some(key), reader.get("Hello, world!"));

// 现在Reader可以在线程间共享，无论是由哪种Rodeo创建的

示例：创建RodeoResolver

use lasso::Rodeo;

// Rodeo和ThreadedRodeo在这里可以互换
let mut rodeo = Rodeo::default();

let key = rodeo.get_or_intern("Hello, world!");
assert_eq!("Hello, world!", rodeo.resolve(&key));

let resolver = rodeo.into_resolver();

// Resolver保留了父对象的所有字符串
assert_eq!("Hello, world!", resolver.resolve(&key));

// 现在Resolver可以在线程间共享，无论是由哪种Rodeo创建的

示例：创建自定义范围的键

有时你希望你的键只占用（或不占用）某个特定的值范围，这样你就可以有自定义的[空位]。这允许你在原本未使用的空间中打包更多数据，这对内存敏感的应用程序至关重要。

use lasso::{Key, Rodeo};

// 首先创建我们的键类型，这将作为我们驻留器的句柄
#[derive(Copy, Clone, PartialEq, Eq)]
struct NicheKey(u32);

// 这将为我们保留上面255个值作为空位
const NICHE: usize = 0xFF000000;

// 实现`Key`是不安全的，并且要求任何给予`try_from_usize`的内容在后续调用`into_usize`时必须产生相同的`usize`
unsafe impl Key for NicheKey {
    fn into_usize(self) -> usize {
        self.0 as usize
    }

    fn try_from_usize(int: usize) -> Option<Self> {
        if int < NICHE {
            // 该值不在我们的空位范围内，所以可以使用
            Some(Self(int as u32))
        } else {
            // 该值与我们的空位冲突，所以返回`None`
            None
        }
    }
}

// 为确保我们遵守`Key`的安全合约，让我们做两个小测试
#[test]
fn value_in_range() {
    let key = NicheKey::try_from_usize(0).unwrap();
    assert_eq!(key.into_usize(), 0);

    let key = NicheKey::try_from_usize(NICHE - 1).unwrap();
    assert_eq!(key.into_usize(), NICHE - 1);
}

#[test]
fn value_out_of_range() {
    let key = NicheKey::try_from_usize(NICHE);
    assert!(key.is_none());

    let key = NicheKey::try_from_usize(u32::max_value() as usize);
    assert!(key.is_none());
}

// 现在我们完成了，可以创建使用我们自定义键的`Rodeo`或`ThreadedRodeo`！
let mut rodeo: Rodeo<NicheKey> = Rodeo::new();
let key = rodeo.get_or_intern("It works!");
assert_eq!(rodeo.resolve(&key), "It works!");

示例：使用FromIterator创建

use lasso::Rodeo;
use core::iter::FromIterator;

// 适用于`Rodeo`和`ThreadedRodeo`
let rodeo = Rodeo::from_iter(vec![
    "one string",
    "two string",
    "red string",
    "blue string",
]);

assert!(rodeo.contains("one string"));
assert!(rodeo.contains("two string"));
assert!(rodeo.contains("red string"));
assert!(rodeo.contains("blue string"));

use lasso::Rodeo;
use core::iter::FromIterator;

// 适用于`Rodeo`和`ThreadedRodeo`
let rodeo: Rodeo = vec!["one string", "two string", "red string", "blue string"]
    .into_iter()
    .collect();

assert!(rodeo.contains("one string"));
assert!(rodeo.contains("two string"));
assert!(rodeo.contains("red string"));
assert!(rodeo.contains("blue string"));

基准测试

基准测试使用Criterion.rs进行
操作系统：Windows 10
CPU：Ryzen 9 3900X，3800Mhz
内存：3200Mhz
Rustc：稳定版 1.44.1

Rodeo

STD RandomState

方法	时间	吞吐量
resolve	1.9251 μs	13.285 GiB/s
try_resolve	1.9214 μs	13.311 GiB/s
resolve_unchecked	1.4356 μs	17.816 GiB/s
get_or_intern（空）	60.350 μs	433.96 MiB/s
get_or_intern（已填充）	57.415 μs	456.15 MiB/s
try_get_or_intern（空）	58.978 μs	444.06 MiB/s
try_get_or_intern（已填充）	57.421 μs	456.10 MiB/s
get（空）	37.288 μs	702.37 MiB/s
get（已填充）	55.095 μs	475.36 MiB/s

AHash

方法	时间	吞吐量
try_resolve	1.9282 μs	13.264 GiB/s
resolve	1.9404 μs	13.181 GiB/s
resolve_unchecked	1.4328 μs	17.851 GiB/s
get_or_intern（空）	38.029 μs	688.68 MiB/s
get_or_intern（已填充）	33.650 μs	778.30 MiB/s
try_get_or_intern（空）	39.392 μs	664.84 MiB/s
try_get_or_intern（已填充）	33.435 μs	783.31 MiB/s
get（空）	12.565 μs	2.0356 GiB/s
get（已填充）	26.545 μs	986.61 MiB/s

FXHash

方法	时间	吞吐量
resolve	1.9014 μs	13.451 GiB/s
try_resolve	1.9278 μs	13.267 GiB/s
resolve_unchecked	1.4449 μs	17.701 GiB/s
get_or_intern（空）	32.523 μs	805.27 MiB/s
get_or_intern（已填充）	30.281 μs	864.88 MiB/s
try_get_or_intern（空）	31.630 μs	828.00 MiB/s
try_get_or_intern（已填充）	31.002 μs	844.78 MiB/s
get（空）	12.699 μs	2.0141 GiB/s
get（已填充）	29.220 μs	896.28 MiB/s

ThreadedRodeo

STD RandomState

方法	时间（1线程）	吞吐量（1线程）	时间（24线程）	吞吐量（24线程）
resolve	54.336 μs	482.00 MiB/s	364.27 μs	71.897 MiB/s
try_resolve	54.582 μs	479.82 MiB/s	352.67 μs	74.261 MiB/s
get_or_intern（空）	266.03 μs	98.447 MiB/s	不适用	不适用
get_or_intern（已填充）	103.04 μs	254.17 MiB/s	441.42 μs	59.331 MiB/s
try_get_or_intern（空）	261.80 μs	100.04 MiB/s	不适用	不适用
try_get_or_intern（已填充）	102.61 μs	255.25 MiB/s	447.42 μs	58.535 MiB/s
get（空）	80.346 μs	325.96 MiB/s	不适用	不适用
get（已填充）	92.669 μs	282.62 MiB/s	439.24 μs	59.626 MiB/s

AHash

方法	时间（1线程）	吞吐量（1线程）	时间（24线程）	吞吐量（24线程）
resolve	22.261 μs	1.1489 GiB/s	265.46 μs	98.658 MiB/s
try_resolve	22.378 μs	1.1429 GiB/s	268.58 μs	97.513 MiB/s
get_or_intern（空）	157.86 μs	165.91 MiB/s	不适用	不适用
get_or_intern（已填充）	56.320 μs	465.02 MiB/s	357.13 μs	73.335 MiB/s
try_get_or_intern（空）	161.46 μs	162.21 MiB/s	不适用	不适用
try_get_or_intern（已填充）	55.874 μs	468.73 MiB/s	360.25 μs	72.698 MiB/s
get（空）	43.520 μs	601.79 MiB/s	不适用	不适用
get（已填充）	53.720 μs	487.52 MiB/s	360.66 μs	72.616 MiB/s

FXHash

方法	时间（1线程）	吞吐量（1线程）	时间（24线程）	吞吐量（24线程）
try_resolve	17.289 μs	1.4794 GiB/s	238.29 μs	109.91 MiB/s
resolve	19.833 μs	1.2896 GiB/s	237.05 μs	110.48 MiB/s
get_or_intern（空）	130.97 μs	199.97 MiB/s	不适用	不适用
get_or_intern（已填充）	42.630 μs	614.35 MiB/s	301.60 μs	86.837 MiB/s
try_get_or_intern（空）	129.30 μs	202.55 MiB/s	不适用	不适用
try_get_or_intern（已填充）	42.508 μs	616.12 MiB/s	337.29 μs	77.648 MiB/s
get（空）	28.001 μs	935.30 MiB/s	不适用	不适用
get（已填充）	37.700 μs	694.68 MiB/s	292.15 μs	89.645 MiB/s

RodeoReader

STD RandomState

方法	时间（1线程）	吞吐量（1线程）	时间（24线程）	吞吐量（24线程）
resolve	1.9398 μs	13.185 GiB/s	4.3153 μs	5.9269 GiB/s
try_resolve	1.9315 μs	13.242 GiB/s	4.1956 μs	6.0959 GiB/s
resolve_unchecked	1.4416 μs	17.741 GiB/s	3.1204 μs	8.1964 GiB/s
get（空）	38.886 μs	673.50 MiB/s	不适用	不适用
get（已填充）	56.271 μs	465.42 MiB/s	105.12 μs	249.14 MiB/s

AHash

方法	时间 (1 线程)	吞吐量 (1 线程)	时间 (24 线程)	吞吐量 (24 线程)
resolve	1.9404 μs	13.181 GiB/s	4.1881 μs	6.1069 GiB/s
try_resolve	1.8932 μs	13.509 GiB/s	4.2410 μs	6.0306 GiB/s
resolve_unchecked	1.4128 μs	18.103 GiB/s	3.1691 μs	8.0703 GiB/s
get (空)	11.952 μs	2.1399 GiB/s	不适用	不适用
get (已填充)	27.093 μs	966.65 MiB/s	56.269 μs	465.44 MiB/s

FXHash

方法	时间 (1 线程)	吞吐量 (1 线程)	时间 (24 线程)	吞吐量 (24 线程)
resolve	1.8987 μs	13.471 GiB/s	4.2117 μs	6.0727 GiB/s
try_resolve	1.9103 μs	13.389 GiB/s	4.2254 μs	6.0529 GiB/s
resolve_unchecked	1.4469 μs	17.677 GiB/s	3.0923 μs	8.2709 GiB/s
get (空)	12.994 μs	1.9682 GiB/s	不适用	不适用
get (已填充)	29.745 μs	880.49 MiB/s	52.387 μs	499.93 MiB/s

RodeoResolver

方法	时间 (1 线程)	吞吐量 (1 线程)	时间 (24 线程)	吞吐量 (24 线程)
resolve	1.9416 μs	13.172 GiB/s	3.9114 μs	6.5387 GiB/s
try_resolve	1.9264 μs	13.277 GiB/s	3.9289 μs	6.5097 GiB/s
resolve_unchecked	1.6638 μs	15.372 GiB/s	3.1741 μs	8.0578 GiB/s