[Django] #36705: Repeated string concatenation is slow on some python implementations, in particular PyPy

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Type:
| Cleanup/optimization
Status: new | Component: Utilities
Version: dev | Severity: Normal
Keywords: PyPy | Triage Stage:
| Unreviewed
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
There is a [https://pypy.org/posts/2023/01/string-concatenation-
quadratic.html known limitation] in PyPy that repeated string
concatenation is slow. The discussion there observes that CPython has an
optimization, but it's fragile and best not relied on.

Seokchan Yoon (thanks for the report!) raised this with the security team,
and we decided any hardening here could be done in public.

To close this ticket, we should:
- implement targeted optimizations in django.utils.numberformat.format()
to avoid repeated string concatenation
- audit for other similar cases
- Add a disclaimer to our
[https://docs.djangoproject.com/en/5.2/topics/performance/#id1
documentation] around PyPy, for example, wording like:

> That said, a lot of a web framework's work is done by concatenating
strings, and PyPy has an issue with that (see
https://pypy.org/posts/2023/01/string-concatenation-quadratic.html). This
may cause performance issues, depending on your use.
--
Ticket URL: <https://code.djangoproject.com/ticket/36705>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy

--------------------------------------+------------------------------------
Reporter: Jacob Walls | Owner: (none)

Type: Cleanup/optimization | Status: new
Component: Utilities | Version: dev

Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted

Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0

--------------------------------------+------------------------------------
Changes (by Natalia Bidart):

* stage: Unreviewed => Accepted

Comment:

Thank you Jacob!
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:1>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy

-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned

Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0

-------------------------------------+-------------------------------------
Changes (by Varun Kasyap Pentamaraju):

* owner: (none) => Varun Kasyap Pentamaraju
* status: new => assigned

Comment:

I am willing to contribute
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:2>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted

Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Changes (by Varun Kasyap Pentamaraju):

* has_patch: 0 => 1

Comment:

Created PR https://github.com/django/django/pull/20045
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:3>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 1

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Jacob Walls):

* needs_better_patch: 0 => 1

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:4>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 0

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Varun Kasyap Pentamaraju):

* needs_better_patch: 1 => 0

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:5>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 1

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Jacob Walls):

* needs_better_patch: 0 => 1

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:6>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 0

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Varun Kasyap Pentamaraju):

* needs_better_patch: 1 => 0

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:7>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:
Keywords: PyPy | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 1

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Jacob Walls):

* needs_better_patch: 0 => 1

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:8>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: assigned
Component: Utilities | Version: dev
Severity: Normal | Resolution:

Keywords: PyPy | Triage Stage: Ready for
| checkin

Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 0

Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Changes (by Jacob Walls):

* needs_better_patch: 1 => 0
* stage: Accepted => Ready for checkin

--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:9>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju

Cleanup/optimization | Status: closed
Component: Utilities | Version: dev
Severity: Normal | Resolution: fixed

Keywords: PyPy | Triage Stage: Ready for
| checkin
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Jacob Walls <jacobtylerwalls@…>):

* resolution: => fixed
* status: assigned => closed

Comment:

In [changeset:"1c7db70e79dce82f50d5958da64ab8e2807a31df" 1c7db70]:
{{{#!CommitTicketReference repository=""
revision="1c7db70e79dce82f50d5958da64ab8e2807a31df"
Fixed #36705 -- Avoided string concatenation in utils.

Repeated string concatenation performs poorly on PyPy.
Thanks Seokchan Yoon for the report.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:10>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: closed
Component: Utilities | Version: dev
Severity: Normal | Resolution: fixed
Keywords: PyPy | Triage Stage: Ready for
| checkin
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Comment (by Adam Johnson):

I'm a little bit skeptical of this change's necessity, and I think it may
have introduced an issue:
https://github.com/django/django/pull/20045/files#r2544009071 . PyPy
currently only supports Python 3.11, while Django's main branch targets
Python 3.12+, so it's not clear when anyone could use the change. Also,
I've never heard of a Django project using PyPy—it seems impractical
ecosystemwise.
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:11>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: closed
Component: Utilities | Version: dev
Severity: Normal | Resolution: fixed
Keywords: PyPy | Triage Stage: Ready for
| checkin
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Comment (by Jacob Walls):

Thanks for spotting the logic change. I replied that there's a chance the
logic change is more correct: we should add a test to be sure.

I heard that Django has never supported PyPy as a deployment target.
Despite whispers of PyPy winding down, it seems to be slowly keeping up in
its own time.

For me, this change wasn't just about PyPy. I was persuaded by the linked
blog post's explanation that even in CPython adequate performance on
catastrophic string concatenation depends on a fragile optimization.
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:12>

[Django]

#36705: Repeated string concatenation is slow on some python implementations, in
particular PyPy
-------------------------------------+-------------------------------------
Reporter: Jacob Walls | Owner: Varun
Type: | Kasyap Pentamaraju
Cleanup/optimization | Status: closed
Component: Utilities | Version: dev
Severity: Normal | Resolution: fixed
Keywords: PyPy | Triage Stage: Ready for
| checkin
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Comment (by Jacob Walls <jacobtylerwalls@…>):

In [changeset:"3f15935420c0f45760804b807a78a26f4ffe28e4" 3f15935]:
{{{#!CommitTicketReference repository=""
revision="3f15935420c0f45760804b807a78a26f4ffe28e4"
Refs #36705 -- Added coverage for multiple types of enclosing punctuation
in urlize().

This case was inadvertently fixed in
ad94446fcc5b50401dd0c48718502d5d1b92df58.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/36705#comment:13>