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

CROSS JOIN aliasing issue with certain Jobs #11

Open
thygrrr opened this issue May 31, 2024 · 1 comment
Open

CROSS JOIN aliasing issue with certain Jobs #11

thygrrr opened this issue May 31, 2024 · 1 comment
Labels
bug Something isn't working good first issue Good for newcomers mitigated This issue is currently mitigated and a temp fix is in place.

Comments

@thygrrr
Copy link
Collaborator

thygrrr commented May 31, 2024

What:

Certain algorithms operating on CROSS JOINS, e.g. in N-Body Problem sample, break under parallelization (i.e. when being run as a Job instead of a For) due to write destination aliasing.

Prelim Fix: (todo in 0.5.x)

Job can throw before operating over Stream Types with Wildcards.
This is trivial to implement in O(1) - in Query<>.Job> / Stream<>.Job(), check if any Stream Type is a wildcard and boom. 💣

This can even be paired with the below "wait for iteration WorkItems to finish" for a great halfway fix; the proper fix however mitigates the impact of Wildcards if the Archetype actually doesn't match them more than once - which is very common.

Proper Fix: (circa 0.7.x)

Join can likely report not only that is it empty or populated, but also whether it has repeat enumerations of the same storages (a simple bool - I think this can be calculated in advance for the entire join before the first Select/Iterate())

Then, Query.Job (or Stream.Job) needs to not queue new WorkItems for the next Iteration before all previous Items have completed (but it can still queue all chunks of each individual iteration at once, because there's no possibility of aliasing between WorkItems in the same Select!)

The problem arises when Join.Iterate() basically swaps Storages around for repeat enumeration, and many patterns of N:N enumeration can be problematic here if multi-threaded.

Related:

This may or may not become a different / simpler issue when other write aliasing protections are in place (e.g. Microscheduler for multiple parallel Jobs)

@thygrrr thygrrr added bug Something isn't working enhancement Improvement on existing implementation labels May 31, 2024
@thygrrr thygrrr assigned thygrrr and unassigned thygrrr May 31, 2024
@thygrrr thygrrr added the good first issue Good for newcomers label May 31, 2024
@thygrrr
Copy link
Collaborator Author

thygrrr commented Jun 13, 2024

Preliminary fix was made in 0.5.0 or 0.5.1, with the AssertNoWildcards placeholder in the job functions.

@thygrrr thygrrr changed the title CROSS JOIN aliasing issue with certain Jobs Bug: CROSS JOIN aliasing issue with certain Jobs Jun 14, 2024
@thygrrr thygrrr added mitigated This issue is currently mitigated and a temp fix is in place. and removed enhancement Improvement on existing implementation labels Jun 14, 2024
@thygrrr thygrrr changed the title Bug: CROSS JOIN aliasing issue with certain Jobs CROSS JOIN aliasing issue with certain Jobs Jun 15, 2024
@thygrrr thygrrr moved this to Backlog in fennecs ⚡🦊 Nov 6, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working good first issue Good for newcomers mitigated This issue is currently mitigated and a temp fix is in place.
Projects
Status: Backlog
Development

No branches or pull requests

1 participant