rust-lang / rust-lang/rust

rustc does not recognize Vec<A>::collect from Vec<B> for complex types

Open
#135,962 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-optimization
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

Imagine I have two structs which are trivially transmutable: Xc -> X and Yc -> Y.

struct X {
    a: u32,
    b: u64,
}

struct Xc {
    a: u32,
    b: u64,
}

impl From<Xc> for X {
    fn from(value: Xc) -> Self {
        Self {
            a: value.a,
            b: value.b,
        }
    }
}

struct Y {
    z: [u8; 32],
}

struct Yc {
    z: [u8; 32],
}

impl From<Yc> for Y {
    fn from(value: Yc) -> Self {
        Self { z: value.z }
    }
}

Then Vec<Xc> -> Vec<X is recognized by optimizer:

#[no_mangle]
fn convert_xs(xs: Vec<Xc>) -> Vec<X> {
    xs.into_iter().map(Into::into).collect()
}

$ cargo asm convert_xs

.section .text.convert_xs,"ax",@progbits
	.globl	convert_xs
	.p2align	4, 0x90
	.type	convert_xs,@function
convert_xs:
	.cfi_startproc
	mov rax, rdi
	movups xmm0, xmmword ptr [rsi]
	mov rcx, qword ptr [rsi + 16]
	movups xmmword ptr [rdi], xmm0
	mov qword ptr [rdi + 16], rcx
	ret

So does Vec<Yc> -> Vec<Y>:

#[no_mangle]
fn convert_ys(ys: Vec<Yc>) -> Vec<Y> {
    ys.into_iter().map(Into::into).collect()
}

$ cargo asm convert_ys

.section .text.convert_ys,"ax",@progbits
	.globl	convert_ys
	.p2align	4, 0x90
	.type	convert_ys,@function
convert_ys:
	.cfi_startproc
	mov rax, rdi
	movups xmm0, xmmword ptr [rsi]
	mov rcx, qword ptr [rsi + 16]
	movups xmmword ptr [rdi], xmm0
	mov qword ptr [rdi + 16], rcx
	ret

But not Vec<(Xc, Yc)>) -> Vec<(X, Y)>:

#[no_mangle]
fn convert_tuple(xy: Vec<(Xc, Yc)>) -> Vec<(X, Y)> {
    xy.into_iter().map(|(x, y)| (x.into(), y.into())).collect()
}

$ cargo asm convert_tuple

.section .text.convert_tuple,"ax",@progbits
	.globl	convert_tuple
	.p2align	4, 0x90
	.type	convert_tuple,@function
convert_tuple:
	.cfi_startproc
	mov rax, rdi
	mov rcx, qword ptr [rsi]
	mov rdx, qword ptr [rsi + 8]
	mov rdi, qword ptr [rsi + 16]
	mov rsi, rdx
	test rdi, rdi
	je .LBB5_3
	lea rsi, [rdi + 2*rdi]
	shl rsi, 4
	add rsi, rdx
	lea rdi, [rsp - 32]
	mov r8, rdx
	.p2align	4, 0x90
.LBB5_2:
	mov r9, qword ptr [r8]
	mov r10d, dword ptr [r8 + 8]
	movups xmm0, xmmword ptr [r8 + 16]
	mov r11, qword ptr [r8 + 32]
	mov qword ptr [rdi + 16], r11
	mov r11d, dword ptr [r8 + 40]
	mov dword ptr [rdi + 24], r11d
	mov r11d, dword ptr [r8 + 44]
	mov dword ptr [rdi + 28], r11d
	movups xmmword ptr [rdi], xmm0
	mov qword ptr [r8], r9
	mov dword ptr [r8 + 8], r10d
	movups xmm0, xmmword ptr [rsp - 36]
	movups xmm1, xmmword ptr [rsp - 20]
	movups xmmword ptr [r8 + 12], xmm0
	movups xmmword ptr [r8 + 28], xmm1
	mov r9d, dword ptr [rsp - 4]
	mov dword ptr [r8 + 44], r9d
	add r8, 48
	cmp r8, rsi
	jne .LBB5_2
.LBB5_3:
	sub rsi, rdx
	shr rsi, 4
	movabs rdi, -6148914691236517205
	imul rdi, rsi
	mov qword ptr [rax], rcx
	mov qword ptr [rax + 8], rdx
	mov qword ptr [rax + 16], rdi
	ret

Why is it? Is there some kind of limitation for this kind of optimization?

This is a MRE. Originally I try to cast Vec<A> -> Vec<B> where A and B are 336 bytes long.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Use the provided MRE as the first reproduction and inspect the generated assembly for convert_xs, convert_ys, and convert_tuple. Compare rustc’s optimization behavior for the struct and tuple cases, then determine whether the tuple case reflects an optimizer limitation. Done means an explanation backed by a minimized compiler result or a demonstrated improvement.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.