Keep an insert's lines in one shared buffer 01a47cd7f0c8

Every line of an insert was its own Vec, in the change and again in the
file graph's atoms: the Linux tree's 40 million lines were as many
allocations twice over, 2.6 GB for 1.8 GB of text. An insert's lines
are now one buffer and the offsets where each ends (Lines, in the new
lines module), cloned by reference; a graph atom holds a LineRef into
its insert's buffer instead of a copy, and a graph read from a
checkpoint puts all its lines in one buffer. Decoding builds Lines
straight from the byte strings. The diff of the whole Linux tree now
takes 3.3 s and 1.1 million allocations (from 6.2 s and 45 million), and
the first commit peaks at 4.3 GB (4.9 GB RSS, from 5.8 GB).

refs #35

Author: Andy McCall @andymccall <[email protected]>
When: 1 month ago · 2026-09-29 23:39 UTC
Signature: ✔ signed by Andy McCall
Hash: 01a47cd7f0c8deefd0326b8e498cf2c2ad6422e2dd7da1d139a73c27fe968ef9
Depends on: 0bdc3f91a39f 119bbf50cb86 17f94b13ae54 192fad1e46a2 1d360c91a289 252e8cb23fbc 387335ff7f4d 614541c3cebd 6f8aeb996558 728da0f92161 75167672ebcd 86e1824f2d0b 982864068a59 a4fad5b085c7 afaba5f1306d c07e0e7d2d85 cc7a00565161 cdb5beba7f05 e8d38e47e9d7 ff0af1ee299d
Depended on by: 91334b7fa574 5b4c51307b14 40a40bb7b798 2306a4d24779 0f93f49ce059
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: 82 atoms, 1 tree operation, 12 files

Browse the tree at this change

hide whitespace changes

added crates/oxy-core/src/lines.rs +163 −0

modified crates/oxy-core/src/cbor.rs +3 −3

modified crates/oxy-core/src/diff.rs +4 −4

modified crates/oxy-core/src/graph.rs +31 −14

modified crates/oxy-core/src/lib.rs +1 −0

modified crates/oxy-core/src/objects.rs +23 −26

modified crates/oxy-core/src/repo/fsck.rs +1 −1

modified crates/oxy-core/src/repo/history.rs +1 −1

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

modified crates/oxy-core/src/rewrite.rs +11 −9

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

modified docs/benchmarks.md +8 −2

1	+	//! The lines of an insert (spec §7.4) held as one buffer and where each
2	+	//! line ends, shared by the change and the file graph it builds: a tree of
3	+	//! forty million lines is then a few allocations per insert, not one per
4	+	//! line, and a graph's atoms point into their insert's buffer rather than
5	+	//! copying it.
6	+
7	+	use std::sync::Arc;
8	+
9	+	#[derive(Default, PartialEq, Eq, Hash)]
10	+	struct Inner {
11	+	buf: Vec<u8>,
12	+	/// The end offset of each line in `buf`.
13	+	ends: Vec<u64>,
14	+	}
15	+
16	+	/// An insert's lines. Cloning is cheap: the buffer is shared.
17	+	#[derive(Clone, Default, PartialEq, Eq, Hash)]
18	+	pub struct Lines(Arc<Inner>);
19	+
20	+	impl Lines {
21	+	/// Lines from their bytes, each keeping its terminator; a final
22	+	/// unterminated line is its own line (the rule of
23	+	/// [`crate::diff::split_lines`]).
24	+	pub fn split(content: &[u8]) -> Lines {
25	+	let mut ends = Vec::new();
26	+	for (i, &c) in content.iter().enumerate() {
27	+	if c == b'\n' {
28	+	ends.push(i as u64 + 1);
29	+	}
30	+	}
31	+	if ends.last().copied().unwrap_or(0) as usize != content.len() {
32	+	ends.push(content.len() as u64);
33	+	}
34	+	Lines(Arc::new(Inner {
35	+	buf: content.to_vec(),
36	+	ends,
37	+	}))
38	+	}
39	+
40	+	pub fn len(&self) -> usize {
41	+	self.0.ends.len()
42	+	}
43	+
44	+	pub fn is_empty(&self) -> bool {
45	+	self.0.ends.is_empty()
46	+	}
47	+
48	+	/// Line `i`, with its terminator.
49	+	pub fn get(&self, i: usize) -> Option<&[u8]> {
50	+	let end = *self.0.ends.get(i)? as usize;
51	+	let start = if i == 0 {
52	+	0
53	+	} else {
54	+	self.0.ends[i - 1] as usize
55	+	};
56	+	Some(&self.0.buf[start..end])
57	+	}
58	+
59	+	pub fn iter(&self) -> impl ExactSizeIterator<Item = &[u8]> + Clone + '_ {
60	+	(0..self.len()).map(move \|i\| self.get(i).unwrap())
61	+	}
62	+
63	+	/// Every line, joined: the bytes they were split from.
64	+	pub fn bytes(&self) -> &[u8] {
65	+	&self.0.buf
66	+	}
67	+
68	+	/// Lines `range` as lines of their own.
69	+	pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
70	+	self.iter().skip(range.start).take(range.len()).collect()
71	+	}
72	+
73	+	/// The lines as owned vectors, for code that edits them one by one.
74	+	pub fn to_vec(&self) -> Vec<Vec<u8>> {
75	+	self.iter().map(<[u8]>::to_vec).collect()
76	+	}
77	+	}
78	+
79	+	impl std::ops::Index<usize> for Lines {
80	+	type Output = [u8];
81	+	fn index(&self, i: usize) -> &[u8] {
82	+	self.get(i).expect("line index out of range")
83	+	}
84	+	}
85	+
86	+	impl<'a> FromIterator<&'a [u8]> for Lines {
87	+	fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
88	+	let mut inner = Inner::default();
89	+	for l in iter {
90	+	inner.buf.extend_from_slice(l);
91	+	inner.ends.push(inner.buf.len() as u64);
92	+	}
93	+	Lines(Arc::new(inner))
94	+	}
95	+	}
96	+
97	+	impl FromIterator<Vec<u8>> for Lines {
98	+	fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
99	+	let mut inner = Inner::default();
100	+	for l in iter {
101	+	inner.buf.extend_from_slice(&l);
102	+	inner.ends.push(inner.buf.len() as u64);
103	+	}
104	+	Lines(Arc::new(inner))
105	+	}
106	+	}
107	+
108	+	impl From<Vec<Vec<u8>>> for Lines {
109	+	fn from(v: Vec<Vec<u8>>) -> Lines {
110	+	v.into_iter().collect()
111	+	}
112	+	}
113	+
114	+	impl std::fmt::Debug for Lines {
115	+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
116	+	f.debug_list()
117	+	.entries(self.iter().map(String::from_utf8_lossy))
118	+	.finish()
119	+	}
120	+	}
121	+
122	+	/// One line of a [`Lines`], held by a file graph's atom.
123	+	#[derive(Clone, Debug, PartialEq, Eq)]
124	+	pub struct LineRef {
125	+	lines: Lines,
126	+	index: u32,
127	+	}
128	+
129	+	impl LineRef {
130	+	pub fn new(lines: Lines, index: u32) -> LineRef {
131	+	LineRef { lines, index }
132	+	}
133	+
134	+	pub fn bytes(&self) -> &[u8] {
135	+	&self.lines[self.index as usize]
136	+	}
137	+	}
138	+
139	+	#[cfg(test)]
140	+	mod tests {
141	+	use super::*;
142	+
143	+	#[test]
144	+	fn lines_split_index_and_join_as_the_line_rule_says() {
145	+	for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
146	+	let l = Lines::split(text);
147	+	let want = crate::diff::split_lines(text);
148	+	assert_eq!(l.len(), want.len(), "{text:?}");
149	+	assert_eq!(l.iter().collect::<Vec<_>>(), want);
150	+	assert_eq!(l.bytes(), text);
151	+	let v: Lines = want.iter().copied().collect();
152	+	assert_eq!(v, l);
153	+	assert_eq!(Lines::from(l.to_vec()), l);
154	+	}
155	+	let l = Lines::split(b"a\nb\nc\n");
156	+	assert_eq!(&l[1], b"b\n");
157	+	assert_eq!(
158	+	l.slice(1..3).to_vec(),
159	+	vec![b"b\n".to_vec(), b"c\n".to_vec()]
160	+	);
161	+	assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
162	+	}
163	+	}

		…	122 unchanged lines
123	123
124	124		/// The canonical encoding of an array of byte strings, written without
125	125		/// building a [`Value`] (large inserts stored as text blobs, spec §6.1).
126		-	pub fn encode_byte_strings(items: &[Vec<u8>]) -> Vec<u8> {
	126	+	pub fn encode_byte_strings(items: &crate::lines::Lines) -> Vec<u8> {
127	127		let mut out = Vec::with_capacity(byte_strings_len(items));
128	128		head(&mut out, 4, items.len() as u64);
129		-	for b in items {
	129	+	for b in items.iter() {
130	130		head(&mut out, 2, b.len() as u64);
131	131		out.extend_from_slice(b);
132	132		}
		…	1 unchanged lines
134	134		}
135	135
136	136		/// The length of [`encode_byte_strings`]' output, without encoding.
137		-	pub fn byte_strings_len(items: &[Vec<u8>]) -> usize {
	137	+	pub fn byte_strings_len(items: &crate::lines::Lines) -> usize {
138	138		head_len(items.len() as u64)
139	139		+ items
140	140		.iter()
		…	460 unchanged lines

		…	103 unchanged lines
104	104		before,
105	105		lines: new_lines[new_index..new_index + new_len]
106	106		.iter()
107		-	.map(\|l\| l.to_vec())
	107	+	.copied()
108	108		.collect(),
109	109		});
110	110		}
		…	11 unchanged lines
122	122		before,
123	123		lines: new_lines[new_index..new_index + new_len]
124	124		.iter()
125		-	.map(\|l\| l.to_vec())
	125	+	.copied()
126	126		.collect(),
127	127		});
128	128		}
		…	150 unchanged lines
279	279		change: h(1),
280	280		index: 1
281	281		},
282		-	lines: vec![b"B\n".to_vec()]
	282	+	lines: vec![b"B\n".to_vec()].into()
283	283		},
284	284		]
285	285		);
		…	37 unchanged lines
323	323		node,
324	324		after: AtomRef::Start,
325	325		before: AtomRef::End,
326		-	lines: vec![b"x\n".to_vec()]
	326	+	lines: vec![b"x\n".to_vec()].into()
327	327		}]
328	328		);
329	329		}
		…	1 unchanged lines

		…	5 unchanged lines
6	6
7	7		use crate::fasthash::{FastMap as HashMap, FastSet as HashSet};
8	8		use crate::hash::ChangeHash;
	9	+	use crate::lines::{LineRef, Lines};
9	10		use crate::objects::AtomRange;
10	11		use std::collections::{BTreeMap, BTreeSet};
11	12
		…	22 unchanged lines
34	35
35	36		#[derive(Default, Clone, Debug)]
36	37		struct AtomInfo {
37		-	/// `None` until the introducing change has been applied.
38		-	content: Option<Vec<u8>>,
	38	+	/// `None` until the introducing change has been applied; a line of the
	39	+	/// insert's shared buffer.
	40	+	content: Option<LineRef>,
39	41		deleted_by: BTreeSet<ChangeHash>,
40	42		}
41	43
		…	117 unchanged lines
159	161		first_index: u32,
160	162		after: Vertex,
161	163		before: Vertex,
162		-	lines: &[Vec<u8>],
	164	+	lines: &Lines,
163	165		) {
164		-	self.insert_owned(change, first_index, after, before, lines.to_vec());
	166	+	self.insert_owned(change, first_index, after, before, lines.clone());
165	167		}
166	168
167	169		/// [`FileGraph::insert`] taking the lines, so loading a state moves
		…	5 unchanged lines
173	175		first_index: u32,
174	176		after: Vertex,
175	177		before: Vertex,
176		-	lines: Vec<Vec<u8>>,
	178	+	lines: Lines,
