Unification persistent data structure

[hertzcodes]

Hello,
what does the comment mean here? you want a persistent map instead of allocating one each time?

// Not a built-in predicate. Call lookupFn.
lookupFn(p, func(fact ast.Atom) error {
 // TODO: This could be made a lot more efficient by using a persistent
 // data structure for composing the unionfind substitutions.
 if newSubst, err := unionfind.UnifyTermsExtend(p.Args, fact.Args, subst); err == nil {
 solutions = append(solutions, newSubst)
 }
 return nil
})
return solutions, nil

[burakemir]

Yes, along those lines.

Currently, the subst is passed in as a "base" union find, and UnifyTermsExtend will copy its contents and return a brand new, self contained object. During evaluation, there are bigger and bigger substitutions - they only grow (get additional mappings) but they have a lot of mappings in common.

The TODO is my wondering whether it is possible to save resource by sharing base and only storing a small "delta" and a pointer to base.

The thing that makes me wonder is that the UnionFind data structure does mutations as side-effect of lookup operations ("path compression"). This is a bit different from (immutable) persistent data structures, so if one keeps that then I believe one won't be able to simply delegate the lookup to a shared base.

[hertzcodes]

@burakemir I would like to work on this. I'm thinking of a mechanic that reverts subst after usage, but I think that would require major changes in many parts of code and it can be acquired each time. I'm not very familliar to code base yet. I'd like you to tell me if you think I'm on the right path

[burakemir]

I can see how an implementation of using a single mutable datastructure that gets updated might be good. However, as you say, a lot of things would have to change. Here, the comment is more about a local change. As with all performance related work, it would be good to start with profiling.

The in-memory storage in the go implementation is in hash maps, so it is as if one is doing hash-joins on these tables. For a set up that makes updating with the next choice of value, I believe it would be better if in-memory storage was organized by columns (like in Apache Arrow). That itself is something that could be done without changing all the rest - just a new FactStore implementation.

I don't have much appetite to rework the mechanics of the go implementation fundamentally... In contrast, the Rust implementation is still work in progress. So if you are open to contributing in Rust, there is opportunity there to redesign with efficiency in mind. The idea and direction there is to compile the Mangle Datalog program (say, to WASM) instead of interpreting it, and support querying data from block (or object) storage.

[hertzcodes]

I have done some changes and still testing it. There are some parts of code like builtin that I'm letting to use copies but rest of the implementation is going to use a persistent immutable data structure. I will open a PR when I'm done and you could think about it.
The FactStore thing is a cool idea but is it really related to this issue? (to be honest I might not have correctly understood it)
About Rust I'd love to contribute but I don't have much expertise as much as I have in go.