EDAN70: Project in Computer Science

A Specialized B-Tree data structures for Datalog Evaluation in Java
Louise Adolfsson and Simon Tenggren
Abstract:
Today there is a high demand for Datalog engines to be able to handle large amounts of data quickly. By implementing a B-Tree in Java there can be significant improvements to its efficiency. In this paper we present and evaluate the Java implementation of a specialized B-Tree data structure. Our B-Tree handles parallel insertions and dense data. It uses a hint system for faster traversals in the B-Tree and has a optimistic read-write lock that allows for it to handle several threads at once efficiently. The B-Tree outperforms the TreeSet greatly and is just slightly better than the Concurrent SkipList Set in some cases. The B-Tree shows potential as a replacement for Java’s data structures from the results of the benchmarks.
(paper) (code)

Flow Based Bug Detection
Oskar Kari
Abstract:
Program analysis is an important tool in modern software developement. In this paper a program analysis tool that solves the redundant assignment problem will be described. This tool will be tested on a real program as well as on smaller test programs. The performance will be analysed and some suggestions for further work will be done.
(paper) (code)

ChocoPy compiler
Tobias Karlsson
Abstract:
The purpose of this essay is to investigate the possibility of using ChocoPy as the programming language when educating students on how to construct a compiler as well as comparing the performance of the ChocoPy compiler with a python compiler. The compiler for ChocoPy is implemented to generate assembly code, targeting X86. ChocoPy could be advantageous to use when teaching compilers since it is a simplified subset of Python. When comparisons were made between the ChocoPy compiler and python interpreter for a certain type of program, the result was that the ChocoPy compiler was between 10 and 20 times faster, depending on the size of the program. A ChocoPy compiler can be created in a compiler course since the resources and knowledge provided by the course is enough to handle all the problems that may arise.
(paper) (code)