There is no such thing as "small integers" in CPython, only PyObjects, of which PyInt_Type and PyLong_Type are implementations. You can't special case integers without changing every C interface that accepts an object, and special casing every piece of code too (i.e. several hundred million lines of 3rd party extension modules, NumPy, lxml, ...). The trade-off is 1 extra machine word per integer (adding to the 2 + heap/alignment slack already present), or 1 conditional branch per object access everywhere.

This isn't so bad on memory either, since Python keeps a static cache of integers that are reused on every int constructor call. Also allowing for slack, I wouldn't be surprised if the machine word came for free.

When the GP talks about "small integers", I'm assuming he's talking about numbers between -5 and 256, which are cached ahead of time. They're never going to be garbage collected, so refcounting is largely unnecessary.

Once again, you can't implement this without specializing every call site that invokes Py_INCREF or Py_DECREF, or in other words, "1 conditional branch per object access everywhere."

You are right, but cost is probably very low. The conditionality of the branch doesn't matter if it's correctly predicted. On a modern processor, a correctly predicted branch-not-taken is usually indistinguishable from free unless you're already front-end constrained, which is rare for an interpreter. A correctly predicted branch-taken costs the same as a unconditional branch.

This is essentially why a JIT can be almost as fast as compiled code even when including the necessary guards. It's only when the branches become unpredictable that the costs become real. The trick with fast interpreted code is threading the execution so that the hardware is able to predict the branches accurately, but this is largely independent of the number of conditional branches.

Right, so the question becomes whether a branch mispredict is cheaper than simply refcounting an object that already lives in L1 cache (by virtue of having any of its words accessed). For Intel Sandy Bridge, this is 14-18 cycles for the mispredict, or ~4+4 for the L1 word read/write. Now the question becomes how often that mispredict will occur, and there's no real way to measure this short of an implementation.

What you propose sounds like it would be a pure headache for all code which otherwise expects a uniform memory API.

Consider a C extension which takes an object and appends it to a list. If small integers did not have a refcount then that extension would have to have special code, like "if object is not a small integer, then increment the reference count".

I have experience turning a Lisp dialect with refcounted integers into supporting non-refcounted integers, identified by a type tag field in the "value cell" type.

> If small integers did not have a refcount then that extension would have to have special code, like "if object is not a small integer, then increment the reference count".

Easily implemented in one place in the "increment_refcount(obj)" inline function:

    // roughly speaking
    if (is_heap_pointer(obj))
      obj->refcount++;

where "is_heap_pointer(obj)" is an inlined bitmask check like

    (((unsigned int) obj) & TAG_MASK) == TAG_PTR)

If TAG_PTR is zero bits, then a value which satisifes is_heap_pointer can be dereferenced straight.

In a garbage collection implementation, you don't have refcounts, but the garbage collector's "mark object" function does the same check:

   if (!is_heap_pointer(obj))
     return;  // don't try to mark non-heap things

   switch (type(obj)) {
   case TYPE_CONS_CELL
      mark_obj(obj->cons.car);
      mark_obj(obj->cons.cdr);
      break;
   // ...
   }

Another thing is that you provide an API to the extension writers, which abstracts the use of objects. For instance, you can give them a function that can be called like this:

   value n = number(42);
   value z = number(INT_MAX);

The first case might construct an unboxed value because the integer is small enough. But perhaps the second returns a bignum because INT_MAX requires 32 bits, wheres unboxed integers only go up to 30 bits.

So in the first case you get an object with no refcount, whereas in the second you get an object with a refcount of 1. The extension code is written such that it doesn't care.

Those are excellent points. In the context of CPython, Guido van Rossum made the design decision to not use tagged objects, based on experience with ABC implementation, which did.

See https://mail.python.org/pipermail/python-dev/2004-July/04614... .

I just realized though that since the patch to support tagged integers is small, a closed system like the CCP Games distribution of Python, which has no extensions they don't control, might be able to use this idea.

I hadn't considered that extensions which needed direct memory access would need access to these objects. But it's a solvable problem. The proposal might read as follows:

"Objects with IDs between 0 and 2055, inclusive, are considered unreleasable. The Python runtime shall initialize the refcount of these objects to 1 when they are first used, and shall make no guarantee that the refcount on such objects accurately reflects the true number of references to that object. Native extensions may increase and decrease the refcount on these objects as if they were normal objects; if those extensions are well-behaved, then the refcount should never decrease below 1. However, native extensions that can statically reason about whether an object is likely to be unreleasable, may benefit in performance by checking for whether objects passed to their functions are indeed unreleasable, and refraining from modifying or checking their refcount in such cases."

Of course it's solvable. My point is that solving it adds a layer of complexity. Now every decref needs a check for "id". As the id is implemented as a pointer, all of these special objects need to be allocated in a contiguous block of memory for this check to be fast, and with two extra if-conditionals. Also, this range can't change without recompiling all extensions ... or that range must be resolved dynamically, adding more overhead for every single decref.

Nor is there much advantage. We know that more advanced implementations can look at program flow and determine that, say, certain operations are only integer based, and therefore unboxable. Or tracing systems can assume that certain types are constant over multiple calls to the same code, and write optimized versions for those types.

These gives much better (eg, >5x according PyPy) optimizations over the error prone change that you believe might be faster.

Python also keeps refcounts for other objects that shouldn't be garbage collected such as None, True, and False. The reason being to prevent having certain objects that need to be refcounted and certain objects that don't. Otherwise, C code would be littered with if statements like the below:

    if (number < -5 || number > 256) {
      decrement_refcount(number);
    }

To be fair, you'd expect that to live in decrement_refcount.

Does that also imply that a small integer is created on the heap? I would think the heap allocation would be the huge performance killer.

Python is not going to call malloc(..) for every single object that you create. It will allocate a block of same-sized objects and maintain a linked list of free slots.