-
Notifications
You must be signed in to change notification settings - Fork 4
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
Crazy brainstorming #5
Comments
There are a lot of things i'd like to do with pararules. There is one feature in my clojure rules engine that i haven't ported over yet. In o'doyle, you can specify Beyond that, i'd like to make pararules use immutable data structures internally, because it would be faster. Clojure has them built-in but in nim i'd have to write them myself. There are a few places i have to make full local copies of sequences so i can hold on to the old version of a piece of data while it's being modified; with immutable data this would be a constant time operation. |
My idea is to finally try to crack the "interactive animation barrier" in UIs and games. Basically allowing "animating" everything (incl. based on user/any input, incl. non-visual outcomes like sound, motor control, etc.). And with "everything" I really mean it (see also https://github.com/slint-ui/slint/tree/master/examples , https://dribbble.com/shots/5362972-Airlines-Survey , and many other modern designs on dribble.com , Bret Victor's demos, etc.). In other words I need complex logic and simultaneously high performance 😉. Btw. if you didn't yet, I can only recommend all the public talks etc. Bret Victor did (e.g. https://www.youtube.com/watch?v=8pTEmbeENF4 , http://worrydream.com/KillMath/ , https://www.youtube.com/watch?v=PUv66718DII , https://www.youtube.com/watch?v=klTjiXjqHrQ , https://www.youtube.com/watch?v=ZfytHvgHybA , https://www.youtube.com/watch?v=FavMKy9sCtA ...).
No worries, I really meant just the true data dependency. No other "ordering".
Yep, that was the idea. It might sound surprising, but
I just want to get around the confusion stemming from:
Yep. My motivation is as mentioned above - basically "all inclusive". I.e. also lots of particles must not get the system on the knees easily. That's another reason why I spoke about (7).
That'd be best. It's just that now it might not be intuitive to decide whether to use
I didn't read any internals of Basically something what JIT language engines try to do but already in compile time to leverage the possibility of the programmer optimizing some bits by hand (or alternatively at least providing some hints of sort - imagine something analogous to
Basically yes. Though I guess there are also other ways to do it. I can imagine leveraging the fact we know in compile time the max number of rules. Therefore it might be more performant to store a flag for certain (or all if stored as compressed bit sets or whatever will be performant) rules denoting whether the rule is still valid or got "retracted". Sure, the rule will stay in memory even if we won't insert it any more (which would lift the retraction flag), but that's the tradeoff for much higher performance than with e.g. tables. But again, I didn't read
Sounds like a very good optimization. It's yet another thing falling under (7) 😉.
I'm looking forward to that! |
I've seen many of Bret Victor's talks but it's hard for me to picture the physical spaces he's talking about. You'd be tempted to say that VR could do it, but he would be the first to say that tactile feedback is crucial, and that is still an open research problem with VR. In dynamicland he's using actual physical objects and projectors, so it's not primarily a software rendering problem i guess.
I'm guessing
I'm still not clear on what
Yeah there may be an opportunity there to optimize but i don't have any ideas for how to do it right now.
I think it would be possible to do this by changing the macro to provide one more branch in the type it generates, which would provide a |
You're right, it's definitely not primarily a SW rendering problem. But if we focus on the SW part, there must not be such an obstackle as superlinear work to be done when scaling in number of inputs. I didn't look at the theory behind rules engines and I kind of sense there might even exist a mathematical proof it can't scale better than superlinearly, but I'm really focused on practical usage and therefore I don't care bubble sort is really the worst mathematically but it's the best known for small inputs (it's very close to an optimal sorting network for the given length).
rule movePlayer(Fact):
what:
(Global, DeltaTime, dt)
(Player, X, x, then = false)
then:
session.insert(Player, X, x + dt) would turn into this: rule movePlayer(Fact):
what:
(Global, DeltaTime, dt)
(Player, X, x, overwrite = true)
then:
session.insert(Player, X, x + dt) while (unlike the first example) the following would not cause any infinite loop (ideally this wouldn't even compile if it detected there is not even a single "overwrite = true" in the given rule movePlayer(Fact):
what:
(Global, DeltaTime, dt) # same as (Global, DeltaTime, dt, overwrite = false)
(Player, X, x) # same as (Player, X, x, overwrite = false)
then:
session.insert(Player, X, x + dt)
It'd find all places, where the given rule is being reacted upon, then recursively do the same search for every neighbouring rule in all the found places. This would yield a set of nodes which form a directed graph of dependencies. Then a simple This should give us the gurantee the situation:
can never happen and thus this confusing behavior demonstrated on the
Hm, I'm now confused as it seems. Having a
Let's see the benchmarks. Profiling the benchmarks could give us sufficient pointers how to approach this. |
But in your example, you have
My best guess is that you're trying to describe truth maintenance, where facts are retracted automatically when the conditions that were true during their insertion become false. This is a pretty useful feature but not one that i've implemented yet.
The |
Sorry, this is all my bad (there is a mistake in my last code example and I realized that'd anyway lead to similar problems I actually want to avoid). Let's rewind this whole topic and let me start from scratch 😉. I'd like So an Of coure, implementation of this principle wouldn't be through a hash map per attribute per rule, but something widely different for performance reasons (perhaps a separate multidimensional "matrix" of compressed bits; IDK). This could be perhaps partially optimized in compile time based on static analysis of the Does this make more sense?
More or less yes - I thought
Ok. Could you then provide the simpliest possible example which would not use So far I feel |
I don't think it would be possible to guarantee there are no infinite loops. After all, a rule can use a conditional to limit inserts: rule movePlayer(Fact):
what:
(Global, DeltaTime, dt)
(Player, X, x)
then:
if x < 100:
session.insert(Player, X, x + dt) So any static analysis would have to take into account arbitrary conditions when deciding if an infinite loop will occur, which is impossible since it requires information only known at runtime.
A big use case for Imagine i insert a bunch of "characters" (basically just x,y coords for now) into the session: for _ in 0 ..< 5:
session.insert(nextId, X, rand(50.0))
session.insert(nextId, Y, rand(50.0))
nextId += 1 I could make a rule that aggregates them together into a single fact: rule getCharacter(Fact):
what:
(id, X, x)
(id, Y, y)
then:
let chars = session.queryAll(this)
session.insert(Derived, AllCharacters, chars) Now the AllCharacters fact will contain something like But the problem with using rule getCharacter(Fact):
what:
(id, X, x)
(id, Y, y)
thenFinally:
let chars = session.queryAll(this)
session.insert(Derived, AllCharacters, chars) |
That's why I wrote "potential But forget about the optimization. The point was to track the dependency chain to see if it contains the current rule or not. I don't see any technical reason to not do it. The only question is IMHO performance. But I'd like to know your detailed opinion because it seems I'm still unsure how exactly FYI my understanding is that the rules engine gets started each frame (assuming a game) explicitly by the programmer (from the main event loop) and then zero or more times internally as a reaction to each If it's not like this, please add a visual diagram describing the flow (including the main event loop of a game and including how
Perfect, thanks for the clear example. It moved me a big leap forward (despite it might not seem so from the following text 😄). Does If so, then I feel such synchronicity "behind the scenes" is quite fragile for the programmer. It might also be problematic for async stuff as well as potentially for multithreading (incl. flowvars). I just hope it's not implemented like this 😉. I still can't get away from the feeling that |
But that would forbid rules from calling themselves at all. There are many times that i want rules to call themselves sometimes, but obviously not infinitely.
No, that has nothing to do with it.
I can't really respond to a vague "feeling", but if you are admittedly confused about something, try understanding it before calling it hacky. |
I've thrown together a small benchmark over here: https://gist.github.com/ajusa/eb2d177ff699fc09a0d5098e67908ed4 This is a simple rule with lots of entities, so it isn't really favorable to pararules. @oakes, I feel like I must be doing something wrong for there to be this much of a difference with polymorph. Please let me know if that is the case, I will update the gist and rerun the benchmarks. My intention is not to mislead or bash pararules in any way, I think this is a super interesting project! |
Joins in a rule are a runtime cost; it's the price you pay for the dynamism they provide. If you don't need that dynamism, you could use a monolithic type instead. So you'd have a type such as It won't completely close the gap but it's the first thing i noticed. With pararules you're still paying the cost of various internal data copies that most likely aren't happening in an ECS; using persistent data structures like i mentioned above will probably help a lot here. But in general it goes back to what i said: a rules engine isn't the right fit for the "one million ant simulation" type of stuff. They really shine for projects with complex interactions with a lot of derivative effects. |
In my experience, it's pretty expensive even with a dozen of entities and not too overly complex logic when running at 60 fps, after applying the advice about |
Yeah there's definitely too much copying going on. Now that I have implemented immutable data structures I can try integrating it into the engine. I'll update here once I find the time to try it. |
I'm happy to give it (porting pararules to parazoa) a go if you are willing to tolerate random naive questions in the process. |
Sure thing. BTW probably the first place I want to remove copying is here, as that is happening every iteration that rules are fired. I bet we can get some big perf improvements by using parazoa there. |
I started with making |
Yeah I'm seeing the same thing. I'll try to find a minimal repro. I wouldn't be surprised if it was some kind of weird interaction between orc and generics... |
The error you mentioned sounds like this one: nim-lang/Nim#20400 |
Just for fun (and being frustrated by my inability to work around the compiler bug), I tried a simple copy-on-write approach: https://github.com/ul/pararules/tree/cow. |
This is brilliant! It doesn't seem to affect the benchmark above but it's worthwhile until we can get parazoa integrated. Please make a PR and I'll merge and tag it (maybe without the nix files). |
It does on my machine™️:
Adding entities regressed, but firing rules improved. |
Concerning perf improvements, I found wrapping pararules/src/pararules/engine.nim Line 233 in 1061808
greatly improved performance when you have a lot of facts and rules that update most of the facts I'm working on a port of pararules to javascript named edict and I found using an immer |
I've just seen your recent talk https://fosdem.org/2022/schedule/event/nim_pararules/ and was delighted by the results you achieved.
That sparked a ton of thoughts which I'd like to mention here and ask for reaction on them 😉.
then = false
not the default behavior? It'd guarantee no cycles and maybe even make the code slightly shorter. Is it due to performance reasons? If not, then why not to introduceoverwrite = true
(basically saying "overwrite is the only possible culprit of cycles" making the whole understanding of the rules yet easier).session.retractCascade()
instead of manually writingsession.retract( id, ... )
?ref
to non-primitive (or generally any bigger struct, sequence, etc.) non-ref
attributes as there doesn't seem to be any real world use case for copying them.staticRuleset
by maintaining "active" and "inactive" state of chosen (each?) rule(s) in the facts DB. This should provide a tradeoff between slow dynamic tables and fast static structure by "paying as you go".Your thoughts & wishes & plans?
The text was updated successfully, but these errors were encountered: