We're updating the issue view to help you get more done. 

PersistentHashMap leaks memory when keys are removed with `without`

Description

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.

Patch: fix-bitmapnode-without.patch

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.

Environment

None

Status

Assignee

Unassigned

Reporter

Ben Bader

Labels

Approval

Ok

Patch

Code

Fix versions

Affects versions

Release 1.8
Release 1.7
Release 1.9

Priority

Critical