Alternatives to binary heap for Priority Queue

[clinuxrulz]

Might be worth comparing the performance of other algorithms such as smooth sort against the current priority queue (binary heap).

Smooth sort has a worse case time complexity of O(n*log(n)).
But it has a best case of O(n) for arrays that are nearly sorted. In the case where a vertex changes rank, the rest of the priority queue would be near sorted (I imagine), so we should be able to get close to O(n) for fixing the order.

[clinuxrulz]

The Vertex objects themselves are like nodes of a heap structure. There could be something there that be exploited. Ranks could become obsolete.

[clinuxrulz]

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 Stream::coalesce_().)

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.

[clinuxrulz]

You know the postQ is like a priority queue designed for small integer key. And during Transaction::close() instead of taking O(n*log(n)) to process, it takes O(n).

[clinuxrulz]

I've had some success with removing the reliance on a priority queue, and still remain glitch free.

https://github.com/clinuxrulz/sodium_rust_concurrency_experiment

I'm also able to update the nodes within a transaction concurrently with a thread pool. (Updating with unique thread for each node ATM, still playing around with the implementation.)

It works the following way:
each node has a visited flag and a dirty state
the dirty state has three values "Dirty", "Clean" and "Unknown"

On Sink Send --> add its dependent nodes to a processing list. and mark the sink node dirty

On End of Transaction -->
- get node from processing list, process its dependencies unless visited mark visited as you go, and move your way up the graph marking dirty state either "Dirty" or "Clean".
- each level up the graph if none of the dependencies were dirty, then the current node is still clean, otherwise the current node is marked dirty and its value-state is updated.

Last Step End Of Transaction --> reset states of visited nodes.

all nodes are protected by a Mutex and either dependencies or dependents are able to be processed in parallel. Locking only when two or more threads are trying to visit the same node.

The end effect is all ancestors of listeners are visited just 1 if the listener is going to fire, and only nodes whose state needs to change will execute its update function. It can potentially visit more nodes than the current push-based implementation, but it will visit less nodes than a fully pull-based implementation. It is sort of between the two. And avoids that O(n*log(n)) of the common priority queue.

Also memory management is not done yet in this version. Still playing around.

---

I'll try to explain it better.
For the current node being processed insure all dependencies have been processed. If any dependencies are discovered to change then update the state of the current node. Then if the current node ends up changing value-wise state then process the dependent nodes concurrently using thread pool.

I'm yet to use a thread pool. ATM I'm just creating new threads all the time.

[clinuxrulz]

All tests are now passing for:

https://github.com/clinuxrulz/sodium_rust_concurrency_experiment

Just the memory management left to do.

I'll let the user choose between multi-threaded or single-threaded graph updates within transactions via configuration through the SodiumCtx (the graph evaluation context).

I am leaning towards using the same API exposed by the TypeScript version in the Rust version, so the end-user does not have to deal with the Gc<> wrappers. That way the API should be less cumbersome. It will be a part of sodium_rust version 2.0 (due to API change). Hoping that is OK with existing users.

Also by eliminating the Gc<> wrapper stuff everywhere it should be easy to expose a C based API and wrap it up C++ headers around the Rust version, to finally provide a optional memory management solution to C++.

I did try doing up a C++ version with a memory management solution for cycles, but the language was too difficult for me to cope with template-wise. The compile error messages went way over my head lol.

[the-real-blackh]

@clinuxrulz, that is totally brilliant! When you've reached a certain level of stability in your super-duper Rust version I'll translate it to C++. C++ has a lot of annoying gotchas to do with the typename keyword and other similar issues. That's a language I am good at. Maybe I'll learn some Rust in the process.

[clinuxrulz]

Ya know for the memory management, we can still continue to use std::shared_ptr (C++) / Arc (Rust). And keep an extra counter ref_count_adjacent which we update on collect cycles.

ref_count_adjacent simply holds the negative number of references to itself found via tracing the nodes. And if the ref_count + ref_count_adjacent == 0, then instead of trying to free the memory directly, we just forcibly disconnect the node from the graph and allow the cycles to clean themselves up naturally via the mechanism use in std::shared_ptr / Arc.

One weak point of sodium_rust version 1.0 (the current release) is if the user says a lambda is referencing a sodium object when it really is not referencing that object. Then it is possible to create a fake-cycle and free memory that is still in use, thus causing a segmentation fault. So I really should forcibly disconnect from the graph rather than directly free the memory.

By forcibly disconnecting a node, I mean you set the node's update callback to NOP and clear its dependencies and dependants. Basically turning an existing node into a NULL node.

[clinuxrulz]

Slowly and steadily working on memory management. Have not found a lot of free time lately.

One thing I've noticed is for existing implementations is a priority queue resort is not required, provided you rewire the graph at a time where the priority queue is empty (after current transaction is finished and before next transaction). This will not violate any of the operational schematics I believe.

E.g.

Where you have two streams s1, and s2 and you use switchS to switch from s1 to s2 at the same moment both streams are firing. At that moment s1 flows through the switch and s2 is suppressed until next transaction. A sign that graph rewrites can happen between transactions where the priority queue is quiet/empty.

[the-real-blackh]

That's great. Removing the priority queue potentially allows for a really significant speed-up. If the language has some kind of JIT compiler then there's a potential for it to strip out a whole lot of function call overheads and so on.

[clinuxrulz]

Currently if collect_cycles is called at the end of each test. I'm memory leak free. If collect_cycles is called at end of transaction then the test return the wrong results (memory freed too early). I think I'm almost there, might just be a mater of wrapping up all the code in each of the methods in transactions to ensure the collect_cycles is only executed on the outer user-code level.

Edit: I need to rethink my memory management solution on this design. I fell into a smart pointer holding a data structure with a smart pointer trap, and wrongly expected the inner smart pointer to increment when the outer sodium object was cloned (outer smart pointer incremented). I'm a little further from the finish line that I thought on this one.

[clinuxrulz]

There's a nicely written gc library for Rust now that uses the same gc algorithm as the TypeScript version.

https://github.com/fitzgen/bacon-rajan-cc

It's more nicely written than the one I have provided in sodium_rust.

Been trying to switch over to it in a separate branch for this non-priority queue version.

So far having gc runtime errors (subtract with overflow). But hopefully I can work it out.

Just would be nice to make GC not our problem. It's hard enough to just implement sodium.

[cubuspl42]

These are all interesting ideas, but I'm not quite sure if I understand them fully. I'll start with the first idea (the smooth sort-based priority queue), because it's simpler.

Currently in Sodium the approach is like this:

G - directed acyclic graph representing the FRP system
R - set of roots of G, i.e. sinks
S - set of roots (sinks) firing in the current transaction
G_S - sub-graph of G with roots S (firing sinks and all their dependents, transitively)
G_S,A - sub-graph of G_S, containing only vertices that are "active" (unfiltered) in the current transaction
P - a priority queue of vertices waiting to be processed

for s in S:
  P.push(s)

while (!P.isEmpty()):
  v = P.pull()

  process v according to the operator it represents, \
  which includes pushing its dependents to P iff v is "active" \
  in the current transaction, i.e. does not filter the event (which \
  can happen in the case of Stream.filter or unchanged Cell)

cleanup

