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_interval get_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) insert_items(0, 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_rank	Base	R log N + N	N	1
remove_by_index_range	Base	N + M	N + M	M
	+Rank	+L*N
remove_by_value_interval remove_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 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.