27

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?

19

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.

  • When talking about escape analysis, I also meant allocating to automatic storage (it doesn't solve everything, but as you say, it solves some things). I also admit I had underestimated the extent to which fields and aliasing could make escape analysis fail more often. Cache misses are the thing I was most concerned about when talking about spatial efficiency, so thanks for addressing that. – Theodoros Chatzigiannakis Jan 1 '15 at 14:49
  • @TheodorosChatzigiannakis I include changing allocation strategy in escape analysis (because honestly that seems to be the only thing it's ever used for). – user7043 Jan 1 '15 at 14:52
  • Re your second paragraph: Objects don't always need to be heap-allocated or be reference types. In fact, when they aren't, this makes the necessary optimizations comparably easy. See C++'s stack-allocated objects for an early example, and Rust's ownernership system for a way to bake escape analysis directly into the language. – amon Jan 1 '15 at 16:17
  • @amon I know, and maybe I should have made that clearer, but it seems OP is only interested in Java- and C#-like languages where heap allocation is almost mandatory (and implicit) because of reference semantics and lossless casts between subtypes. Good point about Rust using what amounts to escape analysis though! – user7043 Jan 1 '15 at 16:25
  • @delnan It's true I'm mostly interested in languages that abstract away the storage details, but please feel free to include anything you think is relevant, even if it's not applicable in those languages. – Theodoros Chatzigiannakis Jan 1 '15 at 16:45
27

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.

  • 4
    Check out the implementation of any of the dynamically typed languages that treat integers and such as objects. The final primitive CPU instruction can very well be hidden in a method (operator overload) in the only-somewhat-privileged class implementation in the runtime library. The details would look different with a static type system and compiler but it's no fundamental problem. At worst it just makes things even slower. – user7043 Jan 1 '15 at 14:17
  • 3
    int + int can be a regular language-level operator that invokes an intrinsic instruction that's guaranteed to compile to (or behave as) the native CPU integer addition op. The benefit of int inheriting from object isn't only the possibility of inheriting another type from int, but also the possibility of an int behaving as an object without boxing. Consider C# generics: you can have covariance and contravariance, but they are only applicable to class types - struct types are automatically excluded, because they can only become object through (implicit, compiler-generated) boxing. – Theodoros Chatzigiannakis Jan 1 '15 at 14:21
  • 3
    @delnan - sure, though in my experience with statically typed implementations, since every non-system call boils down to the primitive operations, having overhead there has a dramatic impact on performance - which in turn has an even more dramatic effect on adoption. – Telastyn Jan 1 '15 at 14:23
  • @TheodorosChatzigiannakis - great, so you could get variance and contravariance on types that have no useful sub/super-type... And implementing that special operator to call the CPU instruction still makes it special. I'm not disagreeing with the idea - I've done very similar things in my toy languages, but I've found that there are practical gotchas during implementation that don't make such things as clean as you'd expect. – Telastyn Jan 1 '15 at 14:24
  • 1
    @TheodorosChatzigiannakis Inlining across library boundaries is certainly possible, though it's yet another item on the "high-end optimizations I'd like to have" shopping list. I feel obliged to point out though that it's notoriously tricky to get completely right without being so conservative as to be useless. – user7043 Jan 1 '15 at 14:34
4

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”.

  • An int is hardly immutable in all languages. – Scott Whitlock Jan 1 '15 at 17:54
  • 6
    @ScottWhitlock I see why you might think that, but in general primitive types are immutable value types. No sane language allows you to change the value of the number seven. However, many languages do allow you to reassign a variable that holds a value of a primitive type to a different value. In C-like languages, a variable is a named memory location, and acts like a pointer. A variable is not the same as the value it points to. An int value is immutable, but an int variable isn't. – amon Jan 1 '15 at 18:31
  • 1
    @amon: No sane language; just Java: thedailywtf.com/articles/Disgruntled-Bomb-Java-Edition – Mason Wheeler Jan 1 '15 at 20:38
  • get rid of subtyping and decide that interfaces aren't types but type constraints.... such a type system wouldn't be called object-oriented any longer but this sounds like prototype based programming, which is definitely OOP. – Michael Jan 2 '15 at 4:51
  • 1
    @ScottWhitlock the question is whether if you then have int b = a, you can do something to b that will change the value of a. There have been some language implementations where this is possible, but it's generally considered pathological and undesired, unlike doing the same for an array. – Random832 Jan 2 '15 at 19:09
2

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.

1

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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