The problem is in `PersistentHashMap.BitmapNode#without(Object)`; when the last value is removed, an empty BitmapNode is returned instead of null. This has knock-on effects in large maps that have interior ArrayNodes, which themselves are not preserved.
Attached is a test script that demonstrates the issue, by measuring heap usage, adding a large number of entries to a map, removing those keys one-by-one, then comparing heap usage afterwards. The output, shows the average amount of heap allocated for an empty map that has had 100,000 entries added then removed:
❯ java -jar clojure.jar demo-phm-leak.clj
Avg. heap:8656352/5 bytes
Avg. heap:8656632/5 bytes
Avg. heap:8654664/5 bytes
Avg. heap:8656884/5 bytes
Avg. heap:1731156 bytes
This was from my a Macbook Pro, running a self-made Clojure built from master, using java 1.8.0_65. The variable sizes are due to the fact that the shape of the PHM tree depends on the insertion order of keys, which is randomized in this script.
Screened by: Alex Miller - The case in question is when bit (the lookup index &'ed with the bitmap) == bitmap (the full bitmap), that means that the only key in this node is the one being removed, in which case the node can be removed (by returning null). Repro'ed benchmark before and after.
I assume this came out of some actual usage with surprising behavior?
It came up when I was profiling a service that uses maps in agents to cache things; overall memory usage seemed high, and I got curious. Hard to say whether this would ever noticeably impact a production system, given that this behavior has been in place for nine years!
Cool find. It looks like an average of 1.7 bytes of unreclaimed space per 'without' operation in your test case, so nice to improve upon, but perhaps not something people would notice due to it causing problems very often.
Hi, is there anything I can or should to to move this forward?
Nope. We batch up tickets to look at them periodically.