borogove

Keep sortId shorter with a large MessageSync rss

created pr with borogove/sort-id-length.1 on 2026-11-10T03:06:30Z · by 9e834e0d

added borogove/sort-id-length.2 on 2026-11-10T19:38:47Z · by 9e834e0d


                      -:  ------- > 1:  25705f6 Never start a sync window at a franctional sortId


                      1:  0bc2ca2 = 2:  341262a Keep sortId shorter with a large MessageSync

added borogove/sort-id-length.3 on 2026-11-10T20:28:29Z · by 9e834e0d


                      1:  25705f6 ! 1:  07afd44 Never start a sync window at a franctional sortId


                      2:  341262a ! 2:  83a6338 Keep sortId shorter with a large MessageSync

added borogove/sort-id-length.4 on 2026-11-10T20:29:20Z · by 9e834e0d


                      1:  07afd44 ! 1:  309d938 Never start a sync window at a franctional sortId


                      2:  83a6338 = 2:  65784dd Keep sortId shorter with a large MessageSync

cmds

checkout latest patchset:

ssh pr.pico.sh pull borogove:sort-id-length | git am -3

checkout specific patchset revision:

ssh pr.pico.sh pull borogove:sort-id-length [rev] | git am -3

add changes to patch request:

git format-patch main --stdout | ssh pr.pico.sh borogove:sort-id-length

add comment to patch request:

ssh pr.pico.sh comment borogove:sort-id-length "lgtm!"

Patchset `borogove/sort-id-length.4` on 2026-11-10T20:29:20Z · commit 65784dd

Never start a sync window at a franctional sortId

Stephen Paul Weber 2026-11-10T02:48:00Z

→ Keep sortId shorter with a large MessageSync

Stephen Paul Weber 2026-11-10T03:03:36Z

Keep sortId shorter with a large MessageSync

Stephen Paul Weber 2026-11-10T03:03:36Z

Doing between over and over again in a small window is worst case for
the algorithm, so use nBetween on a whole page at a time to improve the
size of the sortIds.

Semantic diff summary

0 added, 0 modified, 0 signature changed, 0 removed across 0 analyzed files (2 files skipped: unsupported file type)

+40 -31 borogove/MessageSync.hx #

......@@ -10,6 +10,7 @@ import borogove.queries.MAMQuery;
import thenshim.Promise;
import thenshim.PromiseTools;
using StringTools;
using Lambda;

#if !NO_OMEMO
import borogove.OMEMO;

