From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68]) by lore.proxmox.com (Postfix) with ESMTPS id BAC081FF283 for ; Mon, 29 Sep 2025 15:12:46 +0200 (CEST) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id B7B15128B0; Mon, 29 Sep 2025 15:12:52 +0200 (CEST) From: Dominik Csapak To: yew-devel@lists.proxmox.com Date: Mon, 29 Sep 2025 15:12:10 +0200 Message-ID: <20250929131219.2932214-2-d.csapak@proxmox.com> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20250929131219.2932214-1-d.csapak@proxmox.com> References: <20250929131219.2932214-1-d.csapak@proxmox.com> MIME-Version: 1.0 X-SPAM-LEVEL: Spam detection results: 0 AWL 0.027 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DMARC_MISSING 0.1 Missing DMARC policy KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record Subject: [yew-devel] [PATCH yew-widget-toolkit 2/3] state: keyed slab tree: add key -> node_id cache X-BeenThere: yew-devel@lists.proxmox.com X-Mailman-Version: 2.1.29 Precedence: list List-Id: Yew framework devel list at Proxmox List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Yew framework devel list at Proxmox Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: yew-devel-bounces@lists.proxmox.com Sender: "yew-devel" The methods `find_node_by_key` and `find_node_by_key_mut` have to linearly search for the key in the tree. When doing that for a large number of keys, this becomes very slow. To speed that up, introduce a `key_cache`, which is just a `HashMap` that points to the node_id in the slab tree. We have to be careful to update this cache with every insert or remove operation. * on insert, add the new entry into the cache * on removal, remove the entry and do it recursively for all children of that node * on bulk append: iterate over the newly added subtree and add the keys * on tree/root replace: recalculate the cache for the whole tree. Signed-off-by: Dominik Csapak --- src/state/tree_store/keyed_slab_tree.rs | 94 ++++++++++++++++++------- 1 file changed, 69 insertions(+), 25 deletions(-) diff --git a/src/state/tree_store/keyed_slab_tree.rs b/src/state/tree_store/keyed_slab_tree.rs index e26780c..df163a2 100644 --- a/src/state/tree_store/keyed_slab_tree.rs +++ b/src/state/tree_store/keyed_slab_tree.rs @@ -1,5 +1,5 @@ -use std::cmp::Ordering; use std::collections::HashSet; +use std::{cmp::Ordering, collections::HashMap}; use slab::Slab; @@ -30,6 +30,8 @@ pub struct KeyedSlabTree { listeners: Slab>, + key_cache: HashMap, + pub(crate) view_root: bool, } @@ -98,7 +100,7 @@ impl KeyedSlabTreeNodeMut<'_, T> { /// Find a node by key. pub fn find_node_by_key(&self, key: &Key) -> Option> { self.tree - .find_subnode_by_key(self.node_id, key) + .find_subnode_by_key(key) .map(|node_id| KeyedSlabTreeNodeRef { node_id, tree: self.tree, @@ -108,7 +110,7 @@ impl KeyedSlabTreeNodeMut<'_, T> { /// Find a node by key (mutable). pub fn find_node_by_key_mut(&mut self, key: &Key) -> Option> { self.tree - .find_subnode_by_key(self.node_id, key) + .find_subnode_by_key(key) .map(|node_id| KeyedSlabTreeNodeMut { node_id, tree: self.tree, @@ -189,7 +191,7 @@ impl KeyedSlabTreeNodeRef<'_, T> { /// Find a node by key. pub fn find_node_by_key(&self, key: &Key) -> Option> { self.tree - .find_subnode_by_key(self.node_id, key) + .find_subnode_by_key(key) .map(|node_id| KeyedSlabTreeNodeRef { node_id, tree: self.tree, @@ -240,6 +242,7 @@ impl KeyedSlabTree { filter: None, listeners: Slab::new(), view_root: true, + key_cache: HashMap::new(), } } @@ -374,7 +377,10 @@ impl KeyedSlabTree { /// /// The current tree (if any) is discarded. pub fn set_root(&mut self, record: T) -> KeyedSlabTreeNodeMut { + self.key_cache.clear(); + let key = self.extract_key(&record); let node = self.tree.set_root(record); + self.key_cache.insert(key, node.node_id); KeyedSlabTreeNodeMut { node_id: node.node_id, tree: self, @@ -386,6 +392,7 @@ impl KeyedSlabTree { /// The current tree (if any) is discarded. pub fn set_root_tree(&mut self, data: impl Into>) { self.tree.set_root_tree(data); + self.key_cache = self.recalculate_cache(); } /// Set the whole tree, but safe/restore expanded state @@ -396,7 +403,7 @@ impl KeyedSlabTree { Some(root) => root.extract_expanded_state(), None => HashSet::new(), }; - self.tree.set_root_tree(data); + self.set_root_tree(data); if let Some(mut root) = self.root_mut() { root.apply_expanded_state(&expanded_state); } @@ -437,15 +444,62 @@ impl KeyedSlabTree { level: usize, parent: usize, ) -> usize { - self.tree - .append_subtree_node(subtree, subtree_node, level, parent) + let node_id = self + .tree + .append_subtree_node(subtree, subtree_node, level, parent); + + let key_cache = self.calculate_cache(node_id); + self.key_cache.extend(key_cache); + + node_id + } + + fn remove_subtree_from_cache(&mut self, node_id: usize) { + if let Some(entry) = self.tree.get(node_id) { + self.key_cache.remove(&self.extract_key(&entry.record)); + if let Some(children) = entry.children.clone() { + for child in children { + self.remove_subtree_from_cache(child); + } + } + } } fn remove_node_id(&mut self, node_id: usize) -> Option { + self.remove_subtree_from_cache(node_id); self.tree.remove_node_id(node_id) } + fn calculate_cache(&self, node_id: usize) -> HashMap { + let mut map = HashMap::new(); + if let Some(node) = self.get(node_id) { + let key = self.extract_key(&node.record); + map.insert(key, node_id); + match node.children.clone() { + Some(list) => { + for child_id in list { + map.extend(self.calculate_cache(child_id)); + } + } + None => {} + } + } + + map + } + + fn recalculate_cache(&self) -> HashMap { + match self.tree.root_id { + Some(root_id) => self.calculate_cache(root_id), + None => HashMap::new(), + } + } + fn remove_tree_node_id(&mut self, node_id: usize) -> Option> { + let key_cache = self.calculate_cache(node_id); + for key in key_cache.keys() { + self.key_cache.remove(key); + } match self.tree.remove_tree_node_id(node_id) { Some(tree) => Some(KeyedSlabTree { extract_key: self.extract_key.clone(), @@ -456,37 +510,27 @@ impl KeyedSlabTree { filter: None, listeners: Slab::new(), view_root: true, + key_cache, }), None => None, } } fn insert_record(&mut self, record: T, parent_id: Option) -> usize { - self.tree.insert_record(record, parent_id) + let key = self.extract_key(&record); + let node_id = self.tree.insert_record(record, parent_id); + self.key_cache.insert(key, node_id); + node_id } - fn find_subnode_by_key(&self, node_id: usize, key: &Key) -> Option { - let entry = self.get(node_id)?; - - if key == &self.extract_key(&entry.record) { - return Some(node_id); - } - - if let Some(children) = &entry.children { - for child_id in children { - if let Some(pos) = self.find_subnode_by_key(*child_id, key) { - return Some(pos); - } - } - } - - None + fn find_subnode_by_key(&self, key: &Key) -> Option { + self.key_cache.get(key).copied() } fn find_node_by_key(&self, key: &Key) -> Option { match self.tree.root_id { None => None, - Some(root_id) => self.find_subnode_by_key(root_id, key), + Some(_root_id) => self.find_subnode_by_key(key), } } -- 2.47.3 _______________________________________________ yew-devel mailing list yew-devel@lists.proxmox.com https://lists.proxmox.com/cgi-bin/mailman/listinfo/yew-devel