diff options
| -rw-r--r-- | incria/Cargo.lock | 233 | ||||
| -rw-r--r-- | incria/Cargo.toml | 8 | ||||
| -rw-r--r-- | incria/README.md | 9 | ||||
| -rw-r--r-- | incria/examples/spreadsheet.rs | 28 | ||||
| -rw-r--r-- | incria/src/deps.rs | 12 | ||||
| -rw-r--r-- | incria/src/lib.rs | 5 | ||||
| -rw-r--r-- | incria/src/thunk.rs | 31 |
7 files changed, 69 insertions, 257 deletions
diff --git a/incria/Cargo.lock b/incria/Cargo.lock index d815c99..fa39449 100644 --- a/incria/Cargo.lock +++ b/incria/Cargo.lock @@ -9,24 +9,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" [[package]] -name = "bitflags" -version = "1.3.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" - -[[package]] -name = "bytes" -version = "1.4.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "89b2fd2a0dcf38d7971e2194b6b6eebab45ae01067456a7fd93d5547a61b70be" - -[[package]] -name = "cfg-if" -version = "1.0.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" - -[[package]] name = "hermit-abi" version = "0.2.6" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -36,11 +18,10 @@ dependencies = [ ] [[package]] -name = "inc" +name = "incria" version = "0.1.0" dependencies = [ "once_cell", - "parking_lot", "tokio", ] @@ -51,37 +32,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "2b00cc1c228a6782d0f076e7b232802e0c5689d41bb5df366f2a6b6621cfdfe1" [[package]] -name = "lock_api" -version = "0.4.9" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "435011366fe56583b16cf956f9df0095b405b82d76425bc8981c0e22e60ec4df" -dependencies = [ - "autocfg", - "scopeguard", -] - -[[package]] -name = "log" -version = "0.4.17" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "abb12e687cfb44aa40f41fc3978ef76448f9b6038cad6aef4259d3c095a2382e" -dependencies = [ - "cfg-if", -] - -[[package]] -name = "mio" -version = "0.8.6" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5b9d9a46eff5b4ff64b45a9e316a6d1e0bc719ef429cbec4dc630684212bfdf9" -dependencies = [ - "libc", - "log", - "wasi", - "windows-sys 0.45.0", -] - -[[package]] name = "num_cpus" version = "1.15.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -98,29 +48,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "b7e5500299e16ebb147ae15a00a942af264cf3688f47923b8fc2cd5858f23ad3" [[package]] -name = "parking_lot" -version = "0.12.1" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f" -dependencies = [ - "lock_api", - "parking_lot_core", -] - -[[package]] -name = "parking_lot_core" -version = "0.9.7" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9069cbb9f99e3a5083476ccb29ceb1de18b9118cafa53e90c9551235de2b9521" -dependencies = [ - "cfg-if", - "libc", - "redox_syscall", - "smallvec", - "windows-sys 0.45.0", -] - -[[package]] name = "pin-project-lite" version = "0.2.9" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -145,46 +72,6 @@ dependencies = [ ] [[package]] -name = "redox_syscall" -version = "0.2.16" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "fb5a58c1855b4b6819d59012155603f0b22ad30cad752600aadfcb695265519a" -dependencies = [ - "bitflags", -] - -[[package]] -name = "scopeguard" -version = "1.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd" - -[[package]] -name = "signal-hook-registry" -version = "1.4.1" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d8229b473baa5980ac72ef434c4415e70c4b5e71b423043adb4ba059f89c99a1" -dependencies = [ - "libc", -] - -[[package]] -name = "smallvec" -version = "1.10.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "a507befe795404456341dfab10cef66ead4c041f62b8b11bbb92bffe5d0953e0" - -[[package]] -name = "socket2" -version = "0.4.9" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "64a4a911eed85daf18834cfaa86a79b7d266ff93ff5ba14005426219480ed662" -dependencies = [ - "libc", - "winapi", -] - -[[package]] name = "syn" version = "2.0.16" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -202,16 +89,10 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "0aa32867d44e6f2ce3385e89dceb990188b8bb0fb25b0cf576647a6f98ac5105" dependencies = [ "autocfg", - "bytes", - "libc", - "mio", "num_cpus", - "parking_lot", "pin-project-lite", - "signal-hook-registry", - "socket2", "tokio-macros", - "windows-sys 0.48.0", + "windows-sys", ] [[package]] @@ -232,64 +113,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "e5464a87b239f13a63a501f2701565754bae92d243d4bb7eb12f6d57d2269bf4" [[package]] -name = "wasi" -version = "0.11.0+wasi-snapshot-preview1" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" - -[[package]] -name = "winapi" -version = "0.3.9" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" -dependencies = [ - "winapi-i686-pc-windows-gnu", - "winapi-x86_64-pc-windows-gnu", -] - -[[package]] -name = "winapi-i686-pc-windows-gnu" -version = "0.4.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" - -[[package]] -name = "winapi-x86_64-pc-windows-gnu" -version = "0.4.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" - -[[package]] -name = "windows-sys" -version = "0.45.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "75283be5efb2831d37ea142365f009c02ec203cd29a3ebecbc093d52315b66d0" -dependencies = [ - "windows-targets 0.42.2", -] - -[[package]] name = "windows-sys" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "677d2418bec65e3338edb076e806bc1ec15693c5d0104683f2efe857f61056a9" dependencies = [ - "windows-targets 0.48.0", -] - -[[package]] -name = "windows-targets" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "8e5180c00cd44c9b1c88adb3693291f1cd93605ded80c250a75d472756b4d071" -dependencies = [ - "windows_aarch64_gnullvm 0.42.2", - "windows_aarch64_msvc 0.42.2", - "windows_i686_gnu 0.42.2", - "windows_i686_msvc 0.42.2", - "windows_x86_64_gnu 0.42.2", - "windows_x86_64_gnullvm 0.42.2", - "windows_x86_64_msvc 0.42.2", + "windows-targets", ] [[package]] @@ -298,95 +127,53 @@ version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "7b1eb6f0cd7c80c79759c929114ef071b87354ce476d9d94271031c0497adfd5" dependencies = [ - "windows_aarch64_gnullvm 0.48.0", - "windows_aarch64_msvc 0.48.0", - "windows_i686_gnu 0.48.0", - "windows_i686_msvc 0.48.0", - "windows_x86_64_gnu 0.48.0", - "windows_x86_64_gnullvm 0.48.0", - "windows_x86_64_msvc 0.48.0", + "windows_aarch64_gnullvm", + "windows_aarch64_msvc", + "windows_i686_gnu", + "windows_i686_msvc", + "windows_x86_64_gnu", + "windows_x86_64_gnullvm", + "windows_x86_64_msvc", ] [[package]] name = "windows_aarch64_gnullvm" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "597a5118570b68bc08d8d59125332c54f1ba9d9adeedeef5b99b02ba2b0698f8" - -[[package]] -name = "windows_aarch64_gnullvm" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "91ae572e1b79dba883e0d315474df7305d12f569b400fcf90581b06062f7e1bc" [[package]] name = "windows_aarch64_msvc" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e08e8864a60f06ef0d0ff4ba04124db8b0fb3be5776a5cd47641e942e58c4d43" - -[[package]] -name = "windows_aarch64_msvc" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "b2ef27e0d7bdfcfc7b868b317c1d32c641a6fe4629c171b8928c7b08d98d7cf3" [[package]] name = "windows_i686_gnu" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c61d927d8da41da96a81f029489353e68739737d3beca43145c8afec9a31a84f" - -[[package]] -name = "windows_i686_gnu" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "622a1962a7db830d6fd0a69683c80a18fda201879f0f447f065a3b7467daa241" [[package]] name = "windows_i686_msvc" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "44d840b6ec649f480a41c8d80f9c65108b92d89345dd94027bfe06ac444d1060" - -[[package]] -name = "windows_i686_msvc" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "4542c6e364ce21bf45d69fdd2a8e455fa38d316158cfd43b3ac1c5b1b19f8e00" [[package]] name = "windows_x86_64_gnu" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "8de912b8b8feb55c064867cf047dda097f92d51efad5b491dfb98f6bbb70cb36" - -[[package]] -name = "windows_x86_64_gnu" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "ca2b8a661f7628cbd23440e50b05d705db3686f894fc9580820623656af974b1" [[package]] name = "windows_x86_64_gnullvm" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "26d41b46a36d453748aedef1486d5c7a85db22e56aff34643984ea85514e94a3" - -[[package]] -name = "windows_x86_64_gnullvm" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "7896dbc1f41e08872e9d5e8f8baa8fdd2677f29468c4e156210174edc7f7b953" [[package]] name = "windows_x86_64_msvc" -version = "0.42.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9aec5da331524158c6d1a4ac0ab1541149c0b9505fde06423b02f5ef0106b9f0" - -[[package]] -name = "windows_x86_64_msvc" version = "0.48.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "1a515f5799fe4961cb532f983ce2b23082366b898e52ffbce459c86f67c8378a" diff --git a/incria/Cargo.toml b/incria/Cargo.toml index 64fe414..1ff3824 100644 --- a/incria/Cargo.toml +++ b/incria/Cargo.toml @@ -1,9 +1,11 @@ [package] -name = "inc" +name = "incria" version = "0.1.0" edition = "2021" [dependencies] once_cell = "1.17.1" -parking_lot = "0.12.1" -tokio = { version = "1.28.1", features = ["full"] } +tokio = { version = "1.28.1", features = ["sync", "rt"] } + +[dev-dependencies] +tokio = { version = "1.28.1", features = ["macros", "sync", "rt-multi-thread"] } diff --git a/incria/README.md b/incria/README.md new file mode 100644 index 0000000..01c8438 --- /dev/null +++ b/incria/README.md @@ -0,0 +1,9 @@ +# incria + +Incria is a library for incremental computation. +It lets you record what a calculation depends on and then only re-run that calculation once one of those dependencies has changed. + +This is similar to the [query system used by the Rust compiler](https://rustc-dev-guide.rust-lang.org/query.html), but implemented using async. +By seperating the tracking of dependencies from the calculation logic, you can write clean code that re-runs only when it needs to, and can be parallelised with little extra work. + +For more info, read the rustdoc or check the [/examples](examples). diff --git a/incria/examples/spreadsheet.rs b/incria/examples/spreadsheet.rs index 40b1d5c..135ca80 100644 --- a/incria/examples/spreadsheet.rs +++ b/incria/examples/spreadsheet.rs @@ -1,6 +1,6 @@ use std::{future::Future, pin::Pin}; -use inc::{ +use incria::{ deps, thunk::{Thunk, ThunkMapper}, Mapper, @@ -11,41 +11,41 @@ type Key = (usize, usize); type Value = usize; #[derive(Debug, Default)] -struct CellComputer; +struct CellThunk; -impl Thunk<Key, Value> for CellComputer { +impl Thunk<Key, Value> for CellThunk { fn compute(&self, key: Key) -> Pin<Box<dyn Future<Output = Value> + Send + '_>> { Box::pin(async move { if key.0 > 0 { - let prev1 = *cell_store().get(&(key.0 - 1, key.1 - 1)).await; - let prev2 = *cell_store().get(&(key.0 - 1, key.1)).await; - let prev3 = *cell_store().get(&(key.0 - 1, key.1 + 1)).await; + let prev1 = *cell_mapping().get(&(key.0 - 1, key.1 - 1)).await; + let prev2 = *cell_mapping().get(&(key.0 - 1, key.1)).await; + let prev3 = *cell_mapping().get(&(key.0 - 1, key.1 + 1)).await; prev1 + prev2 + prev3 } else { - key.1 + 1 } }) } } -type CellStore = ThunkMapper<Key, Value, CellComputer>; -static CELL_STORE: OnceCell<CellStore> = OnceCell::new(); -fn cell_store() -> &'static CellStore { - CELL_STORE.get_or_init(CellStore::default) +type CellMapping = ThunkMapper<Key, Value, CellThunk>; +static CELL_MAPPING: OnceCell<CellMapping> = OnceCell::new(); +fn cell_mapping() -> &'static CellMapping { + CELL_MAPPING.get_or_init(CellMapping::default) } -const N: usize = 5; +const N: usize = 20; #[tokio::main] async fn main() { deps::with_node_id(deps::next_node_id(), async { - let val = *dbg!(cell_store().get(&(N, N)).await); + let val = *dbg!(cell_mapping().get(&(N, N)).await); // println!("{}", dep_graphviz()); deps::mark_dirty(21); // println!("{}", dep_graphviz()); - assert_eq!(val, *cell_store().get(&(N, N)).await); + assert_eq!(val, *cell_mapping().get(&(N, N)).await); println!("{}", deps::dep_graphviz()); }) .await; diff --git a/incria/src/deps.rs b/incria/src/deps.rs index 84411c0..d72e684 100644 --- a/incria/src/deps.rs +++ b/incria/src/deps.rs @@ -13,10 +13,10 @@ use std::{ collections::{HashMap, VecDeque}, fmt::Write, future::Future, + sync::Mutex, }; use once_cell::sync::OnceCell; -use parking_lot::Mutex; /// Identifier of a node, unique across a program run. pub type NodeId = usize; @@ -42,6 +42,7 @@ impl DepTracker { fn add_dep(&self, dep: NodeId) { self.deps .lock() + .unwrap() .entry(NODE_ID.get()) .and_modify(|v| v.deps.push(dep)) .or_insert(NodeInfo { @@ -52,14 +53,14 @@ impl DepTracker { /// See [`self::next_node_id`] fn next_node_id(&self) -> usize { - let mut lock = self.next_node_id.lock(); + let mut lock = self.next_node_id.lock().unwrap(); *lock += 1; *lock - 1 } /// See [`self::mark_dirty`] fn mark_dirty(&self, node: NodeId) { - let mut lock = self.deps.lock(); + let mut lock = self.deps.lock().unwrap(); let mut frontier = VecDeque::new(); frontier.push_back(node); while let Some(node_id) = frontier.pop_front() { @@ -85,6 +86,7 @@ impl DepTracker { fn is_dirty(&self, node: NodeId) -> bool { self.deps .lock() + .unwrap() .get(&node) .map(|v| v.dirty) .unwrap_or(false) @@ -92,7 +94,7 @@ impl DepTracker { /// See [`self::clear`] fn clear(&self, node: NodeId) { - let mut lock = self.deps.lock(); + let mut lock = self.deps.lock().unwrap(); let node = match lock.get_mut(&node) { Some(x) => x, None => return, @@ -154,7 +156,7 @@ pub fn clear(dep: NodeId) { /// Dirty nodes will be coloured grey. pub fn dep_graphviz() -> String { let mut out = String::new(); - let deps = dep_tracker().deps.lock(); + let deps = dep_tracker().deps.lock().unwrap(); writeln!(&mut out, "digraph G {{").unwrap(); for (id, info) in deps.iter() { if *id == 0 { diff --git a/incria/src/lib.rs b/incria/src/lib.rs index 2f52fbb..c8c35d6 100644 --- a/incria/src/lib.rs +++ b/incria/src/lib.rs @@ -1,4 +1,9 @@ #![feature(async_fn_in_trait)] +//! Incria is a library for incremental computation. +//! It lets you record what a calculation depends on and then only re-run that calculation once one of those dependencies has changed. +//! +//! This is similar to the [query system used by the Rust compiler](https://rustc-dev-guide.rust-lang.org/query.html), but implemented using async. +//! By seperating the tracking of dependencies from the calculation logic, you can write clean code that re-runs only when it needs to, and can be parallelised with little extra work. pub mod deps; mod mapping; diff --git a/incria/src/thunk.rs b/incria/src/thunk.rs index 6aa44dd..f076ba1 100644 --- a/incria/src/thunk.rs +++ b/incria/src/thunk.rs @@ -1,8 +1,7 @@ //! A mapper based on a function from keys to values. use std::{collections::HashMap, hash::Hash, pin::Pin, sync::Arc}; -use parking_lot::{MappedRwLockReadGuard, Mutex, RwLock, RwLockReadGuard}; -use tokio::sync::Notify; +use tokio::sync::{Mutex, Notify, RwLock, RwLockReadGuard}; use crate::{ deps::{self, NodeId}, @@ -39,13 +38,13 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, C: Thunk<K, V>> Mapper { type Key = K; type Value = V; - type Wrapper<'a> = MappedRwLockReadGuard<'a, V> where V: 'a; + type Wrapper<'a> = RwLockReadGuard<'a, V> where V: 'a; async fn get<'a>(&'a self, key: &Self::Key) -> Self::Wrapper<'a> { // Attempt to reuse or evict the existing value let mut reuse_dep_id = None; { - let finished = self.calculated.read(); + let finished = self.calculated.read().await; if let Some((_, dep)) = finished.get(key) { if !deps::is_dirty(*dep) { deps::add_dep(*dep); @@ -54,7 +53,7 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, C: Thunk<K, V>> Mapper reuse_dep_id = Some(*dep); drop(finished); // Dirty, so we'll recompute below but we should remove it now - if self.calculated.write().remove(key).is_none() { + if self.calculated.write().await.remove(key).is_none() { // Someone else already noticed it was dirty and removed it before us, so we need to deal with that todo!("dirty value removed between us noticing and us doing something") } @@ -62,19 +61,22 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, C: Thunk<K, V>> Mapper } } - let barrier = self.waiting.lock().get(key).cloned(); + let barrier = self.waiting.lock().await.get(key).cloned(); if let Some(barrier) = barrier { // Waiting for completion barrier.notified().await; - let val = RwLockReadGuard::map(self.calculated.read(), |hm| hm.get(key).unwrap()); + let val = RwLockReadGuard::map(self.calculated.read().await, |hm| hm.get(key).unwrap()); deps::add_dep(val.1); - return MappedRwLockReadGuard::map(val, |inf| &inf.0); + return RwLockReadGuard::map(val, |inf| &inf.0); } else { // Needs calculated let notify = Arc::new(Notify::new()); - self.waiting.lock().insert(key.clone(), notify.clone()); + self.waiting + .lock() + .await + .insert(key.clone(), notify.clone()); let dep = if let Some(x) = reuse_dep_id { deps::clear(x); @@ -86,12 +88,17 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, C: Thunk<K, V>> Mapper let val = deps::with_node_id(dep, self.thunk.compute(key.clone())).await; deps::add_dep(dep); - self.calculated.write().insert(key.clone(), (val, dep)); - self.waiting.lock().remove(key); + self.calculated + .write() + .await + .insert(key.clone(), (val, dep)); + self.waiting.lock().await.remove(key); notify.notify_waiters(); - return RwLockReadGuard::map(self.calculated.read(), |hm| &hm.get(key).unwrap().0); + return RwLockReadGuard::map(self.calculated.read().await, |hm| { + &hm.get(key).unwrap().0 + }); } } } |