Hello all,
I’m currently implementing a static allocation algorithm called minimalloc, and in the process, I am using a lot the setarg/3 predicate for destructive assignment.
I think that my most prominent previous use of the predicate was when I tried to make the Dijkstra algorithm go fast, but in that case, the algorithm was deterministic with no backtracking.
In the case of minimalloc, since it is essentially an optimisation algorithm, it heavily uses backtracking during execution.
This left me pondering on how setarg/3 works with backtracking ?
And I have a lot of other questions like:
Does it copy the entire term, so that when backtracking, it just need to revert the reference to the old term ?
Or does maintain a trace of all changes that needs to be reverted on backtracking ?
How fast is it ? is it the fastest way we have in swi-prolog to do destructive updates with backtracking ?
Is it faster than put_attr/3 ? How much faster ?
Please, let me know if any of you have experimented with setarg/3 on a real use case before
Once I have managed to finish the minimalloc implementation, I’ll try to do some experiments (especially with put_attr/3) to answer some of these questions on a real world example.
The docs should tell you that backtracking restores the old value.
If you mean the term whose argument you change? No. It just updates the argument. Note that compounds are internally represented as an array. So, it just places the new value in the given array location and makes a trail entry to restore the old. Normal trail entries just record the address that should be turned back into a variable. setarg/3 trail entries carry the address and the old value. The value can be anything: it is not copied. GC marks the old value, so it is not garbage collected. As discussed here before, if multiple setargs affect the same address between two choice points, only the first is preserved, i.e., GC deletes subsequent trail entries on this address.
It is pretty much the fastest update, except for nb_setarg/3 if the value is a small atomic object (small integer or atom). In that case nb_setarg/3 can simply write without trailing or protecting the value. put_attr/3 has similar performance as setarg/3 if the attribute already exists and is a little slower otherwise. Both use the same underlying machinery.
I now understand the trailing part.
Turns out, it is much easier to use these extra-logical predicates when you know how these works in practice.
Just to be sure, you mean that nb_setarg is faster (for small atomic object) if you don’t need backtracking ? If I need backtracking, my only option is setarg/3 right ?
Okay, so I definitly need to experiment with put_attr/3.
Yes. It is a very simple operation, comparable to an array update in imperative languages. No need for trailing and garbage to be collected. It is ideal to preserve state over backtracking. See for example call_nth/2:
