Squeak primitives

Bryce Kampjes bryce at kampjes.demon.co.uk
Fri Aug 12 21:05:36 UTC 2005


Jesse Welton writes:
 > Don't we essentially use compact SmallIntegers as a size optimization?
 > They save object header space.  If they were to improve computation
 > efficiency at all, I'd think it would be through reducing the work of
 > the allocator and GC.  Oh, and they save an indirection.

They are both a size and a space optimisation. Allocating full objects
is expensive. Well, at least compared with a single instruction.

 > The real issue isn't the use of primitive types, it's the use of
 > primitive types that don't participate in the object system, isn't it?
 > How many instructions do we pay for a dynamic message dispatch vs.
 > static lookup or bytecodes?  It's a lot easier on the compiler witers
 > to make it fast if they don't have to accommodate all that dynamism,
 > and a lot of programmers just don't care all that much about losing
 > it.

I doubt there is any real performance cost for having real objects for
SmallIntegers. There may be a slight real cost for having small
integers overflow into large integers. This is assuming a decent
optimising compiler, something Exupery is intended to provide for
Squeak. However an even better compiler is required to remove the
overhead from array bounds checks (I plan to do this with Exupery but
later).

If we assume that the compiler is either assuming small integer
arithmetic (like the Squeak interpreter) or has dynamic type feedback
(normal in high performance modern GCed OO languages) then the
SmallInteger case will be inlined with type checks and an overflow
check. The type checks can be removed if the argument came from
another SmallInteger operation (the overflow check guarantees
this). Induction variable analysis should allow the overflow check to
be removed from loop variables.

To optimise away the cost of having real integer objects only requires
the machinery needed to optimise dynamic dispatch (dynamic type
feedback for hotspot inlining) and to remove array range checks (a
decent optimising framework). There is no extra framework effort to
optimise away proper object primitive types. You just need to use
dynamic type feedback and SSA (or def-use chaining) both of which are
needed for decent integer performance even with primitive types.

There is a difference between having good average case performance and
having good worst case performance. Primitive types provide good worst
case performance. Garbage collection only provides good average case
performance though it's often better than normal manual
allocation. Good worst case may be worse on average than good average
case performance.

In my opinion primitive types serve (almost) no performance purpose in
a GCed language with reference semantics (objects are always accessed
via references like Java, Smalltalk, and Lisp). In a language like
C/C++ this is different, there is no GC, performance is as
deterministic as the hardware (not very) and objects can be physically
embedded in other objects. But with GC and object access only via
references (object slicing is a problem so access via references is
safer) there is no compiler performace reason for primitive types.

The real reason that Java and C# are faster than Squeak is they have a
larger compiler budget.

Bryce

P.S. The same argument applies to floating point operations as well as
integers. They should be as fast as C with a decent optimising
compiler in common cases however the cost of detagging (reboxing) is
much higher because a new heap allocated object must be created. So
for floats while improving the average case is easy given sufficient
resources there's still a little thought needed to deal with the
remaining cases.

P.P.S. Having small integers overflow gracefully into large integers
is a performance vs. correctness argument. The performance costs may
be nil, more instructions might be executed but that doesn't mean
that it will take longer. Most C programs only execute one instruction
every clock. That leaves plenty of room for "pointless" overflow
checks for safety (I measured with oprofile).



More information about the Squeak-dev mailing list