reverse_complement spends most of its time reading input

[mbrubeck]

On my system, reverse_complement < input25000000.txt spends 67% of its time on the read_to_end call here. According to the profile, that time is almost all spent in memmove.

    let mut data = Vec::with_capacity(1024 * 1024);
    stdin.lock().read_to_end(&mut data).unwrap();

Increasing the initial buffer size to fit the entire dataset cuts the read_to_end time in half, and reduces the total execution time by about 30%, but obviously it also wastes memory if the data is small. (Since this program reads from stdin, it doesn't known the total size before it starts reading.)

[mbrubeck]

The C++ code uses ftell to get the input size before allocating a buffer:

      long start = ftell( stdin );
      fseek( stdin, 0, SEEK_END );
      size = ftell( stdin ) - start;

[llogiq]

The C version uses a buffer that is realloc'd to double size on overflow. Perhaps we could have something similar in a crate? Reading arbitrary-sized input is a common use case after all.

[TeXitoi]

@llogiq Vec already does that automatically, no?

[mbrubeck]

To avoid wasting memory, read_to_end does not double the buffer; instead it grows it by up to DEFAULT_BUF_SIZE (8 KB) at a time. When reading 250 MB of data, that's a lot of reallocations!

https://github.com/rust-lang/rust/blob/08230775a026c955873ba557e624b7f665661f37/src/libstd/io/mod.rs#L351-L354

Also, with a 250 MB buffer, even a single reallocation can be a huge cost. I had to tack an extra byte onto the buffer size to avoid a single reallocation at the end of the file.

[llogiq]

@TeXitoi also depending on alignment and allocator used, RawVec may create just another allocation and move the contents there (interesting realloc implementation)..