Log takes the state index's changes in order; a clean diff loads no base 74b4a3c62ea4

The state index now keeps its changes in log order (newest first), and
the log reads them as a list: no map of 20 000 entries, no Arc each, and
no sort when the order already holds (an older index is sorted as
before). A diff whose working-copy change changes nothing, while the
status cache holds, is empty without loading the base's tree and file
table. On the 19,978-commit VS Code history, under load on Earth: diff
65 to 36 ms (now about status alone), log 42 to 36 ms, the sort 3.75 to
0.26 ms.

Refs #94

Author: Andy McCall @andymccall <[email protected]>
via: agent Claude Code <[email protected]> · delegate for changes, until 2026-11-13 19:00Z · key ea5f78160088
When: 18 days ago · 2026-10-17 03:09 UTC
Signature: ✔ signed by Claude Code
Hash: 74b4a3c62ea49a14291109dfc144c7f840f6af35c6a9e8f150ce53528fdf6e04
Depends on: 10b4fd430eab 252e8cb23fbc 4cce912a0953 4d6c9c1b358c 75167672ebcd 77445673174b 79b5a90ffd43 982864068a59 ac03130a2b95 bf0247ee3590 c6aa5bd9d1c8 ce14f0d68b15 dd6147dcf9c2 f9575918477f fce44ae9ad29 ff0af1ee299d
Depended on by: nothing yet
In bookmarks: carried-not-removed doctor-trust identical-sides keyless-tags main merge-remote-bookmark paths-for-resolutions-and-amend push-notes show-stat subrepo-pin-state
In tags: v0.10.0 v0.11.0 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: 29 atoms, 0 tree operations, 5 files

Browse the tree at this change

hide whitespace changes

modified crates/oxy-core/src/repo/mod.rs +36 −22

modified crates/oxy-core/src/repo/snapshot.rs +26 −3

modified crates/oxy-core/src/repo/tests.rs +13 −0

modified crates/oxy-core/src/state.rs +24 −5

modified src/cli/workspace.rs +4 −1

		…	1507 unchanged lines
1508	1508		#[allow(clippy::type_complexity)]
1509	1509		pub(crate) fn read_state_index_changes(
1510	1510		&self,
1511		-	) -> Option<(
1512		-	Vec<ChangeHash>,
1513		-	crate::fasthash::FastMap<ChangeHash, std::sync::Arc<crate::state::ChangeMeta>>,
1514		-	)> {
	1511	+	) -> Option<(Vec<ChangeHash>, Vec<(ChangeHash, crate::state::ChangeMeta)>)> {
1515	1512		use std::io::Read;
1516	1513		let _t = crate::timing::phase("load: state index changes");
1517	1514		let mut f = fs::File::open(self.state_indexes().first()?).ok()?;
		…	19 unchanged lines
1537	1534		}
1538	1535		drop(checking);
1539	1536		let _decoding = crate::timing::phase("load: of which decoding");
1540		-	Some((heads, State::read_index_changes(&changes[4..]).ok()?))
	1537	+	Some((heads, State::read_index_changes_listed(&changes[4..]).ok()?))
1541	1538		}
1542	1539
1543	1540		/// Save `st`, the history-only state of `deps`, as this workspace's
		…	342 unchanged lines
1886	1883		let _t = crate::timing::phase("log: metadata");
1887	1884		let mut metas = self.metas_of(&below)?;
1888	1885		if !metas.iter().any(\|(h, _)\| *h == wc_hash) {
1889		-	metas.push((wc_hash, crate::state::ChangeMeta::of(&wc)));
	1886	+	// First, where the log puts it, so the order may hold.
	1887	+	metas.insert(0, (wc_hash, crate::state::ChangeMeta::of(&wc)));
1890	1888		}
1891	1889		metas
1892	1890		};
		…	7 unchanged lines
