Looking at different collection constructors the question comes to mind. Why does ArrayList()
construct an empty list with an initial capacity of ten and ArrayDeque()
constructs an empty array deque with an initial capacity sufficient to hold 16 elements.
4
Short answer
Because ArrayDeque capacity must be a power of two, and 16 is the smallest power of two that is at least 10.
ArrayDeque needs to use a lot of % operations everywhere to wrap around a linear array that pretends to be circular.
a % b can be expressed as a & (b - 1) if b is a power of two. The bitwise AND is massively faster so the capacity of ArrayDeque is restricted to be power of two. All % operations are performed with bitmasking instead of actual % in the implementation.
This is also why the newer HashMap doesn’t use prime number table sizes but power of two, again because the % operation needs to be performed so often and the bitwise and is that much faster.
So if the baseline is 10, then structures that have power of two limitations should use 16 becase it’s the smallest power of two that is at least 10.
Do not exclude the possibility that there is no specific reason.
It could be that these two collections have been written by different teams. Both chose a small number as default capacity, but the first team thought decimally and choose 10, while the second team thought binary and choose 16.
0
@Esailija’s answer is good for this specific case.
More generally though, it is a trade-off that depends on many factors. I shall give a few examples:
- How is the data structure typically used? Data structures that are used as data buffers would typically prefer a much higher capacity than data structures used for small tuples, for example.
- What default size of data fits in a cache line on your target CPU platform? It can make a big difference to performance if the default fits in cache line. The choice of 10 is as a default in Java may well be because an array of 10 32-bit words plus the array/object overhead fits in a 64 byte cache line.
- How much do you value space vs runtime efficiency? If you want better runtime performance, it is generally better to pre-allocate more space in order to avoid extra re-allocations later.
As a result of these trade-offs, it is quite understandable that different collection implementations may have a different optimal default capacity.