Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

perf(common): improve equality caching by explicitly invalidating the entry on __del__ #8708

Merged
merged 1 commit into from
Mar 21, 2024

Conversation

kszucs
Copy link
Member

@kszucs kszucs commented Mar 20, 2024

Previously we used a rather complicated mechanism to implement global equality cache for operation nodes involving tricky weak reference tracking registering callbacks to invalidate cache entries.

While this has greatly improved the overall performance of ibis internals we can have a simpler and more lightweight implementation by storing the equality comparison results in a dict[dict[object_id, bool]] data structure which allows us quick lookups and quick deletions. The caching is also specialized to a pair of objects in contrary to the previous WeakCache implementation which supported arbitrary number of key elements requiring multiple iterations over the key tuple.

---------------------------------------------------------------------------- benchmark 'test_bfs': 2 tests -----------------------------------------------------------------------------
Name (time in ms)              Min               Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_bfs (0653_384b10f)     2.4032 (1.21)     2.7302 (1.14)     2.5057 (1.21)     0.0630 (1.0)      2.4830 (1.21)     0.0666 (1.0)         25;12  399.0923 (0.83)        169           1
test_bfs (NOW)              1.9786 (1.0)      2.3859 (1.0)      2.0748 (1.0)      0.0786 (1.25)     2.0521 (1.0)      0.0939 (1.41)         55;7  481.9678 (1.0)         229           1
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------- benchmark 'test_dfs': 2 tests -----------------------------------------------------------------------------
Name (time in ms)              Min               Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_dfs (0653_384b10f)     2.3311 (1.18)     2.9268 (1.27)     2.4361 (1.17)     0.0925 (1.34)     2.3920 (1.14)     0.0478 (1.0)         23;25  410.4854 (0.86)        158           1
test_dfs (NOW)              1.9766 (1.0)      2.3061 (1.0)      2.0900 (1.0)      0.0689 (1.0)      2.0892 (1.0)      0.1262 (2.64)        107;0  478.4618 (1.0)         262           1
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------ benchmark 'test_equality': 2 tests -----------------------------------------------------------------------------------
Name (time in ns)                     Min                 Max                Mean             StdDev              Median                IQR            Outliers  OPS (Mops/s)            Rounds  Iterations
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_equality (0653_384b10f)     488.4580 (3.06)     670.3340 (2.18)     532.9611 (3.12)     14.3697 (2.14)     530.4795 (3.15)     17.6670 (3.26)     2752;186        1.8763 (0.32)      10000        1000
test_equality (NOW)              159.7090 (1.0)      307.0830 (1.0)      171.0032 (1.0)       6.7183 (1.0)      168.4161 (1.0)       5.4170 (1.0)       777;371        5.8478 (1.0)       10000        1000
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------- benchmark 'test_replace_mapping': 2 tests -----------------------------------------------------------------------------
Name (time in ms)                          Min                Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_replace_mapping (0653_384b10f)     9.3701 (1.11)     10.6236 (1.0)      9.6592 (1.02)     0.2626 (1.0)      9.5760 (1.08)     0.1286 (1.0)           4;5  103.5287 (0.98)         30           1
test_replace_mapping (NOW)              8.4357 (1.0)      28.9518 (2.73)     9.5036 (1.0)      3.4945 (13.31)    8.8787 (1.0)      0.3668 (2.85)          3;3  105.2228 (1.0)          87           1
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------ benchmark 'test_replace_pattern': 2 tests ------------------------------------------------------------------------------
Name (time in ms)                           Min                Max               Mean            StdDev             Median               IQR            Outliers      OPS            Rounds  Iterations
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_replace_pattern (0653_384b10f)     13.3895 (1.10)     32.2786 (1.0)      14.7143 (1.10)     3.2605 (1.0)      14.2861 (1.13)     0.5695 (1.0)           2;2  67.9613 (0.91)         61           1
test_replace_pattern (NOW)              12.2229 (1.0)      34.5245 (1.07)     13.3812 (1.0)      3.3891 (1.04)     12.6136 (1.0)      0.7824 (1.37)          2;2  74.7315 (1.0)          64           1
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@kszucs kszucs force-pushed the equality-cache branch 2 times, most recently from 2278cb0 to 4eeb05b Compare March 20, 2024 13:09
@kszucs kszucs requested a review from cpcloud March 20, 2024 13:15
@cpcloud cpcloud added this to the 9.0 milestone Mar 20, 2024
@cpcloud cpcloud added the performance Issues related to ibis's performance label Mar 20, 2024
@kszucs kszucs merged commit ac86f91 into ibis-project:main Mar 21, 2024
81 checks passed
@kszucs kszucs deleted the equality-cache branch March 21, 2024 10:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Issues related to ibis's performance
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants