TinyUFO: add the option to use sharded skip list for storage

This option makes it more memory efficient but a bit slower.

2 files changed, 107 insertions, 0 deletions

diff --git a/tinyufo/benches/bench_memory.rs b/tinyufo/benches/bench_memory.rs
index e55a561..9d49210 100644
--- a/tinyufo/benches/bench_memory.rs
+++ b/tinyufo/benches/bench_memory.rs
@@ -68,6 +68,22 @@ fn bench_tinyufo(zip_exp: f64, items: usize, cache_size_percent: f32) {
     }
 }
 
+fn bench_tinyufo_compact(zip_exp: f64, items: usize, cache_size_percent: f32) {
+    let cache_size = (cache_size_percent * items as f32).round() as usize;
+    let tinyufo = tinyufo::TinyUfo::new_compact(cache_size, (cache_size as f32 * 1.0) as usize);
+
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(items, zip_exp).unwrap();
+
+    for _ in 0..ITERATIONS {
+        let key = zipf.sample(&mut rng) as u64;
+
+        if tinyufo.get(&key).is_none() {
+            tinyufo.put(key, (), 1);
+        }
+    }
+}
+
 /*
 cargo bench --bench bench_memory
 
@@ -78,6 +94,8 @@ moka
 dhat: At t-gmax: 354,232 bytes in 1,581 blocks
 TinyUFO
 dhat: At t-gmax: 37,337 bytes in 351 blocks
+TinyUFO compat
+dhat: At t-gmax: 19,000 bytes in 60 blocks
 
 total items 10000, cache size 10%
 lru
@@ -86,6 +104,8 @@ moka
 dhat: At t-gmax: 535,320 bytes in 7,278 blocks
 TinyUFO
 dhat: At t-gmax: 236,053 bytes in 2,182 blocks
+TinyUFO Compact
+dhat: At t-gmax: 86,352 bytes in 1,128 blocks
 
 total items 100000, cache size 10%
 lru
@@ -94,6 +114,8 @@ moka
 dhat: At t-gmax: 2,489,088 bytes in 62,374 blocks
 TinyUFO
 dhat: At t-gmax: 2,290,635 bytes in 20,467 blocks
+TinyUFO
+dhat: At t-gmax: 766,024 bytes in 10,421 blocks
 */
 
 fn main() {
@@ -116,5 +138,11 @@ fn main() {
             bench_tinyufo(1.05, items, 0.1);
             println!("\nTinyUFO");
         }
+
+        {
+            let _profiler = dhat::Profiler::new_heap();
+            bench_tinyufo_compact(1.05, items, 0.1);
+            println!("\nTinyUFO Compact");
+        }
     }
 }
diff --git a/tinyufo/benches/bench_perf.rs b/tinyufo/benches/bench_perf.rs
index 1295fb2..bee8a11 100644
--- a/tinyufo/benches/bench_perf.rs
+++ b/tinyufo/benches/bench_perf.rs
@@ -32,6 +32,7 @@ Below is from Linux + Ryzen 5 7600 CPU
 lru read total 150.423567ms, 30ns avg per operation, 33239472 ops per second
 moka read total 462.133322ms, 92ns avg per operation, 10819389 ops per second
 tinyufo read total 199.007359ms, 39ns avg per operation, 25124698 ops per second
+tinyufo compact read total 331.145859ms, 66ns avg per operation, 15099087 ops per second
 
 lru read total 5.402631847s, 1.08µs avg per operation, 925474 ops per second
 ...
@@ -45,6 +46,10 @@ tinyufo read total 208.346855ms, 41ns avg per operation, 23998444 ops per second
 ...
 total 148691408 ops per second
 
+tinyufo compact read total 539.403037ms, 107ns avg per operation, 9269507 ops per second
+...
+total 74130632 ops per second
+
 lru mixed read/write 5.500309876s, 1.1µs avg per operation, 909039 ops per second, 407431 misses
 ...
 total 6846743 ops per second
@@ -56,6 +61,10 @@ total 16557962 ops per second
 tinyufo mixed read/write 456.134531ms, 91ns avg per operation, 10961678 ops per second, 294977 misses
 ...
 total 80865792 ops per second
+
+tinyufo compact mixed read/write 638.770053ms, 127ns avg per operation, 7827543 ops per second, 294641 misses
+...
+total 62600844 ops per second
 */
 
 fn main() {
@@ -63,12 +72,14 @@ fn main() {
     let lru = Mutex::new(lru::LruCache::<u64, ()>::unbounded());
     let moka = moka::sync::Cache::new(ITEMS as u64 + 10);
     let tinyufo = tinyufo::TinyUfo::new(ITEMS + 10, 10);
+    let tinyufo_compact = tinyufo::TinyUfo::new_compact(ITEMS + 10, 10);
 
     // populate first, then we bench access/promotion
     for i in 0..ITEMS {
         lru.lock().unwrap().put(i as u64, ());
         moka.insert(i as u64, ());
         tinyufo.put(i as u64, (), 1);
+        tinyufo_compact.put(i as u64, (), 1);
     }
 
     // single thread
@@ -108,6 +119,17 @@ fn main() {
         (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
     );
 
+    let before = Instant::now();
+    for _ in 0..ITERATIONS {
+        tinyufo_compact.get(&(zipf.sample(&mut rng) as u64));
+    }
+    let elapsed = before.elapsed();
+    println!(
+        "tinyufo compact read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+        elapsed / ITERATIONS as u32,
+        (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
     // concurrent
 
     let before = Instant::now();
@@ -185,6 +207,31 @@ fn main() {
         (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
     );
 
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(ITEMS, 1.03).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    tinyufo_compact.get(&(zipf.sample(&mut rng) as u64));
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "tinyufo compact read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
     ///// bench mixed read and write /////
     const CACHE_SIZE: usize = 1000;
     let items: usize = 10000;
@@ -287,4 +334,36 @@ fn main() {
         "total {} ops per second",
         (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
     );
+
+    let tinyufo_compact = tinyufo::TinyUfo::new(CACHE_SIZE, CACHE_SIZE);
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut miss_count = 0;
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(items, ZIPF_EXP).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    let key = zipf.sample(&mut rng) as u64;
+                    if tinyufo_compact.get(&key).is_none() {
+                        tinyufo_compact.put(key, (), 1);
+                        miss_count +=1;
+                    }
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "tinyufo compact mixed read/write {elapsed:?}, {:?} avg per operation, {} ops per second, {miss_count} misses",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32,
+                );
+            });
+        }
+    });
+
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
 }