lasso

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

我应该使用哪个驻留器？

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

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

AHash

FXHash

ThreadedRodeo

STD RandomState

AHash

FXHash

RodeoReader

STD RandomState

AHash

FXHash

RodeoResolver