Home      Publications      C++ Code      Translator      Abstract Machine      Benchmark Results      Links

Bottom-Up Evaluation with the "Push Method"

First Prototype of an Abstract Machine for Bottom-Up Evaluation

Publication:

• Research Article: "An Abstract Machine for Push Bottom-Up Evaluation with Declarative Output"
  (Presented at INAP'17)
• Talk at INAP'17/DECLARE'17

Source code, version from September 19, 2017:

• ZIP-Archive of Source Code and Data Files
• Directory with Single Files
• Doxygen-Generated Documentation
• Link to gitlab

This is the first prototype implementation of an abstract machine for bottom-up evaluation that I recently proposed. I have implemented just enough to be able to execute two benchmarks for a first performance test. Not all proposed machine instructions are implemented yet. Furthermore, the test programs are currently generated in main memory, the reading and writing of "BAM"-programs from/to files still has to be implemented. However, first performance tests are very encouraging: In the two tested benchmarks (TCFF and Join1) the slowdown compared to native machine code was only a factor of 1.5. This is better than the difference that was observed for Prolog code compiled to the WAM vs. native code. I certainly will condtinue the implementation task and also will do tests to check whether the many instructions for special cases are really important for the performance.

Contents of the Directories:

• base: Basic Definitions and Programming Support
• mem: Memory management
• bds: Basic data structures (stack and flexible array)
• dom: Different implementations of string tables (for domains)
• rel: Different implementations of relations (lists, sets, maps)
• input: Input sources (e.g. for reading files)
• pred: Database predicates linked to the corresponding relations
• facts: Data loader for facts
• emu: Emulator (Interpreter) for Bottom-Up Abstract Machine
• test: Main program and performance tests (benchmarks)
• data: Test data files
• doc: Doxygen-Generated Documentation

Installing the Software:

• Download and unpack the Archive:
  [bam.zip]
  or clone the git repository:
  git clone git@gitlab.informatik.uni-halle.de:brass/bam.git
• CMake is used to create a Makefile from CMakeLists.txt Running cmake without parameters prints the available generators. For instance, to generate UNIX makefiles, run cmake -G "Unix Makefiles" .. This assumes that the current directory . is where the sources are stored. CMake can also generate project files for Microsoft Visual C++ and other IDEs.
• Then run make on UNIX, or use your IDE to build the project. The compilation should at least work with the GNU C++ compiler g++ and Microsoft Visual Studio 2015, Express Edition. If the compilation does not work, please contact brass@informatik.uni-halle.de. I have tried to write portable code and would be interested to hear about problems.
• The data files are not part of the git repository, but they are contained in the zip-Archive. If you cloned the git repository, create a directory data and download the needed files from http://users.informatik.uni-halle.de/~brass/push/data/. For the transitive closure benchmark, you will need the files tc_*.
• Documentation can be generated with Doxygen: Just run doxygen in the main directory. The generated documentation will be stored in the directory doc. One can start by opening doc/html/index.html. Currently, not all classes and methods are fully documented, but the generated documentation should be useful.

Using the Program:

The program has compiled in a number of tests and benchmarks. The test/benchmark can be selected with a command line argument. A list of tests is printed if the program is called with the option -l. The most important benchmarks are:

• bam tcff_5_f2:
  Transitive Closure Benchmark with Binding Pattern "ff",
  Implementation 5 (the abstract machine), Data File 2: tc_d1000_parsize50000_xsb_cyc.P.
• bam tcff_4_f2:
  Same Benchmark and data file,
  but Implementation 4 (Push method with functions compiled to native code).
• bam tcff_3_f2:
  Same Benchmark and data file,
  but Implementation 3 (Standard seminaive evaluation compiled to native code).
• bam j1axy_6_10k:
  Join1 Benchmark with query a(X,Y),
  Implementation 6 (the abstract machine with bitmap duplicate check), Data File with 10k rows per relation.
• bam j1axy_4_10k:
  Join1 Benchmark with query a(X,Y),
  Implementation 4 (Push method with functions and bitmap duplicate check, compiled to native code), Data File with 10k rows per relation.

The program is called in the form bam <Options> <Test/Benchmark IDs>. It understands the following options:

• -a: Switch off printing of answers (by default, the first 10 answers are shown).
• -aN: Set the limit for the number of answers to print to N (e.g. -a1000).
• -d: Switch debug output on. The amount of debug output varies by test (it was manually added).
• -h: Print help.
• -l: Print list of tests/benchmarks (ID and short description).
• -m: Print memory pools.
• -r: Print relations.
• -s: Print only summary line ("silent mode") The summary line contains the test ID, times in milliseconds (load time, eval time, total time in case of benchmarks) and the test result (status code). The test result "Warn" usually means that the difference between real lime (wallclock time) and CPU time was quite big. The summary line contains the greater of the two times.
• -b: For benchmarks: Similar to -s, but no newline at end, prints warning message if debug code is compiled in.

Note: The current version writes a file "alert" with error messages and object dumps (in debug mode). I will soon add an option to suppress this. For the time being, one needs write permission for the directory in which one executes bam because of this error log file (which is opened even if there are no errors).

Stefan Brass (brass@informatik.uni-halle.de), December 18, 2017

Original URL: http://www.informatik.uni-halle.de/~brass/push/bam.html   [XHTML 1.0]   [CSS]   [Links]   [Legal Info]