......@@ -59,7 +60,8 @@ class MessageSync {
		if (complete) {
			throw new Exception("Attempt to fetch messages, but already complete");
		}
		final promisedMessages:Array<Promise<Message>> = [];
		final promisedMessages:Array<Promise<(String) -> Message>> = [];
		final pageStartSortA = sortA;
		if (lastPage != null) {
			if (filter.page == null) filter.page = {};
			if (filter.page.before == null) {

......@@ -86,8 +88,6 @@ class MessageSync {
			if (originalMessage == null) { // No message, nothing for us to do
				return EventHandled;
			}
			final sortLower = sortA;
			sortA = FractionalIndexing.between(sortLower, sortB, FractionalIndexing.BASE_95_DIGITS);
			final serverReceivedAt = result.findText("{urn:xmpp:forward:0}forwarded/{urn:xmpp:delay}delay@stamp");
			var timeReceived = serverReceivedAt;
			if (timeReceived == null) {

......@@ -115,7 +115,6 @@ class MessageSync {
				jmi.set(jmiChildren[0].attr.get("id"), originalMessage);
			}

			final sortId = sortA;
#if !NO_OMEMO
			if (originalMessage.hasChild("encrypted", NS.OMEMO)) {
				trace("MAM: Processing OMEMO message from " + originalMessage.attr.get("from"));

......@@ -123,7 +122,7 @@ class MessageSync {
					final decryptedStanza = decryptionResult.stanza;
					trace("MAM: Decrypted stanza: "+decryptedStanza);

					return Message.fromStanza(decryptedStanza, client.jid, (builder, stanza) -> {
					return (sortId) -> Message.fromStanza(decryptedStanza, client.jid, (builder, stanza) -> {
						builder.sortId = sortId;
						builder.debug = {
							source: "mam",

......@@ -133,7 +132,7 @@ class MessageSync {
							startFiler: startFilter,
							now: Date.format(std.Date.now()),
							path: "decrypted",
							sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
							sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
						};
						builder.serverId = result.attr.get("id");
						builder.serverIdBy = serviceJID;

......@@ -143,25 +142,23 @@ class MessageSync {
					});
				}, (err) -> {
					trace("MAM: Decryption failed: "+err);
					return Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
							builder.sortId = sortA;
							builder.debug = {
								source: "mam",
								serverReceivedAt: serverReceivedAt,
								serviceJID: serviceJID,
								filter: filter,
								startFiler: startFilter,
								now: Date.format(std.Date.now()),
								path: "decryption failed",
								sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
							};
							builder.serverId = result.attr.get("id");
							builder.serverIdBy = serviceJID;
							if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
							return contextHandler(builder, stanza);
						},
						new EncryptionInfo(DecryptionFailure, NS.OMEMO, "OMEMO", "internal-error", Std.string(err))
					);
					return (sortId) -> Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
						builder.sortId = sortId;
						builder.debug = {
							source: "mam",
							serverReceivedAt: serverReceivedAt,
							serviceJID: serviceJID,
							filter: filter,
							startFiler: startFilter,
							now: Date.format(std.Date.now()),
							path: "decryption failed",
							sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
						};
						builder.serverId = result.attr.get("id");
						builder.serverIdBy = serviceJID;
						if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
						return contextHandler(builder, stanza);
					}, new EncryptionInfo(DecryptionFailure, NS.OMEMO, "OMEMO", "internal-error", Std.string(err)));
				}));
				return EventHandled;
			}

......@@ -169,7 +166,7 @@ class MessageSync {

			trace("MAM: Processing non-OMEMO message from " + originalMessage.attr.get("from"));

			final msg = Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
			promisedMessages.push(Promise.resolve((sortId) -> Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
				builder.sortId = sortId;
				builder.debug = {
					source: "mam",

......@@ -179,15 +176,13 @@ class MessageSync {
					startFiler: startFilter,
					now: Date.format(std.Date.now()),
					path: "unencrypted",
					sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
					sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
				};
				builder.serverId = result.attr.get("id");
				builder.serverIdBy = serviceJID;
				if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
				return contextHandler(builder, stanza);
			});

			promisedMessages.push(Promise.resolve(msg));
			})));

			return EventHandled;
		});

......@@ -205,9 +200,11 @@ class MessageSync {
			}
			if (result != null || errorHandler == null) {
				PromiseTools.all(promisedMessages).then((messages) -> {
					final sortIds = sortIdsForPage(pageStartSortA, sortB, messages.length);
					if (sortIds.length > 0) sortA = sortIds[sortIds.length - 1];
					handler({
						sync: this,
						messages: messages,
						messages: messages.mapi((i, m) -> m(sortIds[i])),
					});
				});
			}

......@@ -219,6 +216,18 @@ class MessageSync {
		return !complete;
	}

	private static function sortIdsForPage(start:Null<String>, end:Null<String>, count:Int):Array<String> {
		if (count <= 0) return [];
		if (start == null && end != null) {
			final first = FractionalIndexing.between(null, end, FractionalIndexing.BASE_95_DIGITS);
			if (count == 1) return [first];
			final rest = FractionalIndexing.nBetween(first, end, count - 1, FractionalIndexing.BASE_95_DIGITS);
			rest.unshift(first);
			return rest;
		}
		return FractionalIndexing.nBetween(start, end, count, FractionalIndexing.BASE_95_DIGITS);
	}

	public function addContext(handler: (ChatMessageBuilder, Stanza)->ChatMessageBuilder) {
		this.contextHandler = handler;
	}

+68 -0 test/TestSortId.hx #

