Concatenating arrays

help
1

I would like to concatenate arrays. I have seen this was discussed in Can “const fn” concatenate byte slices? before. What's the current state? I don't necessarily require to do it in a const fn (though it would be nice), but I definitely want to avoid allocation.

Ideally, the solution would not require me to add any dependency.

One way would be to use copy_from_slice (as also done in the other thread) or clone_from_slice (for types which are ?Copy). But what's the idiomatic way to do it?

fn main() {
    let a: [u8; 3] = [1, 2, 3];
    let b: [u8; 4] = [4, 5, 6, 7];
    // How to do the following without allocating?
    let c: [u8; 7] = [&a[..], &b].concat().try_into().unwrap();
    assert_eq!(c, [1, 2, 3, 4, 5, 6, 7]);
    // I guess I could do this:
    let mut d: [u8; 7] = Default::default();
    d[0..3].clone_from_slice(&a);
    d[3..7].clone_from_slice(&b);
    assert_eq!(d, [1, 2, 3, 4, 5, 6, 7]);
    // But is there any better way?
}

(Playground)

2

You could make an iterator via chain and .collect into an ArrayVec in arrayvec - Rust

I don't know what you're measure of "better" is, but at least it's another alternative. Once you have a completely full array-vec, it can be turned back into the array via the into_inner method.

3

Ideally, I'd like to not add any dependencies. However, I followed your chain proposal and came up with these two variants, of which one (concat_arrays) requires the very unstable generic_const_exprs feature, while the other (concat_arrays_stable) won't do the length check at compile-time:

#![feature(generic_const_exprs)]

fn concat_arrays<T, const A: usize, const B: usize>(
    a: [T; A], b: [T; B]
) -> [T; A+B]
where
    T: Default,
{
    let mut ary: [T; A+B] = std::array::from_fn(|_| Default::default());
    for (idx, val) in a.into_iter().chain(b.into_iter()).enumerate() {
        ary[idx] = val;
    }
    ary
}

fn concat_arrays_stable<T, const A: usize, const B: usize, const C: usize>(
    a: [T; A], b: [T; B]
) -> [T; C]
where
    T: Default,
{
    assert_eq!(A+B, C);
    let mut ary: [T; C] = std::array::from_fn(|_| Default::default());
    for (idx, val) in a.into_iter().chain(b.into_iter()).enumerate() {
        ary[idx] = val;
    }
    ary
}


fn main() {
    let a: [u8; 3] = [1, 2, 3];
    let b: [u8; 4] = [4, 5, 6, 7];
    let c: [u8; 7] = concat_arrays(a, b);
    assert_eq!(c, [1, 2, 3, 4, 5, 6, 7]);
    let d: [u8; 7] = concat_arrays_stable(a, b);
    assert_eq!(d, [1, 2, 3, 4, 5, 6, 7]);
    // Compiler will notice this is wrong:
    //let _: [u8; 8] = concat_arrays(a, b);
    // But compiler won't notice this is wrong:
    //let _: [u8; 8] = concat_arrays_stable(a, b);
}

(Playground)

Note I was able to get rid of the copying and/or cloning, and I don't need unsafe (at the cost of adding a Default bound).

1 Like
4

Another idea: You could first create the iterator, then call .next().unwrap() inside of the closure given to from_fn. That way, the Default is avoided.

2 Likes
5

Yeah, that works:

fn concat_arrays<T, const A: usize, const B: usize, const C: usize>(a: [T; A], b: [T; B]) -> [T; C] {
    assert_eq!(A+B, C);
    let mut iter = a.into_iter().chain(b);
    std::array::from_fn(|_| iter.next().unwrap())
}

fn main() {
    let a: [u8; 3] = [1, 2, 3];
    let b: [u8; 4] = [4, 5, 6, 7];
    let c: [u8; 7] = concat_arrays(a, b);
    assert_eq!(c, [1, 2, 3, 4, 5, 6, 7]);
    // Compiler won't notice this is wrong, but we get a panic:
    //let _: [u8; 8] = concat_arrays(a, b);
}

(Playground)

Very nice! :smiley: Update: Apparently, it's not very efficient, see post below.

Is there any way to make let _: [u8; 8] = concat_arrays(a, b); throw a compile-time error without using the highly experimental generic_const_exprs feature?

1 Like
6

I won't actually need it, but I found a crude way with stable Rust using macros:

