List performance
The following 𝓞 run time performance analysis is worst-case.
| Operation | Return Type | Unordered (1) | Ordered (2) | Ordered (3) |
|---|---|---|---|---|
| Set Type Ops | ||||
set_type to unordered | 1 | 1 | 1 | |
set_type to ordered | N log N | 1 | 1 | |
| Read Ops | ||||
size | 1 | 1 | 1 | |
get_by_index | Base | N | N | 1 |
get_by_rank | Base | 1 | R log N + N | N |
get_by_index_range | Base | N + M | N + M | M |
| +Rank | +L*N | |||
get_by_value_intervalget_all_by_value | Base | N + M | Log N + N | Log N + M |
get_by_rank_range | Base | R log N + N | N + M | M |
get_by_value_rel_rank_range | Base | R log N + N | N + M + log N | M + log N |
get_all_by_value_list | Base | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| Modify Ops | ||||
set(0, v)append(v)insert(0, v) | 1 | log N + N | log N | |
insert(i > 0, v)set(i > 0, v) | N | - | - | |
| ADD_UNIQUE set/append/insert | N | log N + N | log N | |
append_items(m) | M | (M + N)log M + N | (M + N)log M + N | |
| ADD_UNIQUE append_items/insert_items | N* x M | (M + N)log M + N | (M + N)log M + M | |
increment | N | - | - | |
sort | N log N | 1 | 1 | |
| UNIQUE sort | N log N | N | N | |
clear | 1 | 1 | 1 | |
remove_by_index | Base | N | N | 1 |
remove_by_index_range | Base | N + M | N + M | M |
| +Rank | +L*N | |||
remove_by_value_intervalremove_all_by_value | Base | N + M | log N + N | log N + M |
remove_by_rank_range | Base | R log N + N | N + M | M |
remove_by_value_rel_rank_range | Base | R log N + N | N + M + log N | M + log N |
remove_all_by_value_list | Base | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| Mode Modifiers | ||||
| Data On SSD | +D + W | |||
| Data-in-memory with persistence | +W |
Legend
1: Unordered list2: Ordered list, namespace stores its data on SSD3: Ordered list, namespace stores its data in memoryD: Cost of load from diskW: Cost of write to diskN: Element count of listM: Element count of parameter, range or intervalR: For rank r, R = min(r, N - r - 1)L: For index i, L = min(i, N - i - 1)C: Cost of memcpy on packed listn: The total byte size of list elements.
Every modify op has a +C for copy on write for allowing rollback on failure.
Notes
- List performance is usually dictated by the element access.
- Lists in in-memory namespaces (3) have an offset index, which gives an element access worst-case of 𝓞(1).
- For namespaces with data on SSD, an additional 𝓞(n) memcpy performance cost is incurred. This is negligible compared to element walk 𝓞(N).
- The replication cost is 𝓞(n), because full records are replicated and persisted on replicas.
- Reminder: worst-case, average-case and best-case performance are different categories. You should compare like to like.