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

Activity

Show:
Alex Miller
December 20, 2017, 8:23 PM

I assume this came out of some actual usage with surprising behavior?

Ben Bader
December 20, 2017, 10:44 PM

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!

Andy Fingerhut
December 21, 2017, 1:34 AM

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.

Ben Bader
February 9, 2018, 10:54 PM

Hi, is there anything I can or should to to move this forward?

Alex Miller
February 12, 2018, 2:47 PM

Nope. We batch up tickets to look at them periodically.

Completed

Assignee

Unassigned

Reporter

Ben Bader

Labels

Approval

Ok

Patch

Code

Fix versions

Affects versions

Priority

Critical
Configure