177	179		) {
178	180		self.atoms.reserve(lines.len());
179	181		self.succ.reserve(lines.len() + 1);
180	182		let mut prev = after;
181		-	for (i, line) in lines.into_iter().enumerate() {
	183	+	for i in 0..lines.len() {
182	184		let key = (change, first_index + i as u32);
183		-	self.atoms.entry(key).or_default().content = Some(line);
	185	+	self.atoms.entry(key).or_default().content =
	186	+	Some(LineRef::new(lines.clone(), i as u32));
184	187		let v = Vertex::Atom(key);
185	188		self.succ.entry(prev).or_default().insert(v);
186	189		prev = v;
		…	20 unchanged lines
207	210		}
208	211
209	212		pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
210		-	self.atoms.get(k).and_then(\|a\| a.content.as_deref())
	213	+	self.atoms
	214	+	.get(k)
	215	+	.and_then(\|a\| a.content.as_ref().map(LineRef::bytes))
211	216		}
212	217
213	218		pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
		…	387 unchanged lines
601	606		Value::Uint(*i as u64),
602	607		info.content
603	608		.as_ref()
604		-	.map(\|b\| Value::Bytes(b.clone()))
	609	+	.map(\|b\| Value::Bytes(b.bytes().to_vec()))
605	610		.unwrap_or(Value::Null),
606	611		Value::Array(
607	612		info.deleted_by
		…	25 unchanged lines
633	638		atoms: HashMap::default(),
634	639		succ: HashMap::default(),
635	640		};
636		-	for a in array(field(m, 0, "atoms")?, "atoms")? {
	641	+	let atoms = array(field(m, 0, "atoms")?, "atoms")?;
	642	+	// Every atom's line in one buffer.
	643	+	let mut texts: Vec<&[u8]> = Vec::new();
	644	+	for a in atoms {
	645	+	let e = array(a, "atom")?;
	646	+	if e.len() == 4 && !e[2].is_null() {
	647	+	texts.push(bytes(&e[2], "atom content")?);
	648	+	}
	649	+	}
	650	+	let all: Lines = texts.into_iter().collect();
	651	+	let mut next = 0u32;
	652	+	for a in atoms {
637	653		let e = array(a, "atom")?;
638	654		if e.len() != 4 {
639	655		return Err(ObjectError::Schema("atom: expected 4 fields".into()));
		…	2 unchanged lines
642	658		let content = if e[2].is_null() {
643	659		None
644	660		} else {
645		-	Some(bytes(&e[2], "atom content")?.to_vec())
	661	+	next += 1;
	662	+	Some(LineRef::new(all.clone(), next - 1))
646	663		};
647	664		let deleted_by = array(&e[3], "deleters")?
648	665		.iter()
		…	61 unchanged lines
710	727		fn h(n: u8) -> ChangeHash {
711	728		ObjectRef([n; 32])
712	729		}
713		-	fn lines(v: &[&str]) -> Vec<Vec<u8>> {
714		-	v.iter().map(\|s\| s.as_bytes().to_vec()).collect()
	730	+	fn lines(v: &[&str]) -> Lines {
	731	+	v.iter().map(\|s\| s.as_bytes()).collect()
715	732		}
716	733		fn text(g: &FileGraph, m: &Materialized) -> String {
717	734		String::from_utf8(g.render(m, &\|c\| c.short(4))).unwrap()
		…	358 unchanged lines
1076	1093		use rand::seq::SliceRandom;
1077	1094		type Op = (
1078	1095		ChangeHash,
1079		-	Vec<(u32, Vertex, Vertex, Vec<Vec<u8>>)>,
	1096	+	Vec<(u32, Vertex, Vertex, Lines)>,
1080	1097		Vec<AtomRange>,
1081	1098		);
1082	1099		let ops: Vec<Op> = vec![
		…	83 unchanged lines

		…	9 unchanged lines
10	10		use crate::cbor::{self, Value};
11	11		use crate::hash::{hash_object, ChangeHash, KeyId, ObjectRef, ObjectType};
12	12		use crate::ids::{ChangeId, NodeId};
	13	+	use crate::lines::Lines;
13	14		use std::collections::BTreeMap;
14	15
15	16		pub const FORMAT_VERSION: u64 = 1;
		…	414 unchanged lines
430	431		node: NodeId,
431	432		after: AtomRef,
432	433		before: AtomRef,
433		-	lines: Vec<Vec<u8>>,
	434	+	lines: crate::lines::Lines,
434	435		},
435	436		Delete {
436	437		node: NodeId,
		…	61 unchanged lines
498	499		(3, before.to_value()),
499	500		(
500	501		4,
501		-	Value::Array(lines.iter().map(\|l\| Value::Bytes(l.clone())).collect()),
	502	+	Value::Array(lines.iter().map(\|l\| Value::Bytes(l.to_vec())).collect()),
502	503		),
503	504		]),
504	505		(Edit::Delete { node, atoms }, _) => Value::map([
		…	28 unchanged lines
533	534		0 => {
534	535		let lines = match (m.get(&4), m.get(&5)) {
535	536		(Some(inline), None) => {
536		-	let lines = array(inline, "lines")?
537		-	.iter()
538		-	.map(\|l\| bytes(l, "line").map(\|b\| b.to_vec()))
539		-	.collect::<Result<Vec<_>, _>>()?;
	537	+	let lines = array_lines(inline)?;
540	538		if version >= 2 && cbor::byte_strings_len(&lines) >= TEXT_BLOB_MIN {
541	539		return schema("an insert this large is stored as a text blob in a version 2 change");
542	540		}
		…	299 unchanged lines
842	840		/// the insert claims; [`text_lines`] reads and checks a blob's content.
843	841		/// A resolver may also return no lines, leaving a placeholder for a reader
844	842		/// that fills it in later (history-only states, spec §11).
845		-	pub type Resolver<'a> = dyn FnMut(&ObjectRef, u32) -> Result<Vec<Vec<u8>>, ObjectError> + 'a;
	843	+	pub type Resolver<'a> = dyn FnMut(&ObjectRef, u32) -> Result<Lines, ObjectError> + 'a;
846	844
847	845		/// Receives the stored texts of a change being encoded, a batch at a
848	846		/// time; returns false to stop making more.
		…	16 unchanged lines
865	863
866	864		/// The lines of an inline insert from its array's bytes (see
867	865		/// [`TextRef::Inline`]).
868		-	pub fn inline_lines(array: &[u8]) -> Result<Vec<Vec<u8>>, ObjectError> {
	866	+	pub fn inline_lines(array: &[u8]) -> Result<Lines, ObjectError> {
869	867		let v = cbor::decode(array)?;
870	868		let lines = array_lines(&v)?;
871	869		if lines.is_empty() {
		…	2 unchanged lines
874	872		Ok(lines)
875	873		}
876	874
877		-	fn array_lines(v: &Value) -> Result<Vec<Vec<u8>>, ObjectError> {
878		-	array(v, "lines")?
	875	+	/// The lines of a CBOR array of byte strings, copied once into one buffer.
	876	+	fn array_lines(v: &Value) -> Result<Lines, ObjectError> {
	877	+	Ok(array(v, "lines")?
879	878		.iter()
880		-	.map(\|l\| bytes(l, "line").map(\|b\| b.to_vec()))
881		-	.collect()
	879	+	.map(\|l\| bytes(l, "line"))
	880	+	.collect::<Result<Vec<&[u8]>, _>>()?
	881	+	.into_iter()
	882	+	.collect())
882	883		}
883	884
884	885		impl Change {
		…	90 unchanged lines
975	976		let Some((start, end, count)) = inline else {
976	977		return Edit::from_value(&Value::Map(fields), version, &mut \|text, count\| {
977	978		texts.push(TextRef::Blob(*text, count));
978		-	Ok(Vec::new())
	979	+	Ok(Lines::default())
979	980		});
980	981		};
981	982		if uint(field(&fields, 0, "edit tag")?, "edit tag")? != 0 \|\| fields.contains_key(&5) {
		…	17 unchanged lines
999	1000		node: node_id(field(&fields, 1, "edit.node")?, "edit.node")?,
1000	1001		after: AtomRef::from_value(field(&fields, 2, "after")?, "after")?,
1001	1002		before: AtomRef::from_value(field(&fields, 3, "before")?, "before")?,
1002		-	lines: Vec::new(),
	1003	+	lines: Lines::default(),
1003	1004		})
1004	1005		}
1005	1006
		…	8 unchanged lines
1014	1015		/// The lines a text blob's `content` holds, checked against the rules for
1015	1016		/// one: canonical, as many as the insert claims, and not short enough to
1016	1017		/// have been inline.
1017		-	pub fn text_lines(content: &[u8], count: u32) -> Result<Vec<Vec<u8>>, ObjectError> {
	1018	+	pub fn text_lines(content: &[u8], count: u32) -> Result<Lines, ObjectError> {
1018	1019		if content.len() < TEXT_BLOB_MIN {
1019	1020		return schema(format!(
1020	1021		"a text blob of {} bytes is short enough to be inline",
1021	1022		content.len()
1022	1023		));
1023	1024		}
1024		-	let v = cbor::decode(content)?;
1025		-	let lines = array(&v, "text blob")?
1026		-	.iter()
1027		-	.map(\|l\| bytes(l, "line").map(\|b\| b.to_vec()))
1028		-	.collect::<Result<Vec<_>, _>>()?;
	1025	+	let lines = array_lines(&cbor::decode(content)?)?;
1029	1026		if lines.len() != count as usize {
1030	1027		return schema(format!(
1031	1028		"a text blob holds {} lines, the insert says {count}",
		…	192 unchanged lines
1224	1221		node: n,
1225	1222		after: AtomRef::Start,
1226	1223		before: AtomRef::End,
1227		-	lines: vec![b"hello\n".to_vec(), b"world\n".to_vec()],
	1224	+	lines: vec![b"hello\n".to_vec(), b"world\n".to_vec()].into(),
1228	1225		},
1229	1226		Edit::Delete {
1230	1227		node: n,
		…	60 unchanged lines
1291	1288		);
1292	1289		}
1293	1290
1294		-	fn big_lines(n: usize) -> Vec<Vec<u8>> {
	1291	+	fn big_lines(n: usize) -> Lines {
1295	1292		(0..n)
1296	1293		.map(\|i\| format!("line {i} of a large insert\n").into_bytes())
1297	1294		.collect()
1298	1295		}
1299	1296
1300		-	fn with_insert(mut c: Change, lines: Vec<Vec<u8>>) -> Change {
	1297	+	fn with_insert(mut c: Change, lines: Lines) -> Change {
1301	1298		c.edits[0] = Edit::Insert {
1302	1299		node: NodeId([7; 16]),
1303	1300		after: AtomRef::Start,
		…	57 unchanged lines
1361	1358		node: NodeId([8; 16]),
1362	1359		after: AtomRef::Start,
1363	1360		before: AtomRef::End,
1364		-	lines: vec![b"small\n".to_vec(), b"insert\n".to_vec()],
	1361	+	lines: vec![b"small\n".to_vec(), b"insert\n".to_vec()].into(),
1365	1362		});
1366	1363		let (bytes, stored) = c.encode_parts();
1367	1364		let me = ObjectRef([4; 32]);
		…	36 unchanged lines
1404	1401		assert_eq!(
1405	1402		content,
1406	1403		cbor::encode(&Value::Array(
1407		-	lines.iter().map(\|l\| Value::Bytes(l.clone())).collect()
	1404	+	lines.iter().map(\|l\| Value::Bytes(l.to_vec())).collect()
1408	1405		))
1409	1406		);
1410	1407		assert_eq!(text_lines(&content, 500).unwrap(), lines);
1411	1408		assert!(text_lines(&content, 499).is_err());
1412		-	let small = cbor::encode_byte_strings(&[b"x\n".to_vec()]);
	1409	+	let small = cbor::encode_byte_strings(&vec![b"x\n".to_vec()].into());
1413	1410		assert!(text_lines(&small, 1).is_err(), "short enough to be inline");
1414	1411		}
1415	1412
		…	81 unchanged lines

		…	13 unchanged lines
14	14		pub mod identity;
15	15		pub mod ids;
16	16		pub mod lanes;
	17	+	pub mod lines;
17	18		pub mod objects;
18	19		pub mod oplog;
19	20		pub mod policy;
		…	10 unchanged lines

		…	89 unchanged lines
90	90		ObjectType::Blob => Blob::decode(body).map(\|_\| ()),
91	91		// Structure only: the text blobs are checked with the change graph.
92	92		ObjectType::Change => {
93		-	Change::decode_with(body, &mut \|_, _\| Ok(vec![Vec::new()])).map(\|_\| ())
	93	+	Change::decode_with(body, &mut \|_, _\| Ok(crate::lines::Lines::default())).map(\|_\| ())
94	94		}
95	95		ObjectType::Checkpoint => crate::objects::Checkpoint::decode(body).map(\|_\| ()),
96	96		ObjectType::Op => match Op::decode(body) {
		…	391 unchanged lines

		…	1070 unchanged lines
1071	1071		if let Edit::Insert { node, lines, .. } = e {
1072	1072		let off = per_node.get(node).copied().unwrap_or(0);
1073	1073		let idx = counts.entry(*node).or_default();
1074		-	for _ in lines {
	1074	+	for _ in lines.iter() {
1075	1075		corr.atoms.insert((node, idx), *idx + off);
1076	1076		*idx += 1;
1077	1077		}
		…	128 unchanged lines

		…	1476 unchanged lines
1477	1477		};
1478	1478		f.hunks.push(DiffHunk {
1479	1479		base_line,
1480		-	added: lines.clone(),
	1480	+	added: lines.to_vec(),
1481	1481		removed: vec![],
1482	1482		});
1483	1483		}
		…	226 unchanged lines
1710	1710		node,
1711	1711		after: crate::objects::AtomRef::Start,
1712	1712		before: crate::objects::AtomRef::End,
1713		-	lines: split_lines(&content).iter().map(\|l\| l.to_vec()).collect(),
	1713	+	lines: crate::lines::Lines::split(&content),
1714	1714		});
1715	1715		}
1716	1716		self.statuses.push(PathStatus {
		…	254 unchanged lines
1971	1971		node,
1972	1972		after: crate::objects::AtomRef::Start,
1973	1973		before: crate::objects::AtomRef::End,
1974		-	lines: split_lines(&e.content).iter().map(\|l\| l.to_vec()).collect(),
	1974	+	lines: crate::lines::Lines::split(&e.content),
1975	1975		});
1976	1976		}
1977	1977		} else {
		…	235 unchanged lines
2213	2213		}
2214	2214		match e {
2215	2215		Edit::Insert { lines, .. } => {
2216		-	for l in lines {
	2216	+	for l in lines.iter() {
2217	2217		out.push('+');
2218	2218		out.push_str(&String::from_utf8_lossy(l));
2219	2219		if !l.ends_with(b"\n") {
		…	140 unchanged lines

		…	32 unchanged lines
33	33		for e in &change.edits {
34	34		if let Edit::Insert { node, lines, .. } = e {
35	35		let idx = per_node.entry(*node).or_default();
36		-	for _ in lines {
	36	+	for _ in lines.iter() {
37	37		atoms.insert((node, idx), *idx);
38	38		*idx += 1;
39	39		}
		…	11 unchanged lines
51	51		let mut m: HashMap<crate::ids::NodeId, Vec<Vec<u8>>> = HashMap::new();
52	52		for e in &c.edits {
53	53		if let Edit::Insert { node, lines, .. } = e {
54		-	m.entry(*node).or_default().extend(lines.iter().cloned());
	54	+	m.entry(*node)
	55	+	.or_default()
	56	+	.extend(lines.iter().map(<[u8]>::to_vec));
55	57		}
56	58		}
57	59		m
		…	430 unchanged lines
488	490		node: f,
489	491		after: AtomRef::Start,
490	492		before: AtomRef::End,
491		-	lines: vec![b"a\n".to_vec(), b"b\n".to_vec()],
	493	+	lines: vec![b"a\n".to_vec(), b"b\n".to_vec()].into(),
492	494		}],
493	495		"one",
494	496		);
		…	17 unchanged lines
512	514		index: 1,
513	515		},
514	516		before: AtomRef::End,
515		-	lines: vec![b"c\n".to_vec()],
	517	+	lines: vec![b"c\n".to_vec()].into(),
516	518		},
517	519		],
518	520		"two",
		…	19 unchanged lines
538	540		index: 0,
539	541		},
540	542		before: AtomRef::End,
541		-	lines: vec![b"d\n".to_vec()],
	543	+	lines: vec![b"d\n".to_vec()].into(),
542	544		}],
543	545		"three",
544	546		);
		…	56 unchanged lines
601	603		node: f,
602	604		after: AtomRef::Start,
603	605		before: AtomRef::End,
604		-	lines: vec![b"a\n".to_vec(), b"b\n".to_vec()],
	606	+	lines: vec![b"a\n".to_vec(), b"b\n".to_vec()].into(),
605	607		}],
606	608		"one",
607	609		);
		…	8 unchanged lines
616	618		index: 1,
617	619		},
618	620		before: AtomRef::End,
619		-	lines: vec![b"c\n".to_vec()],
	621	+	lines: vec![b"c\n".to_vec()].into(),
620	622		}],
621	623		"two",
622	624		);
		…	7 unchanged lines
630	632		node: f,
631	633		after: AtomRef::Start,
632	634		before: AtomRef::End,
633		-	lines: vec![b"a\n".to_vec()],
	635	+	lines: vec![b"a\n".to_vec()].into(),
634	636		}];
635	637		let corr = Correspondence {
636	638		atoms: [((f, 0), 0)].into_iter().collect(),
		…	89 unchanged lines
726	728		node: g,
727	729		after: AtomRef::Start,
728	730		before: AtomRef::End,
729		-	lines: vec![b"x\n".to_vec()],
	731	+	lines: vec![b"x\n".to_vec()].into(),
730	732		}],
731	733		"three",
732	734		);
		…	42 unchanged lines

		…	1243 unchanged lines
