Status: maps built in path order, fast maps for node lookups (refs #41) 36e51aa806c6
The walk's listing is sorted, so its result, the tracked paths and the base snapshot's maps are built in bulk rather than by search; a state's graphs and deferred histories are keyed with the fast hasher. One-file status on the Linux tree: 0.72 to 0.77 s (from 0.81 s).
- Author
- Andy McCall @andymccall <[email protected]>
- When
- · 2026-09-30 21:34 UTC
- Signature
- ✔ signed by Andy McCall
- Hash
36e51aa806c69ece6701da9debb1bf95a6a7fa3ba93e5be3cb6f2992359bf6e7- Depends on
- 3f1b8fe25ec9 40a40bb7b798 75167672ebcd 76740263089c 982864068a59 9ac1fbe211b4 cc7a00565161 dfb23a3a8cfa e7ddd552b619 e83354cdac22 e8d38e47e9d7 f6451fbbae3f f9575918477f ff0af1ee299d
- Depended on by
- c2e1d09047db 5552e69c7325 79b5a90ffd43 e96a430c78f3 1ec3f008e96a
- 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.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
- 19 atoms, 0 tree operations, 4 files
Browse the tree at this change
modified crates/oxy-core/src/repo/mod.rs +10 −8
| … | 1260 unchanged lines |
||
| 1261 | 1261 | tracked: &BTreeMap<String, (NodeKind, Option<ObjectRef>)>, |
|
| 1262 | 1262 | keys: Option<&HashMap<String, String>>, |
|
| 1263 | 1263 | ) -> Result<BTreeMap<String, FsEntry>> { |
|
| 1264 | - | let mut out = BTreeMap::new(); |
|
| 1264 | + | let mut out: BTreeMap<String, FsEntry>; |
|
| 1265 | 1265 | let sparse = &self.config.sparse_paths; |
|
| 1266 | 1266 | let in_scope = |p: &str| { |
|
| 1267 | 1267 | sparse.is_empty() |
|
| … | 10 unchanged lines |
||
| 1278 | 1278 | Some(l) => l, |
|
| 1279 | 1279 | None => walk::list(&self.root, &in_scope)?, |
|
| 1280 | 1280 | }; |
|
| 1281 | - | for (rel, target) in symlinks { |
|
| 1282 | - | out.insert(rel, FsEntry::new(NodeKind::Symlink, false, target)); |
|
| 1283 | - | } |
|
| 1284 | 1281 | let keys = keys.filter(|k| { |
|
| 1285 | 1282 | let on_disk: HashSet<&str> = files.iter().map(|(r, _, _)| r.as_str()).collect(); |
|
| 1286 | 1283 | let attrs_unchanged = |
|
| … | 15 unchanged lines |
||
| 1302 | 1299 | // Reading files is most of a walk's cost; do it in parallel. |
|
| 1303 | 1300 | { |
|
| 1304 | 1301 | use rayon::prelude::*; |
|
| 1305 | - | let read: Vec<(String, FsEntry)> = files |
|
| 1302 | + | let mut read: Vec<(String, FsEntry)> = files |
|
| 1306 | 1303 | .par_iter() |
|
| 1307 | 1304 | .map(|(rel, path, meta)| { |
|
| 1308 | 1305 | let key = keys |
|
| … | 3 unchanged lines |
||
| 1312 | 1309 | Ok((rel.clone(), read_file_entry(rel, path, meta, cache, key)?)) |
|
| 1313 | 1310 | }) |
|
| 1314 | 1311 | .collect::<Result<Vec<_>>>()?; |
|
| 1315 | - | for (rel, mut e) in read { |
|
| 1312 | + | for (rel, e) in read.iter_mut() { |
|
| 1316 | 1313 | // A cached blob the store lost (gc, a partial clone): read the file after all. |
|
| 1317 | 1314 | if e.content.is_empty() && e.blob.is_some_and(|b| !self.store.has(&b)) { |
|
| 1318 | - | e.content = std::sync::Arc::new(fs::read(self.root.join(&rel))?); |
|
| 1315 | + | e.content = std::sync::Arc::new(fs::read(self.root.join(rel.as_str()))?); |
|
| 1319 | 1316 | e.blob = None; |
|
| 1320 | 1317 | } |
|
| 1321 | - | out.insert(rel, e); |
|
| 1318 | + | } |
|
| 1319 | + | // The listing is in path order, so the map is built without |
|
| 1320 | + | // searching. |
|
| 1321 | + | out = read.into_iter().collect(); |
|
| 1322 | + | for (rel, target) in symlinks { |
|
| 1323 | + | out.insert(rel, FsEntry::new(NodeKind::Symlink, false, target)); |
|
| 1322 | 1324 | } |
|
| 1323 | 1325 | } |
|
| 1324 | 1326 | drop(_read_phase); |
|
| … | 438 unchanged lines |
modified crates/oxy-core/src/repo/snapshot.rs +13 −13
| … | 328 unchanged lines |
||
| 329 | 329 | }; |
|
| 330 | 330 | let tracked: BTreeMap<String, (NodeKind, Option<ObjectRef>)> = { |
|
| 331 | 331 | let _t = crate::timing::phase("snapshot: tracked paths"); |
|
| 332 | - | let mut t = BTreeMap::new(); |
|
| 333 | - | for (p, e) in view.entries.iter() { |
|
| 334 | - | if e.kind == NodeKind::Dir { |
|
| 335 | - | continue; |
|
| 336 | - | } |
|
| 337 | - | let blob = if e.kind != NodeKind::File || e.mode.opaque { |
|
| 338 | - | base.live_blobs(&e.node).first().copied() |
|
| 339 | - | } else { |
|
| 340 | - | None |
|
| 341 | - | }; |
|
| 342 | - | t.insert(p.clone(), (e.kind, blob)); |
|
| 343 | - | } |
|
| 344 | - | t |
|
| 332 | + | // In the view's path order, so the map is built without searching. |
|
| 333 | + | view.entries |
|
| 334 | + | .iter() |
|
| 335 | + | .filter(|(_, e)| e.kind != NodeKind::Dir) |
|
| 336 | + | .map(|(p, e)| { |
|
| 337 | + | let blob = if e.kind != NodeKind::File || e.mode.opaque { |
|
| 338 | + | base.live_blobs(&e.node).first().copied() |
|
| 339 | + | } else { |
|
| 340 | + | None |
|
| 341 | + | }; |
|
| 342 | + | (p.clone(), (e.kind, blob)) |
|
| 343 | + | }) |
|
| 344 | + | .collect() |
|
| 345 | 345 | }; |
|
| 346 | 346 | let mut fs_entries = { |
|
| 347 | 347 | let _t = crate::timing::phase("snapshot: read working copy"); |
|
| … | 2181 unchanged lines |
modified crates/oxy-core/src/repo/walk.rs +9 −2
| … | 12 unchanged lines |
||
| 13 | 13 | use ignore::Match; |
|
| 14 | 14 | use std::sync::{Arc, Mutex}; |
|
| 15 | 15 | ||
| 16 | - | /// What a listing found. |
|
| 16 | + | /// What a listing found, each list in path order. |
|
| 17 | 17 | #[derive(Default)] |
|
| 18 | 18 | pub(crate) struct Listing { |
|
| 19 | 19 | /// Regular files: path relative to the root (with `/`), full path, stat. |
|
| … | 70 unchanged lines |
||
| 90 | 90 | if let Some(e) = ctx.failed.into_inner().unwrap_or_else(|e| e.into_inner()) { |
|
| 91 | 91 | return fail(e); |
|
| 92 | 92 | } |
|
| 93 | - | Ok(ctx.out.into_inner().unwrap_or_else(|e| e.into_inner())) |
|
| 93 | + | let mut out = ctx.out.into_inner().unwrap_or_else(|e| e.into_inner()); |
|
| 94 | + | // In path order, as the maps built from it want. |
|
| 95 | + | { |
|
| 96 | + | use rayon::prelude::*; |
|
| 97 | + | out.files.par_sort_unstable_by(|a, b| a.0.cmp(&b.0)); |
|
| 98 | + | out.symlinks.sort_unstable_by(|a, b| a.0.cmp(&b.0)); |
|
| 99 | + | } |
|
| 100 | + | Ok(out) |
|
| 94 | 101 | } |
|
| 95 | 102 | ||
| 96 | 103 | fn visit<'s>( |
|
| … | 158 unchanged lines |
modified crates/oxy-core/src/state.rs +16 −14
| … | 61 unchanged lines |
||
| 62 | 62 | /// Shared between clones: a clone copies a graph only when an edit |
|
| 63 | 63 | /// changes it (`Arc::make_mut`), so keeping several states that differ |
|
| 64 | 64 | /// by a few changes costs little more than one. |
|
| 65 | - | files: HashMap<NodeId, Arc<FileGraph>>, |
|
| 65 | + | files: crate::fasthash::FastMap<NodeId, Arc<FileGraph>>, |
|
| 66 | 66 | replaces: HashMap<NodeId, Vec<ReplaceRecord>>, |
|
| 67 | 67 | /// Memoised transitive dependencies. A mutex, not a `RefCell`, so a |
|
| 68 | 68 | /// loaded state can be shared across threads by a host that caches it. |
|
| … | 1 unchanged lines |
||
| 70 | 70 | /// `None` for a full state. For a history-only state (loaded for its |
|
| 71 | 71 | /// changes and tree), the file graphs not built yet, by node: `files` |
|
| 72 | 72 | /// holds only those loaded with [`State::load_graphs`]. |
|
| 73 | - | deferred: Option<HashMap<NodeId, Arc<Deferred>>>, |
|
| 73 | + | deferred: Option<crate::fasthash::FastMap<NodeId, Arc<Deferred>>>, |
|
| 74 | 74 | } |
|
| 75 | 75 | ||
| 76 | 76 | use crate::objects::TextRef; |
|
| … | 291 unchanged lines |
||
| 368 | 368 | ||
| 369 | 369 | /// The deferred block: each node with its graph key and its body, |
|
| 370 | 370 | /// left encoded (see [`Deferred`]). |
|
| 371 | - | fn read_deferred(bytes: &[u8]) -> Result<HashMap<NodeId, Arc<Deferred>>, ObjectError> { |
|
| 371 | + | fn read_deferred( |
|
| 372 | + | bytes: &[u8], |
|
| 373 | + | ) -> Result<crate::fasthash::FastMap<NodeId, Arc<Deferred>>, ObjectError> { |
|
| 372 | 374 | use crate::flat::Reader; |
|
| 373 | 375 | let _t = crate::timing::phase("index: deferred"); |
|
| 374 | 376 | let all: Arc<[u8]> = Arc::from(bytes); |
|
| 375 | 377 | let mut r = Reader::new(bytes); |
|
| 376 | - | let mut deferred: HashMap<NodeId, Arc<Deferred>> = HashMap::new(); |
|
| 378 | + | let mut deferred = crate::fasthash::FastMap::default(); |
|
| 377 | 379 | let n = r.count()?; |
|
| 378 | 380 | deferred.reserve(n); |
|
| 379 | 381 | for _ in 0..n { |
|
| … | 356 unchanged lines |
||
| 736 | 738 | /// need no file contents, or only a few files. |
|
| 737 | 739 | pub fn new_history_only() -> Self { |
|
| 738 | 740 | State { |
|
| 739 | - | deferred: Some(HashMap::new()), |
|
| 741 | + | deferred: Some(Default::default()), |
|
| 740 | 742 | ..Self::default() |
|
| 741 | 743 | } |
|
| 742 | 744 | } |
|
| … | 505 unchanged lines |
||
| 1248 | 1250 | return State::from_checkpoint_payload(bytes); |
|
| 1249 | 1251 | } |
|
| 1250 | 1252 | let mut st = State::payload_common(m)?; |
|
| 1251 | - | let mut deferred = HashMap::new(); |
|
| 1253 | + | let mut deferred = crate::fasthash::FastMap::default(); |
|
| 1252 | 1254 | for f in o::array(o::field(m, 3, "files")?, "files")? { |
|
| 1253 | 1255 | let e = o::array(f, "file")?; |
|
| 1254 | 1256 | if e.len() != 2 { |
|
| … | 405 unchanged lines |
||
| 1660 | 1662 | } |
|
| 1661 | 1663 | }) |
|
| 1662 | 1664 | .collect(); |
|
| 1663 | - | let mut files = BTreeMap::new(); |
|
| 1664 | - | let mut unrendered = BTreeSet::new(); |
|
| 1665 | - | for (p, f, skipped) in rendered { |
|
| 1666 | - | if skipped { |
|
| 1667 | - | unrendered.insert(p.clone()); |
|
| 1668 | - | } |
|
| 1669 | - | files.insert(p, f); |
|
| 1670 | - | } |
|
| 1665 | + | // In the view's path order, so the maps are built without searching. |
|
| 1666 | + | let unrendered: BTreeSet<String> = rendered |
|
| 1667 | + | .iter() |
|
| 1668 | + | .filter(|(_, _, skipped)| *skipped) |
|
| 1669 | + | .map(|(p, _, _)| p.clone()) |
|
| 1670 | + | .collect(); |
|
| 1671 | + | let files: BTreeMap<String, FileState> = |
|
| 1672 | + | rendered.into_iter().map(|(p, f, _)| (p, f)).collect(); |
|
| 1671 | 1673 | Snapshot { |
|
| 1672 | 1674 | tree, |
|
| 1673 | 1675 | files, |
|
| … | 776 unchanged lines |