no locks when calculating next node id

2 files changed, 18 insertions, 9 deletions

diff --git a/incria/src/deps.rs b/incria/src/deps.rs
index f94d3ff..924eb3f 100644
--- a/incria/src/deps.rs
+++ b/incria/src/deps.rs
@@ -10,29 +10,32 @@
 //!
 //! [`self::is_dirty`] should be used when a mapping is retrieved to determine if it needs to be re-evaluated. If it does, [`self::clear`] should be used to reset the mapping's dependencies and dirty state.
 use std::{
+    cell::RefCell,
     collections::{HashMap, VecDeque},
     fmt::Write,
     future::Future,
     sync::{Mutex, OnceLock},
+    thread,
 };
 
 /// Identifier of a node, unique across a program run.
-pub type NodeId = usize;
+pub type NodeId = u64;
 
 tokio::task_local! {
     /// The ID of the node in the dependency tree for the currently running computation
     static NODE_ID: NodeId;
 }
 
+thread_local! {
+    static NEXT_NODE_ID_LSB: RefCell<u64> = RefCell::new(5);
+}
+
 /// Responsible for tracking dependencies.
 /// There is one global instance of this, [`DEP_TRACKER`], with convenience functions for most of its functionality.
 #[derive(Default)]
 struct DepTracker {
     /// Neighbour-List representation of dependency tree
     deps: Mutex<HashMap<NodeId, NodeInfo>>,
-
-    /// Next node ID to issue
-    next_node_id: Mutex<NodeId>,
 }
 
 impl DepTracker {
@@ -50,10 +53,15 @@ impl DepTracker {
     }
 
     /// See [`self::next_node_id`]
-    fn next_node_id(&self) -> usize {
-        let mut lock = self.next_node_id.lock().unwrap();
-        *lock += 1;
-        *lock - 1
+    fn next_node_id(&self) -> NodeId {
+        let tid = thread::current().id().as_u64();
+        let lsb = NEXT_NODE_ID_LSB.with(|lsb| {
+            let old = *lsb.borrow();
+            *lsb.borrow_mut() = old + 1;
+            old
+        });
+
+        (tid.get() << 32) | (lsb & 0xffffffff)
     }
 
     /// See [`self::mark_dirty`]
@@ -160,6 +168,7 @@ pub fn dep_graphviz() -> String {
         } else if info.dirty {
             writeln!(&mut out, "\t{} [style=filled,color=lightgrey]", id).unwrap();
         }
+
         for dep in info.dependents.iter() {
             writeln!(&mut out, "\t{} -> {}", dep, id).unwrap();
         }
diff --git a/incria/src/lib.rs b/incria/src/lib.rs
index 7cd7164..24fa23d 100644
--- a/incria/src/lib.rs
+++ b/incria/src/lib.rs
@@ -1,4 +1,4 @@
-#![feature(async_fn_in_trait)]
+#![feature(async_fn_in_trait, thread_id_value)]
 /*!
 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.