1244	1244		node: f,
1245	1245		after: AtomRef::Start,
1246	1246		before: AtomRef::End,
1247		-	lines: vec![b"one\n".to_vec(), b"two\n".to_vec()],
	1247	+	lines: vec![b"one\n".to_vec(), b"two\n".to_vec()].into(),
1248	1248		}],
1249	1249		);
1250	1250		let h1 = st.add(c1).unwrap();
		…	17 unchanged lines
1268	1268		index: 1,
1269	1269		},
1270	1270		before: AtomRef::End,
1271		-	lines: vec![b"three\n".to_vec()],
	1271	+	lines: vec![b"three\n".to_vec()].into(),
1272	1272		},
1273	1273		],
1274	1274		);
		…	47 unchanged lines
1322	1322		node: f,
1323	1323		after: AtomRef::Start,
1324	1324		before: AtomRef::End,
1325		-	lines: vec![b"a\n".to_vec(), b"c\n".to_vec()],
	1325	+	lines: vec![b"a\n".to_vec(), b"c\n".to_vec()].into(),
1326	1326		},
1327	1327		// Insert between the two lines just inserted, using self references.
1328	1328		Edit::Insert {
		…	6 unchanged lines
1335	1335		change: ObjectRef::ZERO,
1336	1336		index: 1,
1337	1337		},
1338		-	lines: vec![b"b\n".to_vec()],
	1338	+	lines: vec![b"b\n".to_vec()].into(),
