Wednesday, September 6, 2017

Data Locality and STL vs. Swift

David Owens II (tweet):

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.

Joe Groff:

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. 🙄

Joe Groff:

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

Comments RSS · Twitter

Leave a Comment