deserialization code leaves much to be desired

[jrmuizel]

The following rust code gives us a lot of per field overhead:

#[derive(Deserialize)]
pub struct P {
       x: u32,
       y: u32,
       z: u32,
       w: u32
}

pub fn moo(encoded: Vec<u8>) -> P {
    let mut s :&[u8] = &encoded;
    deserialize_from(&mut s, bincode::Infinite).unwrap()
}

I'd ideally want this to compile to some length checks and a single memcpy for all of the fields. Instead I get something that looks like a memcpy loop per field.

I suspect there are a number of things contributing to the problem here. The full assembly of moo follows:

	.globl	__ZN11serde_deser3moo17hd4391294d14f34bdE
	.p2align	4, 0x90
__ZN11serde_deser3moo17hd4391294d14f34bdE:
	.cfi_startproc
	pushq	%rbp
Lcfi16:
	.cfi_def_cfa_offset 16
Lcfi17:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
Lcfi18:
	.cfi_def_cfa_register %rbp
	pushq	%r15
	pushq	%r14
	pushq	%r13
	pushq	%r12
	pushq	%rbx
	subq	$72, %rsp
Lcfi19:
	.cfi_offset %rbx, -56
Lcfi20:
	.cfi_offset %r12, -48
Lcfi21:
	.cfi_offset %r13, -40
Lcfi22:
	.cfi_offset %r14, -32
Lcfi23:
	.cfi_offset %r15, -24
	movq	%rdi, -112(%rbp)
	movq	(%rsi), %r15
	movq	8(%rsi), %rax
	movq	%rax, -104(%rbp)
	movq	16(%rsi), %r12
	leaq	-68(%rbp), %r13
	movl	$0, -68(%rbp)
	movl	$4, %ebx
	movq	%r15, -80(%rbp)
	.p2align	4, 0x90
LBB4_1:
	cmpq	%rbx, %r12
	movq	%r12, %r14
	cmovaeq	%rbx, %r14
	cmpq	$1, %r14
	jne	LBB4_3
	movzbl	(%r15), %eax
	movb	%al, (%r13)
	jmp	LBB4_4
	.p2align	4, 0x90
LBB4_3:
	movq	%r13, %rdi
	movq	%r15, %rsi
	movq	%r14, %rdx
	callq	_memcpy
	testq	%r14, %r14
	je	LBB4_23
LBB4_4:
	addq	%r14, %r15
	subq	%r14, %r12
	addq	%r14, %r13
	subq	%r14, %rbx
	jne	LBB4_1
	movl	-68(%rbp), %eax
	movl	%eax, -72(%rbp)
	leaq	-68(%rbp), %r13
	movl	$0, -68(%rbp)
	movl	$4, %r14d
	.p2align	4, 0x90
LBB4_6:
	cmpq	%r14, %r12
	movq	%r12, %rbx
	cmovaeq	%r14, %rbx
	cmpq	$1, %rbx
	jne	LBB4_8
	movzbl	(%r15), %eax
	movb	%al, (%r13)
	jmp	LBB4_9
	.p2align	4, 0x90
LBB4_8:
	movq	%r13, %rdi
	movq	%r15, %rsi
	movq	%rbx, %rdx
	callq	_memcpy
	testq	%rbx, %rbx
	je	LBB4_23
LBB4_9:
	addq	%rbx, %r15
	subq	%rbx, %r12
	addq	%rbx, %r13
	subq	%rbx, %r14
	jne	LBB4_6
	movl	-68(%rbp), %eax
	movq	%rax, -96(%rbp)
	leaq	-68(%rbp), %r13
	movl	$0, -68(%rbp)
	movl	$4, %r14d
	.p2align	4, 0x90
LBB4_11:
	cmpq	%r14, %r12
	movq	%r12, %rbx
	cmovaeq	%r14, %rbx
	cmpq	$1, %rbx
	jne	LBB4_13
	movzbl	(%r15), %eax
	movb	%al, (%r13)
	jmp	LBB4_14
	.p2align	4, 0x90
LBB4_13:
	movq	%r13, %rdi
	movq	%r15, %rsi
	movq	%rbx, %rdx
	callq	_memcpy
	testq	%rbx, %rbx
	je	LBB4_23
LBB4_14:
	addq	%rbx, %r15
	subq	%rbx, %r12
	addq	%rbx, %r13
	subq	%rbx, %r14
	jne	LBB4_11
	movl	-68(%rbp), %eax
	movq	%rax, -88(%rbp)
	leaq	-68(%rbp), %r13
	movl	$0, -68(%rbp)
	movl	$4, %r14d
	.p2align	4, 0x90
LBB4_16:
	cmpq	%r14, %r12
	movq	%r12, %rbx
	cmovaeq	%r14, %rbx
	cmpq	$1, %rbx
	jne	LBB4_18
	movzbl	(%r15), %eax
	movb	%al, (%r13)
	jmp	LBB4_19
	.p2align	4, 0x90
