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.

MBBS in Philippines said...

UV GULLAS COLLEGE OF MEDICINE is one of Top Medical College in Philippines in Cebu city. International students have the oppertunity to study medicine in phillipines at affordable cost and world class University. The college has successful alumni who have achieved well in the fields of law, business, politics, academe, medicine, sports and other endeavors. At University of the Visayas, we prepare students for a global competition.

Direct MBBS Admissions Open: 2020-21
Mobile No: +91 90329 55688
Apply Now: https://www.careerplus.org.in/philippines-medical-college/uv-gullas-college-of-medicine

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

Digital Vishnu said...

This is incredibly useful information!! Excellent work. All is very fascinating to learn and simple to grasp. Thanks for sharing such great info. Keep Post These kinds of Articles in the future.

Digital Marketing Course in Coimbatore
Digital Marketing Course Training in Tirupur
Digital Marketing Course Training in Madurai
Digital Marketing Course Training in Theni
Digital Marketing Training in Coimbatore

bamgosoo said...

Spot on with this write-up, I truly believe this amazing site needs a
great deal more attention. I'll probably be returning to see more, thanks for the advice!

Also visit my web site; 부산달리기

oncadaycomm said...

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

yasul.top said...

You really make it seem so easy with your presentation but I find this topic to be actually something that I think I would never understand. It seems too complicated and very broad for me. I am looking forward for your next post, I will try to get the hang of it!


ophunter.net said...

I was pretty pleased to uncover this site. I need to to thank you for your time for this particularly wonderful read!! I definitely appreciated every part of it and I have you saved to fav to see new information in your web site.


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.