HarvardPL / formulog

Datalog with support for SMT queries and first-order functional programming
https://harvardpl.github.io/formulog/
Apache License 2.0
155 stars 10 forks source link

Use hash filter in DB #46

Closed aaronbembenek closed 1 year ago

aaronbembenek commented 1 year ago

Profiling showed that a major hotspot was checking whether a tuple was already in our DB and adding a tuple to the DB, because both operations involved working with Java's ConcurrentSkipListSet (used to represent indices). This PR adds a hash set that acts as a filter before any skip list is accessed. It leads to substantial speedups, especially in cases where many duplicate tuples are derived and tested against the DB.