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:

Whereas with a string:

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:

Versus for string:

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:

And string:

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:

LLVM 3.0 s C/C++7.5
LLVM 3.0 v C/C++8
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


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.

snorlax said...

@insane coder (& BrettB)

I took a stab at the POSIX method; does this snippet look correct?


insane coder said...

I haven't reviewed all of it, but the general gist of it looks correct.

TerA said...

Thanks for all the amazing articles that you been sharing all this time. Please keep posting such good quality content on regular because they are awesome.
new xxx stories

oncadaycomm said...

Hard to ignore such an amazing article like this.
You really amazed me with your writing talent.
Thank you for sharing again. 카지노

massage.blue said...

Nice article. I like the part where you mentioned that a good comment is one where I have to pay attention to the article. However, I am not sure where you were going with that concept. Can you explain it to me further? The part that I did not like was in order to have a good comment on the blog post, I have to point out what I liked about your post. What if I did not like the blogpost. Can you explain it to me as well?


gunma.top said...

Howdy superb website! Does running a blog similar to this require a great deal of work? I’ve absolutely no understanding of coding however I had been hoping to start my own blog soon.


MBBS in Philippines said...

Wisdom Overseasis authorized India's Exclusive Partner of Southwestern University PHINMA, the Philippines established its strong trust in the minds of all the Indian medical aspirants and their parents. Under the excellent leadership of the founder Director Mr. Thummala Ravikanth, Wisdom meritoriously won the hearts of thousands of future doctors and was praised as the “Top Medical Career Growth Specialists" among Overseas Medical Education Consultants in India.

Southwestern University PHINMAglobally recognized university in Cebu City, the Philippines facilitating educational service from 1946. With the sole aim of serving the world by providing an accessible, affordable, and high-quality education to all the local and foreign students. SWU PHINMA is undergoing continuous changes and shaping itself as the best leader with major improvements in academics, technology, and infrastructure also in improving the quality of student life.

Zea said...

HD Video Player

Easy Loan Mart said...

Call open() method to open a file “tpoint. txt” to perform read operation using object newfile. If file is open then Declare a string “tp”. Read all data of file object newfile using getline() method and put it into the string tp.
You are also read more How to get Instant Loan

baccaratsite.top said...

I will recommend your website to everyone. You have a very good gloss. Write more high-quality articles. I support you.

casinositewikicom said...

I like the helpful info you provide in your articles. I’ll bookmark your blog and check again here frequently. I’m quite sure I’ll learn plenty of new stuff right here! 카지노


This is one of the best website I have seen in a long time thank you so much. 바둑이사이트