Skip to main content

List Performance

The following 𝓞 run time performance analysis is worst-case.

OperationReturn TypeUnordered (1)Ordered (2)Ordered (3)
Set Type Ops
set_type to unordered111
set_type to orderedN log N11
Read Ops
get_by_rankBase1R log N + NN
get_by_index_rangeBaseN + MN + MM
BaseN + MLog N + NLog N + M
get_by_rank_rangeBaseR log N + NN + MM
get_by_value_rel_rank_rangeBaseR log N + NN + M + log NM + log N
get_all_by_value_listBase(M + N)log M + N(M + N)log M + N(M + N)log M
Modify Ops
set(0, v)
insert(0, v)
1log N + Nlog N
insert(i > 0, v)
set(i > 0, v)
ADD_UNIQUE set/append/insertNlog N + Nlog N
insert_items(0, m)
M(M + N)log M + N(M + N)log M + N
ADD_UNIQUE append_items/insert_itemsN* x M(M + N)log M + N(M + N)log M + M
sortN log N11
UNIQUE sortN log NNN
remove_by_rankBaseR log N + NN1
remove_by_index_rangeBaseN + MN + MM
BaseN + Mlog N + Nlog N + M
remove_by_rank_rangeBaseR log N + NN + MM
remove_by_value_rel_rank_rangeBaseR log N + NN + M + log NM + log N
remove_all_by_value_listBase(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


  • 1: Unordered list
  • 2: Ordered list, namespace stores its data on SSD
  • 3: Ordered list, namespace stores its data in memory
  • D: Cost of load from disk
  • W: Cost of write to disk
  • N: Element count of list
  • M: Element count of parameter, range or interval
  • R: 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 list
  • n: The total byte size of list elements.

Every modify op has a +C for copy on write for allowing rollback on failure.


  • 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.