mod private {
    fn concat_inner<T, const A: usize, const B: usize, const C: usize>((a, b): ([T; A], [T; B])) -> [T; C] {
        let mut iter = a.into_iter().chain(b);
        std::array::from_fn(|_| iter.next().unwrap())
    }
    pub trait Concat {
        type Joined;
        fn concat(self) -> Self::Joined;
    }
    macro_rules! impl_concat {
        ($a:expr, $b:expr) => {
            impl<T> Concat for ([T; $a], [T; $b]) {
                type Joined = [T; $a + $b];
                fn concat(self) -> Self::Joined {
                    concat_inner(self)
                }
            }
        };
    }
    macro_rules! impl_concat_helper {
        ($a:expr) => {
            impl_concat!($a, 1);
            impl_concat!($a, 2);
            impl_concat!($a, 3);
            impl_concat!($a, 4);
            impl_concat!($a, 5);
            impl_concat!($a, 6);
            impl_concat!($a, 7);
            impl_concat!($a, 8);
            impl_concat!($a, 9);
            impl_concat!($a, 10);
        }
    }
    impl_concat_helper!(1);
    impl_concat_helper!(2);
    impl_concat_helper!(3);
    impl_concat_helper!(4);
    impl_concat_helper!(5);
    impl_concat_helper!(6);
    impl_concat_helper!(7);
    impl_concat_helper!(8);
    impl_concat_helper!(9);
    impl_concat_helper!(10);
}
use private::*;

pub fn concat_arrays<A, B>(a: A, b: B) -> <(A, B) as Concat>::Joined
where
    (A, B): Concat,
{
    (a, b).concat()
}

fn main() {
    let a: [u8; 3] = [1, 2, 3];
    let b: [u8; 4] = [4, 5, 6, 7];
    let c: [u8; 7] = concat_arrays(a, b);
    assert_eq!(c, [1, 2, 3, 4, 5, 6, 7]);
    // Now we get a proper compile-time error:
    let _: [u8; 8] = concat_arrays(a, b);
}

(Playground)

The compiler error is really nice now:

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:60:22
   |
60 |     let _: [u8; 8] = concat_arrays(a, b);
   |            -------   ^^^^^^^^^^^^^^^^^^^ expected an array with a fixed size of 8 elements, found one with 7 elements
   |            |
   |            expected due to this

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous error
7

With panicking consts its possible to get monomorphization-time errors.

Rust Playground

1 Like
8

I found this macro and improved it:

/// Usage: `const_assert!(Var1: Ty, Var2: Ty, ... => expression)`
macro_rules! const_assert {
    ($($list:ident : $ty:ty),* => $expr:expr) => {{
        struct Assert<$(const $list: $ty,)*>;
        impl<$(const $list: $ty,)*> Assert<$($list,)*> {
            const OK: () = assert!($expr);
        }
        Assert::<$($list,)*>::OK
    }};
    ($expr:expr) => {{
        const OK: () = assert!($expr);
    }};
}

fn concat_arrays<T, const A: usize, const B: usize, const C: usize>(
    a: [T; A],
    b: [T; B],
) -> [T; C] {
    const_assert!(A: usize, B: usize, C: usize => A + B == C);
    let mut iter = a.into_iter().chain(b);
    std::array::from_fn(|_| iter.next().unwrap())
}

(Playground)

9

There's no way to write a A + B == C bound on const generics in stable, so this is a fundamental problem if you want to make it a fn. The best you can do is the associated const trick to make it a PME.

If you don't need it to be a fn, though, you could use a macro_rules macro that relies on transmute to enforce the length check, which will even work inside a stable const fn: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=bdd5e63a1a9e5edd638c0800a8c4a7c3

(Please don't, though. That was a fun demo to write, but probably isn't a good idea to actually use.)

2 Likes
10

I tried to look at the compiler output of the variant using copy_from_slice and comparing it with the variant using std::array::from_fn for a non-generic implementation.

The following example compiles on the Rust Playground:

pub fn concat_copy(a: [u8; 8], b: [u8; 10]) -> [u8; 18] {
    let mut ary = [0u8; 18];
    ary[..8].copy_from_slice(&a);
    ary[8..].copy_from_slice(&b);
    ary
}

pub fn concat_iter(a: [u8; 8], b: [u8; 10]) -> [u8; 18] {
    let mut iter = a.into_iter().chain(b);
    std::array::from_fn(|_| iter.next().unwrap())
}

(Playground)

However, on Godbolt, I get errors:

error[E0271]: type mismatch resolving `<[u8; 10] as IntoIterator>::Item == &u8`
 --> <source>:9:40
  |
9 |     let mut iter = a.into_iter().chain(b);
  |                                  ----- ^ expected `&u8`, found `u8`
  |                                  |
  |                                  required by a bound introduced by this call
  |
note: required by a bound in `std::iter::Iterator::chain`
 --> /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/iter/traits/iterator.rs:502:25
  |
  = note: required by this bound in `std::iter::Iterator::chain`

error[E0599]: the method `next` exists for struct `std::iter::Chain<std::slice::Iter<'_, u8>, std::array::IntoIter<u8, 10>>`, but its trait bounds were not satisfied
  --> <source>:10:34
   |
10 |     std::array::from_fn(|_| iter.next().unwrap())
   |                                  ^^^^ method cannot be called on `std::iter::Chain<std::slice::Iter<'_, u8>, std::array::IntoIter<u8, 10>>` due to unsatisfied trait bounds
  --> /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/array/iter.rs:14:1
   |
   = note: doesn't satisfy `<_ as Iterator>::Item = &u8`
  --> /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/iter/adapters/chain.rs:22:1
   |
   = note: doesn't satisfy `_: Iterator`
   |
   = note: the following trait bounds were not satisfied:
           `<std::array::IntoIter<u8, 10> as Iterator>::Item = &u8`
           which is required by `std::iter::Chain<std::slice::Iter<'_, u8>, std::array::IntoIter<u8, 10>>: Iterator`

error: aborting due to 2 previous errors

Some errors have detailed explanations: E0271, E0599.
For more information about an error, try `rustc --explain E0271`.
Compiler returned: 1

(Godbolt)

I don't understand what's going on. On my local machine with rustc 1.69.0-nightly (2d14db321 2023-02-15), the code also compiles.

What did I do wrong?

P.S.: I just saw Godbolt uses rustc 1.67.0 (I mistook the 67 for 69), so maybe that's the problem.

P.P.S.: But Playground only uses 1.67.1, so not much of a difference. :thinking:

11

You have to use 2021 edition, i.e. pass the --edition=2021 flag when compiling on Godbolt. In previous editions, a.into_iter() resolved to <[T]>::into_iter, not to <[T; N]>::into_iter, to avoid breakage when the latter was introduced.

4 Likes
12

After checking the compiler output (Godbolt) with --edition=2021 -C opt-level=3, I don't like the iterator based approach anymore:

.LCPI3_0:
        .quad   1
        .quad   0
example::concat_iter:
        push    r14
        push    rbx
        sub     rsp, 104
        lea     r9, [rsp + 88]
        movzx   eax, word ptr [rdx + 8]
        mov     word ptr [rsp + 96], ax
        mov     rax, qword ptr [rdx]
        mov     qword ptr [rsp + 88], rax
        lea     r10, [rsp + 40]
        mov     qword ptr [rsp + 48], 8
        lea     r8, [rsp + 56]
        mov     qword ptr [rsp + 56], rsi
        mov     qword ptr [rsp + 80], 10
        movaps  xmm0, xmmword ptr [rip + .LCPI3_0]
        movaps  xmmword ptr [rsp + 32], xmm0
        movaps  xmmword ptr [rsp + 64], xmm0
        mov     edx, 1
        xor     r11d, r11d
        xor     ebx, ebx
        jmp     .LBB3_1
.LBB3_8:
        lea     rax, [rsi + 1]
        mov     qword ptr [rcx], rax
        add     rsi, r8
.LBB3_9:
        movzx   eax, byte ptr [rsi]
        mov     byte ptr [rsp + rbx + 14], al
        inc     rbx
        cmp     rbx, 18
        je      .LBB3_10
.LBB3_1:
        mov     rcx, r10
        test    rdx, rdx
        cmove   rcx, rdx
        je      .LBB3_4
        mov     rsi, qword ptr [rcx]
        cmp     rsi, 8
        jne     .LBB3_8
        mov     qword ptr [rsp + 32], 0
.LBB3_4:
        cmp     r11, 10
        je      .LBB3_6
        mov     rsi, r11
        inc     r11
        mov     qword ptr [rsp + 72], r11
        add     rsi, r9
        xor     edx, edx
        jmp     .LBB3_9
