Skip to content

[state] Add EventHash → index map for O(1) message lookup #122

@intendednull

Description

@intendednull

Parent: #108

Problem

crates/state/src/materialize.rs does a linear scan over state.messages every time a message-targeting event is applied:

  • Line 369 (EditMessage): state.messages.iter_mut().find(|m| m.id == *message_id)
  • Line 376 (DeleteMessage): same pattern
  • Line 384 (Reaction): same pattern

For a channel with N messages, every edit/delete/reaction is O(N). At 10k messages and a reaction flood, this dominates replay time.

Fix

Add a BTreeMap<EventHash, usize> field on ServerState mapping message hash → index into state.messages. Update it on every Message insertion and use it for lookup in the three sites above.

pub struct ServerState {
    pub messages: Vec<ChatMessage>,
    pub message_index: BTreeMap<EventHash, usize>,
    // ...
}

Watch out for:

  • Ensuring the index is rebuilt correctly on materialize() replay.
  • DeleteMessage currently keeps the message in messages (sets deleted = true), so indexes stay stable. Good.
  • If any future code removes entries from messages, the index needs maintenance.

Test

#[test]
fn message_lookup_is_constant_time() {
    // Build a state with 100k messages, then time a reaction apply.
    // Prior: ~100ms per reaction. After: should be <100µs.
}

Also add a determinism test: materialize a DAG twice and assert the message_index maps match.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions