8 ms·
For processing strings, streams in C++ can be slow
- taspeotis 3y agoWhen I did competitive programming in C++ nobody used fstream for reading input because it was much slower compared to fscanf.
- IAmLiterallyAB 3y agoIt always surprises me how slow streams are. fscanf should be relatively slow because it has to parse the format string at runtime. So the new C++ format should be (and I believe is) much faster
- deleted 3y ago[deleted]
- fooker 3y agoParsing a string is significantly faster than disk io, so this is not an issue unless you are reading minuscule amounts of data.
- tlb 3y agoThat was once true, but not on most modern systems with SSDs. Cheap NVMe SSDs can sustain over 1 GB/s, which only a highly optimized SIMD parsing library can exceed.
- fooker 3y agoYou are missing the point. The format string is tens of bytes, parsing it is fast no matter what compared to reading large amounts of data.
- tlb 3y agoAh, I thought you meant the speed of parsing the payload didn't matter (scanf performance was also discussed). Yes, parsing the format string in printf or scanf isn't a big deal.
- kccqzy 3y agoI believe the Abseil library has formatting functions that's capable of parsing the format string at compile time.
- dezgeg 3y agofscanf() is also pretty slow because of thread safety so each call involves a mutex (which goes unused 99% of the time). I wonder do the new C++ libraries have faster non-threadsafe options?
- GuB-42 3y agoDoes it matter? The little I did competitive programming, input parsing time was negligible compared to the allowed runtime for solving the problem. Inputs were designed so that if you had the right algorithm, you could do it easily even with terrible optimization. Fast code could be an advantage in the algorithm (but not in parsing), as it could help you "cheat" and, for example, do a problem designed for N² in N³. Personally, I used iostreams, just because I found it a bit easier to type. But then, different competition have different rules, and maybe there are some where fscanf really is an advantage.
- gumby 3y agoMy impression is that C++ streams are on their way out -- unlikely to be deprecated (too much existing code) but also unlikely to receive any more attention. They are old enough to likely not have any actual implementation bugs at this point, but in retrospect the design bugs from the 1980s are pretty serious. The rapid incorporation of the excellent `format` package for printing points to a future falling back at least to ANSI buffered IO and possibly raw POSIX IO.
- synergy20 3y agoyou mean format + printf/scanf from C?
- signa11 3y agothis: https://en.cppreference.com/w/cpp/utility/format/format https://en.cppreference.com/w/cpp/utility/format/format most likely.
- corysama 3y agohttps://en.cppreference.com/w/cpp/header/format https://en.cppreference.com/w/cpp/header/format Which is based on https://fmt.dev/latest/index.html https://fmt.dev/latest/index.html
- gumby 3y agoAs others have pointed out I mean `std::format` et al in <format>. There's also a proposal for a type safe scanf: scnlib, sort of format in reverse: https://scnlib.dev/en/master/ https://scnlib.dev/en/master/
- jujube3 3y agoIs there any reason to use the format package rather than printf? Aside from C++ people who claim to hate C needing to save face?
- IcyWindows 3y agoThe library overview goes over the reasons fairly succinctly: https://fmt.dev/latest/index.html#overview https://fmt.dev/latest/index.html#overview
- Calavar 3y ago> When performing string concatenation operations, it is more advantageous in terms of performance to use std::ostringstream rather than std::string. This approach is also used elsewhere, such as debug_utils and node_errors. (From the Node.js GitHub issue.) Sounds like this guy is mixing up his Java knowledge with C++ knowledge. C++ streams are frankly insane: Loads of implicit state, needing to set about a half dozen flags to do any nontrivial formatting, running the risk of accidentally "poisoning" all downstream operations if you forget to reset any of that state, the useless callbacks API [1], obfuscated function names (xsgetn, epptr, egptr), a ridiculously convoluted inheritance hierarchy that includes virtual/diamond inheritance [2], and use of virtual functions for simple buffer manipulation. These were all bad decisions even at the time. [1] https://en.cppreference.com/w/cpp/io/ios_base/register_callback https://en.cppreference.com/w/cpp/io/ios_base/register_callb... [2] https://i.stack.imgur.com/dXhXP.png https://i.stack.imgur.com/dXhXP.png
- AndrewStephens 3y agoiostreams are such a messy design, for all the reasons you mention and more. They are rightly avoided in all code that cares about performance.
- juunpp 3y ago> (From the Node.js GitHub issue.) Sounds like this guy is mixing up his Java knowledge with C++ knowledge. That is exactly it. C++ string streams have had atrocious performance since forever. Good abstraction, not very useful in practice. In Java, if I remember correctly, strings are immutable, so the StringBuilder or whatever ridiculous name it had was the faster way to build a string. > "I recently learned that some Node.js engineers prefer stream classes when building strings, for performance reasons." Pretty much tells you everything you need to know about node js, I guess.
- Rebelgecko 3y agoFor what it's worth, even in Java the compiler is often smart enough to replace naive string concatenation with equivalent StringBuilder usage (although I don't know if it is smart enough to do that in a for loop like this)
- ewalk153 3y agoDaniel’s PR to implement this in node.js[1] is case study in: - crafting a high context yet succinct description - addressing PR feedback well - giving respect to a pedantic commenter who understands the inner workings far less than Daniel while not conceded to make a destructive change. I will share this PR widely as arole model in open source contributions. [1] https://github.com/nodejs/node/pull/50288 https://github.com/nodejs/node/pull/50288
- pitaj 3y agoI'm surprised that the reviewer was so ignorant of amortized constant time insertion.
- rossjudson 3y agoI am not at all surprised. Kids these days have no idea what CPUs can do. ;) I periodically have interview candidates work through problems involving binary search, then switch to bounded and ask them how to make it go faster over N elements, where N is < 1e3. The answer is "just linear search, because CPUs really like to do that".
- beltsazar 3y agoBut amortized analysis has nothing to do with what CPUs can do. CS students learn it in an algorithm course, not in a computer architecture course.
- lifthrasiir 3y agoIf I'm being super pedantic, I would argue that while `string::push_back` should take amortized constant time, `string::append` has no such guarantee [1]. So it is technically possible for `my_string += "a";` (same to `string::append`) will reallocate every time. Very pedantic indeed, but I have seen some C++ implementation where `std::vector<T>` is an alias to `std::deque<T>`, so... One thing I don't like about lemire's phrasing is that he only looks at the current, often only most available, implementations and doesn't make this point explicit for most cases. EDIT: Thankfully he does acknowledge that in a later post [2]. [1] https://timsong-cpp.github.io/cppwp/n4861/strings#string.append https://timsong-cpp.github.io/cppwp/n4861/strings#string.app... [2] https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-character-by-character-how-does-the-capacity-grow/ https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-...
- linuxhansl 3y agoYep. stringstreams make copies of passed strings too. I had to hack around that once like this: struct ZeroCopyBuf : public std::streambuf { ZeroCopyBuf(const std::string &s) : ZeroCopyBuf(s.c_str(), s.length()) {} ZeroCopyBuf(const char *c, std::size_t l) : ZeroCopyBuf(const_cast<char*>(c), l) {} ZeroCopyBuf(char *c, std::size_t l) { setg(c, c, c + l); } }; ... std::string s ...; ZeroCopyBuf buf(s); std::istream is(&buf); Terrible. C++-20 makes it better by adding move semantics to most methods... Still.
- nly 3y agoJust use the Boost Iostreams library The array_source device can be used with any buffer (char*, size_t)
- roeles 3y agoLots of complaints about stream performance here. std::sync_with_stdio(false); Helps with that a bit.
- nly 3y agoSetting the classic locale too
- atemerev 3y agoOK, so, what is the right way then?
- flohofwoe 3y agoIf performance matters most, write your own specialized string processing code which works on "raw" data in memory buffers. If convenience matters look at https://github.com/fmtlib/fmt https://github.com/fmtlib/fmt (or std::format which AFAIK is less feature rich) and https://github.com/imageworks/pystring https://github.com/imageworks/pystring.
- ho_schi 3y agoQuestion std::ios_base::sync_with_stdio(false); What is the effect of turning off synchronization with legacy functions from C? When C++ is used for I/O and no C is used this should be a habit. I’ve the impression that most C++ books don’t mention it (e.g. Primer) or only late. It is similar to String and StringBuilder from Java. You need to know it, remember it and use it by habit. And again, books often mention it only late (e.g. Head First). By the way. I like the plain things from <iostream>, especially the shift << and >> operators and ease of concatenating and handling strings. But as others mentioned, the implementation (e.g. inheritance) looks complicate. Source https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdi...
- adev_ 3y ago<iostreams> are currently a good example of pure product of the 199X/2000s when the hype about Object Oriented was around its peak. Almost everything related to c++ iostreams has this code smell of OOP pushed too far: - Usage of runtime virtual dispatch with virtual calls when it was not necessary. Causing a negative unavoidable impact on performance. - Heavy usage of function overloading with the "<<" operator. Leading to pages long compilation errors when an overload fails. - Hidden states everywhere with the usage of state formatters and globals in the background. - Unnecessary complexity with std::locale which is almost entirely useless for proper internationalisation. - Bloat. Any statically compiled binary will inherit around ~100k of binary fat bloat when using iostream - Useless encapsulation with error reports done as abstracted bit flags. Which is absolutely horrendous when dealing with file I/O: It hides away the underlying error with no proper way to access it. - Deep class hierarchy making the entire thing looks like spaghetti. - Useless abstraction with stringstream that hides the underlying buffer away, making it close to unusable on embedded safety critical systems where memory allocations are forbidden. All of that made <iostreams> aged pretty badly, and for good reasons. Fortunately there is an incoming way out of that with work of Victor Zverovich on std::format and libfmt [1]. [1]: https://github.com/fmtlib/fmt https://github.com/fmtlib/fmt
- shiroiuma 3y ago>Fortunately there is an incoming way out of that with work of Viktor Zverovich on std::format and libfmt Those are great, but iostreams hasn't been necessary in a very long time thanks to other libraries like Qt and Boost.
- adev_ 3y agoYes. Several alternatives have been available for a while. The success of Victor has been to make the C++ committee accepts the idea that a new formatter was necessary and to bring <format> in the STL. This was not a small task: The committee has its fair amount of dinosaur gatekeepers and windmills [1]. For the best and the worst. We at least now have a way forward to evolve from <iostream> if we want to with maybe one day the hope of getting something that can entirely replace iostream. [1]: Windmills: Person displacing air around but not much more than air.
- DeathArrow 3y agoAnything object oriented is slower than anything procedural. Boxing and unboxing is expensive, running constructors and destructors is expensive, copying objects is expensive, virtual tables are expensive. And stuff isn't aligned greatly in memory, we can expect lots of cache misses and branch mispredictions. The fastest possible way is to have C strings in an array and run a function over it. If there are advantages to OOP, speed is not one of them. Here's a great talk about software speed: https://www.youtube.com/watch?v=pgoetgxecw8 https://www.youtube.com/watch?v=pgoetgxecw8
- JaDogg 3y agoYeah I agree. Can the same be said for functional programming (closures, high order functions, etc)? (not procedural)
- nicbn 3y ago(As with OO) depends heavily on implementation, but my 2 cents is that functional doesn't apply as much constraints to optimization. If a compiler is sophisticated enough a functional program should perform as well as a procedural one that uses a comparable garbage collector. But of course real compilers have shortcomings. I recommend taking a read at Haskell's wiki performance article[1] to have an understanding of the shortcomings that are specific to Haskell. [1] https://wiki.haskell.org/Performance https://wiki.haskell.org/Performance
- xmcqdpt2 3y agoAs they say, closures are the poor man's objects and vis versa. That said, most usage of closures in practice tend to have very little state manipulation -- a closure with 5 mutable fields is weird, an object with 5 mutable fields is "clean code" approved. Also, closures have only one entry point which makes making complex ones much more difficult (you have to implement a state machine or dispatch or whatever.) Standard "design patterns" over-the-top OOP translated to FP would be like passing around collection of closures (one per method) that all alter a big shared mutable state. At that point OOP is definitely going to be faster, but the FP code would be so ugly you wouldn't write it like that to start with.
- assbuttbuttass 3y agoThe best part of C++ is you can ignore all the iostream nonsense and use printf
- neverartful 3y agoAgreed! And not just printf -- any or all of the IO functions.
- olliej 3y agoThe whole C++ stream API is wretched and seems designed to make things clunky, slow, and unnecessarily stateful. Not to mention the wanton abuse of shift operators.