ID:2364107
 
(See the best response by MrStonedOne.)
What are the performance characteristics of a list?

The question I am really asking is how are lists implemented under the hood?

Linked list? Hash table? Vector? Composite?

Knowing the complexity costs of various things would help in addressing performance and optimization issues.
Best response
Lists are vectors with an attached hash table or tree for associations (list["key"] = "value")

They expand a bit more cautiously then std::vector's, using a more linear curve rather then an exponential one.
Hands down the best question I've seen on this board in at least two years.
User lists are vectors (or rather, just arrays; they don't use STL). Lookup of a list item by index is O(1). A Find() call is O(N) in the worst case and is done starting from the end of the array.

When a list is first created, it's pulled from a pool of already-allocated arrays if feasible to avoid as much churn as possible. When it grows in length, it grows to the new size plus about 25%. (For best performance when adding a bunch of items, if you know the intended size you should set the length that high first.) When it shrinks, it doesn't get rid of the slack space until the number of items is under 25% of its allocated space.

The attached structure for handling associative lists is a red-black binary tree. Red-black trees are used in many places internally, although not for the string tree which is a simpler form of binary tree. Lookup is of course O(log N), which makes associative lists often better to work with than Find() when you have to tell at a glance if an item is present or not.

There are however other lists that are implemented as linked lists internally. The obj and mob contents of another atom are two linked lists: one for objs, one for mobs. Images use linked lists too. While you have some ability to reorder an atom's contents list, you can't ever put mobs in front of objs in the list because the objs always come first, as a direct result of the linked list format.

Login to reply.