A cheaper tree view; history loads and snapshots timed finer d0d52107b074
Computing a state's tree view worked out every node's live modes twice and grouped every directory's children by name in a new map. The view now keeps each node's mode from its conflict scan and groups the children, already sorted by name, as runs; a node with one placement or one mode skips the conflict checks. On the Linux tip the view takes 0.29 s (from about 0.4 s). History loads time fetching the object apart from decoding it, and snapshots time the tree view apart from the graph keys. refs #35
- Author
- Andy McCall @andymccall <[email protected]>
- When
- · 2026-09-30 05:23 UTC
- Signature
- ✔ signed by Andy McCall
- Hash
d0d52107b0742c40adb5d3171c16eaf3ef4ae55c1d6d958b00c8266f2fbeda7b- Depends on
- 0bdc3f91a39f 75167672ebcd 86e1824f2d0b 8b276e0106d1 982864068a59 cc7a00565161 ff0af1ee299d
- Depended on by
- c2e1d09047db 05059d434aca 992467d31d26 e83354cdac22
- In bookmarks
- agents-in-readme bare-hashes carried-not-removed carry-identical doctor-trust identical-sides keyless-tags main merge-remote-bookmark only-help-103 paths-for-resolutions-and-amend push-notes show-stat subrepo-pin-state switch-says
- In tags
- v0.1.0 v0.10.0 v0.11.0 v0.2.0 v0.3.0 v0.3.1 v0.4.0 v0.4.1 v0.4.2 v0.4.3 v0.4.4 v0.4.5 v0.4.6 v0.5.0 v0.5.1 v0.6.0 v0.7.0 v0.8.0 v0.9.0
- Edits
- 14 atoms, 0 tree operations, 3 files
Browse the tree at this change
modified crates/oxy-core/src/repo/mod.rs +10 −2
| … | 851 unchanged lines |
||
| 852 | 852 | let mut seen: BTreeSet<ChangeHash> = BTreeSet::new(); |
|
| 853 | 853 | { |
|
| 854 | 854 | let _t = crate::timing::phase("load: read and add changes"); |
|
| 855 | - | let (mut read, mut add) = (std::time::Duration::ZERO, std::time::Duration::ZERO); |
|
| 855 | + | let (mut read, mut add, mut fetch) = ( |
|
| 856 | + | std::time::Duration::ZERO, |
|
| 857 | + | std::time::Duration::ZERO, |
|
| 858 | + | std::time::Duration::ZERO, |
|
| 859 | + | ); |
|
| 856 | 860 | while let Some(h) = stack.pop() { |
|
| 857 | 861 | if !seen.insert(h) { |
|
| 858 | 862 | continue; |
|
| … | 2 unchanged lines |
||
| 861 | 865 | // A history-only state reads text only for the graphs it |
|
| 862 | 866 | // builds; either way the hash is the one asked for. |
|
| 863 | 867 | let (c, texts) = if history { |
|
| 864 | - | self.store.get_change_lazy(&h)? |
|
| 868 | + | let bytes = self.store.get_typed(&h, ObjectType::Change)?; |
|
| 869 | + | fetch += t0.elapsed(); |
|
| 870 | + | Change::decode_skeleton(&bytes, h) |
|
| 871 | + | .map_err(|e| crate::store::StoreError::Corrupt(h, e.to_string()))? |
|
| 865 | 872 | } else { |
|
| 866 | 873 | (self.store.get_change(&h)?, Vec::new()) |
|
| 867 | 874 | }; |
|
| … | 4 unchanged lines |
||
| 872 | 879 | add += t1.elapsed(); |
|
| 873 | 880 | } |
|
| 874 | 881 | crate::timing::record("load: of which reading", read); |
|
| 882 | + | crate::timing::record("load: of which fetching", fetch); |
|
| 875 | 883 | crate::timing::record("load: of which applying", add); |
|
| 876 | 884 | } |
|
| 877 | 885 | let _t = crate::timing::phase("load: validate"); |
|
| … | 820 unchanged lines |
modified crates/oxy-core/src/repo/snapshot.rs +5 −2
| … | 287 unchanged lines |
||
| 288 | 288 | let _t = crate::timing::phase("snapshot: load base history"); |
|
| 289 | 289 | self.load_state_history(&old_wc.deps)? |
|
| 290 | 290 | }; |
|
| 291 | - | let keys_phase = crate::timing::phase("snapshot: tree view and graph keys"); |
|
| 292 | - | let view = base.tree().view(); |
|
| 291 | + | let view = { |
|
| 292 | + | let _t = crate::timing::phase("snapshot: tree view"); |
|
| 293 | + | base.tree().view() |
|
| 294 | + | }; |
|
| 295 | + | let keys_phase = crate::timing::phase("snapshot: graph keys"); |
|
| 293 | 296 | let keys: HashMap<String, String> = view |
|
| 294 | 297 | .entries |
|
| 295 | 298 | .iter() |
|
| … | 2052 unchanged lines |
modified crates/oxy-core/src/tree.rs +39 −26
| … | 221 unchanged lines |
||
| 222 | 222 | let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect(); |
|
| 223 | 223 | nodes.sort(); |
|
| 224 | 224 | let mut multi: HashSet<NodeId> = HashSet::new(); |
|
| 225 | + | // Each node's mode and the atom it comes from, for the entries. |
|
| 226 | + | let mut modes: HashMap<NodeId, (Option<OpKey>, Mode)> = HashMap::new(); |
|
| 225 | 227 | for n in &nodes { |
|
| 226 | 228 | let lp = self.live_placements(n); |
|
| 227 | - | let distinct_places: BTreeSet<(&NodeId, &str)> = lp |
|
| 228 | - | .iter() |
|
| 229 | - | .map(|(_, p)| (&p.parent, p.name.as_str())) |
|
| 230 | - | .collect(); |
|
| 231 | - | if distinct_places.len() > 1 { |
|
| 232 | - | multi.insert(*n); |
|
| 233 | - | view.conflicts.push(TreeConflict::MultiPlacement { |
|
| 234 | - | node: *n, |
|
| 235 | - | placements: lp.iter().map(|(k, _)| *k).collect(), |
|
| 236 | - | }); |
|
| 229 | + | // One placement (nearly every node) cannot be in two places. |
|
| 230 | + | if lp.len() > 1 { |
|
| 231 | + | let distinct_places: BTreeSet<(&NodeId, &str)> = lp |
|
| 232 | + | .iter() |
|
| 233 | + | .map(|(_, p)| (&p.parent, p.name.as_str())) |
|
| 234 | + | .collect(); |
|
| 235 | + | if distinct_places.len() > 1 { |
|
| 236 | + | multi.insert(*n); |
|
| 237 | + | view.conflicts.push(TreeConflict::MultiPlacement { |
|
| 238 | + | node: *n, |
|
| 239 | + | placements: lp.iter().map(|(k, _)| *k).collect(), |
|
| 240 | + | }); |
|
| 241 | + | } |
|
| 237 | 242 | } |
|
| 238 | 243 | let lm = self.live_modes(n); |
|
| 239 | - | let distinct_modes: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect(); |
|
| 240 | - | if distinct_modes.len() > 1 { |
|
| 241 | - | view.conflicts.push(TreeConflict::Mode { |
|
| 242 | - | node: *n, |
|
| 243 | - | modes: distinct_modes.into_iter().collect(), |
|
| 244 | - | }); |
|
| 244 | + | if lm.len() > 1 { |
|
| 245 | + | let distinct_modes: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect(); |
|
| 246 | + | if distinct_modes.len() > 1 { |
|
| 247 | + | view.conflicts.push(TreeConflict::Mode { |
|
| 248 | + | node: *n, |
|
| 249 | + | modes: distinct_modes.into_iter().collect(), |
|
| 250 | + | }); |
|
| 251 | + | } |
|
| 245 | 252 | } |
|
| 253 | + | let mode_atom = lm.iter().map(|(k, _)| *k).max(); |
|
| 254 | + | let mode = mode_atom |
|
| 255 | + | .and_then(|k| self.modes.get(&k).map(|(_, m)| *m)) |
|
| 256 | + | .unwrap_or_default(); |
|
| 257 | + | modes.insert(*n, (mode_atom, mode)); |
|
| 246 | 258 | } |
|
| 247 | 259 | ||
| 248 | 260 | // BFS from the root, assigning paths. |
|
| … | 5 unchanged lines |
||
| 254 | 266 | let Some(kids) = children.get(&dir) else { |
|
| 255 | 267 | continue; |
|
| 256 | 268 | }; |
|
| 257 | - | // Name conflicts within this directory. |
|
| 258 | - | let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new(); |
|
| 259 | - | for (k, p) in kids { |
|
| 260 | - | by_name.entry(p.name.as_str()).or_default().push((*k, p)); |
|
| 269 | + | // Name conflicts within this directory: the children are sorted |
|
| 270 | + | // by name, so each name's group is a run of them. |
|
| 271 | + | let mut groups: Vec<(&str, &[(OpKey, &Placement)])> = Vec::new(); |
|
| 272 | + | let mut start = 0; |
|
| 273 | + | for i in 1..=kids.len() { |
|
| 274 | + | if i == kids.len() || kids[i].1.name != kids[start].1.name { |
|
| 275 | + | groups.push((kids[start].1.name.as_str(), &kids[start..i])); |
|
| 276 | + | start = i; |
|
| 277 | + | } |
|
| 261 | 278 | } |
|
| 262 | - | for (name, group) in by_name { |
|
| 279 | + | for (name, group) in groups { |
|
| 263 | 280 | let distinct: BTreeSet<NodeId> = group.iter().map(|(_, p)| p.node).collect(); |
|
| 264 | 281 | if distinct.len() > 1 { |
|
| 265 | 282 | view.conflicts.push(TreeConflict::Name { |
|
| … | 21 unchanged lines |
||
| 287 | 304 | format!("{dir_path}/{leaf}") |
|
| 288 | 305 | }; |
|
| 289 | 306 | let kind = self.kind(&node).unwrap_or(NodeKind::File); |
|
| 290 | - | let modes = self.live_modes(&node); |
|
| 291 | - | let mode_atom = modes.iter().map(|(k, _)| *k).max(); |
|
| 292 | - | let mode = mode_atom |
|
| 293 | - | .and_then(|k| self.modes.get(&k).map(|(_, m)| *m)) |
|
| 294 | - | .unwrap_or_default(); |
|
| 307 | + | let (mode_atom, mode) = modes.get(&node).copied().unwrap_or_default(); |
|
| 295 | 308 | view.entries.insert( |
|
| 296 | 309 | path.clone(), |
|
| 297 | 310 | TreeEntry { |
|
| … | 536 unchanged lines |