This commit improves the performance of type resolution when returning interface types from a resolver by defining resolve_type that is called once per item. Without the existence of resolve_type the is_type_of method on each interface implementation is called until a True value is returned. See performance improvements below:

resolve_performance_dracula resolve_performance_dufte

Benchmark Code


from collections import defaultdict
from functools import partial
from timeit import timeit
from typing import DefaultDict, List, Sequence, Type, TypeVar

import matplotx
import numpy as np
from matplotlib import pyplot as plt
from perfplot._main import PerfplotData

import strawberry
from strawberry.scalars import ID


T = TypeVar("T")


@strawberry.interface
class Item:

    id: ID


@strawberry.interface
class ResolvedItem:

    id: ID

    def resolve_type(self, *args):
        type_definition = self._type_definition  # type: ignore
        if isinstance(self, type_definition.origin):
            return type_definition.name


def create_schema(n_items: int, n_types: int, item_type: Type) -> strawberry.Schema:
    CONCRETE_TYPES = []
    for i in range(n_types):
        CONCRETE_TYPES.append(strawberry.type(type(f"Item{i}", (item_type,), {})))

    items_list = [CONCRETE_TYPES[i % n_types](id=i) for i in range(n_items)]

    @strawberry.type
    class Query:

        items: List[item_type]  # type: ignore

    class Schema(strawberry.Schema):
        def execute_sync(self, *args, **kwargs):
            kwargs.update(root_value=Query(items=items_list))
            return super().execute_sync(*args, **kwargs)

    return Schema(query=Query, types=CONCRETE_TYPES)


get_resolve_type_schema = partial(create_schema, item_type=ResolvedItem)
get_is_type_of_schema = partial(create_schema, item_type=Item)

query = "query { items { id } }"


def benchmark(n_range: Sequence[int], n_repeats: int = 3):
    kernels = {
        "is_type_of (n_types = 2)": partial(get_is_type_of_schema, n_types=2),
        "is_type_of (n_types = 16)": partial(get_is_type_of_schema, n_types=16),
        "is_type_of (n_types = 32)": partial(get_is_type_of_schema, n_types=32),
        "resolve_type (n_types = 2)": partial(get_resolve_type_schema, n_types=2),
        "resolve_type (n_types = 16)": partial(get_resolve_type_schema, n_types=16),
        "resolve_type (n_types = 32)": partial(get_resolve_type_schema, n_types=32),
    }
    results: DefaultDict[str, List[float]] = defaultdict(list)
    for label, schema_fn in kernels.items():
        timings = results[label]
        for n_items in n_range:
            schema = schema_fn(n_items=n_items)
            repeats = []
            for _ in range(n_repeats):
                repeats.append(timeit(lambda: schema.execute_sync(query), number=1))
            timings.append(min(repeats))
    timings = np.vstack([np.array(r) for r in results.values()])
    return PerfplotData(
        n_range=n_range,
        labels=tuple(kernels.keys()),
        xlabel="$n_{items}$",
        timings_s=timings,
        flop=None,
        title=None,
    )


results = benchmark(n_range=[2 ** k for k in range(0, 13, 4)], n_repeats=10)

for style in ("dufte", "dracula"):
    plt.style.use(getattr(matplotx.styles, style))
    results.save(
        f"resolve_performance_{style}.svg",
        transparent=False,
        bbox_inches="tight",
        relative_to=0,
    )

Types of Changes

[ ] Core
[ ] Bugfix
[x] New feature
[x] Enhancement/optimization
[ ] Documentation

Checklist

[x] My code follows the code style of this project.
[x] My change requires a change to the documentation.
[ ] I have updated the documentation accordingly.
[x] I have read the CONTRIBUTING document.
[x] I have added tests to cover my changes.
[x] I have tested the changes and verified that they work and don't break anything (as well as I can manage).

Jun 07 '22 17:06 skilkis

@patrick91 @bellini666 @BryceBeagle another area we can gain a tiny bit of performance. This is low priority, but I wanted to make this draft PR so we keep it in mind 😊

Jun 07 '22 17:06 skilkis

Codecov Report

Merging #1949 (5a6cb92) into main (1360e30) will increase coverage by 0.00%. The diff coverage is 100.00%.

Additional details and impacted files

@@           Coverage Diff           @@
##             main    #1949   +/-   ##
=======================================
  Coverage   96.11%   96.11%           
