水印

一个简单的水印集合。

水印集合可以持有任何整数值，并支持两种操作

• insert(element: T)
  • 将项目插入集合
• contains(element: T)
  • 检查项目是否曾经添加到集合中

水印集合在“插入”全部发生，并且主要按顺序发生时表现最佳。例如，在跟踪已看到的消息 ID 时。

示例

创建一个简单的幂等数据处理程序

let mut ws = watermark::WatermarkSet::default();
for message in message_bus {
  if !ws.contains(message.id) {
    ws.insert(message.id);
    // Do some work with message.data
  }
}

操作

内部，水印集合包含一个“水印”和一个“最近添加”项目的位向量。水印保证所有低于该数值的项目都已看到，而最近添加的项目处理其他一切。这意味着如果所有元素最终都添加了，内存使用率将保持非常低，成员资格测试也非常便宜。

性能

此 crate 随附一些简单的基准测试，您可以自己运行。以下是我机器上与哈希集相比的结果

Specs:
 - AMD Ryzen 7 3700x 8-Core Processor
 - 2x16gb DDR4 3200

WatermarkSet Insert/In Order
                        time:   [7.6194 us 7.8101 us 7.9793 us]
                        thrpt:  [125.32 Melem/s 128.04 Melem/s 131.24 Melem/s]

HashSet Insert/In Order time:   [40.319 us 40.340 us 40.372 us]
                        thrpt:  [24.770 Melem/s 24.789 Melem/s 24.802 Melem/s]
Found 8 outliers among 100 measurements (8.00%)
  1 (1.00%) low severe
  2 (2.00%) low mild
  3 (3.00%) high mild
  2 (2.00%) high severe

WatermarkSet Insert/Out of Order
                        time:   [9.1897 us 9.4983 us 9.7602 us]
                        thrpt:  [102.46 Melem/s 105.28 Melem/s 108.82 Melem/s]

HashSet Insert/Out of Order
                        time:   [26.327 us 26.342 us 26.355 us]
                        thrpt:  [37.943 Melem/s 37.962 Melem/s 37.983 Melem/s]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

WatermarkSet Contains/Aligned
                        time:   [242.04 ns 242.25 ns 242.47 ns]
                        thrpt:  [2.6396 Gelem/s 2.6419 Gelem/s 2.6442 Gelem/s]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe

HashSet Contains/Aligned
                        time:   [7.6920 us 7.7382 us 7.8144 us]
                        thrpt:  [81.900 Melem/s 82.706 Melem/s 83.204 Melem/s]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe

WatermarkSet Contains/Unaligned
                        time:   [290.21 ns 290.39 ns 290.56 ns]
                        thrpt:  [2.2026 Gelem/s 2.2039 Gelem/s 2.2053 Gelem/s]
Found 4 outliers among 100 measurements (4.00%)
  2 (2.00%) low mild
  1 (1.00%) high mild
  1 (1.00%) high severe

HashSet Contains/Unaligned
                        time:   [7.9000 us 7.9021 us 7.9043 us]
                        thrpt:  [80.969 Melem/s 80.991 Melem/s 81.012 Melem/s]
Found 5 outliers among 100 measurements (5.00%)
  1 (1.00%) low mild
  3 (3.00%) high mild
  1 (1.00%) high severe