92

Does anyone know the answer and/or have an opinion about this?

Since tuples would normally not be very large, I would assume it would make more sense to use structs than classes for these. What say you?

1
  • 3
    For anyone stumbling here after 2016. In c# 7 and newer, Tuple literals are of the type family ValueTuple<...>. See reference at C# tuple types Mar 21, 2019 at 8:05

5 Answers 5

98

Microsoft made all tuple types reference types in the interests of simplicity.

I personally think this was a mistake. Tuples with more than 4 fields are very unusual and should be replaced with a more typeful alternative anyway (such as a record type in F#) so only small tuples are of practical interest. My own benchmarks showed that unboxed tuples up to 512 bytes could still be faster than boxed tuples.

Although memory efficiency is one concern, I believe the dominant issue is the overhead of the .NET garbage collector. Allocation and collection are very expensive on .NET because its garbage collector has not been very heavily optimized (e.g. compared to the JVM). Moreover, the default .NET GC (workstation) has not yet been parallelized. Consequently, parallel programs that use tuples grind to a halt as all cores contend for the shared garbage collector, destroying scalability. This is not only the dominant concern but, AFAIK, was completely neglected by Microsoft when they examined this problem.

Another concern is virtual dispatch. Reference types support subtypes and, therefore, their members are typically invoked via virtual dispatch. In contrast, value types cannot support subtypes so member invocation is entirely unambiguous and can always be performed as a direct function call. Virtual dispatch is hugely expensive on modern hardware because the CPU cannot predict where the program counter will end up. The JVM goes to great lengths to optimize virtual dispatch but .NET does not. However, .NET does provide an escape from virtual dispatch in the form of value types. So representing tuples as value types could, again, have dramatically improved performance here. For example, calling GetHashCode on a 2-tuple a million times takes 0.17s but calling it on an equivalent struct takes only 0.008s, i.e. the value type is 20× faster than the reference type.

A real situation where these performance problems with tuples commonly arises is in the use of tuples as keys in dictionaries. I actually stumbled upon this thread by following a link from the Stack Overflow question F# runs my algorithm slower than Python! where the author's F# program turned out to be slower than his Python precisely because he was using boxed tuples. Manually unboxing using a hand-written struct type makes his F# program several times faster, and faster than Python. These issues would never had arisen if tuples were represented by value types and not reference types to begin with...

20
  • 2
    @Bent: Yes, that's exactly what I do when I come across tuples on a hot path in F#. Would be nice if they had provided both boxed and unboxed tuples in the .NET Framework though...
    – J D
    May 6, 2011 at 8:13
  • 18
    Regarding virtual dispatch, I think that your blame is misplaced: the Tuple<_,...,_> types could have been sealed, in which case no virtual dispatch would be needed despite being reference types. I'm more curious about why they aren't sealed than why they are reference types.
    – kvb
    Apr 13, 2012 at 18:58
  • 2
    From my testing, for the scenario in which a tuple would be generated in one function and returned to another function, and then never used again, exposed-field structures seem to offer superior performance for any size data item that's not so huge as to blow the stack. Immutable classes are only better if the references will be passed around enough to justify their construction cost (the larger the data item, the less they have to be passed round for the tradeoff to favor them). Since a tuple is supposed to represent simply a bunch of variables stuck together, a struct would seem ideal.
    – supercat
    Feb 9, 2013 at 22:51
  • 6
  • 3
    I think your opinion has been pretty well validated by the fact that C# 7's new Tuple syntax actually creates ValueTuple<>s, which are structs. Nov 27, 2017 at 22:59
45

The reason is most likely because only the smaller tuples would make sense as value types since they would have a small memory footprint. The larger tuples (i.e. the ones with more properties) would actually suffer in performance since they would be larger than 16 bytes.

Rather than have some tuples be value types and others be reference types and force developers to know which are which I would imagine the folks at Microsoft thought making them all reference types was simpler.

Ah, suspicions confirmed! Please see Building Tuple:

The first major decision was whether to treat tuples either as a reference or value type. Since they are immutable any time you want to change the values of a tuple, you have to create a new one. If they are reference types, this means there can be lots of garbage generated if you are changing elements in a tuple in a tight loop. F# tuples were reference types, but there was a feeling from the team that they could realize a performance improvement if two, and perhaps three, element tuples were value types instead. Some teams that had created internal tuples had used value instead of reference types, because their scenarios were very sensitive to creating lots of managed objects. They found that using a value type gave them better performance. In our first draft of the tuple specification, we kept the two-, three-, and four-element tuples as value types, with the rest being reference types. However, during a design meeting that included representatives from other languages it was decided that this "split" design would be confusing, due to the slightly different semantics between the two types. Consistency in behavior and design was determined to be of higher priority than potential performance increases. Based on this input, we changed the design so that all tuples are reference types, although we asked the F# team to do some performance investigation to see if it experienced a speedup when using a value type for some sizes of tuples. It had a good way to test this, since its compiler, written in F#, was a good example of a large program that used tuples in a variety of scenarios. In the end, the F# team found that it did not get a performance improvement when some tuples were value types instead of reference types. This made us feel better about our decision to use reference types for tuple.

5
  • 3
    Great discussion here: blogs.msdn.com/bclteam/archive/2009/07/07/… Mar 9, 2010 at 16:50
  • Ahh, I see. I'm still a little confused that value types do not mean anything in practice here :P Mar 9, 2010 at 17:01
  • I just read the comment about no generic interfaces and when looking at the code earlier that was exactly another thing that struck me. It's really quite uninspiring how ungeneric the Tuple types are. But, I guess you can always make your own... There's no syntactic support in C# anyway. Yet at least... Still, the use of generics and the constraints it has still feels limited limited in .Net. There's a substantial potential for very generic very abstract libraries but generics probably need extra things like covariant return types. Mar 9, 2010 at 20:11
  • 7
    Your "16 byte" limit is bogus. When I tested this on .NET 4 I found that the GC is so slow that unboxed tuples up to 512 bytes can still be faster. I'd also question Microsoft's benchmark results. I bet they ignored parallelism (the F# compiler is not parallel) and that is where avoiding GC really pays off because .NET's workstation GC is also not parallel.
    – J D
    May 2, 2011 at 10:54
  • Out of curiosity, I wonder if the compiler team tested the idea of making tuples be EXPOSED-FIELD structs? If one has an instance of a type with various traits, and needs an instance which is identical except for one trait which is different, an exposed-field struct can accomplish that much faster than any other type, and the advantage only grows as structs get bigger.
    – supercat
    Dec 23, 2012 at 21:25
8

If the .NET System.Tuple<...> types were defined as structs, they would not be scalable. For instance, a ternary tuple of long integers currently scales as follows:

type Tuple3 = System.Tuple<int64, int64, int64>
type Tuple33 = System.Tuple<Tuple3, Tuple3, Tuple3>
sizeof<Tuple3> // Gets 4
sizeof<Tuple33> // Gets 4

If the ternary tuple were defined as a struct, the result would be as follows (based on a test example I implemented):

sizeof<Tuple3> // Would get 32
sizeof<Tuple33> // Would get 104

As tuples have built-in syntax support in F#, and they are used extremely often in this language, "struct" tuples would pose F# programmers at risk of writing inefficient programs without even being aware of it. It would happen so easily:

let t3 = 1L, 2L, 3L
let t33 = t3, t3, t3

In my opinion, "struct" tuples would cause a high probability of creating significant inefficiencies in everyday programming. On the other hand, the currently existing "class" tuples also cause certain inefficiencies, as mentioned by @Jon. However, I think that the product of "occurrence probability" times "potential damage" would be much higher with structs than it currently is with classes. Therefore, the current implementation is the lesser evil.

Ideally, there would be both "class" tuples and "struct" tuples, both with syntactic support in F#!

Edit (2017-10-07)

Struct tuples are now fully supported as follows:

11
  • 2
    If one avoids unnecessary copying, a exposed-field struct of any size will be more efficient than an immutable class of the same size, unless each instance gets copied enough times that the cost of such copying overcome the cost of creating a heap object (the break-even number of copies varies with object size). Such copying may be unavoidable if one wants a struct which pretends to be immutable, but structs which is designed to appear as collections of variables (which is what struct are) can be used efficiently even when they are huge.
    – supercat
    Oct 25, 2012 at 16:14
  • 2
    It may be that F# does not play nicely with the idea of passing structs by ref, or may not like the fact that so-called "immutable structs" aren't, especially when boxed. It's too bad .net never implemented the concept of passing parameters by an enforceable const ref, since in many cases such semantics are what is really required.
    – supercat
    Oct 25, 2012 at 16:29
  • 1
    Incidentally, I regard the amortized cost of GC as being part of the cost of allocating objects; if an L0 GC would be necessary after every megabyte of allocations, then the cost of allocating 64 bytes is about 1/16,000 of the cost of an L0 GC, plus a fraction of the cost of any L1 or L2 GC's that become necessary as a consequence of it.
    – supercat
    Oct 26, 2012 at 20:48
  • 4
    "I think that the product of occurrence probability times potential damage would be much higher with structs than it currently is with classes". FWIW, I have very rarely seen tuples of tuples in the wild and consider them a design flaw but I very often see people struggle with awful performance when using (ref) tuples as keys in a Dictionary, e.g. here: stackoverflow.com/questions/5850243/…
    – J D
    Oct 30, 2014 at 0:43
  • 3
    @Jon It's two years since I wrote this answer, and I now agree with you that it would be preferrable if at least 2- and 3-tuples were structs. An F# language user voice suggestion has been made in this regard. The issue has some urgency, as there has been a massive growth of applications in big data, quantitative finance, and gaming in the recent years. Oct 30, 2014 at 10:57
4

For 2-tuples, you can still always use the KeyValuePair<TKey,TValue> from earlier versions of the Common Type System. It's a value type.

A minor clarification to the Matt Ellis article would be that the difference in use semantics between reference and value types is only "slight" when immutability is in effect (which, of course, would be the case here). Nevertheless, I think it would have been best in the BCL design not to introduce the confusion of having Tuple cross over to a reference type at some threshold.

3
  • If a value will be used once after it's returned, an exposed-field struct of any size will outperform any other type, provided only that it's not so monstrously huge as to blow the stack. The cost of building a class object will only be recouped if the reference ends up being shared multiple times. There a times when it's useful for a general-purpose fixed-size heterogeneous type to be a class, but there are other times when a struct would be better--even for "big" things.
    – supercat
    Feb 11, 2013 at 3:58
  • Thanks for adding this useful rule-of-thumb. I am hoping however that you didn't misunderstand my position: I'm a value-type junkie. (stackoverflow.com/a/14277068 should leave no doubt). Feb 20, 2013 at 22:00
  • Value types are one of the great features of .net, but unfortunately the person who wrote up the msdn dox failed to recognize that there are multiple disjoint usage cases for them, and that different usage cases should have different guidelines. The style of struct msdn recommends should only be used with structs that represent a homogenous value, but if one needs to represent some independent values fastened together with duct tape, one shouldn't use that style of struct--one should use a struct with exposed public fields.
    – supercat
    Feb 20, 2013 at 22:23
0

I don't know but if you have ever used F# Tuples are part of the language. If I made a .dll and returned a type of Tuples it be nice to have a type to put that in. I suspect now that F# is part of the language (.Net 4) some modifications to CLR were made to accommodate some common structures in F#

From http://en.wikibooks.org/wiki/F_Sharp_Programming/Tuples_and_Records

let scalarMultiply (s : float) (a, b, c) = (a * s, b * s, c * s);;

val scalarMultiply : float -> float * float * float -> float * float * float

scalarMultiply 5.0 (6.0, 10.0, 20.0);;
val it : float * float * float = (30.0, 50.0, 100.0)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.