=======================================
  Files         211      211           
  Lines        9232     9242   +10     
  Branches     1489     1491    +2     
=======================================
+ Hits         8873     8883   +10     
  Misses        229      229           
  Partials      130      130

Jun 07 '22 17:06 codecov[bot]

@skilkis @patrick91 Hey everyone, what's the status on this PR? I'm really interested in this feature and willing to help implement it 🙏🏽🍓

Jul 13 '23 14:07 iamkhav

Hey @iamkhav, thanks for the comment this PR has gone stale for a while. Implementation wise I'm done, I'll quickly rebase and push my latest changes. I see that @patrick91 recently implemented codspeed on this repo so that's very exciting. I'll add a simple benchmark with this PR. Would you be interested in contributing a benchmark as well? 🚀

Jul 13 '23 20:07 skilkis

Before:

------------------------------------------------------------------------------------------ benchmark: 4 tests ------------------------------------------------------------------------------------------
Name (time in ms)                         Min                 Max                Mean            StdDev              Median               IQR            Outliers      OPS            Rounds  Iterations
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_interface_performance[1]         18.0224 (1.0)       50.3003 (1.77)      20.0878 (1.0)      5.1488 (5.14)      18.9523 (1.0)      0.7415 (1.39)          2;4  49.7814 (1.0)          41           1
test_interface_performance[16]        22.0060 (1.22)      28.4240 (1.0)       22.8433 (1.14)     1.0016 (1.0)       22.6946 (1.20)     0.5321 (1.0)           3;3  43.7764 (0.88)         40           1
test_interface_performance[256]       69.1364 (3.84)      76.1349 (2.68)      72.2835 (3.60)     2.7917 (2.79)      72.1791 (3.81)     5.3980 (10.14)         4;0  13.8344 (0.28)          8           1
test_interface_performance[4096]     219.6461 (12.19)    231.3732 (8.14)     226.4553 (11.27)    4.4473 (4.44)     227.2840 (11.99)    5.8001 (10.90)         2;0   4.4159 (0.09)          5           1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

After:

---------------------------------------------------------------------------------------- benchmark: 4 tests ----------------------------------------------------------------------------------------
Name (time in ms)                        Min                Max               Mean            StdDev             Median               IQR            Outliers      OPS            Rounds  Iterations
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_interface_performance[1]        14.3921 (1.0)      46.2064 (2.79)     16.3355 (1.05)     4.2380 (10.94)    15.5533 (1.0)      0.6572 (1.46)          2;5  61.2163 (0.96)         57           1
test_interface_performance[16]       14.8669 (1.03)     16.5732 (1.0)      15.6205 (1.0)      0.3874 (1.0)      15.6228 (1.00)     0.5508 (1.22)         19;0  64.0185 (1.0)          61           1
test_interface_performance[256]      15.8977 (1.10)     24.4618 (1.48)     17.5442 (1.12)     1.2834 (3.31)     17.2590 (1.11)     0.8033 (1.78)          7;4  56.9989 (0.89)         53           1
test_interface_performance[4096]     18.7340 (1.30)     21.2899 (1.28)     19.5104 (1.25)     0.4120 (1.06)     19.4837 (1.25)     0.4509 (1.0)          14;1  51.2548 (0.80)         51           1
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This can be verified by commenting out the resolve_type=_get_resolve_type() argument in GraphQLCoreConverter.from_interface

Jul 13 '23 20:07 skilkis

CodSpeed Performance Report

Merging #1949 will improve performances by ×26

_{Comparing skilkis:feature/improve_interface_performance (5a6cb92) with main (1360e30)}

Summary

🔥 4 improvements ✅ 1 untouched benchmarks

Benchmarks breakdown

	Benchmark	`main`	`skilkis:feature/improve_interface_performance`	Change
🔥	`test_interface_performance[1]`	277.5 ms	218.4 ms	+27.09%
🔥	`test_interface_performance[16]`	364.8 ms	214.5 ms	+70.1%
🔥	`test_interface_performance[256]`	1,801.3 ms	223.8 ms	×8
🔥	`test_interface_performance[4096]`	6,359.1 ms	246.7 ms	×26

Jul 13 '23 20:07 codspeed-hq[bot]

Thanks for adding the RELEASE.md file!

Here's a preview of the changelog:

Improve the time complexity of strawberry.interface using resolve_type. Achieved time complexity is now O(1) with respect to the number of implementations of an interface. Previously, the use of is_type_of resulted in a worst-case performance of O(n).

