# Zipping slices sucks

**URL:** <https://internals.rust-lang.org/t/zipping-slices-sucks/1544>\
**Category:** libs\
**Created:** [February 5, 2015, 3:32am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544 "2015-02-05T03:32:34Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![cgaebel](https://avatars.discourse-cdn.com/v4/letter/c/da6949/32.png) [@cgaebel](https://internals.rust-lang.org/u/cgaebel)\
**Post date:** [February 5, 2015, 3:32am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/1 "2015-02-05T03:32:34Z")

</div>

```rust
fn sum(x: &[i32], y: &[i32], z: &[i32]) -> i32 {
  fn repack<'a>(((x, y), z): ((&'a i32, &'a i32), &'a i32)) -> (&'a i32, &'a i32, &'a i32) { (x, y, z) }
  let mut s = 0;
  for (&x, &y, &z) in x.iter().zip(y.iter()).zip(z.iter()).map(repack) {
    s += x + y + z;
  }
  s
}

```

The inner loop has 3 comparisons per iteration, when the equivalent in C would have 1. I have no idea how to solve this nicely, but it’s a problem. I’d love to hear some ideas.

---

<div class="post-metadata">

**Author:** ![Aatch](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aatch/32/433_2.png) [@Aatch](https://internals.rust-lang.org/u/Aatch)\
**Post date:** [February 5, 2015, 3:39am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/2 "2015-02-05T03:39:44Z")

</div>

I’m curious as to how the equivalent C could could manage only 1 comparison per iteration, since you have to make sure you haven’t reached the end of any of the slices. Which means checking each slice individually.

---

<div class="post-metadata">

**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\
**Post date:** [February 5, 2015, 3:43am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/3 "2015-02-05T03:43:33Z")

</div>

I imagine the equivalent C would do a one-time `min` on the lengths, and then every iteration would just be comparing against the min.

I’m hopeful that there’s a fast-path to be had with trusted\_len here. Basically if the lengths are trusted take the min and apply `assume` or something.

---

<div class="post-metadata">

**Author:** ![Aatch](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aatch/32/433_2.png) [@Aatch](https://internals.rust-lang.org/u/Aatch)\
**Post date:** [February 5, 2015, 4:26am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/4 "2015-02-05T04:26:51Z")

</div>

Ok, so see what was possible without using zip, I did this:

```rust
pub fn sum(x: &[i32], y: &[i32], z: &[i32]) -> i32 {
    let n = min(x.len(), min(y.len(), z.len()));
    let mut i = 0;
    let mut s = 0;
    while i < n {
        unsafe {
            s += *x.get_unchecked(i)
                + *y.get_unchecked(i)
                + *z.get_unchecked(i);
        }
        i += 1;
    }
    s
}

fn min(a: usize, b: usize) -> usize {
    if a < b { a } else { b }
}

```

Which LLVM helpfully vectorizes and indeed only does a single comparison for each iterator. I’m not sure if the zip iterator could manage it though. I’ll do some more investigation.

---

<div class="post-metadata">

**Author:** ![DanielKeep](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/danielkeep/32/1332_2.png) [@DanielKeep](https://internals.rust-lang.org/u/DanielKeep)\
**Post date:** [February 5, 2015, 6:01am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/5 "2015-02-05T06:01:57Z")

</div>

Out of curiosity, I benchmarked the unsafe sum function and a naive version:

```rust
pub fn naive(x: &[i32], y: &[i32], z: &[i32]) -> i32 {
    x.iter().zip(y.iter()).zip(z.iter())
        .map(flatten) // ((a, b), c) -> (a, b, c)
        .fold(0, |a, (x, y, z)| a + *x + *y + *z)
}

```

And a safe version of the loop:

```rust
pub fn naive_loop(x: &[i32], y: &[i32], z: &[i32]) -> i32 {
    let n = min(x.len(), min(y.len(), z.len()));
    let mut s = 0;
    for i in 0..n {
        s += x[i] + y[i] + z[i];
    }
    s
}

```

Results were:

```nohighlight
test tests::naive ... bench: 2094 ns/iter (+/- 106)
test tests::naive_loop ... bench: 1412 ns/iter (+/- 44)
test tests::unsafe_loop ... bench: 360 ns/iter (+/- 16)

```

I can understand the unsafe one being faster… but the iterator version, which is _supposed_ to _avoid_ bounds checks, being slower than a naive loop? That’s… _really_ less than ideal.

**Edit** : [“compressed” test case on playpen](http://is.gd/Sjv4Xh) if you want to reproduce. Make sure to read comment on the test data set.

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 5, 2015, 9:35am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/6 "2015-02-05T09:35:00Z")

</div>

Remember that when we boast about Rust’s iterators and how they behave exactly as efficiently as C++ iterators, it’s about how rust managed to get the slice’s iterators to compile to the exact same code, and that even [that effort hasn’t reached the finish line just yet.](https://github.com/rust-lang/rust/pull/21886)

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 7, 2015, 12:09pm UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/7 "2015-02-07T12:09:21Z")

</div>

I’m extremely excited, [because exactly that works!](https://github.com/bluss/rust-itertools/commit/7bf94f9238f75b399123f5234d8a51a11658d9b1) (At least in the two-iterator case… three or more has improvements possible)…

Edit: Just let’s experiment with that a bit. It seems I’m worse at benchmarking than at implementing this… didn’t get everything exactly right in that commit (iter by value vs ptr) etc. Looks like triple iteration maybe is equally fast already…

---

<div class="post-metadata">

**Author:** ![cgaebel](https://avatars.discourse-cdn.com/v4/letter/c/da6949/32.png) [@cgaebel](https://internals.rust-lang.org/u/cgaebel)\
**Post date:** [February 7, 2015, 6:08pm UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/8 "2015-02-07T18:08:52Z")

</div>

It’s a shame that only works for the 2-zip case, and falls down for the k-zip case.

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 7, 2015, 7:48pm UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/9 "2015-02-07T19:48:38Z")

</div>

It doesn’t! That was just my benchmarks being inconsistent. It’s fixed in the next commit and both the 2-slice and 3-slice cases are just as fast with numerical loop + unchecked indexing as using ZipTrusted.

---

<div class="post-metadata">

**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\
**Post date:** [February 7, 2015, 7:49pm UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/10 "2015-02-07T19:49:23Z")

</div>

Niiiiice

TrustedLen ftw

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 7, 2015, 8:00pm UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/11 "2015-02-07T20:00:24Z")

</div>

llvm::assume is magic.

---

<div class="post-metadata">

**Author:** ![DanielKeep](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/danielkeep/32/1332_2.png) [@DanielKeep](https://internals.rust-lang.org/u/DanielKeep)\
**Post date:** [February 8, 2015, 8:38am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/12 "2015-02-08T08:38:24Z")

</div>

The solution to all optimisation problems:

```rust
let magic: f64 = get_magic();
llvm::assume(magic == magic);

```

😛

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 25, 2019, 8:23am UTC](https://internals.rust-lang.org/t/zipping-slices-sucks/1544/13 "2019-03-25T08:23:51Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.