Tuesday, November 29, 2011


Reading in an entire file at once in C++, part 2



Last week I discussed 6 different methods on how to quickly get an entire file into a C++ string.

The conclusion was that the straight forward method was the ideal method, this was verified across several compilers. Since then, people asked me a number of questions.

What if I want to use a vector instead of a string, are the speeds different?
Forget C++ containers, what about directly into a manually allocated buffer?
What about copying into a buffer via mmap?
What do these various cases say about compilers or their libraries? Can this indicate what they're good or bad at compiling?

So to establish some baseline numbers, I created an application which reads the same files the same amount of times using the fastest method possible. It directly creates a buffer aligned to the partition's blocking factor, informs the OS to do the fastest possible sequential read, and then reads the file directly into the buffer. I also tested the suggested method to mmap a file, and copy the contents from there to an allocated buffer. The times achieved for these were 5 and 9 respectively. The latter is slower because of the extra memcpy() required, you want to read directly into your destination buffer whenever possible. The fastest time I now achieved should more or less be the fastest theoretical limit I'm able to get with my hardware. Both GCC and LLVM got the exact same times. I did not test with VC++ here as it doesn't support POSIX 2008.

Now regarding our 6 methods from last time, all of them except the Rdbuf method are possible with std::vector, since there is no std::vector based std::istream.

An interesting thing to note is that C++ string implementations vary greatly from implementation to implementation. Some offer optimizations for very small strings, some offer optimizations for frequent copies, by using reference counting. Some always ensure the string ends with a 0 byte so you can immediately pass them as a C string. In this latter case, operations which operate on strings as a range are rather quick, as the data is copied, then a 0 is appended. Whereas a loop which constantly pushes bytes on the back will have to needlessly set the extra trailing byte to 0 each time. Vector implementations on the other hand don't need to worry about a trailing 0 byte, and generally don't try to internally use all kinds of elaborate storage methods. So if std::vector works for you, you may want to use that.

Let's review times for the 5 applicable methods with our various compilers.

GCC 4.6 with a vector:
MethodDuration
C23.5
C++22.8
Iterator73
Assign81.8
Copy68


Whereas with a string:
MethodDuration
C24.5
C++24.5
Iterator64.5
Assign68
Copy63


We see that with a vector, the basic methods became a bit faster, but interestingly enough, the others got slower. However, which methods are superior to the others have remained the same.

Now for LLVM 3 with a vector:
MethodDuration
C8
C++8
Iterator860
Assign1328
Copy930


Versus for string:
MethodDuration
C7.5
C++7.5
Iterator110
Assign102
Copy97


With LLVM, everything is slower with a vector, and for the more complex solutions, much much slower. There's two interesting things we can see about LLVM though. For more straight forward logic, their compiler's optimizations are extremely smart. The speeds approach the theoretical best. I did some profiling on GCC and LLVM, as they're using the same C and C++ libraries, and found that in the straight C/C++ methods for my test program, GCC made 300 memory allocations, but LLVM made only 200. LLVM apparently is smart enough to see inside the various allocations, skip the ones that aren't needed, and place the data directly into the output buffer. But for complex code, LLVM's optimizations aren't that great. In the case of vectors and iterators, downright awful. Someone should file some bug reports with them.

Now for Visual C++ 2010 using vector:
MethodDuration
C17.8
C++18.7
Iterator180.6
Assign159.5
Copy165.6


And string:
MethodDuration
C16.5
C++20.4
Iterator224.4
Assign222.8
Copy320


We see here that the Copy method, which uses push_back() got a huge performance improvement. This seems to indicate that the STL implementation adds a 0 at the end of each operation, especially push_back(), instead of just when c_str() is called. Otherwise, string is faster.

It's also sad to see that GCC while winning all the cases where iterators were involved, was significantly slower in all the straight forward cases. This seems to indicate that GCC has the smartest optimizations, but fails to optimize well when the logic is straightforward. Someone should look into that.

It seems if you're trying to hold a collection of bytes, or whatever your wchar_t is, but don't care about the specialties of any particular container, as long as you don't push_back() a lot, string seems to be faster.

Finally, here's a table of all the compilers and methods I tested ordered by speed:


MethodDuration
POSIX5
LLVM 3.0 s C/C++7.5
LLVM 3.0 v C/C++8
MMAP9
VC 2010 s C16.5
VC 2010 v C17.8
VC 2005 s C18.3
VC 2010 v C++19.7
VC 2010 s C++20.4
VC 2005 s C++21
GCC 4.6 v C++22.8
GCC 4.6 v C23.5
VC 2005 v C24
GCC 4.6 s C/C++24.5
VC 2005 v C++26
LLVM 3.0 s Rdbuf31.5
GCC 4.6 s Rdbuf32.5
GCC 4.6 s Copy63
GCC 4.6 s Iterator64.5
GCC 4.6 s Assign68
GCC 4.6 v Copy68
GCC 4.6 v Iterator73
GCC 4.6 v Assign81.8
LLVM 3.0 s Copy97
LLVM 3.0 s Assign102
LLVM 3.0 s Iterator110
VC 2010 v Assign159.5
VC 2010 v Copy165.6
VC 2005 v Copy172
VC 2010 s Rdbuf176.2
VC 2010 v Iterator180.6
VC 2005 s Rdbuf199
VC 2005 s Iterator209.3
VC 2005 s Assign221
VC 2010 s Assign222.8
VC 2010 s Iterator224.4
VC 2010 s Copy320
VC 2005 v Iterator370
VC 2005 v Assign378
VC 2005 s Copy483.5
LLVM 3.0 v Iterator860
LLVM 3.0 v Copy930
LLVM 3.0 v Assign1328

3 comments:

iCrazy said...

Excellent follow-up. Thanks for sharing!e

BrettB said...

Could you post a snippet of your POSIX code?

insane coder said...

Hi BrettB,

I'm not sure I still even have the test code I wrote for this article.

However, the concept behind fast POSIX file to memory usage involves the following:
Direct file access functions (the classic open/read/close).
Best alignment of data in memory and multiple of the file's blocking factor (posix_memalign and fstat with st_blksize).
Informing the OS of I/O strategy (posix_fadvise and posix_madvise).

In terms of getting the entire file, and a C++ string, then a lot of the details above aren't relavent. But you'll still want open, posix_fadvise, read, and close, to setup a fast no nonsense read with as little overhead as possible.