The following are the performance characteristics Scala Collections, based on the official documentation of Scala.
- Const: The operation takes only constant time.
- eConst: The operation takes effectively constant time, but this might depend on some assumptions such as the maximum length of a vector or the distribution of hash keys.
- Linear: The operation grows linearly with the collection size.
- Log: The operation grows logarithmically with the collection size.
- aConst: The operation takes the amortized constant time. Some invocations of the operation might take longer, but if many operations are performed on average only constant time per operation is taken.
- NA: Operation is not supported.
Performance characteristics of sequence types (immutable) are presented in the following table.
| Immutable CO* | Head | Tail | Apply | Update | Prepend | Append | Insert |
| List | Const | Const | Linear | Linear | Const | Linear | NA |
| Stream | Const | Const | Linear | Linear | Const | Linear | NA |
| Vector | eConst | eConst | eConst | eConst | eConst | eConst | NA |
| Stack | Const | Const | Linear | Linear | Const | Linear | Linear |
| Queue | aConst | aConst | Linear | Linear | Const | Const | NA |
| Range | Const | Const | Const | NA | NA | NA | NA |
| String | Const | Linear | Const | Linear | Linear | Linear | NA |
Table 1: Performance characteristics of sequence types (immutable) [*CO== Collection Object]
The following table shows the meaning of the operations described in Table 1 and Table 3 here:
| Head | Is used to select the first few elements of an existing sequence. |
| Tail | Is used to select all elements except the first one and returns a new sequence. |
| Apply | Is used for indexing purposes. |
| Update | It is used as the functional update for immutable sequences. For the mutable sequence, it is a side-effecting update (with update for mutable sequences). |
| Prepend | It is used to add an element to the front of an existing sequence. A new sequence is produced for immutable sequences. For the mutable sequence, the existing one is modified. |
| Append | It is used to add an element at the end of an existing sequence. A new sequence is produced for immutable sequences. For a mutable sequence, the existing one is modified. |
| Insert | It is used to insert an element at an arbitrary position in an existing sequence. This can be done however directly for mutable sequences. |
Table 2: The meaning of the operation described in table 1
Performance characteristics of sequence types (mutable) are shown in Table 3 as follows:
| Mutable CO* | Head | Tail | Apply | update | Prepend | Append | Insert |
| ArrayBuffer | Const | Linear | Const | Const | Linear | aConst | Linear |
| ListBuffer | Const | Linear | Linear | Linear | Const | Const | Linear |
| StringBuilder | Const | Linear | Const | Const | Linear | aCconst | Linear |
| MutableList | Const | Linear | Linear | Linear | Const | Const | Linear |
| Queue | Const | Linear | Linear | Linear | Const | Const | Linear |
| ArraySeq | Const | Linear | Const | Const | NA | NA | NA |
| Stack | Const | Linear | Linear | Linear | Const | Linear | Linear |
| ArrayStack | Const | Linear | Const | Const | aConst | Linear | Linear |
| Array | Const | Linear | Const | Const | NA | NA | NA |
Table 3: Performance characteristics of sequence types (mutable) [*CO== Collection Object]
For more information about mutable collections and other types of collections, you can refer to this link (http://docs.scala-lang.org/overviews/collections/performance-characteristics.html).
Performance characteristics of set and map types are shown in the following table:
| Collection types | Lookup | Add | Remove | Min |
| immutable | - | - | - | - |
| HashSet/HashMap | eConst | eConst | eConst | Linear |
| TreeSet/TreeMap | Log | Log | Log | Log |
| BitSet | Const | Linear | Linear | eConst* |
| ListMap | Linear | Linear | Linear | Linear |
| Collection types | Lookup | Add | Remove | Min |
| mutable | - | - | - | - |
| HashSet/HashMap | eConst | eConst | eConst | Linear |
| WeakHashMap | eConst | eConst | eConst | Linear |
| BitSet | Const | aConst | Const | eConst* |
| TreeSet | Log | Log | Log | Log |
Table 4: Performance characteristics of set and map types [ * applicable only if bits are densely packed]
The following table shows the meaning of each operation described in Table 4:
| Operation | Meaning |
| Lookup | Is used to test whether an element is contained in a set. Secondly, it is also used to select a value associated with a particular key. |
| Add | It is used to add a new element to a set. Secondly, it is also used to add a new key/value pair to a map. |
| Remove | It is used to remove an element from a set or a key from a map. |
| Min | It is used to select the smallest element of the set or the smallest key of a map. |
Table 5: The meaning of each operation described in Table 4
One of the basic performance metrics is the memory usage by a particular collection object. In the next section, we will provide some guidelines about how to measure these metrics based on memory usage.