1339	1339		},
1340	1340		],
1341	1341		);
		…	80 unchanged lines
1422	1422		node: f,
1423	1423		after: AtomRef::Start,
1424	1424		before: AtomRef::End,
1425		-	lines: vec![b"1\n".to_vec(), b"2\n".to_vec()],
	1425	+	lines: vec![b"1\n".to_vec(), b"2\n".to_vec()].into(),
1426	1426		}],
1427	1427		))
1428	1428		.unwrap();
		…	28 unchanged lines
1457	1457		index: 1,
1458	1458		},
1459	1459		before: AtomRef::End,
1460		-	lines: vec![b"3\n".to_vec()],
	1460	+	lines: vec![b"3\n".to_vec()].into(),
1461	1461		}],
1462	1462		);
1463	1463		let mut full = st.clone();
		…	29 unchanged lines
1493	1493		node,
1494	1494		after: AtomRef::Start,
1495	1495		before: AtomRef::End,
1496		-	lines: vec![line.to_vec()],
	1496	+	lines: vec![line.to_vec()].into(),
1497	1497		};
1498	1498		let c1 = change(
1499	1499		vec![],
		…	74 unchanged lines
1574	1574		parent: NodeId::ROOT,
1575	1575		name: name.into(),
1576	1576		};
1577		-	let lines: Vec<Vec<u8>> = (0..300)
	1577	+	let lines: crate::lines::Lines = (0..300)
