What are the caveats of implementing fundamental types (like int) as classes?

Question

When designing and implenting an object-oriented programming language, at some point one must make a choice about implementing fundamental types (like int, float, double or equivalents) as classes or something else. Clearly, languages in the C family have a tendency not to define them as classes (Java has special primitive types, C# implements them as immutable structs, etc).

I can think of a very important advantage when fundamental types are implemented as classes (in a type system with a unified hierarchy): these types can be proper Liskov subtypes of the root type. Thus, we avoid complicating the language with boxing/unboxing (either explicit or implicit), wrapper types, special variance rules, special behavior, etc.

Of course, I can partially understand why language designers decide the way they do: class instances tend to have some spatial overhead (because the instances may contain a vtable or other metadata in their memory layout), that primitives/structs don't need to have (if the language doesnt allow inheritance on those).

Is spatial efficiency (and improved spatial locality, especially in large arrays) the only reason why fundamental types are often not classes?

I've generally assumed the answer to be yes, but compilers have escape analysis algorithms and thus they can deduce whether they can (selectively) omit the spatial overhead when an instance (any instance, not just a fundamental type) is proven to be strictly local.

Is the above wrong, or is there something else I'm missing?

Answer 1

Yes, it pretty much comes down to efficiency. But you seem to be underestimating the impact (or overestimating how well various optimizations work).

First, it's not just "spatial overhead". Making primitives boxed/heap-allocated has performance costs too. There's the additional pressure on the GC to allocate and collect those objects. This goes doubly if the "primitive objects" are immutable, as they should be. Then there's more cache misses (both because of the indirection and because less data fits into a given amount of cache). Plus the bare fact that "load the address of an object, then load the actual value from that address" takes more instructions than "load the value directly".

Second, escape analysis isn't go-faster fairy dust. It only applies to values that, well, don't escape. It's certainly nice to optimize local calculations (such as loop counters and intermediate results of calculations) and it will give measurable benefits. But a much larger majority of values live in the fields of objects and arrays. Granted, those can be subject to escape analysis themselves, but as they're usually mutable reference types, any aliasing of them presents a significant challenge to the escape analysis, which now has to prove that those aliases (1) don't escape either, and (2) don't make a difference for the purpose of eliminating allocations.

Given that calling any method (including getters) or passing an object as argument to any other method can help the object escape, you'll need interprocedural analysis in all but the most trivial cases. This is far more expensive and complicated.

And then there are cases where things really do escape and can't reasonably be optimized away. Quite many of them, actually, if you consider how often C programmers go through the trouble of heap-allocating things. When an object containing an int escapes, escape analysis ceases to apply to the int as well. Say goodbye to efficient primitive fields.

This ties into another point: The analyses and optimizations required are seriously complicated and an active area of research. It's debatable whether any language implementation ever achieved the degree of optimization you suggest, and even if so, it's been a rare and herculean effort. Surely standing on the shoulders of these giants is easier than being a giant yourself, but it's still far from trivial. Don't expect competitive performance any time in the first few years, if ever.

That is not to say such languages can't be viable. Clearly they are. Just don't assume it will be line-for-line as fast as languages with dedicated primitives. In other words, don't delude yourself with visions of a sufficiently smart compiler.

Answer 2

Is spatial efficiency (and improved spatial locality, especially in large arrays) the only reason why fundamental types are often not classes?

No.

The other issue is that fundamental types tend to be used by fundamental operations. The compiler needs to know that int + int isn't going to be compiled to a function call, but to some elementary CPU instruction (or equivalent byte-code). At that point, if you have the int as a regular object, you're going to have to effectively unbox the thing anyways.

Those sort of operations also don't really play nice with subtyping. You can't dispatch to a CPU instruction. You can't dispatch from a CPU instruction. I mean the entire point of subtyping is so you can use a D where you can a B. CPU instructions aren't polymorphic. To get primitives to do that, you have to wrap their operations with dispatch logic that costs multiple times the amount of operations as the simple addition (or whatever). The benefit of having int be part of the type hierarchy becomes a little moot when it's sealed/final. And that's ignoring all of the headaches with dispatch logic for binary operators...

Basically, the primitive types would need to have a lot of special rules around how the compiler handles them, and what the user can do with their types anyway, so it is often times simpler to just treat them as completely distinct.

Answer 3

There are only very few cases where you need “fundamental types” to be full objects (here, an object is data that either contains a pointer to a dispatch mechanism or is tagged with a type that can be used by a dispatch mechanism):

• You want user-defined types to be able to inherit from fundamental types. This is usually not wanted as it introduces performance- and security-related headaches. It is a performance problem because compilation cannot assume that an int will have a specific fixed size or that no methods have been overridden, and it is a security issue because semantics of ints could be subverted (consider an integer that is equal to any number, or that changes its value rather than being immutable).

• Your primitive types have supertypes and you want to have variables with type of a supertype of a primitive type. For example, assume your ints are Hashable, and you want to declare a function that takes a Hashable parameter which might receive regular objects but also ints.

  This can be “solved“ by making such types illegal: get rid of subtyping and decide that interfaces aren't types but type constraints. Obviously that reduces the expressiveness of your type system, and such a type system wouldn't be called object-oriented any longer. See Haskell for a language that uses this strategy. C++ is halfway there because primitive types do not have supertypes.

  The alternative is full or partial boxing of fundamental types. The boxing type need not be user-visible. Essentially, you define an internal boxed type for each fundamental type and implicit conversions between the boxed and fundamental type. This can get awkward if the boxed types have different semantics. Java exhibits two problems: boxed types have a concept of identity whereas primitives only have a concept of value equivalence, and boxed types are nullable whereas primitives are always valid. These issues are completely avoidable by not offering a concept of identity for value types, offering operator overloading, and not making all objects nullable by default.

• You do not feature static typing. A variable may hold any value, including primitive types or objects. Therefore all primitive types need to be always boxed in order to guarantee strong typing.

Languages that do have static typing do well to use primitive types wherever possible and only fall back to boxed types as a last resort. While many programs are not tremendously performance sensitive, there are cases where the size and makeup of primitive types is extremely relevant: Think of large-scale number crunching where you need to fit billions of data points into memory. Switching from double to float might be a viable space optimization strategy in C, but it would have next to no effect if all numeric types are always boxed (and therefore waste at least half of their memory for a dispatch mechanism pointer). When boxed primitive types are used locally, it is fairly straightforward to remove the boxing through the use of compiler intrinsics, but it would be short-sighted to bet the overall performance of your language on a “sufficienty advanced compiler”.

Answer 4

Most implementations I'm aware of impose three restrictions on such classes that allow the compiler to efficiently use the primitive types as the underlying representation the vast majority of the time. These restrictions are:

• Immutability
• Finality (unable to be derived from)
• Static typing

The situations where a compiler needs to box a primitive into an object in the underlying representation are relatively rare, such as when an Object reference is pointing to it.

This adds a fair bit of special case handling in the compiler, but it's not just limited to some mythical super-advanced compiler. That optimization is in real production compilers in major languages. Scala even allows you to define your own value classes.

Answer 5

In Smalltalk all of them (int, float, etc.) are first class objects. The only special case is that SmallIntegers are codified and treated differently by the Virtual Machine for the sake of efficiency, and therefore the SmallInteger class will not admit subclasses (which is not a practical limitation.) Note that this doesn't require any special consideration on the part of the programmer as the distinction is circumscribed to automatic routines like code generation or garbage collection.

Both the Smalltalk Compiler (source code -> VM bytecodes) and the VM nativizer (bytecodes -> machine code) optimize the code generated (JIT) so that to reduce the penalty of elementary operations with these basic objects.

Answer 6

I was designing an OO langauge and runtime (this failed for a completely different set of reasons).

There is nothing inherently wrong with making things like int true classes; in fact this makes the GC easier to design as there are now only 2 kinds of heap headers (class & array) rather than 3 (class, array, and primitive) [the fact that we can merge class & array after this is not relevant].

The real important case the primitive types should have mostly final/sealed methods (+ really matters, ToString not so much). This allows the compiler to staticly resolve almost all calls to the functions themselves and inline them. In most cases this doesn't matter as copying behavior (I chose to make embedding available at language level [so did .NET]), but in some cases if the methods aren't sealed the compiler will be forced to generate the call to the function used to implement int + int.