Interestingly if all nodes are firing at once. Pull base FRP is faster than push based FRP generally.
Push base is O(n*log(n)) for n-firing objects (for a static graph). Pull based is O(n) for n-total objects regardless of how many firing (for both static and dynamic graphs).
One thing I thought about was grouping same-rank things firing at the same time in a single element of the priority queue (a priority queue of lists of same rank things firing). As when many things are firing, many are likely to have the same rank. So we can minimise the size of the priority queue in an effort to lower the cost of priority queue resorts when they happen. This however would required an alternative implementation for
Cell::apply in order to work. (one that tags the left and right streams so simultaneous stream values are combined in the correct order, because we would no longer be able to use
Imagine a balance merge of 1024 streams all firing at once. Instead of having a priority queue of 1024 elements as single entries, we can have a priority queue with 10 elements each element containing a list of entries. It is much faster to do a resort of a 10 element priority queue, than a 1024 element one. Also without packing them up in lists of entries if the value type of the streams are newly constructed sodium cell initial starting with rank zero, then we have 1024 resorts of the priority queue of 1024 elements to look forward to. Ouch O(n^2*log(n)).
I've read on stack overflow somewhere there should be specialised implementations for integer-key based priority queues for small integer keys that operate in amortised O(1) time for insert/removal. I'm having trouble finding an actual implementation though.