Don Syme and several others sent tweets to correct my claims about boxing in F#. I made the mistake of assuming that structs cannot be used as interface implementations without being boxed and allocated on the heap. As it turns out, .NET constraints allow structs to implement interfaces without being boxed. Out of sheer curiosity, I attempted to (ab)use this facility to systematically remove heap allocation. I decided to write a simple functional program that would not use the heap at all, performing all computation on the stack.
I went for encoding lists and implementing list reversal:
This method for getting rid of heap allocation would not work in C as this particular use of generics implies runtime code generation. As far as I understand, the CLR here generates new code paths for every possible list length.
My little benchmark has stack-allocated lists of 5 elements each being reversed a bit slower than heap-allocated lists. But it is fun to try. FSI reports zero GC usage.
Be careful, here: The intended difference between value and reference types in .NET is value vs. reference semantics, not stack vs. heap allocation. As Eric Lippert notes, value types are sometimes allocated on the heap in the CLR, depending on how you use them:
ReplyDeletehttp://blogs.msdn.com/b/ericlippert/archive/2009/04/27/the-stack-is-an-implementation-detail.aspx
I also think you are incorrect to claim that the CLR generates new code for every list length (was that a typo?). However, it may generate new code for certain list type parameters. This is discussed in detail in this post:
http://www.bluebytesoftware.com/blog/2011/10/23/OnGenericsAndSomeOfTheAssociatedOverheads.aspx
@Craig, thanks for the pointers. I still think I am careful enough and my understanding is correct though:
ReplyDelete1. Concerning semantics, I am dealing with immutable structures: value and reference semantics for these are identical, no?
2. So then, I am interested specifically in heap allocation. I wrote code that would avoid it. F# FSI reports garbage collection cycles, and my code produces 0, so I believe I succeeded.
3. This is definitely not a typo. AFAIK CLR generates new native code for every instantiation of a generic parameter with a struct. Look carefully at the list code above. It generates new struct types for every list length (and element type). Lists of length 2 and 1 have *different types*. This is by design, this is what lets stack-allocated list reversal happen. This way CLR can manage on the stack since it can statically know the size of the list, which varies with the length.
1. They're not the same thing in implementation, but by coincidence they're usually used the same way. My point here is strictly semantic; in practice you are right.
ReplyDelete3. If you are talking about the F# list (Microsoft.FSharp.Collections.List) then I agree, but of course you would not use that from C# anyway! I thought you were referring to the System.Collections.Generic.List type in your comments on C#, but perhaps not.
Ah no, sorry for the confusion! I am just discussing my own code :) It just happens to be called List (IList<'T>). The point of the blog was an exercise (without any claims to practical value) of constructing a data structure with the same meaning and operations as F# immutable lists that would not use the heap at all. Turns out it is possible. You can use either C# or F# to implement this data structure. What I said about "CLR generating new code paths for every possible list length" applies to either implementation, but it only applies to stack-allocated lists of course, not to F# list<'T> or System.Collection.Generics List<'T> :)
ReplyDelete