README
Overview
This repo contains two implementations of the treap challenge set forth by the Completely Unscientific Benchmarks game in the ATS programming language.
The first implementation (treap.dats) isn’t documented because it shows how ATS can be used
as just another standard ML with persistent datastructures and full garbage
collection; if you have some familiarity with ML-like languages there are no
surprises. Although not well-advertised ATS can be pretty accessible with the
“hard” parts freely mixed in when you need performance.
The second (treap-ats.org) is a fully literate program that uses and explains
the linear logic and typesafe manual memory management features of ATS. You can
view it here on Github but the Rawgit link looks a lot better.
Installation
You don’t need to have ATS to run these examples, the build.sh script pulls
ATS and its dependencies directly from Github, builds the compiler from scratch
in ./ATS/ and compiles the implementations. Nothing outside this directory is
affected. All you need is git, libgmp and standard C build tools, on
Debian based machines the following seems to suffice:
apt-get install build-essential
If all goes well there should be two executables in the current directory
treap and treap_manual, the output of the first and second implementations
respectively.
I have only built this repo on Linux, OSX may work, Windows probably will not.
Performance
The performance of the first GC’ed implementation is pretty bad which is
expected because ATS falls back to libgc which isn’t known for its speed.
The second, however, performs as well as the fastest C++ entry with and is completely typesafe, but not without a lot of help from Hongwei Xi, the creator of ATS, so a huge thanks to him. The key was use references in tight inner loops and to avoid indirection in the layout of the treap data structure itself.