3 ms·

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

by _wmd 12y ago

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.

j_baker 12y ago
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.
- _wmd 12y ago
  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."
  - nkurz 12y ago
    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.
    - _wmd 12y ago
      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.

by _wmd 12y ago

j_baker 12y ago

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.

_wmd 12y ago
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."
- nkurz 12y ago
  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.
  - _wmd 12y ago
    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.