Insertion to a priority queue based on a heap is O(log(length(P)). All of G_S,A vertices will be processed, and only them (which is obvious from the algorithm). So the time complexity is O(size(G_S,A) * log(length(P)). If G is much wider than deeper (I believe that that's a reasonable assumption), then size(P) is proportional to size(G_S,A), so complexity of the algorithm is O(size(G_S,A) * log(size(G_S,A)).

As I understand it, the single and only reason for this approach is not to process the inactive part of G_S. As I understand it, it's virtually impossible to hold that single optimization without using any kind of priority queue. It changes if you are ready to give up that optimization, though.

Using the most classic topological sorting algorithms will remove the logarithm from the equation, making it O(size(G_S)). So basically you can choose from linear-logarithmic complexity based on a smaller variable, or linear complexity on a bigger variable.

From your first post (and the title), I conclude that you want to switch heap-based priority queue for smooth sorting. If only insertion complexity changes, how does that not make it O(size(G_S,A) ^ 2)?

[clinuxrulz]

Ultimately what I ended up with is the "no priority queue at all" approach.

I guess the easiest way to explain it is a fully PULL-based implementation does not require a priority queue at all. And what I'm trying to do is be like a pull based but do not visit every single node in the graph within a transaction (falling half-way between pull based and push based).

There are situations were a pull-based implementation out performs a push based implementation when a lot of nodes are firing.

With the half pull/push based impl, I'm keeping a flag to make sure that nodes are visited at most once per transaction.

Now. A fully pull based implementation typically you start at the listeners and work backwards towards the sinks. What I do differently is I pull starting at the sinks (that have fired) and work my way up to the listeners to avoid visiting every node in the graph.

[clinuxrulz]

One thing to note about current push based with priority queue implementations. Is be careful with how heavy you use switchC/switchS. They cause ranks to changes, and when ranks change, the priority queue is emptied and refilled.

If n nodes are firing and all of them cause change of ranks, then you can have a nasty O((n^2)*log(n)) for that transaction. I think I fell in that trap when trying to invent an incremental lambda calculus abstraction powered by sodium.

That is partly what lead me to seek alternatives to the priority queue. No ranks -> no rank related problems.

[cubuspl42]

Okey, I believe I understand your approach now. So when you write...

...otherwise the current node is marked dirty and its value-state is updated.

...then you actually mean a pull-based update, right?

This algorithm looks like an over-complicated topological sorting. It needs two-way edges and two variables per node. DFS+stack topological needs a stack and one variable per node. And it's a classic battle tested algorithm, so unlike a custom one, can be assumed to be proven. I don't want to sound boring mentioning this algorithm again, I'm just kindly reminding that topological sorting is not a new problem, there are solutions out there with linear complexity.

Of course I'm 100% open to any arguments against basic toposort algorithms, sometimes there are some difficult to catch gotchas which make apparantly obvious algorithms unsuitable.

I'm personally quite afraid that dropping the inactive vertices optimization (which your priority queue-less algorithm does) is quite dangerous in the general case. It can cut-off potentially very big chunks of the graph, but it probably depends on the actual use case. I have some ideas for greatly reducing the size of the priority queue instead, without providing any kind of vertex-groups/sets/layers, but I'm yet to verify if that approach is actually correct.

[clinuxrulz]

I'd be happy to take on any ideas you can suggest. Including the topological sort, especially if there is a linear time complexity solution out there.

This must be the algorithm you speak of: https://iq.opengenus.org/topological-sorting-dfs/

It says:

Worst case time complexity:Θ(|V|+|E|)
Average case time complexity:Θ(|V|+|E|)
Best case time complexity:Θ(|V|+|E|)
Space complexity:Θ(|V|)

I'd have to study the implementation a bit and see if it can be worked into the code easily.

I wonder if the algorithm can be adapted for when the graph changes in the case of switchS / switchC. If it can be a incremental topological sort. Having a small change in the graph lead to a small amount of work to update the result of the sort.

.... speak of the devil: https://crates.io/crates/incremental-topo

[cubuspl42]

In your concurrent approach, there's no priority queue, no ranks, so there's nothing to be done during switches, right? The DFS-based topological sorting is a drop-in replacement for your push-pull algorithm (maybe minus concurrency, I didn't really think much about that aspect!). It will have the same time complexity, i.e. O(size(G_S)), each transaction. There's no need to do anything during switches, unless I'm missing something obvious.

Just sort topologically every time, starting with a set of firing sinks. You already do that in your algorithm, just in a non-obvious way. I'm only suggesting a standard algorithm to replace the custom one, not really any change to the approach.

[clinuxrulz]

Yep, no ranks so nothing to do during switch (other than just rewiring edges of the graph of course)

Sadly I lose the concurrency the moment I put in the garbage collect (to fix memory management problems). Because I only have single threaded GCs at my disposal.

[cubuspl42]

Out of curiosity, how big is your FRP graph? Have you performance tested your concurrent solution, without the GC? If so, how are the result compared to the priority queue way?