Data Locality and STL vs. Swift
What if I told you that even in an array of 10,000 items and a linked list of 10,000 items, insertion into the middle is still going to be faster in the array? Would you believe me?
[…]
The problem is that the
->operator (de-referrencing) is a relatively expensive operation.
He also found that for the simple case of an array of integers, Swift’s Array was about half the speed of std::vector. This is pretty good, and it looks like there’s room for it to be improved.
The optimizer is also not great at telling that insert/append-type operations maintain uniqueness so it can leave out checks.
If you’re seeing protocol overhead it’s probably also failing to specialize something.
Update (2017-09-06): David Owens II:
Actually, they are even perf now. I was using Int instead of Int32, so the size was 64bits instead of 32bits like the C++ version. 🙄
Another linked list variant is a contiguous array of (value, next index) pairs, so you get locality and can efficiently insert by appending
and you can easily sort in-place into an ordered vector as a pre-pass to benefit from sequential memory access