.LBB3_10:
        mov     eax, dword ptr [rsp + 14]
        mov     ecx, dword ptr [rsp + 17]
        mov     dword ptr [rdi + 3], ecx
        mov     dword ptr [rdi], eax
        mov     rax, qword ptr [rsp + 21]
        movzx   ecx, word ptr [rsp + 29]
        movzx   edx, byte ptr [rsp + 31]
        mov     qword ptr [rdi + 7], rax
        mov     byte ptr [rdi + 17], dl
        mov     word ptr [rdi + 15], cx
        mov     rax, rdi
        add     rsp, 104
        pop     rbx
        pop     r14
        ret
.LBB3_6:
        lea     rdi, [rip + .L__unnamed_1]
        lea     rdx, [rip + .L__unnamed_2]
        mov     esi, 43
        call    qword ptr [rip + core::panicking::panic@GOTPCREL]
        ud2
        mov     r14, rax
        lea     rsi, [rsp + 14]
        mov     rdi, rbx
        call    core::ptr::drop_in_place<core::array::Guard<u8,18_usize>>
        lea     rdi, [rsp + 32]
        call    core::ptr::drop_in_place<core::iter::adapters::chain::Chain<core::array::iter::IntoIter<u8,8_usize>,core::array::iter::IntoIter<u8,10_usize>>>
        mov     rdi, r14
        call    _Unwind_Resume@PLT
        ud2
        call    qword ptr [rip + core::panicking::panic_no_unwind@GOTPCREL]
        ud2

Compare with the short output of the variant using copy_from_slice:

example::concat_copy:
        mov     rax, rdi
        mov     qword ptr [rdi], rsi
        mov     rcx, qword ptr [rdx]
        mov     qword ptr [rdi + 8], rcx
        movzx   ecx, word ptr [rdx + 8]
        mov     word ptr [rdi + 16], cx
        ret

As I don't need to be generic in my case, I think I'll just stick to copy_from_slice and write a helper function for my particular use case.

13

Two things:

  1. LLVM is bad at dealing with array::IntoIter because it SRoAs poorly, and chain is notoriously bad for .next().
  2. I recently rewrote array from_fn/map and friends (https://github.com/rust-lang/rust/pull/107634) so try nightly for better results -- no new feature flags, just a better implementation in core

So here's another approach that now works https://godbolt.org/z/YGcE3G5eM, if you'd prefer:

pub fn concat_index(a: [u8; 8], b: [u8; 10]) -> [u8; 18] {
    std::array::from_fn(|i| {
        if let Some(i) = i.checked_sub(a.len()) {
            b[i]
        } else {
            a[i]
        }
    })
}

There's drain_array_with in core::array::drain - Rust internally as a library implementation detail that might make the iterator version work again, but it's got an awkward API so I don't know how best to expose it, and thus haven't proposed it to libs-api.

1 Like
14

What's SRoA?

Edit: Found the term.

The next pass to run, SROA (scalar replacement of aggregates), is one of our heavy hitters. The name ends up being a bit misleading since SROA is only one of its functions. This pass examines each alloca instruction (function-scoped memory allocation) and attempts to promote it into SSA registers. A single alloca will turn into multiple registers when it is statically assigned multiple times and also when the alloca is a class or struct that can be split into its components (this splitting is the “scalar replacement” referred to in the name of the pass). A simple version of SROA would give up on stack variables whose addresses are taken, but LLVM’s version interacts with alias analysis and ends up being fairly smart (though the smarts are not needed in our example).

And also here.

15

TL/DR is that SRoA is the pass that splits up objects into their individual parts so that the struct itself disappears and LLVM can work on the individual fields instead.

That's a critical step because it turns the iterator into the same as if it was just written as separate locals -- meaning it knows it doesn't need to write progress back into the struct and that it looks the same as a normal C loop would.

And I think this is the big problem with array::IntoIter -- when there are pointers into the iterator itself (because the array is there) it has a much harder time proving that it's correct to split it up.

So looking at jbe's example in LLVM-IR you'll see

%iter = alloca %"core::iter::adapters::chain::Chain<core::array::iter::IntoIter<u8, 8>, core::array::iter::IntoIter<u8, 10>>", align 16

where the whole iterator is still a stack variable, which is likely a huge part of why it doesn't optimize.

16

Seems to be one more reason to avoid self-referential types unless strictly necessary, by the way?

17

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.