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
-
I didn't new thet had a capacity limit. I just simply add new elements with add(). It always works.– Tulains CórdovaAug 1, 2013 at 20:23
-
1I think he's talking about the initial array size of the array inside the ArrayList implementation. As its name implies, ArrayList is just a plain-old array under the covers, and it creates larger arrays automatically when you try to add more elements than its current array size contains.– dsw88Aug 1, 2013 at 20:26
-
1I think StringBuilder is another one that has a default capacity, was it 10 or 16?– IngoDec 17, 2013 at 17:28
-
@Ingo Interesting. I wasn't even aware things outside of collections messed with capacity but I suppose it makes sense. At the time there was no tag for capacity so I that didn't spark much interest in other uses.– Old Badman GreyDec 20, 2013 at 7:23
Add a comment
|
3 Answers
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.
@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.
