How much extra memory take a value encoded in a algebraic type in F#?

I'm doing a interpreter for a little language to do Array/relational programming like in kdb+.

I wonder how much memory F# add when a value is encoded in a AGDT like this:

type value =
  | Dec of int
  | Num of int array
  | Float of float array
  | Array of value
  | Arr of value array

let print x =
    printfn "%A" x


let a = [|1; 2|]
let b = Num(a)
let c = [| Dec(1); Dec(2) |]
//print (sizeof Arr) Don't have a easy way to do this

I wonder if in F# a,b,c are equally performant or not. The idea is that the interpreter need to process mainly arrays.

Because look like (according to my searchs in SO) .NET not have a direct way to check the size on memory of a value, I do something alike in swift:

indirect enum ExprC {
    case IntC(x:Int32)
    case IntA(x:Array<Int32>)
    case ArrayC(x:Array<ExprC>)
}
let values:[Int32] = [1, 2]
let v1 = ExprC.ArrayC(x: [ExprC.IntC(x:1), ExprC.IntC(x: 2)])
let v2 = ExprC.IntA(x: values)

print(sizeofValue(values))
print(sizeofValue(v1))
print(sizeofValue(v2))

//RESULTS
//8
//8
//8

BTW, this results was against my expectations, I have imagine that the encoding must have a extra storage cost, so I'm unsure if this will happend to in F#.

Solution

The F# compiler translates ADTs to .NET sealed class hierarchies. Your example would be translated into something like this (loosely speaking):

public class value {
  public class Dec : value { public int Item { get; } }
  public class Num : value { public int[] Item { get; } }
  public class Float : value { public double[] Item { get; } }
  public class Array : value { public value Item { get; } }
  public class Arr : value { public value[] Item { get; } }
}

Beyond that, it's really hard to tell, because the way classes are allocated may vary with VM implementation and underlying machine architecture. For example, on the full .NET FW on Windows on x86/x64, the object will have a 32- or 64-bit object header plus whatever the content of the object is, possibly aligned (check out this post for some details). This means that, for example, your Dec case will take up either 8 or 12 bytes.

However, other VM implementations may do different things. CoreCLR, Mono, MicroFW, .NET CF - all may have their own opinion about object allocation, and .NET Native compiler may even optimize the whole thing out completely.

This is why .NET can't tell you, in general, the "size" of a class: in general, it doesn't know. To think about it, it may not even always make sense to talk about "size". Swift can get away with it, because it doesn't have an open-standard VM, so it can do whatever the hell it wants.

If you really need to guarantee a particular memory layout, .NET does have a thing for that (look up StructLayoutAttribute), but it wouldn't work with ADTs, quite understandably.

Finally, I feel that you may be misdirecting your attention. Why do you want to know these things, exactly? If you really care about memory footprint, you shouldn't use F# (or Swift) at all, you should use C (or, if you're really into functional programming, check out Rust). Otherwise, remember about "premature optimization".