1578	1578		.map(\|i\| format!("line {i}\n").into_bytes())
1579	1579		.collect();
1580	1580		let c1 = change(
		…	4 unchanged lines
1585	1585		node: small,
1586	1586		after: AtomRef::Start,
1587	1587		before: AtomRef::End,
1588		-	lines: vec![b"x\n".to_vec()],
	1588	+	lines: vec![b"x\n".to_vec()].into(),
1589	1589		},
1590	1590		Edit::Insert {
1591	1591		node: big,
		…	26 unchanged lines
1618	1618		change: h1,
1619	1619		index: 21,
1620	1620		},
1621		-	lines: vec![b"new a\n".to_vec(), b"new b\n".to_vec()],
	1621	+	lines: vec![b"new a\n".to_vec(), b"new b\n".to_vec()].into(),
1622	1622		},
1623	1623		Edit::Insert {
1624	1624		node: small,
		…	2 unchanged lines
1627	1627		index: 0,
1628	1628		},
1629	1629		before: AtomRef::End,
1630		-	lines: vec![b"y\n".to_vec()],
	1630	+	lines: vec![b"y\n".to_vec()].into(),
1631	1631		},
1632	1632		],
1633	1633		);
		…	96 unchanged lines
1730	1730		node: f,
1731	1731		after: AtomRef::Start,
1732	1732		before: AtomRef::End,
1733		-	lines: vec![b"a\n".to_vec()],
	1733	+	lines: vec![b"a\n".to_vec()].into(),
