Affects Version/s: Release 1.7, Release 1.8, Release 1.9
Fix Version/s: None
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.