1900	1898		}
1901	1899		let _sorting = crate::timing::phase("log: sort");
1902	1900		// The hash makes the order total, so an unstable sort gives the same.
1903		-	entries.sort_unstable_by(\|a, b\| {
	1901	+	// From the state index the order already holds (oxygen#94).
	1902	+	let order = \|a: &LogEntry, b: &LogEntry\| {
1904	1903		b.is_working_copy
1905	1904		.cmp(&a.is_working_copy)
1906		-	.then(b.change.hlc.cmp(&a.change.hlc))
1907		-	.then(b.hash.cmp(&a.hash))
1908		-	});
	1905	+	.then(crate::state::log_order(
	1906	+	(&a.hash, &a.change.hlc),
	1907	+	(&b.hash, &b.change.hlc),
	1908	+	))
	1909	+	};
	1910	+	if !entries.is_sorted_by(\|a, b\| order(a, b).is_le()) {
	1911	+	entries.sort_unstable_by(order);
	1912	+	}
1909	1913		Ok(entries)
1910	1914		}
1911	1915
		…	31 unchanged lines
1943	1947		is_working_copy: false,
1944	1948		})
1945	1949		.collect();
1946		-	entries.sort_unstable_by(\|a, b\| b.change.hlc.cmp(&a.change.hlc).then(b.hash.cmp(&a.hash)));
	1950	+	let order = \|a: &LogEntry, b: &LogEntry\| {
	1951	+	crate::state::log_order((&a.hash, &a.change.hlc), (&b.hash, &b.change.hlc))
	1952	+	};
	1953	+	if !entries.is_sorted_by(\|a, b\| order(a, b).is_le()) {
	1954	+	entries.sort_unstable_by(order);
	1955	+	}
1947	1956		Ok(entries)
1948	1957		}
1949	1958
		…	14 unchanged lines
1964	1973		// (it is closed), and no walk is needed to find it.
1965	1974		if let Some((index_heads, all)) = &read {
1966	1975		let asked: crate::fasthash::FastSet<&ChangeHash> = heads.iter().collect();
1967		-	if heads.iter().all(\|h\| all.contains_key(h))
1968		-	&& index_heads.iter().all(\|h\| asked.contains(h))
1969		-	{
	1976	+	let in_index = \|\| {
	1977	+	let index_heads: crate::fasthash::FastSet<&ChangeHash> =
	1978	+	index_heads.iter().collect();
	1979	+	// Usually the heads asked are the index's: no set of all.
	1980	+	heads.iter().all(\|h\| index_heads.contains(h)) \|\| {
	1981	+	let all: crate::fasthash::FastSet<&ChangeHash> =
	1982	+	all.iter().map(\|(h, _)\| h).collect();
	1983	+	heads.iter().all(\|h\| all.contains(h))
	1984	+	}
	1985	+	};
	1986	+	if index_heads.iter().all(\|h\| asked.contains(h)) && in_index() {
1970	1987		let (_, all) = read.expect("matched above");
1971	1988		#[cfg(test)]
1972	1989		{
		…	5 unchanged lines
1978	1995		stack.extend(self.store.get_change_meta(&h)?.deps);
1979	1996		}
1980	1997		}
1981		-	assert_eq!(seen, all.keys().copied().collect::<HashSet<_>>());
	1998	+	assert_eq!(seen, all.iter().map(\|(h, _)\| *h).collect::<HashSet<_>>());
1982	1999		}
1983		-	return Ok(all
1984		-	.into_iter()
1985		-	.map(\|(h, m)\| (h, std::sync::Arc::unwrap_or_clone(m)))
1986		-	.collect());
	2000	+	return Ok(all);
1987	2001		}
1988	2002		}
1989		-	let mut indexed = read.map(\|(_, all)\| all);
	2003	+	let mut indexed: Option<crate::fasthash::FastMap<ChangeHash, crate::state::ChangeMeta>> =
	2004	+	read.map(\|(_, all)\| all.into_iter().collect());
1990	2005		let _walk = crate::timing::phase("metadata: walk");
1991	2006		let (mut stored, mut from_store) = (0usize, std::time::Duration::ZERO);
1992	2007		let mut seen: crate::fasthash::FastSet<ChangeHash> = Default::default();
		…	7 unchanged lines