......@@ -465,4 +465,72 @@ class TestSortId extends utest.Test {

		startBatch();
	}

	public function testLongChannelSyncSortIdStaysShort(async: Async) {
		final persistence = new Dummy();
		final client = new Client("test@example.com", persistence);
		final disco = new Caps("", [], ["http://jabber.org/protocol/muc", "urn:xmpp:mam:2"], []);
		final channel = new Channel(client, client.stream, persistence, "longsync@example.com", Open, false, false, null, null, null, disco);
		client.chats.push(channel);

		final messageCount = 700;
		final maxAllowedLength = 100;
		var maxSortIdLength = 0;
		var finished = false;

		client.addSyncMessageListener((message) -> {
			final sortId = message.sortId;
			if (sortId == null) return;
			if (sortId.length > maxSortIdLength) maxSortIdLength = sortId.length;
		});

		client.on("chats/update", (chats) -> {
			if (finished || channel.sync != null) return EventHandled;
			finished = true;
			Assert.isTrue(maxSortIdLength < maxAllowedLength, 'max sortId length $maxSortIdLength should be < $maxAllowedLength for a single $messageCount-message sync');
			async.done();
			return EventHandled;
		});

		client.stream.on("sendStanza", (stanza: Stanza) -> {
			if (stanza.name != "iq") return EventUnhandled;
			final query = stanza.findChild("{urn:xmpp:mam:2}query");
			if (query == null) return EventUnhandled;

			final iqId = stanza.attr.get("id");
			final queryId = query.attr.get("queryid");
			if (iqId == null || queryId == null) {
				Assert.fail("MAM query was not sent");
				return EventHandled;
			}

			haxe.Timer.delay(() -> {
				for (i in 0...messageCount) {
					final serverId = 'long-$i';
					client.stream.onStanza(new Stanza("message", { from: channel.chatId, xmlns: "jabber:client" })
						.tag("result", { xmlns: "urn:xmpp:mam:2", queryid: queryId, id: serverId })
							.tag("forwarded", { xmlns: "urn:xmpp:forward:0" })
								.tag("delay", { xmlns: "urn:xmpp:delay", stamp: "2023-01-01T00:00:00Z" }).up()
								.tag("message", { from: channel.chatId + "/user", to: "test@example.com", id: serverId, xmlns: "jabber:client" })
									.textTag("body", 'message $serverId')
								.up()
							.up()
						.up()
					);
				}

				client.stream.onStanza(new Stanza("iq", { type: "result", id: iqId, from: channel.chatId, xmlns: "jabber:client" })
					.tag("fin", { xmlns: "urn:xmpp:mam:2", complete: "true" })
						.tag("set", { xmlns: "http://jabber.org/protocol/rsm" })
							.textTag("first", "long-0")
							.textTag("last", 'long-${messageCount - 1}')
						.up()
					.up()
				);
			}, 0);
			return EventHandled;
		});

		channel.doSync(null);
	}
}

...	...		@@ -115,7 +115,6 @@ class MessageSync {
115	115		jmi.set(jmiChildren[0].attr.get("id"), originalMessage);
116	116		}
117	117
118		-	final sortId = sortA;
119	118		#if !NO_OMEMO
120	119		if (originalMessage.hasChild("encrypted", NS.OMEMO)) {
121	120		trace("MAM: Processing OMEMO message from " + originalMessage.attr.get("from"));

...	...		@@ -179,15 +176,13 @@ class MessageSync {
179	176		startFiler: startFilter,
180	177		now: Date.format(std.Date.now()),
181	178		path: "unencrypted",
182		-	sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
	179	+	sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
183	180		};
184	181		builder.serverId = result.attr.get("id");
185	182		builder.serverIdBy = serviceJID;
186	183		if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
187	184		return contextHandler(builder, stanza);
188		-	});
189		-
190		-	promisedMessages.push(Promise.resolve(msg));
	185	+	})));
191	186
192	187		return EventHandled;
193	188		});

...	...		@@ -219,6 +216,18 @@ class MessageSync {
219	216		return !complete;
220	217		}
221	218
	219	+	private static function sortIdsForPage(start:Null<String>, end:Null<String>, count:Int):Array<String> {
	220	+	if (count <= 0) return [];
	221	+	if (start == null && end != null) {
	222	+	final first = FractionalIndexing.between(null, end, FractionalIndexing.BASE_95_DIGITS);
	223	+	if (count == 1) return [first];
	224	+	final rest = FractionalIndexing.nBetween(first, end, count - 1, FractionalIndexing.BASE_95_DIGITS);
	225	+	rest.unshift(first);
	226	+	return rest;
	227	+	}
	228	+	return FractionalIndexing.nBetween(start, end, count, FractionalIndexing.BASE_95_DIGITS);
	229	+	}
	230	+
222	231		public function addContext(handler: (ChatMessageBuilder, Stanza)->ChatMessageBuilder) {
223	232		this.contextHandler = handler;
224	233		}