1734	1734		}],
1735	1735		))
1736	1736		.unwrap();
		…	18 unchanged lines
1755	1755		node: f,
1756	1756		after: AtomRef::Start,
1757	1757		before: AtomRef::End,
1758		-	lines: vec![b"a\n".to_vec()],
	1758	+	lines: vec![b"a\n".to_vec()].into(),
1759	1759		}],
1760	1760		))
1761	1761		.unwrap();
		…	14 unchanged lines
1776	1776		parent: NodeId::ROOT,
1777	1777		name: name.into(),
1778	1778		};
1779		-	let big_lines: Vec<Vec<u8>> = (0..400)
	1779	+	let big_lines: crate::lines::Lines = (0..400)
1780	1780		.map(\|i\| format!("line {i} of a long file\n").into_bytes())
1781	1781		.collect();
1782	1782		let h1 = st
		…	5 unchanged lines
1788	1788		node: small,
1789	1789		after: AtomRef::Start,
1790	1790		before: AtomRef::End,
1791		-	lines: vec![b"x\n".to_vec()],
	1791	+	lines: vec![b"x\n".to_vec()].into(),
1792	1792		},
1793	1793		Edit::Insert {
1794	1794		node: big,
		…	129 unchanged lines

		…	383 unchanged lines
384	384		\| Before \| 61 s \| 7.1 GB \| 10.1 GB \|
385	385		\| After \| 40.7 s \| 7.4 GB \| 8.7 GB \|
386	386		\| Texts stored a batch at a time while encoding \| 41.6 s \| 4.8 GB \| 5.8 GB \|
	387	+	\| Lines in one shared buffer per insert (Earth under load) \| 50.1 s \| 4.3 GB \| 4.9 GB \|
387	388		\| Git \| 33.7 to 37.9 s \| \| 42 MB \|
388	389
389	390		Storing a change's texts a batch at a time as they are made (the
390	391		encoder hands each batch of 256 to the store) removed the storing peak.
391		-	The peak is now the working copy's content (1.6 GB) and its lines, a Vec
392		-	each (2.6 GB): M2.
	392	+	The peak was then the working copy's content (1.6 GB) and its lines, a
	393	+	Vec each (2.6 GB). An insert's lines are now one buffer with line ends
	394	+	(`Lines`), shared by the change and by the file graph, whose atoms point
	395	+	into it: the diff of the whole tree takes 3.3 s and 1.1 million
	396	+	allocations (from 6.2 s and 45 million), and the peak is 4.3 GB (4.9 GB
	397	+	RSS). That run shared Earth with Flow jobs (load average 6.5 on 4 cores),
	398	+	so its total time is not comparable with the rows above.
393	399

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

Keep an insert's lines in one shared buffer 01a47cd7f0c8

Keyboard