CODEWITHSUNDEEP
arraysvectorrustmonadsslice
Иван
Иван

Reputation: 53

Is it more efficient to slice an array or use Iterator::skip?

I want to call a function for each element in a slice [0+k .. n], where k is an offset and n is the number of elements in the vector. Importantly, I want the index of the element from the original slice.

I have found two ways of doing this:

  1. Use enumerate and skip the beginning items

    vec.iter().enumerate().skip(k).map(|(i, v)| (f(v), i)).min()

  2. Take a subslice and add the offset to the index from `enumerate

    vec[k..].iter().enumerate().map(|(i, v)| (f(v), i + k)).min()

In both cases, vec is a vector of strings, and f returns a specific character in the string (v.chars().nth(offset)). Which of these solutions is most efficient?

Upvotes: 5

Views: 2023

Answers (1)

Shepmaster
Shepmaster

Reputation: 431599

Let's use this code as an example. It's similar to your example, but a bit simpler:

fn main() {
    let items = ["a", "bb", "ccc", "dddd", "eeeee"];
    let k = 3;

    let one = items.iter().enumerate().skip(k).map(|(i, v)| (v.len(), i));
    let two = items[k..].iter().enumerate().map(|(i, v)| (v.len(), i + k));

    // Sanity check that the results are the same
    let items1: Vec<_> = one.collect();
    let items2: Vec<_> = two.collect();

    println!("{}", items1 == items2);
}

Which will be more performant is a tricky topic. Rust and LLVM have good optimizations that can make code quite fast.

Based purely on my gut feeling, I would probably use the first one if I knew that I was going to skip just "a few" of the items, and the second one if I didn't know how many or if it were a lot.

In the first case, you conceptually have to iterate through all of the items that you want to skip over. It is possible that the optimizer could reduce this down, but it's complicated by the interaction with enumerate and map, so I wouldn't count on it without inspecting assembly.

The second one (items[k..]) uses subslicing, which will be an O(1) operation as it's simply going to index into a chunk of memory. Then you do addition which will also be simple.

However, the only true test is to do some profiling. We will create a large input array and start part way:

fn main() {
    let items = ["a", "bb", "ccc", "dddd", "eeeee"];
    let items: Vec<_> = items.iter().cycle().take(10_000_000).collect();

    let k = 371_223;

    // let one = items.iter().enumerate().skip(k).map(|(i, v)| (v.len(), i));
    let two = items[k..].iter().enumerate().map(|(i, v)| (v.len(), i + k));

    // let items1: Vec<_> = one.collect();
    let items2: Vec<_> = two.collect();

    // println!("{}", items1.len());
    println!("{}", items2.len());
}

Running that code, compiled with optimizations, has the following times averaged over 10 runs:

  1. 153.6ms
  2. 160.1ms

So, contrary to what my gut feeling said, the first version is faster. It's entirely possible that my benchmarking is incorrect, but that's why you should do benchmarking on your real code.

Also, note that this is really fast either way. That's about 15 or 16 nanoseconds per item. What's one nanosecond among friends?

Upvotes: 6

Related Questions