...	...		@@ -465,4 +465,72 @@ class TestSortId extends utest.Test {
465	465
466	466		startBatch();
467	467		}
	468	+
	469	+	public function testLongChannelSyncSortIdStaysShort(async: Async) {
	470	+	final persistence = new Dummy();
	471	+	final client = new Client("test@example.com", persistence);
	472	+	final disco = new Caps("", [], ["http://jabber.org/protocol/muc", "urn:xmpp:mam:2"], []);
	473	+	final channel = new Channel(client, client.stream, persistence, "longsync@example.com", Open, false, false, null, null, null, disco);
	474	+	client.chats.push(channel);
	475	+
	476	+	final messageCount = 700;
	477	+	final maxAllowedLength = 100;
	478	+	var maxSortIdLength = 0;
	479	+	var finished = false;
	480	+
	481	+	client.addSyncMessageListener((message) -> {
	482	+	final sortId = message.sortId;
	483	+	if (sortId == null) return;
	484	+	if (sortId.length > maxSortIdLength) maxSortIdLength = sortId.length;
	485	+	});
	486	+
	487	+	client.on("chats/update", (chats) -> {
	488	+	if (finished \|\| channel.sync != null) return EventHandled;
	489	+	finished = true;
	490	+	Assert.isTrue(maxSortIdLength < maxAllowedLength, 'max sortId length $maxSortIdLength should be < $maxAllowedLength for a single $messageCount-message sync');
	491	+	async.done();
	492	+	return EventHandled;
	493	+	});
	494	+
	495	+	client.stream.on("sendStanza", (stanza: Stanza) -> {
	496	+	if (stanza.name != "iq") return EventUnhandled;
	497	+	final query = stanza.findChild("{urn:xmpp:mam:2}query");
	498	+	if (query == null) return EventUnhandled;
	499	+
	500	+	final iqId = stanza.attr.get("id");
	501	+	final queryId = query.attr.get("queryid");
	502	+	if (iqId == null \|\| queryId == null) {
	503	+	Assert.fail("MAM query was not sent");
	504	+	return EventHandled;
	505	+	}
	506	+
	507	+	haxe.Timer.delay(() -> {
	508	+	for (i in 0...messageCount) {
	509	+	final serverId = 'long-$i';
	510	+	client.stream.onStanza(new Stanza("message", { from: channel.chatId, xmlns: "jabber:client" })
	511	+	.tag("result", { xmlns: "urn:xmpp:mam:2", queryid: queryId, id: serverId })
	512	+	.tag("forwarded", { xmlns: "urn:xmpp:forward:0" })
	513	+	.tag("delay", { xmlns: "urn:xmpp:delay", stamp: "2023-01-01T00:00:00Z" }).up()
	514	+	.tag("message", { from: channel.chatId + "/user", to: "test@example.com", id: serverId, xmlns: "jabber:client" })
	515	+	.textTag("body", 'message $serverId')
	516	+	.up()
	517	+	.up()
	518	+	.up()
	519	+	);
	520	+	}
	521	+
	522	+	client.stream.onStanza(new Stanza("iq", { type: "result", id: iqId, from: channel.chatId, xmlns: "jabber:client" })
	523	+	.tag("fin", { xmlns: "urn:xmpp:mam:2", complete: "true" })
	524	+	.tag("set", { xmlns: "http://jabber.org/protocol/rsm" })
	525	+	.textTag("first", "long-0")
	526	+	.textTag("last", 'long-${messageCount - 1}')
	527	+	.up()
	528	+	.up()
	529	+	);
	530	+	}, 0);
	531	+	return EventHandled;
	532	+	});
	533	+
	534	+	channel.doSync(null);
	535	+	}
468	536		}

...	...		@@ -10,6 +10,7 @@ import borogove.queries.MAMQuery;
10	10		import thenshim.Promise;
11	11		import thenshim.PromiseTools;
12	12		using StringTools;
	13	+	using Lambda;
13	14
14	15		#if !NO_OMEMO
15	16		import borogove.OMEMO;

...	...		@@ -59,7 +60,8 @@ class MessageSync {
59	60		if (complete) {
60	61		throw new Exception("Attempt to fetch messages, but already complete");
61	62		}
62		-	final promisedMessages:Array<Promise<Message>> = [];
	63	+	final promisedMessages:Array<Promise<(String) -> Message>> = [];
	64	+	final pageStartSortA = sortA;
63	65		if (lastPage != null) {
64	66		if (filter.page == null) filter.page = {};
65	67		if (filter.page.before == null) {

...	...		@@ -86,8 +88,6 @@ class MessageSync {
86	88		if (originalMessage == null) { // No message, nothing for us to do
87	89		return EventHandled;
88	90		}
89		-	final sortLower = sortA;
90		-	sortA = FractionalIndexing.between(sortLower, sortB, FractionalIndexing.BASE_95_DIGITS);
91	91		final serverReceivedAt = result.findText("{urn:xmpp:forward:0}forwarded/{urn:xmpp:delay}delay@stamp");
92	92		var timeReceived = serverReceivedAt;
93	93		if (timeReceived == null) {

...	...		@@ -123,7 +122,7 @@ class MessageSync {
123	122		final decryptedStanza = decryptionResult.stanza;
124	123		trace("MAM: Decrypted stanza: "+decryptedStanza);
125	124
126		-	return Message.fromStanza(decryptedStanza, client.jid, (builder, stanza) -> {
	125	+	return (sortId) -> Message.fromStanza(decryptedStanza, client.jid, (builder, stanza) -> {
127	126		builder.sortId = sortId;
128	127		builder.debug = {
129	128		source: "mam",

...	...		@@ -133,7 +132,7 @@ class MessageSync {
133	132		startFiler: startFilter,
134	133		now: Date.format(std.Date.now()),
135	134		path: "decrypted",
136		-	sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
	135	+	sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
137	136		};
138	137		builder.serverId = result.attr.get("id");
139	138		builder.serverIdBy = serviceJID;

...	...		@@ -143,25 +142,23 @@ class MessageSync {
143	142		});
144	143		}, (err) -> {
145	144		trace("MAM: Decryption failed: "+err);
146		-	return Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
147		-	builder.sortId = sortA;
148		-	builder.debug = {
149		-	source: "mam",
150		-	serverReceivedAt: serverReceivedAt,
151		-	serviceJID: serviceJID,
152		-	filter: filter,
153		-	startFiler: startFilter,
154		-	now: Date.format(std.Date.now()),
155		-	path: "decryption failed",
156		-	sortId: { method: "between", startSortA: startSortA, lower: sortLower, upper: sortB },
157		-	};
158		-	builder.serverId = result.attr.get("id");
159		-	builder.serverIdBy = serviceJID;
160		-	if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
161		-	return contextHandler(builder, stanza);
162		-	},
163		-	new EncryptionInfo(DecryptionFailure, NS.OMEMO, "OMEMO", "internal-error", Std.string(err))
164		-	);
	145	+	return (sortId) -> Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
	146	+	builder.sortId = sortId;
	147	+	builder.debug = {
	148	+	source: "mam",
	149	+	serverReceivedAt: serverReceivedAt,
	150	+	serviceJID: serviceJID,
	151	+	filter: filter,
	152	+	startFiler: startFilter,
	153	+	now: Date.format(std.Date.now()),
	154	+	path: "decryption failed",
	155	+	sortId: { method: "between", startSortA: startSortA, lower: pageStartSortA, upper: sortB },
	156	+	};
	157	+	builder.serverId = result.attr.get("id");
	158	+	builder.serverIdBy = serviceJID;
	159	+	if (timeReceived != null && builder.timeReceived == null) builder.timeReceived = timeReceived;
	160	+	return contextHandler(builder, stanza);
	161	+	}, new EncryptionInfo(DecryptionFailure, NS.OMEMO, "OMEMO", "internal-error", Std.string(err)));
165	162		}));
166	163		return EventHandled;
167	164		}

...	...		@@ -169,7 +166,7 @@ class MessageSync {
169	166
170	167		trace("MAM: Processing non-OMEMO message from " + originalMessage.attr.get("from"));
171	168
172		-	final msg = Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
	169	+	promisedMessages.push(Promise.resolve((sortId) -> Message.fromStanza(originalMessage, client.jid, (builder, stanza) -> {
173	170		builder.sortId = sortId;
174	171		builder.debug = {
175	172		source: "mam",

...	...		@@ -205,9 +200,11 @@ class MessageSync {
205	200		}
206	201		if (result != null \|\| errorHandler == null) {
207	202		PromiseTools.all(promisedMessages).then((messages) -> {
	203	+	final sortIds = sortIdsForPage(pageStartSortA, sortB, messages.length);
	204	+	if (sortIds.length > 0) sortA = sortIds[sortIds.length - 1];
208	205		handler({
209	206		sync: this,
210		-	messages: messages,
	207	+	messages: messages.mapi((i, m) -> m(sortIds[i])),
211	208		});
212	209		});
213	210		}

borogove

Patchset borogove/sort-id-length.4 on 2026-11-10T20:29:20Z · commit 65784dd

Patchset `borogove/sort-id-length.4` on 2026-11-10T20:29:20Z · commit 65784dd