-
-
Notifications
You must be signed in to change notification settings - Fork 18
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
Parallel comemo & optimizations #5
Conversation
Using a sharded list of accelerators.
So, after much discussion on the Discord, here are some more changes:
Overall, this provides a nice performance bump for Typst, being about 1.5x faster in most tests than before these additional changes. Note that this was measured on a currently ongoing rework of Typst to be parallelized so take those numbers with a grain of salt. |
It seems that they are using Acquire/AcqRel/... now. Do they give a big performance gain? |
Not really but it doesn't have any negative impact either, do you have any idea on which would be better ? |
i prefer seqcst because it is very hard to get the correct memory order. if it is wrong, it will be very hard to reproduce and diagnose the bug. |
Cargo.toml
Outdated
@@ -10,6 10,16 @@ license = "MIT OR Apache-2.0" | |||
categories = ["caching"] | |||
keywords = ["incremental", "memoization", "tracked", "constraints"] | |||
|
|||
[features] | |||
default = [ "last_was_hit" ] | |||
last_was_hit = [] |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think a more generic debugging/testing feature would be nicer. It should probably also not be enabled by default.
Thank you for the great work here! |
This PR introduces the following changes:
OnceCell
Box<dyn Any>
that was used beforeTypeId
when doing cache lookupsImmutableConstraint
which involves the following changes:#[track]
ed struct only has immutable methods, we can just use aHashMap
of visited functions which is faster for lookups, also has some niceties to save some work during validation, etc.Constraint
:Vec<Call<T>>
for storing function calls in orderHashMap<u128, usize>
for storing immutable calls since the last mutable call, this allows much faster lookups in the event of a mixed mutable-immutables tracked struct.test_evict
running in parallel and evicting the cache of other testslast_was_hit
is now behind a feature flag: we don't need it in actual applications and it saves some time, it's thread-localDashMap
to avoid a bug in Safari. The problem with making two implementations is thatConstraint
,ImmutableConstraint
, andACCELERATOR
would all change leading to large code duplication, but if @laurmaedje wants it implemented this may, I think it would show better performance on "native" targets.hashbrown::HashMap
as they can be slightly faster and we already have this dependency in Typst fromindexmap
.memoized_generic
that still uses aBox<dyn Any>
under the hood. However, generic memoized functions are not part of Typst and therefore I am unsure whether the burden of maintaining two implementations is worth it.Self
, it has to be the full name of the type. This is very minor and has little to no impact on functionality.SeqCst
ordering, but I wonder whether they could be made with a less restrictive ordering but I am not knowledgeable enough for this.Overall, and in spite of locking, these changes bring gigantic performance gains in incremental in Typst, in some cases doubling incremental performance.