Clojure

PersistentHashMap leaks memory when keys are removed with `without`

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Critical Critical
  • Resolution: Completed
  • Affects Version/s: Release 1.7, Release 1.8, Release 1.9
  • Fix Version/s: Release 1.10
  • Component/s: None
  • Labels:
  • Patch:
    Code
  • Approval:
    Ok

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.

Activity

Hide
Ben Bader added a comment -

This patch fixes the leak by changing `BitmapNode#without(Object)` such that, when there are no other values in the node, the method returns `null` instead of an empty BitmapNode.

Output from the demo script, from a Clojure build incorporating the patch:

~/Development/clojure collapse-empty-mapnodes* 16s
❯ java -jar clojure.jar demo-phm-leak.clj
Avg. heap:64 bytes
Avg. heap:64 bytes
Avg. heap:64 bytes
Avg. heap:64 bytes
Avg. heap:64 bytes

Show
Ben Bader added a comment - This patch fixes the leak by changing `BitmapNode#without(Object)` such that, when there are no other values in the node, the method returns `null` instead of an empty BitmapNode. Output from the demo script, from a Clojure build incorporating the patch: ~/Development/clojure collapse-empty-mapnodes* 16s ❯ java -jar clojure.jar demo-phm-leak.clj Avg. heap:64 bytes Avg. heap:64 bytes Avg. heap:64 bytes Avg. heap:64 bytes Avg. heap:64 bytes
Hide
Ben Bader added a comment -

Note that this patch doesn't have a similar change for the transient overload of `without`; because it relies on a helper method `editAndRemovePair` that correctly handles the empty case, that method doesn't have this bug.

Show
Ben Bader added a comment - Note that this patch doesn't have a similar change for the transient overload of `without`; because it relies on a helper method `editAndRemovePair` that correctly handles the empty case, that method doesn't have this bug.
Hide
Alex Miller added a comment -

Thanks for the report!

Show
Alex Miller added a comment - Thanks for the report!
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - I assume this came out of some actual usage with surprising behavior?
Hide
Ben Bader added a comment -

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!

Show
Ben Bader added a comment - 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!
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Ben Bader added a comment -

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

Show
Ben Bader added a comment - Hi, is there anything I can or should to to move this forward?
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - Nope. We batch up tickets to look at them periodically.

People

Vote (2)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: