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.