google / btree

BTree provides a simple, ordered, in-memory data structure for Go programs.
Apache License 2.0
3.9k stars 414 forks source link

Fix memory leak in freeNode and splitNode. #11

Closed keep94 closed 7 years ago

keep94 commented 7 years ago

This PR includes two important changes to help the GC reclaim memory. Both changes involve making sure that elements past the end of a slice but still within the slice's capacity can be gced.

The first change is freelist.newNode() setting the last element to nil in the freelist before shrinking the size of the freelist by 1.

The second change is adding a truncate method to the items and children types and making sure that callers use truncate instead of something like items := items[:i]. truncate() sets all the items past the end of the slice to nil allowing them to be GCed.

keep94 commented 7 years ago

I see no significant change in Insert, Delete, or Get.

benchmarkAscend seems to run slightly faster with my PR (230us vs 250us).

I see no significant change with the other Ascend/Descend benchmarks.

I don't understand why benchmarkAscend would run faster with my PR as ascending the btree is a read-only operation and shouldn't be splitting nodes or touching the freelist.

keep94 commented 7 years ago

Thanks for the comments. Sorry I didn't see them before. Very clever code you proposed. I integrated your changes and reran the benchmarks. I saw no significant change in the performance of insert and delete.

keep94 commented 7 years ago

BenchmarkAscend still runs faster with this PR (220us vs 250us) I don't understand why.