Alternatives to binary heap for Priority Queue

[clinuxrulz]

No performance testing done yet. I'm yet to have done a large Rust project using sodium. The only FRP graphs ran are just the test cases for making sure sodium does the right thing.

I'm doing an alternative Rust version to make up for performance issues I felt in the TypeScript version. Which is a little counter productive. But I also really wanted to tidy up the interface exposed by the Rust version so it more closely matches the TypeScript version as well. And to get rid of all those Gc<> wrappers the end user has to use currently in sodium-rust version 1 and make it more nicer to use.

I'll start using it once I've got the GC issue out of the way. I could try out the algorithm on a fork of the TypeScript version of sodium, I have a large-ish TypeScript project I could try it out on.

When I felt a performance hit one time on a TypeScript. I believe I had about 1000 nodes firing in a single transaction. When I stepped the code, there were switches activating causing rank changes too. I quickly learnt to batch my Stream events into a Stream of a collection of changes, rather than firing each change individually. That got me a bit of a speed boost. But it sill bothered me that a 1000 nodes firing would cause such a slow down.

I mainly fell into Rust for getting into web-assembly. However the debug support for web assembly is not really there yet (In a production ready sense). DWARF is working for source maps, but not for inspection of variables. Hopefully it goes done one day. Not a real big fan of printf() debugging, it hurts my productivity too much.

[cubuspl42]

I believe that performance of change propagation algorithm can be measured without any memory management implemented at all. It seems to be a totally separate problem not affecting performance very much.

Like you say, switches are a challange when implementing FRP. Actually, a few post earlier, you wrote an interesting thing about switches and a priority queue.

One thing I've noticed is for existing implementations is a priority queue resort is not required,

I don't really understand the whole priority queue regeneration step either (not really a resort, cause heaps aren't sorted, but that's a detail). Could you elaborate more on your observation? What is, in your understanding, the minimal set of steps needed to be done when a switch switches?

[clinuxrulz]

With some experimentation I've concuded that:

switchS can be made efficient. In that the graph can change inbetween transactions (after the current and before the next) where the priority queue is empty. Zero time for fixing the ordering in an empty queue. I could do this without effecting the results of sodium.

However I could not do the same for switchC for some reason. Maybe it just needs more thought.

By resort I mean if the ranks change due to switch, then existing nodes in the priority queue need to be cleared out and placed back in again to insure the still come out in the right order (existing implementations)

In the TypeScript version the checkRegen() method in Transaction.ts is where that resort happens. If you want to see what happens specifically.