Before:

---------------------------------------------------------------------------
Name (time in ms)                         Min                 Max
---------------------------------------------------------------------------
test_interface_performance[1]         18.0224 (1.0)       50.3003 (1.77)
test_interface_performance[16]        22.0060 (1.22)      28.4240 (1.0)
test_interface_performance[256]       69.1364 (3.84)      76.1349 (2.68)
test_interface_performance[4096]     219.6461 (12.19)    231.3732 (8.14)
---------------------------------------------------------------------------

After:

---------------------------------------------------------------------------
Name (time in ms)                        Min                Max
---------------------------------------------------------------------------
test_interface_performance[1]        14.3921 (1.0)      46.2064 (2.79)
test_interface_performance[16]       14.8669 (1.03)     16.5732 (1.0)
test_interface_performance[256]      15.8977 (1.10)     24.4618 (1.48)
test_interface_performance[4096]     18.7340 (1.30)     21.2899 (1.28)
---------------------------------------------------------------------------

Here's the preview release card for twitter:

Here's the tweet text:

🆕 Release (next) is out! Thanks to San Kilkis for the PR 👏

Get it here 👉 https://github.com/strawberry-graphql/strawberry/releases/tag/(next)

Jul 13 '23 20:07 botberry

Hey @skilkis, thanks so much for the quick response! As requested, here are the benchmark results obtained from running the tests on my machine.

Before:

------------------------------------------------------------------------------------------- benchmark: 4 tests ------------------------------------------------------------------------------------------
Name (time in ms)                         Min                 Max                Mean            StdDev              Median               IQR            Outliers       OPS            Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_interface_performance[1]          6.6333 (1.0)        8.3878 (1.0)        6.9347 (1.0)      0.2959 (1.0)        6.8261 (1.0)      0.3523 (1.0)          19;5  144.2030 (1.0)         123           1
test_interface_performance[16]         8.4697 (1.28)      10.3100 (1.23)       8.8984 (1.28)     0.4019 (1.36)       8.7234 (1.28)     0.6608 (1.88)         22;1  112.3792 (0.78)         76           1
test_interface_performance[256]       32.9080 (4.96)      35.2016 (4.20)      33.6217 (4.85)     0.7459 (2.52)      33.6041 (4.92)     0.8256 (2.34)          1;1   29.7427 (0.21)          9           1
test_interface_performance[4096]     111.7712 (16.85)    115.1568 (13.73)    113.4827 (16.36)    1.4652 (4.95)     113.6300 (16.65)    2.6300 (7.46)          2;0    8.8119 (0.06)          5           1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

After:

--------------------------------------------------------------------------------------- benchmark: 4 tests ---------------------------------------------------------------------------------------
Name (time in ms)                       Min                Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_interface_performance[1]        5.1455 (1.0)       6.2182 (1.0)      5.5483 (1.0)      0.1878 (1.0)      5.5265 (1.0)      0.2634 (1.0)          48;2  180.2352 (1.0)         157           1
test_interface_performance[16]       5.3090 (1.03)      6.9405 (1.12)     5.6823 (1.02)     0.2224 (1.18)     5.6597 (1.02)     0.3209 (1.22)         51;1  175.9864 (0.98)        164           1
test_interface_performance[256]      5.4854 (1.07)      7.0765 (1.14)     6.0096 (1.08)     0.3587 (1.91)     5.9452 (1.08)     0.5926 (2.25)         59;0  166.3992 (0.92)        164           1
test_interface_performance[4096]     6.1811 (1.20)     99.4073 (15.99)    7.6783 (1.38)     8.2804 (44.09)    6.8460 (1.24)     0.5935 (2.25)          1;1  130.2373 (0.72)        125           1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Jul 14 '23 10:07 iamkhav

just-do-it-running-gif-by-rocky

Jul 14 '23 17:07 patrick91

strawberry
strawberry copied to clipboard

Improve interface performance using resolve_type

Types of Changes

Checklist

Codecov Report

CodSpeed Performance Report

Merging #1949 will improve performances by ×26

Summary

Benchmarks breakdown

strawberry strawberry copied to clipboard

Improve interface performance using resolve_type

Types of Changes

Checklist

Codecov Report

CodSpeed Performance Report

Merging #1949 will improve performances by ×26

Summary

Benchmarks breakdown

strawberry
strawberry copied to clipboard