For tabled predicates, SWI-Prolog will create a table for each call variant. This means that if for a tabled predicate foo/2 you do foo(a, X) and later on do foo(b, X), these will actually use entirely different tables. This will also be the case for foo(I, X) if I is already ground by the time we get there.
Suppose that this tabled predicate is part of some long-lived service, and I is an atom we received as part of a service request. This means that over time the total tabled data keeps growing. That is a bit problematic, cause memory is finite, and we’re bound to run out at some point.
So what is to be done? We could do abolish_all_tables now and then. But that’s pretty extreme. It’d be much better to have some kind of LRU mechanism, where maybe for the last 100 I inputs the table is remembered, but anything older gets thrown away.
I think this is accomplishable with abolish_table_subgoals/1. By keeping track of the last 100 I bindings in some FIFO structure, any request handling could end with abolishing the first recorded I with abolish_table_subgoals(foo(I)) (for a bound I), before appending the current I to the FIFO.
Before I run off to implement this, does something like this already exist? Is this even a viable approach? Is there a better approach?
You seem to be proposing a somewhat more complicated method of handling a cache than the usual “set max # of entries; when that’s reached, throw away the oldest as each new entry is added”, but maybe that’s because you need to fit in with the current implementation.
Also, LRU has some edge cases where the performance of an LRU cache is worse than no cache – if there’s a repetitive cycle of inserts that’s one more item than the size of the cache, then every new entry removes an old entry; so switching to random replacement becomes the better strategy.
Did you notice SWI-Prolog -- Variant and subsumptive tabling? That can solve part of the problem. In this case we must make a call to foo(_,_) and any goal to foo(X, Y), where X is either bound or unbound will use this table.
Otherwise, yes, one of the things to consider is to clean old tables. Another thing one may do is to destroy dependent tables. I.e., if I call tabled foo/2, it may create a lot of other tables. You can remove these. Of course, that may imply additional work to compute other tables.
That is a whole area that has also been discussed with the XSB developers Theresa Swift and David Warren. It is long ago, but I think also XSB does not do so.
Another possible improvement is that tries are translated into VM code after completion, but we do not prune the trie itself. I think that in most cases we can simply destroy the trie structure. Note that the compiled representation is both faster to access (that is why it exists) and quite a bit smaller than the trie nodes.
There are a lot of things to do for tabling, notably when it comes to performance and memory management and usage. The project that lead to the current implementation ended after completing the functionality and demonstrating some of the things we can do in SWI-Prolog, like shared tabling and monotonic tabling.
I did see those. But maybe I am misunderstanding them.
My understanding is that you need a sort of predicate that is able to generate all possible answers from unbound inputs. In my scenario, the X in foo(X, Y) could be any atom, so either foo(_,_) would have infinite results (and be untablable) or it would not work properly with subsumptive tabling.
For a concrete example, TerminusDB uses tabling for a lot of schema operations. Our schemas are in TerminusDB layer objects, which are blobs, and therefore, atoms. A lot of the tabled predicates take one of these layer blobs as an input. Since new schemas keep getting created and loaded, especially in a multi-user environment, there is no bound to how much we might end up tabling if we don’t do cleanup.
In the case of TerminusDB we just keep all schema-related tables private (thread-local) and then abolish all private tables at the end of an HTTP request. This is really not ideal, cause it means that on repeat requests for data using the same schema, we have to regenerate a bunch of stuff that we could have kept around if there was a more fine-grained cleanup mechanism.
That is interesting. So there’s a bunch of memory lying around that we’re not actually using anymoire. But even if these got cleaned up, the basic problem of unbounded table growth remains right? You just get to do it for longer cause there’s less memory cost to the tabling.
Ideally we should just be able to tell the tabling system that some table is going to be one of these long-lived always-accumulating tables and it has to be bounded somehow. In my dreams, I thought of a syntax like this:
LRU assumes some kind of recency bias; otherwise, random replacement is probably better. I found some discussion that suggested replacing the older of 2 random cache items.
(Note that LRU and oldest are not the same thing.)
Some garbage collection systems divide memory into short-lived and long-lived – GC first scans only the recent items and those still in use are moved to the “long-lived” section; long-lived are scanned only every N short-lived scans.)
Possibly some kind of “cost” for a table entry might be useful, but it’s not clear to me how to cheaply compute that. And, of course, just because something was expensive to compute doesn’t mean that it’ll ever be needed again. Which suggests a frequency-based policy …
I personally have had good success with LRU (not oldest), but point taken, there’s other mechanisms possible here, and a generic solution might be better if it abstracted over the exact staleness measure. On the other hand, genericness potentially comes with a cost too, in not being able to make optimizations which you can make if you know specifics. Not sure if that would apply here though.
I tried reading some of the tabling code today to see if I could integrate bounded tables there directly, and felt a little out of depth. I’ll keep at it.
Another approach is to have multiple replacement algorithms, and switch when the current one starts giving poor performance. I’ve seen this with operating system virtual memory paging: a switch between LRU and random … I’m not sure what the criteria were but I think it was something simple and quick, such as # of cache invalidations (I might still have the email address of the guy who wrote this code if you’re interested in more details).
[Speaking of virtual memory – in the mainframe days, I recall having quite large over-commit of virtual-to-real (perhaps 5:1) but nowadays, anything more than 2:1 or even less seems to perform quite badly. I wonder why …]
My overall idea would be to add some usage statistics to tables and a trigger that invokes a callback to Prolog to consider a cleanup. For shared tables we could signal the gc thread that is already responsible for atom and clause garbage collection.
Maintaining the right stats is probably not trivial. The system is full of tradeoffs that are hard to get right
Note that we can basically delete any table whenever we want. It won’t change semantics, just cause some slowdown to recompute it.
Couldn’t adding a new table directly evict an old one? Why does there need to be a callback or signaling mechanism?
So as @peter.ludemann suggested, probably random selection of some table to evict is the most viable thing to implement as an mvp. Then later we could figure out what metrics really work and how to properly keep them around. Or more likely, just keep it at random cause it is good enough. Though I personally expect I’ll at least want to be able to pin certain special tables that I know I’ll keep using often. But that’s for later.
:- table foo/2 as bounded(100).
To keep 100 tables around. Maybe that should be 100 per variant. Maybe different variants should have different bounds. I don’t know.
I mean the thing that gets created for a particular call variant in non-subsumptive tabling. I understand ‘table’ as ‘table of results for one particular call variant’. So for a nondeterministic predicate, that could be several results in one table, while deterministic predicates will always just have one result in them. Multiple calls with different ground inputs would construct different tables, which could each have wildly different sizes.
Please correct me if my understanding of tabling or my terminology is wrong here.
So probably this would not work, because tabling itself can trigger more tabling (like with fibbonaci). If we start deleting tables while trying to generate a result (which needs those values) we might just get in an infinite loop.
I guess that’s why it should be a callback or a signal.
Looking back this statement makes no sense. If each variant is a table, obviously there would not be ‘100 per variant’.
My thinking was that if you have a foo(A,B) but you always have A ground, then that’s kind of like a family of variants (one per binding of A), that is different from when A and B are both vars. But to =@= there’s no way to see it as such.
As @maren points out, deleting tables during “completion” is not an option (at least, not those in the current ccc (closely connected component, i.e., a set of tables that are mutually connected).
In general, I’m not so sure we should have this as a property of a particular predicate. It won’t be particularly simple for the user to select the right predicate. Isn’t a general policy to minimize (limit) table space usage that allows the system to select variants to purge a better plan? That is why I as aiming to make the relevant data and a trigger available.
That approach is a little similar to the current GC policy: if GC time exceeds a certain percentage it triggers a goal that is given access to the stats for the last 5 (?) GC runs. The trigger can adjust the GC policy parameters. Also the HTTP server does something like that: if there is no thread available to process a request it triggers a goal. That goal may assess running server threads, CPU usage, system load, etc. to decide on whether to add a new worker thread, have the client wait or reply with a “busy”. This trigger based action keeps the C code relatively simple and allows the plugin of arbitrary complex Prolog code to mitigate the signalled problem.
Getting back to limiting the number of entries with a tabled predicate, I ran across this paper: Geometric Search Trees which, amongst other things, mentions hash-tries. Perhaps changing to hash-tries (or some other random set data structure) would make it easier to prune a tabled predicate’s “cache”.
(I do not claim any expertise on such data structures, but just throwing out some random thoughts that might be saying something completely stupid.)
SWI-Prolog tries surely use hash tables Not sure that is what is meant here. I’m more suspicious that using hash tables is one of the causes of the rather excessive memory usage of the tabling implementation.
So far, work on tabling was geared to get the full XSB functionality at a reasonable performance, not about reducing or optimizing memory management. There is probably a lot to gain. Both by considering the data structures and by using the fact that while establishing the tables for a set of dependent predicates there is a lot of allocation. Once done, a lot can be discarded. Many similar cases, e.g., findall/3, use dedicated allocation that can be released to the OS once the work completes.
The world of “containers” has changed a lot since I learned about them in the late Bronze Age and I haven’t kept up … my thought was: – if random replacement is a good strategy, and if hash values are used as keys, then simply removing the first entry or last entry or whatever entry is most convenient might be an easy and cheap way to get a random replacement strategy.
[LRU presumes that recently accessed items are more likely to be used again; random replacement assumes that there’s no obvious way to guess which items are more likely to be used … classic virtual memory paging algorithms often switch between LRU and random replacement because the worst case behavior of LRU can be really bad. OTOH, garbage collection algorithms often keep a “used more than once” list which is garbage collected less often; so something as simple as a bit that marks whether a table entry has been used might be a good strategy for pruning the entries.]
Random seems a really poor men’s choice. There is a lot to say about the cost for creating a table, either using timing or by analysis of its dependencies and size. Usage is probably another aspect that is worth measuring.
Not sure that is what is meant here. I’m more suspicious that using hash tables is one of the causes of the rather excessive memory usage of the tabling implementation.