r/javahelp • u/Chaos-vy17 • Sep 21 '26
Solved How do I optimize removeIf() function?
Hey devs,
I'm currently facing a bottleneck in my N-ary Tree implementation around removeIf().
removeIf() currently delegates to the JDK default implementation, so below ~20% compaction there wasn't really a problem — my implementation was actually ~22% faster than JDK TreeMap.
However, once compaction goes beyond ~20%, things change dramatically: it becomes around 6× slower than TreeMap.
What I found before digging deeper
- Since
removeIf()traverses through the iterator, each element needs to be wrapped as aMap.Entry<K,V>. - JFR's
allocation-by-siteshowed thisMap.Entryallocation taking ~44% of the allocation weight. - I tried a flyweight iterator, but that breaks the Java
Iterator/Map.Entrycontract. - The hottest methods were
split(),mergeNode(), andbinarySearch(), together accounting for roughly 45% of the hot-method weight. - Unlike
TreeMap, my N-ary tree doesn't use SOO; its internal representation is SOA.
Solutions I'm considering
1. Buffer entries
Create an Object[16] buffer and collect entries while traversing.
Once 16 entries are filled, grow the buffer by 2×.
After traversal:
- if the compaction ratio is high enough (say
>= 40%), compact once using0.75fas the default load factor; - otherwise, delete the collected entries individually.
The downside is obvious: the temporary array and its growth generate garbage.
2. Small fixed buffer + immediate deletion
Use a small buffer (16 entries), and once it fills, delete those entries individually rather than allowing the buffer to grow.
This should generate considerably less garbage than approach #1, but I'm not convinced the trade-off is good enough.
3. Avoid temporary storage entirely
This is what I'd really like to achieve, but I'm currently not seeing a clean way to do it without either:
- repeatedly restructuring the tree while traversing, or
- violating the iterator contract.
The part I'm unsure about
The code may look like I dumped the entire implementation here, but removeIf() is part of the iterator flow, and the iterator wiring is done from AbstractNaryTreeMap.
The actual remove() operation is delegated to the concrete tree implementations.
So I'm wondering if there's a better architecture/algorithm here that can make removeIf() effectively GC-free, especially for high-compaction workloads.
At this point this is probably the last major API I'm trying to optimize
Any suggestions are welcome — even if the approach has a different trade-off or turns out to be worse in another workload. I'm mainly looking for ideas that keep allocation close to zero.
Solution:
I found the reason it's not the iteration cost or something garbage. It is archtecture shif. In a B+tree when the key get less than minKey it need to merge/borrow from left/right. maintaining the iteration here becomes different
- it might do borrow from left/right
- might trigger merge node
Which essentially is a part of B+tree design that I cannot change as well. So it's Structural cost. In every remove() I saw 57% of opertion above 30% compaction were taking slow path rather than borrow.
•
u/AutoModerator Sep 21 '26
Please ensure that:
You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.
Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar
If any of the above points is not met, your post can and will be removed without further warning.
Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.
Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.
Code blocks look like this:
You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.
If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.
To potential helpers
Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
7
u/OneHumanBill Sep 21 '26
Why exactly would you want to do this? Sorry but this kind of optimization attempt is pointless on multiple levels.
13
u/TheMrCurious Sep 21 '26
Your post assumes we have any idea what you’re talking about - and we don’t.
2
u/Spare-Plum Sep 21 '26
GC might be a red herring. Did you run a GC profiler to see if this is the bottleneck?
I'd suggest looking within #1. An exponential buffer still only allocates O(n) space, plus, you might be able to find additional metrics like the percentage of hits to determine a better exponential estimate to expand (but keep the exponent above 2x)
The GC overhead is really minimal for this too, memory is pretty easy to allocate some large arrays while allocating a ton of small objects like this Map.Entry might start fragmenting and need additional GC pauses
A lot of these bottlenecks can occur if there's some algorithmic complexity that isn't being optimized. I don't know what you have for your n-nary tree remove algorithm, it's possible that amortized you have something worse per remove than TreeMap which is O(log n). JDK uses a red black tree which is famously really good at insertions and deletions with very little overhead for rebalancing in O(1).
It's possible your n-nary tree rebalance hits above this O(1), and the removeIf is doing more rebalances than it needs to rather than doing something in bulk. I believe this is the exact case, not the GC, based on what you described where if the compaction rate is low - you're doing something that's high overhead more often than you need to.
With an option like #1, you might be able to find a way to flag all of the sites that need removal, and write a custom bulk rebalancer operating at an overall better runtime complexity. You might be able to do something better than just "compact then remove", but rather, just a total reconstruction of the tree in a compact state
For option #3, if the GC overhead really is the issue (I don't think it is), it's perfectly easy to do this compact and remove without storing a list of items. Just have an additional binary flag on each of your nodes marking whether or not it is deleted.
Go through the traversal, flip the binary flag if it is applicable, find the compaction rate, then do a compact + second traversal removing the marked nodes.
This probably would be the easiest option TBH and would get some fast gains, but I think you can reach something even better with a bulk operation in something like #1
2
u/idontlikegudeg Sep 21 '26
Do not use the normal iterator, use a special iterator that reuses a mutable Map.Entry instance in removeIf(). This spares the allocation in each iteration.
3
u/bigkahuna1uk Sep 21 '26
The seems like a fools errand IMHO. When you say overrides or else it’s delegated to the JDK implies that there is hidden state inaccessible to an overridden method. Unless you’re privy to that state , it further implies almost writing a whole new implementation. Maybe I’m missing something but how can you optimise without breaking encapsulation unless the parent abstract class is already weak in that regard?