search

souffle-lang / souffle

Soufflé is a variant of Datalog for tool designers crafting analyses in Horn clauses. Soufflé synthesizes a native parallel C++ program from a logic specification.
http://souffle-lang.github.io/
Universal Permissive License v1.0
912 stars 200 forks source link

Removal of RamMerge #1199

Closed b-scholz closed 4 years ago

b-scholz commented 4 years ago

There is no need to have a specific merge operation in RAM. This can be simulated by a simple loop-nest that inserts the tuples from the source operation, e.g., a merge operation MERGE A WITH B can be expressed as, 

FOR t0 IN A
 PROJECT (t0.0, ... ) INTO B

This would parallelise the execution of the merge operation and would simplify the code. I would expect a performance gain rather than a performance penalty from this refactoring. Underlying operations such as insertAll could be removed from the codebase simplifying the interfaces.

Special care needs to be taken for the extend() method of equivalence relations.

b-scholz commented 4 years ago

This seems to be hard and the gains are limited because of the extend() method of eqrel.

I implemented it naively and noticed a slow down. Further investigations are necessary but if true we could replace copy rules by merge operations to speed up the performance.

b-scholz commented 4 years ago

The benefits of refactoring outweighs the complexity of the job at hand. I close this issue.

b-scholz commented 4 years ago

In my branch b-scholz:ram_merge I implemented a rough version. Without specialised merge, Doop slowed down with -j 8 (8 threads) 23.149s -> 25.157s for 1-object-sensitive+heap.dl and antlr. This shows that parallelisation might not be the best strategy for simple copy operations.

However, sequentially we have a speedup which indicates that simple scan/project loops should not be parallelized.
32.698s -> 31.650s

b-scholz commented 4 years ago

It seems that this worthwhile to be pursued. More performance testing is necessary.