LBB4_18:
	movq	%r13, %rdi
	movq	%r15, %rsi
	movq	%rbx, %rdx
	callq	_memcpy
	testq	%rbx, %rbx
	je	LBB4_23
LBB4_19:
	addq	%rbx, %r15
	subq	%rbx, %r12
	addq	%rbx, %r13
	subq	%rbx, %r14
	jne	LBB4_16
	movl	-68(%rbp), %eax
	movq	-88(%rbp), %rcx
	movq	%rcx, %rdx
	shlq	$32, %rdx
	addq	-96(%rbp), %rdx
	movq	-112(%rbp), %rbx
	movl	-72(%rbp), %ecx
	movl	%ecx, (%rbx)
	movq	%rdx, 4(%rbx)
	movl	%eax, 12(%rbx)
	movq	-104(%rbp), %rsi
	testq	%rsi, %rsi
	je	LBB4_22
	movl	$1, %edx
	movq	-80(%rbp), %rdi
	callq	___rust_dealloc
LBB4_22:
	movq	%rbx, %rax
	addq	$72, %rsp
	popq	%rbx
	popq	%r12
	popq	%r13
	popq	%r14
	popq	%r15
	popq	%rbp
	retq
LBB4_23:
	leaq	_str.6(%rip), %rdi
	movl	$27, %esi
	callq	__ZN3std5error205_$LT$impl$u20$core..convert..From$LT$$RF$$u27$b$u20$str$GT$$u20$for$u20$alloc..boxed..Box$LT$std..error..Error$u20$$u2b$$u20$core..marker..Send$u20$$u2b$$u20$core..marker..Sync$u20$$u2b$$u20$$u27$a$GT$$GT$4from17h4799454266726278E
	movq	%rdx, %rcx
	leaq	-64(%rbp), %rdi
	movl	$17, %esi
	movq	%rax, %rdx
	callq	__ZN3std2io5error5Error4_new17h85c79fbf3c4b32d5E
	movb	-64(%rbp), %al
	movb	-57(%rbp), %cl
	movb	%cl, -42(%rbp)
	movzwl	-59(%rbp), %ecx
	movw	%cx, -44(%rbp)
	movl	-63(%rbp), %ecx
	movl	%ecx, -48(%rbp)
	movq	-56(%rbp), %rcx
	movb	%al, -64(%rbp)
	movb	-42(%rbp), %al
	movb	%al, -57(%rbp)
	movzwl	-44(%rbp), %eax
	movw	%ax, -59(%rbp)
	movl	-48(%rbp), %eax
	movl	%eax, -63(%rbp)
	movq	%rcx, -56(%rbp)
	leaq	-64(%rbp), %rdi
	callq	__ZN7bincode8internal132_$LT$impl$u20$core..convert..From$LT$std..io..error..Error$GT$$u20$for$u20$alloc..boxed..Box$LT$bincode..internal..ErrorKind$GT$$GT$4from17hcfbfdc14cc272f8bE
	movq	%rax, %rdi
	callq	__ZN4core6result13unwrap_failed17h7caf794916bf7f7dE
	.cfi_endproc

[jrmuizel]

Note: this assembly was compiled with noalias annotations so it could be even worse on stable.

[jrmuizel]

So the implementation of Read for &'a [u8] is likely not doing us any favors here:

        let amt = cmp::min(buf.len(), self.len());
        let (a, b) = self.split_at(amt);

        // First check if the amount of bytes we want to read is small:
        // `copy_from_slice` will generally expand to a call to `memcpy`, and
        // for a single byte the overhead is significant.
        if amt == 1 {
            buf[0] = a[0];
        } else {
            buf[..amt].copy_from_slice(a);
        }

        *self = b;
        Ok(amt)

It will be interesting to see what the generated code looks like with a slimmed down version.

[jrmuizel]

I suspect we can apply basically the same optimization as servo/webrender#1830 and see a reasonable improvement.

[jrmuizel]

Indeed that works. With the following rust code:

#[derive(Deserialize)]
pub struct P {
    x: u32,
    y: u32,
    z: u32,
    w: u32
}

use bincode::{serialize, deserialize, deserialize_from, Infinite};

struct UnsafeReader {
    buf: *const u8,
    end: *const u8
}

impl UnsafeReader {
    fn new(buf: &[u8]) -> UnsafeReader {
        unsafe {
            let end = buf.as_ptr().offset(buf.len() as isize);
            let buf = buf.as_ptr();
            UnsafeReader { buf, end }
        }
    }
}

use std::io::{Read, Result};
use std::ptr;

impl Read for UnsafeReader {
    fn read(&mut self, buf: &mut [u8]) -> Result<usize> {
        unsafe {
            if self.buf.offset(buf.len() as isize) > self.end {
                panic!();
            }
            ptr::copy_nonoverlapping(self.buf, buf.as_mut_ptr(), buf.len());
            self.buf = self.buf.offset(buf.len() as isize);
        }
        Ok(buf.len())
    }
}

pub fn moo(encoded: Vec<u8>) -> P {
    //let mut s: &[u8] = &encoded;
    let mut s = UnsafeReader::new(&encoded);
    deserialize_from(&mut s, bincode::Infinite).unwrap()
}

We end up with much better code:

__ZN11serde_deser3moo17hd4391294d14f34bdE:
        .cfi_startproc
        pushq   %rbp
Lcfi13:
        .cfi_def_cfa_offset 16
Lcfi14:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Lcfi15:
        .cfi_def_cfa_register %rbp
        pushq   %rbx
        pushq   %rax
Lcfi16:
        .cfi_offset %rbx, -24
        movq    %rdi, %rbx
        movq    16(%rsi), %rax
        cmpq    $3, %rax
        jle     LBB5_7
        cmpq    $7, %rax
        jle     LBB5_7
        cmpq    $11, %rax
        jle     LBB5_7
        cmpq    $15, %rax
        jle     LBB5_7
        movq    (%rsi), %rdi
        movq    8(%rsi), %rsi
        movl    (%rdi), %r8d
        movl    4(%rdi), %ecx
        movl    8(%rdi), %edx
        movl    12(%rdi), %eax
        shlq    $32, %rdx
        orq     %rcx, %rdx
        movl    %r8d, (%rbx)
        movq    %rdx, 4(%rbx)
        movl    %eax, 12(%rbx)
        testq   %rsi, %rsi
        je      LBB5_6
        movl    $1, %edx
        callq   ___rust_dealloc
LBB5_6:
        movq    %rbx, %rax
        addq    $8, %rsp
        popq    %rbx
        popq    %rbp
        retq
LBB5_7:
        leaq    _str.V(%rip), %rdi
        leaq    _ref.T(%rip), %rdx
        movl    $14, %esi
        callq   __ZN3std9panicking11begin_panic17h9172a5d41e198dfeE
        .cfi_endproc

I do wonder why llvm isn't able to fold the length checks into a single check though.

[ZoeyR]

Have you compared the original assembly to the code produced by calling deserialize? If I remember correctly, deserialize is optimized for reading from slices, whereas deserialize_from is not.

[jrmuizel]

calling deserialize() gives worse code than deserialize_from(). You end up with calls to __ZN5serde2de9SeqAccess12next_element17h778123818a969aa4E for each field and it looks like __ZN5serde2de9SeqAccess12next_element17h778123818a969aa4E has an indirect call that it makes every time it's called.

[pcwalton]

@jrmuizel Boy, that's strange. Does running opt again clean it up?

[ZoeyR]

I think I found the reason that deserialize is worse than deserialize_from. It looks like we just wrap the slice and call the built in read method on it currently. We should probably actually implement some optimizations on it.

Edit: but since we already have the framework in place, It should be trivial to implement the optimization on SliceReader

[ZoeyR]

So I made a quick and dirty modification of bincode here replacing SliceReader with the one proposed by @jrmuizel. I ran bincode_bench but I'm not sure what to make of the results. For some reason both the code path that used a reader and the codepath that used a slice both saw speed improvements. This could be due to different system loads at the time. If that were the case it seems that the changes actually caused a slowdown since the improvement of the slice path was far less than that of the reader path.

Here are the results of the benches:

bincode master branch:

{
    "info": {
        "strategy": "bincode",
        "version": "eager-prealloc",
        "output": "vec (prealloc)",
        "debug": false,
        "iterations": 500
    },
    "total_time": 8757899807,
    "total_read": 448104000,
    "avg_time": 17515799
}
{
    "info": {
        "strategy": "serde-bench",
        "version": "0.0.5",
        "output": "vec",
        "debug": false,
        "iterations": 500
    },
    "total_time": 8365259918,
    "total_read": 448104000,
    "avg_time": 16730519
}
{
    "info": {
        "strategy": "bincode",
        "version": "eager-prealloc",
        "output": "vec",
        "debug": false,
        "iterations": 500
    },
    "total_time": 6487526926,
    "total_read": 448104000,
    "avg_time": 12975053
}

raw_reader branch:

{
    "info": {
        "strategy": "bincode",
        "version": "eager-prealloc",
        "output": "vec (prealloc)",
        "debug": false,
        "iterations": 500
    },
    "total_time": 7985701923,
    "total_read": 448104000,
    "avg_time": 15971403
}
{
    "info": {
        "strategy": "serde-bench",
        "version": "0.0.5",
        "output": "vec",
        "debug": false,
        "iterations": 500
    },
    "total_time": 7312162883,
    "total_read": 448104000,
    "avg_time": 14624325
}
{
    "info": {
        "strategy": "bincode",
        "version": "eager-prealloc",
        "output": "vec",
        "debug": false,
        "iterations": 500
    },
    "total_time": 6128483943,
    "total_read": 448104000,
    "avg_time": 12256967
}

The sets marked with vec (prealloc) were run through bincode::deserialize_from and the bincode bench simply marked vec was run though bincode::deserialize

[jrmuizel]

I did some performance testing and needed #207 to make it go fast.

[jrmuizel]

FWIW, rerunning opt doesn't clean up the comparison chain.