[Django] #32948: Optimise Q combination and inversion
Django
-------------------------------------+-------------------------------------
Reporter: Keryn | Owner: Keryn Knight
Knight |
Type: | Status: assigned
Cleanup/optimization |
Component: Database | Version: dev
layer (models, ORM) |
Severity: Normal | Keywords:
Triage Stage: | Has patch: 0
Unreviewed |
Needs documentation: 0 | Needs tests: 0
Patch needs improvement: 0 | Easy pickings: 0
UI/UX: 0 |
-------------------------------------+-------------------------------------
This is corollary to #32946 and #32940.
Q is currently inconsistent with it's friends `WhereNode` and `Node` in
that it doesn't use the `_new_instance` trick. Even using the
`_new_instance` trick leaves some performance on the table vs just
inlining the `__class__` switch, because it's an extra method call which
affects both `_combine()` and `__invert__()`.
The `_combine` method also has conditionals for what to do about an
''empty'' node being combined, either lhs or rhs. One side uses
`deconstruct`, the other uses the shallow copy protocol (only since
c8b659430556dca0b2fe27cf2ea0f8290dbafecd), which is unimplemented.
If `__copy__` is not implemented, it ultimately falls back (after some
branching checks) to the builtin `__reduce_ex__(4)` + `copy._reconstruct`
which gives:
{{{
In [3]: x = Q()
In [4]: %timeit copy.copy(x)
2.2 µs ± 70.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [5]: %timeit copy.copy(Q())
3.52 µs ± 264 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
}}}
If we implement the necessary method like so:
{{{
def __copy__(self):
obj = self._new_instance()
obj.__dict__ = self.__dict__.copy()
return obj
}}}
we can reduce those numbers to:
{{{
In [3]: x = Q()
In [4]: %timeit copy.copy(x)
1.27 µs ± 6.19 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops
each)
In [5]: %timeit copy.copy(Q())
2.37 µs ± 28.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
}}}
we can then reduce the work further by not invoking `copy.copy()` at all,
by setting the `copy = __copy__` attribute on the Q class.
From there, we can avoid calling `self.deconstruct()` at all, instead
calling `self.copy()` knowing that `self` has values, but `other` does
not. Both are basically on-par with eachother speedwise, with deconstruct
being faster on empty nodes (which `self` isn't) and copy being minimally
faster when there's a different connector (eg: `OR`).
For inverting, we can similarly change it to avoid the `Node.add()` call:
{{{
def __invert__(self):
obj = self.copy()
obj.negate()
return obj
}}}
which would allow it to go from:
{{{
In [2]: %timeit ~Q()
2.89 µs ± 18.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [3]: %timeit ~Q(a=1, b=2, c=3, d=4)
3.77 µs ± 57.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
}}}
to:
{{{
In [2]: %timeit ~Q()
2.34 µs ± 9.49 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [3]: %timeit ~Q(a=1, b=2, c=3, d=4)
3.14 µs ± 72.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
}}}
In totality, then, baselines:
{{{
In [2]: full = Q(a=1, b=2, c=3)
In [3]: full2 = Q(d=4, e=5, f=6)
In [4]: empty = Q()
In [5]: %timeit full & full2
2.65 µs ± 17.9 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [6]: %timeit full | full2
3 µs ± 39.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
In [7]: %timeit ~(full | full2)
5.09 µs ± 122 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [8]: %timeit ~(full & full2)
4.67 µs ± 58.5 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [9]: %timeit empty & full
2.81 µs ± 18.3 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [10]: %timeit full & empty
3.16 µs ± 43.4 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [11]: %timeit empty | full
2.8 µs ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [12]: %timeit full | empty
3.13 µs ± 20.3 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [13]: values = (Q(a=1), Q(b=2), Q(c=3), Q(d=4), Q(e__in=[1,2,3,4]))
In [14]: %timeit reduce(or_, values)
12 µs ± 212 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
}}}
and after the changes:
{{{
In [5]: %timeit full & full2
2.11 µs ± 20.8 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [6]: %timeit full | full2
2.39 µs ± 37.7 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [7]: %timeit ~(full | full2)
3.62 µs ± 47.2 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [8]: %timeit ~(full & full2)
3.34 µs ± 28.1 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
In [9]: %timeit empty & full
1.57 µs ± 14.7 ns per loop (mean ± std. dev. of 7 runs, 1000000
loops each)
In [10]: %timeit full & empty
1.68 µs ± 18.7 ns per loop (mean ± std. dev. of 7 runs, 1000000
loops each)
In [11]: %timeit empty | full
1.66 µs ± 24.1 ns per loop (mean ± std. dev. of 7 runs, 1000000
loops each)
In [12]: %timeit full | empty
1.8 µs ± 23 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops
each)
In [13]: values = (Q(a=1), Q(b=2), Q(c=3), Q(d=4), Q(e__in=[1,2,3,4]))
In [14]: %timeit reduce(or_, values)
9.59 µs ± 56.1 ns per loop (mean ± std. dev. of 7 runs, 100000
loops each)
}}}
A final note then, if inlining the `_new_instance` code into the copy
method were done, it looks like it shaves off 100-120ns per copy, from my
quick tests. So there is still performance on the table to put it fully
ahead of deconstruct (and another possibility exists - that the
deconstruction for migrations in some way gets more complex, negatively
affecting runtime performance for self copies)
I have a patch series which will need a little tidying (don't they
always?) but should pass CI when I open the PR for discussion.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.
Django
-------------------------------------+-------------------------------------
Type: | Knight
Cleanup/optimization | Status: assigned
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* stage: Unreviewed => Accepted
Comment:
Tentatively accepted, readability with the proposed patch is crucial to
me.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:1>
Django
-------------------------------------+-------------------------------------
Type: | Knight
Cleanup/optimization | Status: assigned
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Claude Paroz):
+1 to privilege readability over micro-optimization, if such a choice has
to be made.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:2>
Django
-------------------------------------+-------------------------------------
Type: | Knight
Cleanup/optimization | Status: assigned
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* has_patch: 0 => 1
Comment:
I don't ''think'' readability has been hurt by the change; I could argue
that it's been improved even, perhaps. Do judge for yourselves, naturally.
At this point there's 2 PRs to look at:
my original one: https://github.com/django/django/pull/14673
Nick P's one based on mine above:
https://github.com/django/django/pull/14677
Please note that the discussion about Nick's variant happened in-line in
my PR, as regrettably I didn't see the other PR until ''after'' we'd
started discussing the changes.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:3>
Django
-------------------------------------+-------------------------------------
Type: | Knight
Cleanup/optimization | Status: assigned
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 1
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* needs_better_patch: 0 => 1
Comment:
Marking as "needs improvement" because we need to reach a consensus before
the next review.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:4>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* owner: Keryn Knight => Nick Pope
* needs_better_patch: 1 => 0
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:5>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 1 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* needs_tests: 0 => 1
Comment:
From the discussion it seems that extra test coverage is needed.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:6>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* needs_tests: 1 => 0
Comment:
Unflagging "needs tests" as some have been added to cover the various
approaches to copying/cloning which should provide confidence that the
behaviour hasn't changed.
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:7>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"cc52e02c96e9e26d59c6512f18516657e353cbe1" cc52e02c]:
{{{
#!CommitTicketReference repository=""
revision="cc52e02c96e9e26d59c6512f18516657e353cbe1"
Refs #32948 -- Added more tests for django.utils.tree.Node.
The tests for creating new instances or copying instances of Node and
its subclasses didn't fully capture the behaviour of the implementation,
particularly around whether the `children` list or is contents were the
same as the source.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:8>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
| checkin
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* stage: Accepted => Ready for checkin
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:9>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"9dff316be41847c505ebf397e4a52a0a71e0acc4" 9dff316b]:
{{{
#!CommitTicketReference repository=""
revision="9dff316be41847c505ebf397e4a52a0a71e0acc4"
Refs #32948, Refs #32946 -- Used Q.create() internally for dynamic Q()
objects.
Node.create() which has a compatible signature with Node.__init__()
takes in a single `children` argument rather than relying in unpacking
*args in Q.__init__() which calls Node.__init__().
In addition, we were often needing to unpack iterables into *args and
can instead pass a list direct to Node.create().
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:14>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"ed9eca8457e1673d09adfc65392a214027053109" ed9eca84]:
{{{
#!CommitTicketReference repository=""
revision="ed9eca8457e1673d09adfc65392a214027053109"
Refs #32948 -- Simplified WhereNode and Node.__deepcopy__()/add().
We can use copy() in Node.add() instead of create() as we don't need the
children to be cloned via [:] subscript in __init__().
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:11>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"ddf0002bb760e5f1df664a81bd2a554c522f2c0f" ddf0002]:
{{{
#!CommitTicketReference repository=""
revision="ddf0002bb760e5f1df664a81bd2a554c522f2c0f"
Refs #32948 -- Renamed Node._new_instance() to Node.create().
Node._new_instance() was added in
6dd2b5468fa275d53aa60fdcaff8c28bdc5e9c25 to work around Q.__init__()
having an incompatible signature with Node.__init__().
It was intended as a hook that could be overridden if subclasses needed
to change the behaviour of instantiation of their specialised form of
Node. In practice this doesn't ever seem to have been used for this
purpose and there are very few calls to Node._new_instance() with other
code, e.g. Node.__deepcopy__() calling Node and overriding __class__ as
required.
Rename this to Node.create() to make it a more "official" piece of
private API that we can use to simplify a lot of other areas internally.
The docstring and nearby comment have been reworded to read more
clearly.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:10>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"19b866c254b54d904a942f34d662dfacd9005a77" 19b866c2]:
{{{
#!CommitTicketReference repository=""
revision="19b866c254b54d904a942f34d662dfacd9005a77"
Refs #32948 -- Added Node.__copy__().
This allows the copy.copy() usage in the Q._combine() method to finish
sooner, instead of having to fallback to using the __reduce_ex__(4)
method.
Thia also avoids having to fall into copy.copy() at in Q._combine(),
when combining a Q() with another Q().
Co-authored-by: Keryn Knight <ke...@kerynknight.com>
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:12>
Django
-------------------------------------+-------------------------------------
Type: | Status: assigned
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by Mariusz Felisiak <felisiak.mariusz@…>):
In [changeset:"845667f2d1eb7063c568764a01fc9ee633ec5817" 845667f2]:
{{{
#!CommitTicketReference repository=""
revision="845667f2d1eb7063c568764a01fc9ee633ec5817"
Refs #32948 -- Simplified and optimized Q._combine() and __invert__().
- Removed use of Q.deconstruct() in Q._combine().
- Simplified and optimized Q.__invert__() by taking a shallow copy and
swapping the negated attribute only.
- Simplified construction in Q._combine().
- Simplified conditions in Q._combine() as Q.conditional = True the
first isinstance() check is unnecessary.
- Removed copy.copy() branch in Q._combine().
Co-authored-by: Keryn Knight <ke...@kerynknight.com>
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:13>
Django
-------------------------------------+-------------------------------------
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Keywords: | Triage Stage: Ready for
| checkin
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* status: assigned => closed
* resolution: => fixed
--
Ticket URL: <https://code.djangoproject.com/ticket/32948#comment:15>