Does your list collection hold strong refs to removed elements?

Jul 12, 2015 at 5:46 PM
I was reading your docs and your description of using a mutable array at the list's Tail as an optimization. But doesn't that mean that after running this code:

var list = new YourList<object>();
var list2 = list.AddTail(new object());
var list3 = list2.AddTail(new ReallyBigObject());
list3 = null;

Does list2 now hold a strong reference to ReallyBigObject? If so, that's a serious problem for some folks as people will expect that they've released all references to that object, allowing GC and finalization to occur.
Jul 13, 2015 at 5:48 PM
Yes you are right. The reference to the big object will be still in memory. I think it is really not good idea to rely on finalize especially if you are using persistent collections.

The only problem is memory leak of course .. but it is price for faster modification operations. It would be nice to remove not accessible objects but I am not sure if it is possible in C#.
Jul 14, 2015 at 5:56 AM
I see. Yes, I agree with your implementation folks better not count on GC acting the way they'd expect from most other collection implementations. I suggest you call it out though. Whether or not they're depending on finalizers (which is unusual), not reclaiming memory by releasing all references they know about can catch folks off guard.
Jul 14, 2015 at 5:32 PM
It is hard to say whether it is better or not to implement it in this way. In my opinion it is better to optimize modification operations which is very often except to handle these edge cases. I realize that it can be quite confusing in some situations but in these cases it is better to look for other collections.

It is not such easy to optimize modification operations in persistent structures and therefore it is usual to implement solutions which can leads to memory leaks. E.g. Clojure's PersistentVector (on which is base this implementation) provides SubVec (sub vector) which returns the same structure with offset. In other words if you have very large vector and create SubVec from it with only one element the whole large vector will be still in memory. It is confusing too but also fast. In many languages the Substring method of string (which is also persistent) is implemented in the same way.