2000	2015		if let Some(meta) = indexed.as_mut().and_then(\|m\| m.remove(&h)) {
2001	2016		#[cfg(test)]
2002	2017		assert_eq!(
2003		-	*meta,
	2018	+	meta,
2004	2019		self.store.get_change_meta(&h)?,
2005	2020		"the state index holds a change's metadata"
2006	2021		);
2007		-	let meta = std::sync::Arc::unwrap_or_clone(meta);
2008	2022		stack.extend(meta.deps.iter().copied());
2009	2023		out.push((h, meta));
2010	2024		continue;
		…	360 unchanged lines

		…	1668 unchanged lines
1669	1669		let (base, snapshot) = self.change_base(&c)?;
1670	1670		(c, base, snapshot)
1671	1671		}
1672		-	None => self.working_copy_with_base()?,
	1672	+	None => match self.working_copy_with_base_unless_unchanged()? {
	1673	+	Some(all) => all,
	1674	+	None => return Ok(Vec::new()),
	1675	+	},
1673	1676		};
1674	1677		Ok(diff_files_of(&c, &base, &base_snapshot))
1675	1678		}
		…	52 unchanged lines
1728	1731		/// answer, no snapshot is taken, and the base's snapshot holds its tree
1729	1732		/// but no file; otherwise a snapshot makes all three.
1730	1733		pub fn working_copy_with_base(&self) -> Result<(Change, State, Snapshot)> {
	1734	+	match self.working_copy_with_base_unless_unchanged()? {
	1735	+	Some(all) => Ok(all),
	1736	+	None => {
	1737	+	let (_, wc) = self.working_copy()?;
	1738	+	let base = self.load_state_indexed(&wc.deps)?;
	1739	+	let (base, snapshot) = self.tree_base_for(&wc, base)?;
	1740	+	Ok((wc, base, snapshot))
	1741	+	}
	1742	+	}
	1743	+	}
	1744	+
	1745	+	/// [`Repo::working_copy_with_base`], or `None` when the status cache
	1746	+	/// holds and the working-copy change changes nothing: its diff is
	1747	+	/// empty, and the base is not loaded for it (oxygen#94).
	1748	+	pub fn working_copy_with_base_unless_unchanged(
	1749	+	&self,
	1750	+	) -> Result<Option<(Change, State, Snapshot)>> {
1731	1751		if self.status_by_manifest()?.is_some() {
1732	1752		let (_, wc) = self.working_copy()?;
	1753	+	if wc.tree_ops.is_empty() && wc.edits.is_empty() {
	1754	+	return Ok(None);
	1755	+	}
1733	1756		let base = self.load_state_indexed(&wc.deps)?;
1734	1757		let (base, snapshot) = self.tree_base_for(&wc, base)?;
1735		-	return Ok((wc, base, snapshot));
	1758	+	return Ok(Some((wc, base, snapshot)));
1736	1759		}
1737	1760		let snap = self.snapshot_status("oxy diff")?;
1738		-	Ok((snap.wc, snap.base, snap.base_snapshot))
	1761	+	Ok(Some((snap.wc, snap.base, snap.base_snapshot)))
1739	1762		}
1740	1763
1741	1764		/// The log restricted to changes touching `path` (its node, so renames
		…	1306 unchanged lines

		…	6040 unchanged lines
6041	6041		let (wc, base, snapshot) = repo.working_copy_with_base().unwrap();
6042	6042		assert_eq!(render_change(&wc, &base, &snapshot), slow);
6043	6043		assert_eq!(repo.diff_files(None).unwrap().len(), 3);
	6044	+
	6045	+	// Committed, nothing changes: the diff is empty without loading the
	6046	+	// base (oxygen#94), and the same as rendering it.
	6047	+	repo.commit("all", &[]).unwrap();
	6048	+	repo.snapshot_status("oxy status").unwrap();
	6049	+	assert!(repo.status_by_manifest().unwrap().is_some());
	6050	+	assert!(repo
	6051	+	.working_copy_with_base_unless_unchanged()
	6052	+	.unwrap()
	6053	+	.is_none());
	6054	+	let (wc, base, snapshot) = repo.working_copy_with_base().unwrap();
	6055	+	assert_eq!(render_change(&wc, &base, &snapshot), "");
	6056	+	assert!(repo.diff_files(None).unwrap().is_empty());
6044	6057		}
6045	6058
6046	6059		/// oxygen#41: a manifest written from a walk keeps every directory's time;
		…	1936 unchanged lines

		…	39 unchanged lines
40	40		pub kind: ChangeKind,
41	41		}
42	42
	43	+	/// The log's order of changes: newest first by clock, then by hash, so
	44	+	/// it is total.
	45	+	pub fn log_order(a: (&ChangeHash, &Hlc), b: (&ChangeHash, &Hlc)) -> std::cmp::Ordering {
	46	+	b.1.cmp(a.1).then(b.0.cmp(a.0))
	47	+	}
	48	+
43	49		impl ChangeMeta {
44	50		/// In the flat layout of local indexes and caches ([`crate::flat`]).
45	51		pub(crate) fn write_flat(&self, w: &mut crate::flat::Writer) {
		…	172 unchanged lines
218	224		// [`State::read_index_changes`]).
219	225		let mut w = Writer::default();
220	226		w.fixed(Self::INDEX_MAGIC);
	227	+	// In log order, newest first (oxygen#94): the log takes them as
	228	+	// they come, with no map and no sort.
221	229		let mut changes: Vec<(&ChangeHash, &Arc<ChangeMeta>)> = self.changes.iter().collect();
222		-	changes.sort_by_key(\|(h, _)\| **h);
	230	+	changes.sort_unstable_by(\|a, b\| log_order((a.0, &a.1.hlc), (b.0, &b.1.hlc)));
223	231		w.count(changes.len());
224	232		for (h, m) in changes {
225	233		w.object(h);
		…	172 unchanged lines
398	406		}
399	407
400	408		/// The changes of a state index: its first block, which a reader can
401		-	/// take without the rest (the log needs no more).
	409	+	/// take without the rest.
402	410		pub fn read_index_changes(
403	411		bytes: &[u8],
404	412		) -> Result<crate::fasthash::FastMap<ChangeHash, Arc<ChangeMeta>>, ObjectError> {
	413	+	Ok(Self::read_index_changes_listed(bytes)?
	414	+	.into_iter()
	415	+	.map(\|(h, m)\| (h, Arc::new(m)))
	416	+	.collect())
	417	+	}
	418	+
	419	+	/// The same changes as a list in the order the index keeps them, which
	420	+	/// a current index keeps in log order ([`log_order`]): what the log
	421	+	/// needs (oxygen#94).
	422	+	pub fn read_index_changes_listed(
	423	+	bytes: &[u8],
	424	+	) -> Result<Vec<(ChangeHash, ChangeMeta)>, ObjectError> {
405	425		use crate::flat::Reader;
406	426		let mut r = Reader::new(bytes);
407	427		if r.fixed::<18>()?.as_slice() != Self::INDEX_MAGIC {
408	428		return Err(ObjectError::Schema("state index: not a state index".into()));
409	429		}
410	430		let n = r.count()?;
411		-	let mut changes = crate::fasthash::FastMap::default();
412		-	changes.reserve(n);
	431	+	let mut changes = Vec::with_capacity(n);
413	432		for _ in 0..n {
414	433		let h = r.object()?;
415		-	changes.insert(h, Arc::new(ChangeMeta::read_flat(&mut r)?));
	434	+	changes.push((h, ChangeMeta::read_flat(&mut r)?));
416	435		}
417	436		if !r.at_end() {
418	437		return Err(ObjectError::Schema("state index: trailing bytes".into()));
		…	2321 unchanged lines

		…	991 unchanged lines
992	992		print!("{}", render_change(&c, &base, &snapshot));
993	993		}
994	994		None => {
995		-	let (wc, base, snapshot) = repo.working_copy_with_base()?;
	995	+	// Nothing changed: nothing to show, and no base to load.
	996	+	let Some((wc, base, snapshot)) = repo.working_copy_with_base_unless_unchanged()? else {
	997	+	return Ok(0);
	998	+	};
996	999		let text = {
997	1000		let _t = oxy_core::timing::phase("diff: render the change");
998	1001		render_change(&wc, &base, &snapshot)
		…	1777 unchanged lines

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

Log takes the state index's changes in order; a clean diff loads no base 74b4a3c62ea4

Keyboard