Filter seem to slow down as graph size increases #65
Comments
|
The timings appear to be similar in a windows build of the lifecycle portion of the petrol pump example. The main issue is not necessarily the increase in the time taken when using filter, but the fact that in order to maintain a responsive UI processing a single event should ideally be >1ms and definitely >25ms. The code posted above forms a pretty trivial example and is already approaching the 1ms mark (admittedly in debug) |
|
I haven't had time to maintain sodium lately. I did read the code you emailed me, and the performance issue does seem to be on the sodium-rust side. |
|
Thank you for taking the time to review this issue, I will give those suggestions a try. I may need some support (if you are willing) as I am pretty new to Rust once I get stuck |
|
It turns out this issue is unrelated to the use of filter but is instead more to do with the number of nodes (in what appears to be a chain). I created a test that strings together a number of #[derive(Clone,Copy)]
enum SomeVal {
Val1,
Val2,
Val3,
}
fn generate_nodes( s: &Stream<SomeVal>, count: u32 ) -> Stream<SomeVal> {
let new_s= s.map( | v: &SomeVal | -> SomeVal { v.clone() } );
match count {
0 => new_s,
_ => generate_nodes( &new_s, count - 1 ),
}
}The test results for this show a clearly exponential trend:
The majority of this time is spend in fn mark_roots(&self) {
...
for root in &old_roots {
self.reset_ref_count_adj(root);
}
...
}If there were an index associated with each of the roots in old_roots in the above loop, then the time taken for each iteration would be fn mark_roots(&self) {
...
let mut root_num = 0;
for root in &old_roots {
let tt1 = Instant::now();
let depth = self.reset_ref_count_adj(root);
let tt2 = Instant::now();
println!( "mark_root: reset_ref: {},{},{}", root_num, depth, (tt2-tt1).as_micros() );
root_num = root_num + 1;
}
...
}and fn reset_ref_count_adj(&self, s: &GcNode) -> i32 {
println!( "ref_reset: {},{},{}", s.id, s.name, s.data.visited.get() );
if s.data.visited.get() {
return 0;
}
s.data.visited.set(true);
s.data.ref_count_adj.set(0);
let mut depth = 0;
s.trace(|t| {
depth = self.reset_ref_count_adj(t) + 1;
});
s.data.visited.set(false);
return depth;
}When running this with From the above it feels like the |
|
Thanks for digging into that. If I can find time, I can have a close look. So, it must be a garbage collector bug. |
|
It does indeed appear to be the case. It would be much appreciated if you could give a quick description of how the GC algorithm is supposed to work. I am planning on looking into it a bit further in parallel, so would be good to have some guidance with the way it is intended to work |
|
https://pages.cs.wisc.edu/~cymen/misc/interests/Bacon01Concurrent.pdf The non-concurrent one in that pdf. If I remember correctly, ref_count_adj is the temporary negative count (represented as positive integer) when detecting cycles. I.E. If ref_count - ref_count_adj == 0, then a cycle is found. Otherwise reset its ref_count_adj to zero at end if no cycle found. |
|
@alexgcrombie I believe you are right about that |
|
@alexgcrombie I split Also constructing your graph within a transaction helps a lot too. |
While porting the petrol pump example from the FRP book, I noticed that running the just the lifecycle portion (rust equivalent of listing 4.5) of the example that when sending events in debug mode took 1-2s to process a single event, and in production mode this was reduced to 200ms. The code is written to be as close to the Java code in form as I could make it (all of the inputs are modeled as sinks, which then generate the "inputs" interface that the book presents)
In another test application of my own I noticed a x5 slow down when using filter_option (but from my testing the timing is very similar for a plain filter as well), this time going from 200uS to ~1ms in debug mode, and ~27uS to 200uS in production.
One thing to note is that this is being built on Linux using the latest release of Rust.
The code is as follows for the normal case:
and the filter enabled code:
The above code is the only portion using filters, and as such it results in the following timings. For the non-filtered case:
and for the filter using case:
The above are the debug timings, but the ratio between the cases remains similar even in a release build. In the release build the timings are ~23uS (with no filters) and ~160uS (with filters).
The text was updated successfully, but these errors were encountered: