Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

C persistent hash map with Python bindings

branch: master
README.md

Perper

Efficient persistent hashtrie implemented in C

This project implements a persistent hash map as seen in Clojure. It is implemented in C, but provides Python bindings for convenience.

Check this page for more info about how persistent hash tries are implemented.

ctags annotated source is avaliable in the gh-pages branch. I recommend starting in perper.pyx or hashmap.c, and clicking your way through.

Usage

from perper import PersistentDict

p = PersistentDict()
q = p.setitem("foo", "bar")
r = q.delitem("foo")

p["foo"] # None
q["foo"] # "bar"
r["foo"] # None

Performance

It's fast, but Clojure and Perseus(on pypy!) are equally fast.

from perper import PersistentDict

p = PersistentDict()
for x in xrange(10000):
    for y in xrange(1000):
        p = p.setitem(y, x)
real    0m20.730s
user    0m20.689s
sys 0m0.020s
#include "hashmap.h"

int main(int argc, char *argv[]) {
    int x;
    int y;
    OInt *key;
    OInt *val;
    BasicNode *p = new_empty_node();
    BasicNode *q;
    for(x=0;x<10000;x++) {
        for(y=0;y<1000;y++) {
            key = new_oint(y);
            val = new_oint(x);
            q = INSERT(p, key, val);
            release((Object*)key);
            release((Object*)val);
            release((Object*)p);
            p = q;
        }
    }
    release((Object*)p);
    return 0;
}
real    0m14.430s
user    0m14.413s
sys 0m0.000s
from perseus import frozendict

p = frozendict()
for x in xrange(10000):
    for y in xrange(1000):
        p = p.withPair(y, x)
CPython:
real    2m58.169s
user    2m57.791s
sys 0m0.024s
PyPy:
real    0m14.687s
user    0m14.505s
sys 0m0.116s
user=> (time (reduce conj {} (for [x (range 10000) y (range 1000)] [y x])))
"Elapsed time: 13728.298915 msecs"

TODO

  • Make it faster, Java beats us.
  • Use C primitives instead of Python objects where possible
  • Implement hash and equality to support nested maps
Something went wrong with that request. Please try again.