Skip to main content
Loading

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
size111
get_by_indexBaseNN1
get_by_rankBase1R log N + NN
get_by_index_rangeBaseN + MN + MM
+Rank+L*N
get_by_value_interval
get_all_by_value
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)
append(v)
insert(0, v)
1log N + Nlog N
insert(i > 0, v)
set(i > 0, v)
N--
ADD_UNIQUE set/append/insertNlog N + Nlog N
append_items(m)
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
incrementN--
sortN log N11
UNIQUE sortN log NNN
clear111
remove_by_indexBaseNN1
remove_by_rankBaseR log N + NN1
remove_by_index_rangeBaseN + MN + MM
+Rank+L*N
remove_by_value_interval
remove_all_by_value
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

Legendโ€‹

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

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.