In libstdc++ 4.4.3-4ubuntu5, getline() is extremely slow, taking around 23us of user time per line on an Intel T9300 processor. By contrast, fgets() takes about 0.3us per line. Calling ios::sync_with_stdio(false) before the loop start reduces the time per line to around 0.3us, on par with fgets(). This suggests that the problem is with the stdio synchronisation code.
If the problem is in the stdio sync code, then file a glibc PR.
(In reply to comment #1) > If the problem is in the stdio sync code, then file a glibc PR. > I mean the "stdio sync code" as in the code in libstdc++ which synchronises with glibc, not actual code within glibc. If there was a problem with glibc, glibc would be slow, but it isn't.
There is nothing we can do to speed up further the v3 side of the synced code, thus, unless you have evidence that other implementations perform much better than v3, and provide details, this is closed.
Benchmarking on Solaris indicates that cin.getline() takes only 1us per iteration there, but I don't think the source code is available, so it's hard to provide details. However, I think that a huge speedup could be achieved by making basic_istream<char>::getline() into a simple wrapper around a GNU-specific virtual function in basic_streambuf. This would allow it to be specialised in stdio_sync_filebuf, where it could be implemented using fgets() or getdelim() instead of getc(). This would have the additional positive impact of making it atomic. Currently, cin.getline() does not properly lock the underlying libc stream with flockfile(). This means that if one thread is calling cin.getline(), and another thread is calling getc(), then cin.getline() may return mangled partial lines due to interleaved calls to getc() from the other thread.
For sure we cannot add virtual functions to basic_streambuf without breaking the ABI. Also, getline certainly isn't just fgets, takes a delim char, uses traits, etc. Sure, anyway, in principle you can often speed-up special cases, but also given that in ~5-7 years nobody else reported anything about the performance of the synced getline, I don't think anything is going to happen anytime soon, I could keep this open, but it would be futile, we have a lot of work to do, for C++0x, in particular.
By the way, I don't know anything about your testcase (it would be a good idea attaching something here, just in case), but on my machines, i7 mostly, I don't see anything similar to your performance gap, I see something more similar to 9-10x, which, considering that a real synced mode must be unbuffered, seems completely reasonable to me.
(In reply to comment #0) > Calling ios::sync_with_stdio(false) before the loop start reduces the time per > line to around 0.3us, on par with fgets(). This suggests that the problem is > with the stdio synchronisation code. It's well known (though maybe not well enough) that you should use sync_with_stdio(false) to get good performance, unless you specifically need the synchronisation. (In reply to comment #4) > Benchmarking on Solaris indicates that cin.getline() takes only 1us per > iteration there, but I don't think the source code is available, so it's hard > to provide details. If you mean the classic iostreams provided with Sun Studio (rather than GCC on Solaris or something else) then that stream library is not standard-conforming and you're comparing apples and oranges. If you mean the STLport iostreams provided with Sun Studio and enabled by -library=stlport4, the source is available, but I'd be surprised if you see a significant speed difference.
(In reply to comment #5) > For sure we cannot add virtual functions to basic_streambuf without breaking > the ABI. I'm mostly looking for a long-term fix, to improve the speed of libstdc++ applications generally, especially those that don't have developers who would go to the trouble to track down the source of slowness in their programs. The short-term fix is to call ios::sync_with_stdio(false). So it's fine for me to wait for the next major version. > Also, getline certainly isn't just fgets, takes a delim char, uses > traits, etc. The delim char can be taken care of with getdelim(). I don't think it's unreasonable to specialise for default traits, that would take care of 99% of use cases. > Sure, anyway, in principle you can often speed-up special cases, > but also given that in ~5-7 years nobody else reported anything about the > performance of the synced getline, I don't think anything is going to happen > anytime soon, I could keep this open, but it would be futile, we have a lot of > work to do, for C++0x, in particular. OK, let's keep it open. (In reply to comment #6) > By the way, I don't know anything about your testcase (it would be a good idea > attaching something here, just in case), but on my machines, i7 mostly, I don't > see anything similar to your performance gap, I see something more similar to > 9-10x, which, considering that a real synced mode must be unbuffered, seems > completely reasonable to me. Probably the main difference is the number of bytes per line in the input file. I'm using a file with 1M lines and an average of 429 bytes per line. Using less bytes per line would bring more pressure on to the constant per-line overhead, and less on the inner loop. But a 9-10x difference doesn't sound reasonable to me. The synced mode is not unbuffered, before or after my suggested change, it uses the internal buffer in glibc. (In reply to comment #7) > It's well known (though maybe not well enough) that you should use > sync_with_stdio(false) to get good performance, unless you specifically need > the synchronisation. Maybe you should tell that to Paolo Carlini, who closed bug 15002 as "resolved fixed" in 2004, or to Loren Rittle, who closed bug 5001 as "resolved fixed" in 2003, declaring "This issue was addressed by gcc 3.2.X such that sync_with_stdio was no longer required for reasonable performance."
Created attachment 21732 [details] 100000 lines, 500 bytes per line Test file attached as requested, compressed with gzip. Test code follows. getline-test.cpp #include <iostream> int main(int argc, char** argv) { char buffer[65536]; while (std::cin.getline(buffer, sizeof(buffer), '\n')); return 0; } fgets-test.cpp: #include <stdio.h> int main(int argc, char** argv) { char buffer[65536]; while (fgets(buffer, sizeof(buffer), stdin)); return 0; } $ time ./fgets-test < 500x100k.txt real 0m0.076s user 0m0.040s sys 0m0.032s $ time ./getline-test < 500x100k.txt real 0m2.727s user 0m2.672s sys 0m0.028s
(In reply to comment #8) > Maybe you should tell that to Paolo Carlini, who closed bug 15002 as "resolved > fixed" in 2004, And it *is* fixed. Did you actually open the testcases? Just plain fstreams, thus no syncing. or to Loren Rittle, who closed bug 5001 as "resolved fixed" in > 2003, declaring "This issue was addressed by gcc 3.2.X such that > sync_with_stdio was no longer required for reasonable performance." And indeed it's true.
(In reply to comment #8) > But a 9-10x difference doesn't sound reasonable to me. The synced mode is not > unbuffered, before or after my suggested change, it uses the internal buffer in > glibc. So? We are not changing glibc here. The C++ library does *not* use buffering in the synced mode, and it does otherwise, for fstreams in particular. Where do you think the performance difference is essentially coming from?
By the way, getdelim is not standard, thus would work only on linux, even more special casing. More importantly, fgets *stores* newline and '\0', at variance with getline, I don't think it can be used as-is as an implementation detail.
And, getdelim insist on allocating resp. reallocating the buffer. That is of course usually desirable when used from C, but I'm afraid it isn't in this case, where you have user provided buffer with fixed size. You don't want to read more than that size, while getdelim will read any amount of data.
(In reply to comment #11) > So? We are not changing glibc here. The C++ library does *not* use buffering in > the synced mode, and it does otherwise, for fstreams in particular. Where do > you think the performance difference is essentially coming from? Sure, buffering would help, because the interface between the C++ library and the buffer in the C library is slow. I just meant that the lack of a buffer in C++ isn't an excuse for slowness since it should theoretically be possible for C++ to access the buffer in the C library without much overhead. At another level, your question is unsolved and interesting, because while(getc(stdin)!=EOF); is much faster than cin.getline(), taking only 0.632s of user time for the attached test case. And a loop of getc_unlocked() only takes 0.188s of user time. So there may be opportunity for optimisation here without resorting to fgets() or getdelim(), which as you say, suck in various ways. I'll see if I have time for some more testing. If I wrote a patch involving a new virtual method or two, would it be looked at?
If you write a patch it would be of course looked at. But *please* try first something that doesn't break the ABI, because we have *no* idea when you changes would be applied otherwise. About the *_unlocked functions, we know those glibc extensions exist, but, as far as I can see would only change the complexity by a not so so small multiplicative constant and, after years and years of using everywhere the normal versions, I don't believe we should change just now the configuration on Linux only. But, as I said, provided you don't break the ABI (to be concrete) and the improvements are substantive, you are certainly welcome to submit patches to the libstdc++ mailing list. Thanks.
The *_unlocked versions are faster a lot actually, at least for the one character ops, because no locking is performed and the calls are inlined. But the question is whether libstdc++ can use them, unless there is some restriction that would disallow several threads from using the same FILE * (including using STL APIs in one thread and C stdio APIs in another thread).
At some point I tried quickly replacing some getc, did notice an improvement of course, but of the order of magnitude I mentioned. Worth further investigating sure (and simple, just replace in stdio_sync_ and measure, on Linux). In terms of the C++ Standard, I think that C++98 would allow essentially *anything*, not so C++0x, and within C++98 too I'm afraid we can break code making already some assumptions about the thread safety, which we don't spell out anywhere as impl def behavior, still...
Created attachment 21752 [details] gprof output I haven't managed to get libstdc++ to compile with -pg, but compiling the test program with -static at least gives you a function breakdown. gprof output attached for 1 million lines, 500 bytes per line. To summarise: fgetc: 36.13% istream::getline: 18.01% ungetc: 16.70% _IO_sputbackc: 9.54% stdio_sync_filebuf::underflow: 5.66% stdio_sync_filebuf::uflow: 4.93% I should have spotted it from reading the code, it's not a loop of getc(), it's a loop of ungetc(getc()) && getc(). It really demonstrates how poorly suited the streambuf interface is to unbuffered input. The virtual functions called by istream::getline() don't give much flexibility. So I still have no other ideas apart from breaking the ABI.
(In reply to comment #16) > The *_unlocked versions are faster a lot actually, at least for the one > character ops, because no locking is performed and the calls are inlined. > But the question is whether libstdc++ can use them, unless there is some > restriction that would disallow several threads from using the same FILE * > (including using STL APIs in one thread and C stdio APIs in another thread). My current idea is to do: flockfile(stdin); while (!eof) { c = getc_unlocked(stdin); ... } funlockfile(stdin); This is not only much faster, it's an improvement to the current behaviour in terms of locking and thread safety. The current behaviour, as I said in comment #4, could cause data to be badly mangled if one thread uses stdio while another uses cin.getline(). Using getc() in preference to getc_unlocked() does not help. And unlike getdelim(), the unlocked I/O functions are in POSIX.1-2001, says the man page, so it's relatively portable.
Good about POSIX, we would add a configure time test with some hope to enable the mechanism outside Linux too. Anyway, I'm sure your kind of loop would improve the performance a lot - if only we could have it without breaking the ABI I would be in favor of having it immediately - still, we would still use a single char function, I think the complexity for long lines would still scale badly. As a matter of fact, I think the only completely satisfactory design would be that used by the old v2, with a low level libio layer, doing buffering and the low level operations, and used by the C and C++ libraries on top. Missing that, I don't think the C++ library, working purely on top of the Standard C library will ever be able to performe as well as C in the synced mode. The only hope could be exploiting, on Linux systems, a glibc *extension* (we do that in many other cases), like an fgetc not writing '\0' and newline, which the glibc people would essentially provide exactly to help the C++ library implementation. Anyway, sorry if I may have appeared a little too harsh in my first replies, the fact is I know the history of these facilities, I know all the effort other people besides me put to have a good overall compromise (eg, stdio_sync isn't mine and solved a *a lot* of problems), we are certainly open to improvements, but realistic ones, at least until we break all the ABIs.
#if __GNUC__ >= 3 # define _IO_BE(expr, res) __builtin_expect ((expr), res) #else # define _IO_BE(expr, res) (expr) #endif #define _IO_getc_unlocked(_fp) \ (_IO_BE ((_fp)->_IO_read_ptr >= (_fp)->_IO_read_end, 0) \ ? __uflow (_fp) : *(unsigned char *) (_fp)->_IO_read_ptr++) ... __STDIO_INLINE int getc_unlocked (FILE *__fp) { return _IO_getc_unlocked (__fp); } i.e. if getc_unlocked is called directly, it should be very fast, unless the underlying stream is unbuffered. This is direct access to the buffer, just STL getline couldn't use memchr. Anyway, not sure which STL getline we are talking about here, because e.g. src/istream.cc getline seems to access the stdio buffer directly: streamsize __size = std::min(streamsize(__sb->egptr() - __sb->gptr()), streamsize(__n - _M_gcount - 1)); if (__size > 1) { const char_type* __p = traits_type::find(__sb->gptr(), __size, __delim);
Jakub, when, by default, cin & co boil down to stdio_sync_filebuf, the underlying basic_streambuf is unbuffered, everything is unbuffered in the C++ library.
(In reply to comment #21) > Anyway, not sure which STL getline we are talking about here, because e.g. > src/istream.cc getline seems to access the stdio buffer directly: > streamsize __size = std::min(streamsize(__sb->egptr() > - __sb->gptr()), > streamsize(__n - _M_gcount > - 1)); __sb->gptr() and __sb->egptr() are always null for this kind of streambuf, so __size is always zero, and so the loop just calls snextc() on every iteration.
Created attachment 21766 [details] dynamic_cast<> hack The attached patch uses a dynamic_cast<> hack to avoid the need to break the ABI. I added *_unlocked functions to cstdio, I'm not sure if this is necessary, but it's easy enough to remove that part if not. I also added some lightly-tested autoconf stuff. I'm an autoconf newbie so that part should probably be reviewed carefully. stdio_sync_filebuf<wchar_t>::_M_getline() is currently unreachable, since I only edited basic_istream<char>::getline() and not basic_istream<wchar_t>::getline(). It would be easy enough to fix that. I haven't used getwc_unlocked() because it's a GNU extension, POSIX only has non-wide unlocked I/O. The timings for 1M lines with 500 bytes per line, user time only, are: Old library: 26.7s New library: 1.65s fgets: 0.280s So it's better, but not perfect.
Good. Please give me a couple of days to come to your code. Note, since you don't have a Copyright Assignment on file, it will be difficult to fully acknowledge your work in the ChangeLog. Thus, I would suggest having first a minimal patch, limited to char, limited in any way ;) but still sufficient to bring most of the improvement we are aiming to within the ABI.