16 ms·
How fast can a BufferedReader read lines in Java?
- adrianN 7y agoSo what's the reason for this? Is it maybe because of some unicode shenanigans? Java characters are 16bit iirc, and strings have some forty bytes of constant overhead.
- d2mw 7y agoI'm no Java ninja, but a few things jump out of https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/19fb8f93c59dfd791f62d41f332db9e306bc1422/src/java.base/share/classes/java/io/BufferedReader.java#L314 https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/19fb8f93c... : - at least one heap allocation for every line. After it finds the EOL it first uses 'new String' followed by '.toString() - the C++ version will almost certainly be backing on to memchr() behind the scenes, which will be using SIMD instructions where it makes sense (e.g. large enough scan size, probably true in this case). the Java version is a manual bytewise-coded loop. - the C++ version is reusing its output buffer, no reallocations assuming the same string length or less No idea about encodings in Java, maybe that is playing a role too
- adrianN 7y agoYes the reuse of the buffer in C++ seems likely and would probably explain a large part of the difference, but I don't know enough of the std::string implementation to be sure about that.
- soup10 7y agothe stringbuffer and string allocation will make it slower for sure, curious what performance the other ways of reading lines in java have
- deleted 7y ago[deleted]
- zlynx 7y agoI haven't looked recently but several years ago I was shocked to discover the GNU libstdc++ didn't use strchr or memchr. It used a hand-coded for loop because it was a template for various kinds of character. There was no specialization for 8-bit char, either. As a result std::string was disgustingly slow compared to C code.
- deleted 7y ago[deleted]
- nitwit005 7y agoThere is a layer of classes, so presumably there are multiple buffers and extra copying. It's also converting the underlying encoding to UTF-16, allocating String objects, and copying the data into them.
- nottorp 7y agoJava is... java. I was once working on an Android app on a cheap custom board with 128 M ram (don't ask why Android on a single function custom board, wasn't my decision). Among other things, I had to parse a 80000 line csv file. Splitting and the rest of the processing created so many temporary strings the system ran out of ram. We eventually gave up.
- cheez 7y agoWhy didn't you just write it using the NDK?
- TheChaplain 7y agoMyself I've worked with gigabyte sized CSV files without issues, so it was likely your implementation rather than the fault of the Java language.
- adrianN 7y agoDid you do it in 128 megs of RAM?
- Zach_the_Lizard 7y agoDepending on what needs to be done with the CSV files, it's very possible to do it in 128MB of RAM. For example, if we need to read the rows, transform them a bit, and then write to another file, we can read up to N rows, transform them, and then write them. That should result in bounded memory consumption because only up to N rows need to be kept. Similar strategies are possible if the rows are used as input to an ETL job, calling a Web service with the results of parsing the file, etc. Editing a file gets trickier, though it's not impossible. Maybe using a [piece table](https://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table) plus some smart buffering the file can keep memory consumption below some constant, letting it function for large files, but with the downside of lower performance for files larger than whatever the constant is?
- deleted 7y ago[deleted]
- derefr 7y agoI don't know what Java's BufferedReader is doing, but it's probably not the optimal thing in terms of IO throughput. I would blame the algorithm long before blaming anything inherent about the JVM. Erlang is another language where "naive" IO is kind of slow. https://github.com/bbense/beatwc/ https://github.com/bbense/beatwc/ is a project someone did to test various methods of doing IO in Erlang/Elixir, and their performance for a line-counting task, relative to the Unix wc(1) command. It's interesting to see which approaches are faster. Yes, parallelism gains you a bit, but a much larger win comes from avoiding the stutter-stop effect of cutting the read buffer off whenever you hit a newline. Instead, the read buffer should be the same size as your IO source's optimal read-chunk size (a disk block; a TCP huge packet), and you should grab a whole buffer-ful of lines at a time, do a pattern-matching binary scan to collect all the indices of the newlines, and then use those indices to part the buffer out as slice references. This achieves quite a dramatic speedup, since most of the time you don't need movable copies of the lines, and can copy the line (or more likely just part of it) yourself when you need to hold onto it. This approach is probably also already built in to Java's "better" IO libraries, like NIO.
- derefr 7y agoI'm reminded to add, in the vein of the author's complaint, that there is a similar ridiculousness in Erlang land, that cannot be circumnavigated so easily: reading/writing to zlib-compressed files using Erlang's file:open(..., [compressed]) option—or generating/parsing zlib-compressed ETF binaries using erlang:binary_to_term(..., [compressed]))—holds [the moral equivalent of†] a global lock. Only one process can be zlib-compressing or zlib-decompressing a chunk of data at once, no matter how many cores your system has. This means that, even when your data set compresses so well that you'd theoretically gain a ton of speed by having the data streamed from disk compressed, and then decompressed during parsing—this doesn't apply in practice, since you're introducing an artificial bottleneck in your IO reads. I'm not actually sure if this is a bug in Erlang, per se, or if it's just the intended behavior and compressed file IO was never intended to be used for performance, only for e.g. embedded devices with tiny ROMs. (If people here think it's a bug, I'll probably go to the effort at some point to profile the performance impact and submit it as a bug on https://bugs.erlang.org. https://bugs.erlang.org.) † What it's actually doing, is that all zlib compression/decompression passes get sent to a zlib "port driver" as messages. Port drivers can handle multiple requests in-flight at once (they're the in-process equivalent to sockets—each Erlang process's port against the port-driver is its own "connection") but the zlib port driver shim is coded to expose zlib as a single-threaded, blocking, request-response style of server, rather than one that accepts connections in parallel and instantiates a separate zlib context for each separate connection it receives.
- znpy 7y agoThe post does nothing to explain how and why, it just throws a couple of outputs from a non specified machine and does no comparison. It has no baseline and no specs. For all I know, he could have got his 0.5 GB/sec on ab old Pentium II processor. There is no analysis. I am perplexed.
- aristus 7y agoLemire is one of the leading experts on string matching and the author of several core libraries you probably use every day. edit fine, so instead maybe click on the links in the post to see that this article is just one of a series. He's probably tired of copy-pasting the specs of his reference hardware (Skylake https://arxiv.org/pdf/1902.08318.pdf https://arxiv.org/pdf/1902.08318.pdf) since all he's concerned about is the relative performance of different software. There is a difference between "I'm being dumb because I don't know what I'm doing" and "I'm being lazy because I've done it 1,000 times and the target audience knows what I mean".
- adrianN 7y agoThen they should know enough to give at least some theories that can explain the difference and tell us something more about the test setup.
- deleted 7y ago[deleted]
- saagarjha 7y agoThat doesn’t excuse him from needing to describe the hardware he ran the benchmark on.
- phkahler 7y agoIt should be sufficient to state that it was the same hardware as the C++ measurement. He didnt even say that but it seemed implicit to me.
- nullwasamistake 7y agoEh, he didn't use NIO. BufferedReader is an ancient Java relic. Like reading from STDIN in c, it's not made to be fast, it's there for convenience and backwards compatibility. Read a file using something like Vert.X, which is optimized for speed. I'm 100% confident it will be faster than the naive c approach
- egwor 7y agoDo you have a quick github project example?
- nullwasamistake 7y agoSorry, I'm too lazy to create a throwaway GitHub repo. I make way too many flamey and policital comments to tie my real name to HN posts :-/
- djhworld 7y agoDo you have example of alternatives for the BufferedReader with the NIO APIs? I do a lot of work with large GZIP that are read line by line using the standard IO (i.e. GzipInputStrem(FileInputStream)) etc) but your comment has really made me second guess my choice of doing that...
- _old_dude_ 7y agoThe NIO API uses channels and buffers Path path = ... var count = 0; try(var channel = FileChannel.open(path)) { var buffer = ByteBuffer.allocateDirect(8192); while(channel.read(buffer) != -1) { while(buffer.hasRemaining()) { if (buffer.get() == '\n') { count++; } } buffer.clear(); } } System.out.println(count); but in your particular case, i don't think there is a Gzip decoder that works on ByteBuffer.
- nullwasamistake 7y agoI would check out the compression handlers in Netty, which underlies Vert.X and many other projects that need high IO performance. You should be able to hack something together that feeds zero copy buffers into Netty compression handler. Maybe using Netty or Vert.X file API, or maybe just raw NIO2. I'm not sure how fast this would be, but my gut says "very". Netty can easily saturate 40 Gigabit Ethernet lines, and file IO should have less overhead. That's ~5 gigabytes a second. It's going to be a good bit of coding for sure. Vert.X/Netty/NIO2 are all async and pretty low level. They're generally 1 thread per core, and along with SSD read patterns you're probably best off reading files in parallel, one per core. Might not be worth the effort. You may want to look into ZStandard as well. It's Superior to Gzip in most ways when you need something fast but decent.
- jnordwick 7y agoImpressive bad for a professor. Even worse for someone who says on their page "I like crazy fast code." He certainly doesn't seem to know how to produce it (or if you believe he does - he's being intentionally obtuse or lazy). Using the simplest, slowest, oldest method to read as file line by line from a time when there wasn't such a thing a high performance Java (trading systems are built in Java that rival c++ performance), then complaining about the performance. It is probably mostly in the GC and copying. Each call to readline is going to new off a string and copy into it. Also the conversion from bytes to string needs to go through a Unicode conversion and check with probably another copy in there somewhere. I wouldn't be surprised if bufferedreader did some more allocations and copying too. Some of the Java libraries especially from early Java aren't implemented for performance but for simplicity. Java probably has the most readable standard library of any language. He should reimplement it as a byte buffer with nio channel. For all of Java's good points, it's standard library can really suck for performance ever though hotspot can produce excellent code and it doesn't need to be that way. I've seen huge systems that never GC or have a scheduled GC once a week. If you take his class, go ask the university for your money back. Hopefully her puts more effort into thanks, but I doubt it.
- zaphar 7y agoAlternatively if you took his class then you you probably learned that BufferedReader is not the most performant way to read lines from IO and probably learned the correct alternatives. If you work at some of the places java commonly gets used then you'll see BufferedReader all over the place. This article isn't a critique of Java. It's a warning about BufferedReader. If you do high performance java you'll be hiring exceptional java engineers who will not be using BufferedReader and you won't have this problem. If you are a run of the mill java shop you probably don't work with code that isn't using BufferedReader and this article is for you when you are debugging a pathological performance problem that suddenly reared it's head in production. This professor seems like a good one to me.
- tom_mellior 7y agoIf the article's point was that better alternatives exist, it should have made that point by mentioning those better alternatives and ideally benchmarking them as well. I agree with others that this particular article comes across as very lazy and not up to Lemire's usual standard.
- tantalor 7y agoOne thing that jumps out at me is the test code writes to "volume" variable in the read loop, I assume for counting the number of bytes in the file, but never reads it back. A clever compiler will optimize away those writes, the string length check, the loop over the lines, and actually reading the file. I'm not saying that's happening here, but it's a basic fact when writing benchmarks that you have to actually test something real and not a transient property of the program after the compiler has had its chance to be really smart.
- elFarto 7y agoThe first issue I can see with that code is it's not doing what he expects. He does this to read the file into a StringBuffer: bf.lines().forEach(s -> sb.append(s)); However, this ends up reading all the lines into one giant line, since the String's that lines() produces have the newline character stripped. This leads to the second lines() call to read a 23MB line (the file produced by gen.py). This is less than optimal. The fastest version I managed to write was: public void readString5(String data) throws IOException { int lastIdx = 0; for (int idx = data.indexOf('\n'); idx > -1; idx = data.indexOf('\n', lastIdx)) { parseLine(data.substring(lastIdx, idx)); lastIdx = idx+1; } parseLine(data.substring(lastIdx)); } Not the prettiest thing, but it went from 0.594 GB/s to 1.047 GB/s. Also, it doesn't quite do the same as the lines() method, but that's easily changed.
- ricardobeat 7y agoThat's a pretty big error if you're correct. What does it say about the language when a CS professor falls for this on a 40 line file?
- bhaak 7y agoGetting benchmarks right is difficult, even for a CS professor. The language doesn't even enter there. What does it say about you that you're asking a leading question in this way?
- ricardobeat 7y agoI'm always interested in thoughts about language design and programming in general. We have fifty+ years of commercial software development and it still sucks. This caught my eye as the kind of error that shouldn't even be allowed to happen.
- bhaak 7y agoThere are several simple data transformation steps. There's nothing inherently wrong with these steps. The compiler can't read your mind and guess what you wanted to do. How would this be possible to be prevented with any programming language, existing or hypothetical? Even if the meta information that the appended string doesn't contain any newlines would be passed on, the second call to lines() would rather use is as an optimization hint instead of raising an error.
- ubu7737 7y agoThis is absurd, the original platform libraries do not account for the fastest use-cases in any specialized IO case. Java NIO channel should have been used for this. It was demonstrated back in the early 2000s with the "Grand Canyon" demo achieving very good throughput for its time, and it's still the gold standard.
- tawy12345 7y agoI'm amazed at how upset some commenters are about a blog post that did a toy experiment and didn't actually make any strong claims. I'm actually a stickler about good benchmarks - it riles me when people draw sweeping conclusions from poorly-designed experiments. Lemire is actually one of the good ones. If you want something more fully developed than a blog post, read one of his papers. I personally really enjoy his blog because of this - he's good at picking interesting exploratory experiments that provide some insight, without trying to over-generalize from the results. If you read his conclusion, the point is that there is a good probability that even relatively simple programs are CPU-bound. His experiment supports that point. My experience also matches that - I've seen a lot of data processing code that could be I/O bound in theory (i.e. a perfect implementation could max out CPU or network) but is CPU bound in practice. Usually because of string manipulation, regexes, or any number of other things. > This is not the best that Java can do: Java can ingest data much faster. However, my results suggest that on modern systems, Java file parsing might be frequently processor-bound, as opposed to system bound. That is, you can buy much better disks and network cards, and your system won’t go any faster. Unless, of course, you have really good Java engineers.
- jnordwick 7y agoI can make a lot of things cpu bound with crappy implementation. I'm not going to write a blog post about any of them.
- Sindisil 7y agoHonestly, it seems that nearly everyone here is missing his point. Some of the blame for that probably lies with his headline choice, but he clearly states at the end of this post: """ This is not the best that Java can do: Java can ingest data much faster. However, my results suggest that on modern systems, Java file parsing might be frequently processor-bound, as opposed to system bound. That is, you can buy much better disks and network cards, and your system won’t go any faster. Unless, of course, you have really good Java engineers. Many firms probably just throw more hardware at the problem. """ It's not about this piece of code. It's not even about Java In the previous post he mentions at the start of this one, he pointed out: """ These results suggest that reading a text file in C++ could be CPU bound in that sense that buying an even faster disk would not speed up your single-threaded throughput. """ So, I take his point to be that one shouldn't make assumptions about performance. Rough performance scales -- such as have been posted here many times (e.g. [1]) -- make great rules of thumb for implementation choices or as a guide for where to look first for bottlenecks. To optimize in the real world, though, you're best served using real measurements. [1] https://www.prowesscorp.com/computer-latency-at-a-human-scale/ https://www.prowesscorp.com/computer-latency-at-a-human-scal...
- deleted 7y ago[deleted]
- pjmlp 7y agoCompletely wrong. It is like asserting something about C based on GCC specific behaviour. Java is not a single language implementation.
- tom_mellior 7y agoAgreed. I think you are being downvoted because you forgot to paste in your benchmark results.
- pjmlp 7y agoYeah, I forgot that we aren't allowed to have opinions without doing the hard work. So now I have to go out and do benchmarks across all these implementations just to prove they aren't the same?!? https://en.m.wikipedia.org/wiki/List_of_Java_virtual_machines https://en.m.wikipedia.org/wiki/List_of_Java_virtual_machine...
- IloveHN84 7y agoBut all the stream API isso terribile for performance..you write a one line code and you are already at O(n^5)
- chvid 7y agoAt least two problems with the java code. Concatenation of strings using the plus operator creates a new string and copies the content of the old, that pushes the complexity of the code from o(n) to o(n2) where n is the number of lines. Secondly order is not guaranteed with the for each operation on streams. The correct way to do it is using collect(Collectors.joining(“\n”)) or straight forward imperative style (without streams). I don’t think the general statement holds (that java or buffered reader is cpu bound in particular).
- vbezhenar 7y agoJava has many inefficient parts. For example there's no immutable array concept (or owning concept, like in Rust), so there's a lot of unnecessary array copies happens in JDK. String is not well designed. There was an attempt to abstract String concept into CharSequence, but a lot of code still uses Strings. I made a similar benchmark. The idea is as follows: we have 2 GB byte array (because arrays in Java have 32 bit limit, LoL) filled with 32..126 values, imitating ASCII text and 13 values imitating newlines. The first test is simply does XOR the whole array. It's the ideal result which should correspond to memory bandwidth. The second test wraps this array into ByteArrayInputSteram, converts it into Reader using InputStreamReader with UTF-8 encoding, reads lines using BufferedReader and in the end also XORs every char value. For 2 GB I have 516 ms as an ideal time (3,8 GB/s which is still almost order of magnitude less than theoretical 19.2 GB/s DDR4 speed) and 3566 ms as a BufferedReader, so you can have almost 7x speed improvement with better implementation. Benchmark: https://pastebin.com/xMD4W8mn https://pastebin.com/xMD4W8mn
- barbarbar 7y agoI am a bit confused. The scanFile reads from a file. But the readLines inside the for loop is reading from a StringReader - and not from a file?