66 lines
2 KiB
Markdown
66 lines
2 KiB
Markdown
# simplex-chat-0003: introduceToRemaining `notElem` list scan on every member
|
||
|
||
**Target:** simplex-chat/simplex-chat
|
||
**File:** `src/Simplex/Chat/Library/Internal.hs`
|
||
**Lines:** 1073
|
||
**Severity:** HIGH
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
|
||
## Description
|
||
|
||
`introduceToRemaining` fetches two lists from the database:
|
||
- `members :: [GroupMember]` — all group members (M items)
|
||
- `introducedGMIds :: [GroupMemberId]` — already-introduced members (K items)
|
||
|
||
It then calls:
|
||
|
||
```haskell
|
||
let recipients = filter (introduceMemP introducedGMIds) members
|
||
where
|
||
introduceMemP introducedGMIds mem =
|
||
memberCurrent mem
|
||
&& groupMemberId' mem `notElem` introducedGMIds -- O(K) per member
|
||
&& groupMemberId' mem /= groupMemberId' m
|
||
```
|
||
|
||
For each of the M members, `notElem` walks the full `introducedGMIds` list:
|
||
**O(M × K)** total.
|
||
|
||
`getIntroducedGroupMemberIds` is declared as returning `IO [GroupMemberId]`
|
||
(Store/Groups.hs:1740) — a plain list.
|
||
|
||
This function is called every time a new member joins a group and introductions
|
||
to remaining un-introduced members must be sent — a hot path in group join
|
||
flows that scales quadratically with group membership.
|
||
|
||
## Fix
|
||
|
||
Convert `introducedGMIds` to a `S.Set GroupMemberId` before the filter:
|
||
|
||
```haskell
|
||
let introducedSet = S.fromList introducedGMIds
|
||
recipients = filter (introduceMemP introducedSet) members
|
||
where
|
||
introduceMemP introducedSet mem =
|
||
memberCurrent mem
|
||
&& groupMemberId' mem `S.notMember` introducedSet
|
||
&& groupMemberId' mem /= groupMemberId' m
|
||
```
|
||
|
||
`S` is already imported as `qualified Data.Set as S` in this module (line 46).
|
||
|
||
## Complexity
|
||
|
||
| Before | After |
|
||
|--------|-------|
|
||
| O(M × K) per join event | O(M + K) per join event |
|
||
|
||
At M=1000, K=900 (near-full group): ~900× reduction in comparisons.
|
||
|
||
## Patch
|
||
|
||
`defects/simplex-chat/patch/simplex-chat-0003.patch`
|
||
|
||
## Unit Test
|
||
|
||
`defects/simplex-chat/unit/SimplexChatTest.java` (shared with -0001/-0002)
|