queryMerged picks the newest candidate across live streams with a linear scan:
// Stream counts are small (one per author/kind/tag value), so a
// linear pick beats heap overhead.
var best: ?usize = null;
for (streams.items, 0..) |s, i| {
if (!s.live) continue;
if (best == null or revStreamNewer(s, streams.items[best.?])) best = i;
}The premise was true when it was written. A filter naming a full contact list is
one stream per author, and the scan runs once per event returned, so the cost is
streams x events.
Measured through a client's feed query (one kind, 300 events returned,
ReleaseFast, best of three):
| authors |
query |
| 128 |
257us |
| 256 |
465us |
| 512 |
893us |
| 1024 |
1,750us |
| 2048 |
3,480us |
Linear in the number of streams, which is exactly what the scan predicts. A
binary heap would make each pick logarithmic: at 2048 streams that is roughly 11
comparisons per event instead of 2048.
Not urgent, and worth saying why. At the author counts anything currently sends,
the scan is the cheaper option once heap overhead is counted, and 257us at 128
authors is not a problem. This becomes the top cost only if a caller starts
naming a whole contact list, which today they cannot: filters that wide are
refused by relays anyway (strfry caps a filter's field items at 65535 bytes,
which is 2047 pubkeys).
So this is a note with numbers rather than a fix waiting to happen. If someone
raises an author cap and the merge shows up in a profile, the crossover point is
the thing to measure first, because the answer at 128 streams may well still be
the scan.
queryMergedpicks the newest candidate across live streams with a linear scan:The premise was true when it was written. A filter naming a full contact list is
one stream per author, and the scan runs once per event returned, so the cost is
streams x events.Measured through a client's feed query (one kind, 300 events returned,
ReleaseFast, best of three):
Linear in the number of streams, which is exactly what the scan predicts. A
binary heap would make each pick logarithmic: at 2048 streams that is roughly 11
comparisons per event instead of 2048.
Not urgent, and worth saying why. At the author counts anything currently sends,
the scan is the cheaper option once heap overhead is counted, and 257us at 128
authors is not a problem. This becomes the top cost only if a caller starts
naming a whole contact list, which today they cannot: filters that wide are
refused by relays anyway (strfry caps a filter's field items at 65535 bytes,
which is 2047 pubkeys).
So this is a note with numbers rather than a fix waiting to happen. If someone
raises an author cap and the merge shows up in a profile, the crossover point is
the thing to measure first, because the answer at 128 streams may well still be
the scan.