Jun 21, 2022 · Apr 17, 2022 · Apr 17, 2022 · Apr 18, 2022 · Apr 18, 2022 · Apr 18, 2022
diff --git a/Include/internal/pycore_range.h b/Include/internal/pycore_range.h

 typedef struct {
    PyObject_HEAD
 long index;
 long start;
 long step;
 long len;
 sdigit index;
 sdigit start;
 sdigit step;
 sdigit len;
 } _PyRangeIterObject;

 #ifdef __cplusplus
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
        /* cast to unsigned to avoid possible signed overflow
           in intermediate calculations. */
        return PyLong_FromLong((long)(r->start +
                                      (unsigned long)(r->index++) * r->step));
                                      (digit)(r->index++) * r->step));
    return NULL;
 }

    _PyRangeIterObject *it = PyObject_New(_PyRangeIterObject, &PyRangeIter_Type);
    if (it == NULL)
        return NULL;
    it->start = start;
    it->step = step;
    it->len = len;
    it->start =Py_SAFE_DOWNCAST(start, long, sdigit);
    it->step =Py_SAFE_DOWNCAST(step, long, sdigit);
    it->len =Py_SAFE_DOWNCAST(len, long, sdigit);
    it->index = 0;
    return (PyObject *)it;
 }
        goto long_range;
    }
    ulen = get_len_of_range(lstart, lstop, lstep);
    if (ulen > (unsigned long)LONG_MAX) {
    if (ulen > PyLong_MASK ||
        lstart > PyLong_MASK || lstart < -(long)PyLong_MASK ||
        lstop > PyLong_MASK || lstop < -(long)PyLong_MASK ||
        lstep > PyLong_MASK || lstep < -(long)PyLong_MASK)
    {
        goto long_range;
    }
    /* check for potential overflow of lstart + ulen * lstep */
    if (ulen) {
        if (lstep > 0) {
            if (lstop > LONG_MAX - (lstep - 1))
                goto long_range;
        }
        else {
            if (lstop < LONG_MIN + (-1 - lstep))
                goto long_range;
        }
    }
    return fast_range_iter(lstart, lstop, lstep, (long)ulen);

  long_range:
diff --git a/Python/ceval.c b/Python/ceval.c
            _PyRangeIterObject *r = (_PyRangeIterObject *)TOP();
            DEOPT_IF(Py_TYPE(r) != &PyRangeIter_Type, FOR_ITER);
            STAT_INC(FOR_ITER, hit);
            if (r->index < r->len) {
                PyObject *res = PyLong_FromLong(
                    (long)(r->start + (unsigned long)(r->index++) * r->step));
                if (res == NULL) {
                    goto error;
            _Py_CODEUNIT next = next_instr[INLINE_CACHE_ENTRIES_FOR_ITER];
            assert(_PyOpcode_Deopt[_Py_OPCODE(next)] == STORE_FAST);
            PyObject **local_ptr = &GETLOCAL(_Py_OPARG(next));
            PyObject *local = *local_ptr;
            if (r->index >= r->len) {
                goto iterator_exhausted_no_error;
            }
            JUMPBY(INLINE_CACHE_ENTRIES_FOR_ITER + 1);
            sdigit value = r->start + (digit)(r->index++) * r->step;
            if (value < _PY_NSMALLPOSINTS && value >= -_PY_NSMALLNEGINTS) {
                *local_ptr = Py_NewRef(&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS+value]);
                Py_XDECREF(local);
                NOTRACE_DISPATCH();
            }
            if (local && PyLong_CheckExact(local) && Py_REFCNT(local) == 1) {
                if (value > 0) {
                    assert(value <= PyLong_MASK);
                    ((PyLongObject *)local)->ob_digit[0] = value;
                    Py_SET_SIZE(local, 1);
                }
                else {
                    assert(value >= -(sdigit)PyLong_MASK);
                    ((PyLongObject *)local)->ob_digit[0] = -(sdigit)value;
                    Py_SET_SIZE(local, -1);
                }
                PUSH(res);
                JUMPBY(INLINE_CACHE_ENTRIES_FOR_ITER);
                NOTRACE_DISPATCH();
            }
            goto iterator_exhausted_no_error;
            PyObject *res = PyLong_FromLong(value);
            if (res == NULL) {
                // undo the JUMPBY
                next_instr -= INLINE_CACHE_ENTRIES_FOR_ITER + 1;
                goto error;
            }
            *local_ptr = res;
            Py_XDECREF(local);
            NOTRACE_DISPATCH();
        }

        TARGET(BEFORE_ASYNC_WITH) {
diff --git a/Python/specialize.c b/Python/specialize.c
    assert(_PyOpcode_Caches[FOR_ITER] == INLINE_CACHE_ENTRIES_FOR_ITER);
    _PyForIterCache *cache = (_PyForIterCache *)(instr + 1);
    PyTypeObject *tp = Py_TYPE(iter);
    _Py_CODEUNIT next = instr[1+INLINE_CACHE_ENTRIES_FOR_ITER];
    int next_op = _PyOpcode_Deopt[_Py_OPCODE(next)];
    if (tp == &PyListIter_Type) {
        _Py_SET_OPCODE(*instr, FOR_ITER_LIST);
        goto success;
    }
    else if (tp == &PyRangeIter_Type) {
    else if (tp == &PyRangeIter_Type && next_op == STORE_FAST) {
        _Py_SET_OPCODE(*instr, FOR_ITER_RANGE);
        goto success;
    }
    else {
        SPECIALIZATION_FAIL(JUMP_BACKWARD,
        SPECIALIZATION_FAIL(FOR_ITER,
                            _PySpecialization_ClassifyIterator(iter));
        goto failure;
    }
Original file line number	Diff line number	Diff line change
Expand Up		@@ -10,10 +10,10 @@ extern "C" {

		typedef struct {
		PyObject_HEAD
		long index;
		long start;
		long step;
		long len;
		sdigit index;
		sdigit start;
		sdigit step;
		sdigit len;
		} _PyRangeIterObject;

		#ifdef __cplusplus
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -770,7 +770,7 @@ rangeiter_next(_PyRangeIterObject *r)
		/* cast to unsigned to avoid possible signed overflow
		in intermediate calculations. */
		return PyLong_FromLong((long)(r->start +
		(unsigned long)(r->index++) * r->step));
		(digit)(r->index++) * r->step));
		return NULL;
		}

Expand DownExpand Up		@@ -911,9 +911,9 @@ fast_range_iter(long start, long stop, long step, long len)
		_PyRangeIterObject *it = PyObject_New(_PyRangeIterObject, &PyRangeIter_Type);
		if (it == NULL)
		return NULL;
		it->start = start;
		it->step = step;
		it->len = len;
		it->start =Py_SAFE_DOWNCAST(start, long, sdigit);
Copy link Member markshannonApr 20, 2022 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Would it be cleaner to change the signature of`fast_range_iter` to take sdigits, rather than longs? Copy link MemberAuthor sweeneydeApr 24, 2022• edited Loading Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. I'm not so sure -- downcasts need to happen somewhere, and`fast_range_iter` is called in two places. The`PyLong_AsLong` calls could theoretically be replaced with`Py_SIZE` checks and`ob_digit[0]` accesses, but I think the existing code is fine using the public API.
		it->step =Py_SAFE_DOWNCAST(step, long, sdigit);
		it->len =Py_SAFE_DOWNCAST(len, long, sdigit);
		it->index = 0;
		return (PyObject *)it;
		}
Expand DownExpand Up		@@ -1097,20 +1097,13 @@ range_iter(PyObject *seq)
		goto long_range;
		}
		ulen = get_len_of_range(lstart, lstop, lstep);
		if (ulen > (unsigned long)LONG_MAX) {
		if (ulen > PyLong_MASK \|\|
		lstart > PyLong_MASK \|\| lstart < -(long)PyLong_MASK \|\|
		lstop > PyLong_MASK \|\| lstop < -(long)PyLong_MASK \|\|
		lstep > PyLong_MASK \|\| lstep < -(long)PyLong_MASK)
		{
		goto long_range;
		}
		/* check for potential overflow of lstart + ulen * lstep */
		if (ulen) {
		if (lstep > 0) {
		if (lstop > LONG_MAX - (lstep - 1))
		goto long_range;
		}
		else {
		if (lstop < LONG_MIN + (-1 - lstep))
		goto long_range;
		}
		}
		return fast_range_iter(lstart, lstop, lstep, (long)ulen);

		long_range:
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -4399,17 +4399,42 @@ _PyEval_EvalFrameDefault(PyThreadState tstate, _PyInterpreterFrame frame, int
		_PyRangeIterObject r = (_PyRangeIterObject )TOP();
		DEOPT_IF(Py_TYPE(r) != &PyRangeIter_Type, FOR_ITER);
		STAT_INC(FOR_ITER, hit);
		if (r->index < r->len) {
		PyObject *res = PyLong_FromLong(
		(long)(r->start + (unsigned long)(r->index++) * r->step));
		if (res == NULL) {
		goto error;
		_Py_CODEUNIT next = next_instr[INLINE_CACHE_ENTRIES_FOR_ITER];
		assert(_PyOpcode_Deopt[_Py_OPCODE(next)] == STORE_FAST);
		PyObject **local_ptr = &GETLOCAL(_Py_OPARG(next));
		PyObject local = local_ptr;
		if (r->index >= r->len) {
		goto iterator_exhausted_no_error;
		}
		JUMPBY(INLINE_CACHE_ENTRIES_FOR_ITER + 1);
		sdigit value = r->start + (digit)(r->index++) * r->step;
		if (value < _PY_NSMALLPOSINTS && value >= -_PY_NSMALLNEGINTS) {
Copy link Member markshannonJun 17, 2022 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. I think there are too many branches here. Ideally a specialized instruction should have a few`DEOPT_IF` tests, then the rest of the code should be (mostly) branchless. This also includes far too much knowledge of the internals of the`int` object, IMO. Would performance be measurably worse if`start`,`end` and`stop` were`Py_ssize_t` and this code were simplified to `PyLong_FromSsize_t`? This feels like an elaborate workaround the oddities of our`int` implementation. We should be fixing that, not working around it. Copy link MemberAuthor sweeneydeJun 18, 2022 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. I think there may be a middle ground here: add a function like this to longobject.c: `int_PyLong_AssignValueLong(PyLongObject *location, long value){ if value in small: set to small, decref old long elif refcnt(location) == 1 and the right size: mutate in place else: Py_SETREF(location, PyLong_FromLong(value));}` Sort of similar in spirit to`PyUnicode_Append()` That way, the PyLongObject implementation details stay out of the eval loop, but we still get the benefit of avoiding the allocation, which I believe is the main source of the speedup. Copy link MemberAuthor sweeneyde*Jun 19, 2022 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. This could theoretically be re-used for`enumerate()` as well. And even if the implementation of integers changes (e.g. new freelists, no more small ints), the operation still makes sense.
		*local_ptr = Py_NewRef(&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS+value]);
		Py_XDECREF(local);
		NOTRACE_DISPATCH();
		}
sweeneyde marked this conversation as resolved. OutdatedShow resolvedHide resolved
		if (local && PyLong_CheckExact(local) && Py_REFCNT(local) == 1) {
		if (value > 0) {
		assert(value <= PyLong_MASK);
		((PyLongObject *)local)->ob_digit[0] = value;
		Py_SET_SIZE(local, 1);
		}
		else {
		assert(value >= -(sdigit)PyLong_MASK);
		((PyLongObject *)local)->ob_digit[0] = -(sdigit)value;
		Py_SET_SIZE(local, -1);
		}
		PUSH(res);
		JUMPBY(INLINE_CACHE_ENTRIES_FOR_ITER);
		NOTRACE_DISPATCH();
		}
		goto iterator_exhausted_no_error;
		PyObject *res = PyLong_FromLong(value);
		if (res == NULL) {
		// undo the JUMPBY
		next_instr -= INLINE_CACHE_ENTRIES_FOR_ITER + 1;
		goto error;
		}
		*local_ptr = res;
		Py_XDECREF(local);
		NOTRACE_DISPATCH();
		}

		TARGET(BEFORE_ASYNC_WITH) {
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -2064,16 +2064,18 @@ _Py_Specialize_ForIter(PyObject iter, _Py_CODEUNIT instr)
		assert(_PyOpcode_Caches[FOR_ITER] == INLINE_CACHE_ENTRIES_FOR_ITER);
		_PyForIterCache cache = (_PyForIterCache )(instr + 1);
		PyTypeObject *tp = Py_TYPE(iter);
		_Py_CODEUNIT next = instr[1+INLINE_CACHE_ENTRIES_FOR_ITER];
		int next_op = _PyOpcode_Deopt[_Py_OPCODE(next)];
		if (tp == &PyListIter_Type) {
		_Py_SET_OPCODE(*instr, FOR_ITER_LIST);
		goto success;
		}
		else if (tp == &PyRangeIter_Type) {
		else if (tp == &PyRangeIter_Type && next_op == STORE_FAST) {
		_Py_SET_OPCODE(*instr, FOR_ITER_RANGE);
		goto success;
		}
		else {
		SPECIALIZATION_FAIL(JUMP_BACKWARD,
		SPECIALIZATION_FAIL(FOR_ITER,
		_PySpecialization_ClassifyIterator(iter));
		goto failure;
		}
Expand Down