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

Add EOS optimization #114

Open
YarikTH opened this issue Mar 5, 2023 · 3 comments
Open

Add EOS optimization #114

YarikTH opened this issue Mar 5, 2023 · 3 comments
Labels
enhancement New feature or request

Comments

@YarikTH
Copy link
Owner

YarikTH commented Mar 5, 2023

Description

There are some common cases when computation graph is complete:

  1. Event stream is guarantied to be finished. For example ureact::once has already passed a single event or make_never<int>()
  2. Calculated signal value is guarantied to be constant: there is no alive input interfaces in source. Computation tree can be replaced with a single constant node.

Further development of the idea can be seen in RxCpp.
It has completed as a first class citizen, so it is no longer an optimization, but part of some algorithms like combine_latest, with_latest_from etc.
But it is subject for another issue.

@YarikTH YarikTH added the enhancement New feature or request label Mar 5, 2023
@YarikTH
Copy link
Owner Author

YarikTH commented Aug 16, 2023

Initial step can be self detaching the node from its dependencies if it is considered done ("take(N)" for example or "happened"). Currently the same is done by observer nodes.

Reactive graph visualization even trivial one could be very useful for this feature.

Also, if const propagation will be done in "update()", then signals should have additional "has_changed" flag to be checked by dependencies. So constness propagation and change propagation could be separated. Now the fact of calling "update()" is considered as a fact that at least one of the dependencies has changed.

Additional thought is - to be able to replace a node with a different one (parent node, never node, constant node) we need to introduce additional level of indirection. I have no idea how it impacts performance and how to deal with ownership if this new feature will replace current shared_ptr based model.

@YarikTH
Copy link
Owner Author

YarikTH commented Sep 4, 2023

Instead of additional level of indirection, specialized std::shared_ptr analog can be introduced on top of nodes slot_map. node_ro_ptr, node_rw_ptr should contain just id in slot_map and inc/dec read only and read write counters of the node_info. If RW counter reaches zero, then at least it is marked as complete and propagation of it has started, and/or the node is replaced with it's lightweight constant analog.

In case of completion, potentially many nodes are expired. To minimize nodes constantination it's maybe better to start from the newly constanted nodes with the most level and move downwards. Thus if most deep node it alive, then it is replaced with constant analog, otherwise it is destroyed.


There is an idea of caching of all existing constant nodes to reuse them (link all never<> or const(0) for example), but most likely overhead of tracking all of them is bigger than profit of having less duplicated nodes.

@YarikTH
Copy link
Owner Author

YarikTH commented Sep 16, 2023

New idea (not sure it is viable): recreate const and never nodes on top of the existing nodes using placement new. It should be ok, because such nodes should use the same or less amount of memory. Need to check how shared pointers handle the fact that object they pointing suddenly changed its type.


Anyway, const detection and propagation comes first, const tree minimization - second.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant