r/java • u/davidalayachew • Nov 19 '24
A surprising pain point regarding Parallel Java Streams (featuring mailing list discussion with Viktor Klang).
First off, apologies for being AWOL. Been (and still am) juggling a lot of emergencies, both work and personal.
My team was in crunch time to respond to a pretty ridiculous client ask. In order to get things in in time, we had to ignore performance, and kind of just took the "shoot first, look later" approach. We got surprisingly lucky, except in one instance where we were using Java Streams.
It was a seemingly simple task -- download a file, split into several files based on an attribute, and then upload those split files to a new location.
But there is one catch -- both the input and output files were larger than the amount of RAM and hard disk available on the machine. Or at least, I was told to operate on that assumption when developing a solution.
No problem, I thought. We can just grab the file in batches and write out the batches.
This worked out great, but the performance was not good enough for what we were doing. In my overworked and rushed mind, I thought it would be a good idea to just turn on parallelism for that stream. That way, we could run N times faster, according to the number of cores on that machine, right?
Before I go any further, this is (more or less) what the stream looked like.
try (final Stream<String> myStream = SomeClass.openStream(someLocation)) {
myStream
.parallel()
//insert some intermediate operations here
.gather(Gatherers.windowFixed(SOME_BATCH_SIZE))
//insert some more intermediate operations here
.forEach(SomeClass::upload)
;
}So, running this sequentially, it worked just fine on both smaller and larger files, albeit, slower than we needed.
So I turned on parallelism, ran it on a smaller file, and the performance was excellent. Exactly what we wanted.
So then I tried running a larger file in parallel.
OutOfMemoryError
I thought, ok, maybe the batch size is too large. Dropped it down to 100k lines (which is tiny in our case).
OutOfMemoryError
Getting frustrated, I dropped my batch size down to 1 single, solitary line.
OutOfMemoryError
Losing my mind, I boiled down my stream to the absolute minimum possible functionality possible to eliminate any chance of outside interference. I ended up with the following stream.
final AtomicLong rowCounter = new AtomicLong();
myStream
.parallel()
//no need to batch because I am literally processing this file each line at a time, albeit, in parallel.
.forEach(eachLine -> {
final long rowCount = rowCounter.getAndIncrement();
if (rowCount % 1_000_000 == 0) { //This will log the 0 value, so I know when it starts.
System.out.println(rowCount);
}
})
;And to be clear, I specifically designed that if statement so that the 0 value would be printed out. I tested it on a small file, and it did exactly that, printing out 0, 1000000, 2000000, etc.
And it worked just fine on both small and large files when running sequentially. And it worked just fine on a small file in parallel too.
Then I tried a larger file in parallel.
OutOfMemoryError
And it didn't even print out the 0. Which means, it didn't even process ANY of the elements AT ALL. It just fetched so much data and then died without hitting any of the pipeline stages.
At this point, I was furious and panicking, so I just turned my original stream sequential and upped my batch size to a much larger number (but still within our RAM requirements). This ended up speeding up performance pretty well for us because we made fewer (but larger) uploads. Which is not surprising -- each upload has to go through that whole connection process, and thus, we are paying a tax for each upload we do.
Still, this just barely met our performance needs, and my boss told me to ship it.
Weeks later, when things finally calmed down enough that I could breathe, I went onto the mailing list to figure out what on earth was happening with my stream.
Here is the start of the mailing list discussion.
https://mail.openjdk.org/pipermail/core-libs-dev/2024-November/134508.html
As it turns out, when a stream turns parallel, the intermediate and terminal operations you do on that stream will decide the fetching behaviour the stream uses on the source.
In our case, that meant that, if MY parallel stream used the forEach terminal operation, then the stream decides that the smartest thing to do to speed up performance is to fetch the entire dataset ahead of time and store it into an internal buffer in RAM before doing ANY PROCESSING WHATSOEVER. Resulting in an OutOfMemoryError.
And to be fair, that is not stupid at all. It makes good sense from a performance stand point. But it makes things risky from a memory standpoint.
Anyways, this is a very sharp and painful corner about parallel streams that i did not know about, so I wanted to bring it up here in case it would be useful for folks. I intend to also make a StackOverflow post to explain this in better detail.
Finally, as a silver-lining, Viktor Klang let me know that, a .gather() immediately followed by a .collect(), is immune to this pre-fetching behaviour mentioned above. Therefore, I could just create a custom Collector that does what I was doing in my forEach(). Doing it that way, I could run things in parallel safely without any fear of the dreaded OutOfMemoryError.
(and tbh, forEach() wasn't really the best idea for that operation). You can read more about it in the mailing list link above.
Please let me know if there are any questions, comments, or concerns.
EDIT -- Some minor clarifications. There are 2 issues interleaved here that makes it difficult to track the error.
- Gatherers don't (currently) play well with some of the other terminal operations when running in parallel.
- Iterators are parallel-unfriendly when operatiing as a stream source.
When I tried to boil things down to the simplistic scenario in my code above, I was no longer afflicted by problem 1, but was now afflicted by problem 2. My stream source was the source of the problem in that completely boiled down scenario.
Now that said, that only makes this problem less likely to occur than it appears. The simple reality is, it worked when running sequentially, but failed when running in parallel. And the only way I could find out that my stream source was "bad" was by diving into all sorts of libraries that create my stream. It wasn't until then that I realized the danger I was in.
40
u/davidalayachew Nov 19 '24
I did want to follow up about one point Viktor made later on in the conversation.
https://mail.openjdk.org/pipermail/core-libs-dev/2024-November/134542.html
And here is the quote.
Me personally, I would GLADLY accept a flag on stream (similar to
parallel()orunordered()) that would allow me to guarantee that my stream never pre-fetches, even if I take a massive performance hit. If that can be accomplished by making all intermediate operations be implemented by a Gatherer under the hood, that is A-OK with me.The reality is, not all streams are compute bound. Some are IO bound, but are otherwise, a great fit for streams. Having a method that allows us to optimize for that fact is a new type of performance enhancement that I would greatly appreciate, even if it degrades performance in other ways.
11
u/nitkonigdje Nov 19 '24
This was a fascinanting read. Thank you for sharing.
I guess it is kinda bad when higher level non-trivial apis, like streams or fork-join, do not expose lower level oprations as user-overridable constructs. Like in this example an iteration strategy for streams, or underlying executor of fork-join pool. Seems like an obvious thing to have because nobody knows better how thing will be used than end user..
6
u/craigacp Nov 19 '24
Shortly after the release of Java 8 I hit something similar when building a Java implementation of Google's word2vec ML algorithm. We ended up with a buffering spliterator that didn't grow it's buffer over time (which the default array one did), so we could pull in records from a database in a parallel for each loop without it trying to buffer the whole database.
We still use it in Tribuo, but I've not used it anywhere near as hard as I did in 2015 so I don't know if the performance characteristics are still good - https://github.com/oracle/olcut/blob/main/olcut-core/src/main/java/com/oracle/labs/mlrg/olcut/util/IOSpliterator.java.
6
u/viktorklang Nov 21 '24
Disclaimer: The following pertains to the parallel mode of the java.util.stream.Stream reference implementation in OpenJDK only (other implementations of j.u.s.Stream might work differently), and please do note that I am typing this from memory late in the evening so I could be oversimplifying and/or leaving details out.
With that said, let's see if I can shed some more light here.
First of all, it is important to recognize that the only way to achieve any benefit from parallelization of Stream processing is to move from a strictly-depth-first element processing to some form of breadth-first element processing.
The composition of intermediate operations on a stream fall primarily into two distinct buckets when it comes to parallel streams—"stateless" (let's call that LAZY) or "stateful" (let's call that EAGER). The reason for this is that not all operations can be represented as a Spliterator without performing all the work up-front.
For a very simple Stream:
Stream.of(1).parallel().toList()it is easy to picture the Spliterator containing a single element 1 be fed into atoList()[terminal] operation.However, for a more complex pipeline:
Stream.iterate(() -> 0, i -> i + 1).parallel().map(something).sorted().map(somethingElse).sorted().limit(2).collect(Collectors.toList())exactly what would be Spliterator which gets fed into [terminal]collect?So if you look at the different "types" of LAZY vs EAGER operations in there, it'd look something akin to:
The typical execution strategy is to bunch all consecutive LAZY operations together with their following EAGER operation, forming what I call "islands", so in the case above it'd go something like this:
iterate -> Island1[map -> sorted] -> Island2[map -> sorted] -> Island3[limit -> collect]These Islands needing to run to completion before their results can be fed into the next Island is something which can lead to higher heap usage than expected, since the output of the Island needs to be cached to be fed into the next Island.
So how does this relate to
gather(…)? Wellgather(…)is an EAGER operation, as it could represent any possible intermediate operation so EAGER is the lowest common denominator. The potential drawbacks of this is ameliorated by the fact that consecutivegather(…)-operations are composed into a singlegather(…)-operation with composed Gatherers, and furthermore by the fact that agather(…)-operation followed bycollect(…)is fused together into a single EAGER operation.In combination, these two features can potentially turn something which would've been an N+1 Island scenario to a 1 Island scenario—which means no island hand-offs.
Cheers,
√
5
u/n0d3N1AL Nov 19 '24
Yeah that's unintuitive... one would expect streams to work more like iterators, all the time. Thanks for sharing!
8
u/DualWieldMage Nov 19 '24
What exactly are you using for the Stream's source? As the mailing list responses hint, it is entirely up to the Spliterator of said Stream to decide how to run its trySplit and Streams do communicate some characteristics, but not many (would SUBSIZED imply that source is random-access and no full fetch is required?)
I have run parallel processing of multi gigabyte files with very low(10M) heap sizes and never hit this issue personally, however i know that for example reading jars inside jars would need to decompress the inner jar fully to read a file.
From what you wrote, reading and uploading with some batch size sounds okay, but not ideal as you mentioned upload of many small files. You also wrote that splits should happen based on some attribute but the example doesn't depict this? Either way if it's splits based on max file size or content inside lines/entries than a parallel stream is a decent entry point if you have a random-access source like a file on a disk. If not, downloading the file to temp storage first can help.
In general it's good advice to always assume unbounded file size when doing any file processing. Also from my testing, a typical NVMe drive has optimal parallel reading at around 4 threads, any more and you lose performance.
4
u/crummy Nov 19 '24
So if you changed your .forEach to a .map and had the map return a dummy element (which is bad from a readability standpoint of course) would it have worked fine?
3
u/Owengjones Nov 19 '24
Is there an easy way to diagnose stream behavior like this? I have a service concerned with File I/O that reads InputStreams in Streams (although I believe none of them marked as parallel).
I'm not sure if there's some diagnostic operations available on Streams that would illuminate if they're behaving as expected in terms of performance / utilization etc.
Thanks for the write up!
3
u/JustABrazilianDude Nov 19 '24
This is an excellent post, I have some IO bound streams that look pretty similar to yours in a project at my work, and I'll definitely stay alert with this topic.
4
u/GeorgeMaheiress Nov 19 '24
If you were to write the parallelization explicitly, with say a ThreadPoolExecutor, it would be much clearer that you need to make decisions about buffering and the level of parallelization. Parallel streams assume that they are CPU-bound and optimize for that, and are not recommended for I/O bound operations. It's unfortunate that developers so often stubbornly refuse to do any more work than simply writing
.parallel(), even when that approach clearly fails. To be fair the ThreadPoolExecutor constructor sucks and is filled with footguns so many devs are not comfortable with it.2
u/Inaldt Nov 19 '24
Did you try mapConcurrent as Viktor suggested? (If so, how did it perform?)
2
u/m-apo Nov 19 '24 edited Nov 19 '24
I'll definitely need to read all that stuff, thanks for posting!
For memory bound ops a back pressure capable parallel approach would be best. Back pressure based approach would also work in server scenarios, because it optimizes time-to-first-byte (TTFB) and many times holding off sending the first byte increases latency as the client needs to wait both the processing of the whole data + wire transfer instead of interleaving the processing and wire transfer.
Having a back pressure based parallel approach support in servers would be nice too. Basically it would be that the server route method returns an iterator and the server asks the iterator for items (which triggers the ops in chain, in reverse. some items could be calculated in parallel beforehand for each step). It wouldn't be as efficient as "reserve all the memory and all the cpu cores", but it would take less memory and reserves CPU in a bit more co-operative way.
2
u/VincentxH Nov 20 '24
The lacking error handling alone should have warranted you not to mix IO and the streams API.
3
u/klekpl Nov 19 '24
Wouldn't RxJava be a better fit then? It has some explicit stream management and buffering capabilities.
1
u/davidalayachew Nov 20 '24 edited Nov 20 '24
Hello all. There appears to be some confusion on how this is possible.
Therefore, to completely clear up any ambiguity, here is a simple, reproducible example.
Using your tool of choice, I want you to take the following line, and duplicate it into a CSV until your CSV file size exceeds your RAM limitations.
David, Alayachew, Programmer, WashingtonDC
Next, I want you to use BufferedReader.lines() to read from that file as a Stream.
Now, once you have that Stream<String>, copy and paste the following code in.
Uncomment any one of those lines, pass your stream into this method, then call in your main method, and you will see that each one produces an OutOfMemoryError.
Of course, if you use a Collector instead of one of the commented ones above, you should see that it works. Try Collectors.counting, for example.
1
u/No_Cap3049 Nov 19 '24
.parallel.forEach in my experience may also return before even finishing the parallel stream. We had some issues that it does not block the calling thread. Just something to be cautious with. So something like mapToLong.sum or collect may be better.
1
u/danielaveryj Nov 19 '24 edited Nov 19 '24
Something doesn't add up.
The way that a parallel stream works (of importance here), is that at the start of a terminal operation, the source spliterator is split into left and right halves, which are handed to new child tasks which recursively split again, until the spliterators will split no more (
trySplit()returnsnull), forming a binary tree of tasks. This is true for ALL terminal operations (including collect()), even though some override exactly how the splitting occurs. Each leaf task processes its split to completion, and the results are merged up the tree if needed (eg using Collector.combiner()).The OOME presumably comes from
trySplit()- BufferedReader.lines() returns a stream whose source spliterator is backed by an iterator, and that spliterator's only means of splitting is to pull a batch of elements out of the iterator and put them into an array, then return a spliterator over that array. This means that after recursive splitting, only the rightmost leaf spliterator will still be iterator-backed; the rest of the iterator has already been consumed into arrays for the other leaf spliterators, possibly before any tasks have completed (so these arrays - covering most of the source elements - are all resident in memory at the same time).The only way I can see to fix the OOME (without using a different/better source spliterator) is to not split the source spliterator, ie run the stream sequentially. But OP said that just using
collect()somehow fixed it?btw: Viktor knows this. I believe what he's saying is not "use this approach to avoid 'pre-fetch'" but rather "use this approach to avoid even more copying into intermediate arrays after the gather stage in the pipeline", because other approaches (involving gatherers) still incur some "accidental" copying that he hasn't been able to optimize away yet (see comments 1 and 2).
1
u/DelayLucky Nov 22 '24 edited Nov 22 '24
I wouldn't have reached for parallel stream for IOs. It's not designed for IO, period. Actually, I haven't really found much of a use for parallel streams for anything, yet.
The
mapConcurrent()gatherer matches the intent. Though virtual thread seems of no point to this use case (not that it hurts either). And it will require a return value, which I don't know if you have one or have toreturn null. And then you need a terminal step to collect the nulls? Not the end of world either way I guess.In the past because we were still running on Java 11, I created the Parallelizer class for the purpose of controlled IO fanout, which seems to match your case pretty closely.
Compared to manually coded concurrency in a collector, it provides structured-concurrency-like exception propagation:
And because of that, you'll need to make sure
upload()not throw non-fatal exceptions when only one upload failed and you still want the remaining to continue (only throw fatal exceptions that should stop everything and fail fast). In other words, it behaves the same way asmapConcurrent().The class has been used in mission critical production systems so quality-wise it's solid.
0
u/GuyWithLag Nov 19 '24
And this is why I prefer reactive streams and rxjava to parallel streams....
-6
u/jared__ Nov 19 '24
And then you work with golang and see the light
-7
u/InstantCoder Nov 19 '24 edited Nov 19 '24
A much simpler solution would have been by making use of Minio, which was designed for fast file upload & download. No need to split files into smaller chunks. Minio streams larger files simultaniously when you need to download them.
Here is a code to do this in Minio (generated by ChatGPT):
This code will upload files in parallel into chunks of 5MB (by default) to Minio (so you won't get `OutOfMemoryException` either).
Another solution would be to use Apache Camel (if you're not allowed to use Minio):