I definitely want to get this fixed some time soon.
The issue is that when you have cycles in normal reference-counting smart pointers, the items in the cycle keep each other alive and the memory is never freed. This problem doesn't exist in languages that use garbage collection.
The important part is a cycle detector. Here's the code for it:
See lines 157 to 292.
The algorithm from this paper is almost certainly more efficient than a roll-your-own solution would be.
Another thing is that the C++ implementation has a separation between the implementation (which is typeless) and the API which is templated. I'd like to remove this because I think it's unnecessary complication and almost certainly has a negative effect on performance. I also think we can make good use of move semantics if we simplify the implementation.
So, maybe the first step is to start a branch, and do a new version that simplifies the code. Basically, everything in sodium.cpp should be moved to sodium.h and all the stuff that de-types everything and turns things into pointers should be taken out and replaced by plain template-based code.