Crit-bit trees | Hacker News Reader

Crit-bit trees

cr.yp.to

98 pointssiromoney41 comments

For a fuller explanation: https://github.com/agl/critbit/blob/master/critbit.pdf?raw=t...

(Note: self promotion.)

Github could really do with treating PDF files differently so I can view them in my browser.

An updated firefox should include pdf.js and there are plugins for at least chromium. Github could do it, but you could also do it yourself.

The problem is Github triggers a download action, regardless of whether you have a PDF plugin.

this is a security feature of sorts, mime sniffing is disabled.

Try this: https://rawgithub.com/agl/critbit/master/critbit.pdf

Adaptive radix tree (https://github.com/armon/libart) is also an impressive data structure. It also supports ordered iterations while showing similar random read/write performance to hash tables. Crit-bit tree is memory efficient, but it suffers for cache misses with many keys (> 1M).

That's the problem I see, it's memory efficient, but lookups will cost thousands of cycles for modestly sized trees. A hash table on the other hand can do lookups in a couple hundred cycles (cold cache for both.)

But cold caches are an unrealistic assumption. The top-most levels of a tree will always be in cache, unless you almost never access them -- in which case there's no problem either. Additionally, a radix tree is ordered, whereas a hash table is not.

Yes, that's correct. However, that's still over a thousand cycles for a tree of depth 5 below the cached part. That's a modestly sized tree (or several smaller trees.) Don't forget lot's of things compete for cache, it's usually safer to assume a cold cache unless you know your data structure is very high traffic.

If you're interested in working to help with a nice Haskell library, one of the core Haskell lib developers Bryan O'Sullivan is publically-building a critbit library for Haskell

http://hackage.haskell.org/package/critbit

Contribution information is available on the github page

https://github.com/bos/critbit

Also, as always, Edward Kmett weighs in with some particularly insightful comparisons of critbit trees, PATRICIA trees, and other variants

http://www.reddit.com/r/haskell/comments/1e1ywq/critbit_tree...

The activity for critbit seems to have died in the last half year:

https://github.com/bos/critbit/graphs/contributors

I while ago I took Adam Langley's and DJB's crit-bit code and put a CDB-compatible API around it, it's at;

https://github.com/colmmacc/nutrient

still a work in progress, but it made it considerably easier for me to fully understand what's going on. May help others.

For those like me who did not understand the rather vague explanation, this is simply a bit-based trie. Not as exciting as the page makes it sound.

The article mentions replacing the python hash-backed dict with a crit-bit tree… Sounds like a good opportunity to try it out with pypy. If it has no drawbacks then it should show up up as a speed improvement in their benchmarks.

I can already tell you that no tree can ever compare performance-wise to a well designed hash table (like python's.) "costly string compares" are much cheaper than cache misses. And for class attributes and the like Python doesn't even do the string compares, just a quick pointer compare.

cache miss = 100 cycles

cache miss + tlb miss = 200 cycles

memcmp compares many bytes per cycle, it's clear to see that the cache misses will dominate the runtime, and trees involve O(log(N)) cache misses. A hash table is typically two cache misses. For interned python strings it's only one.

"no tree can ever compare performance-wise to a well designed hash table"

This is not always true...if you have to hash strings when executing queries, data structures like TRIEs or naive 256-ary trees may be faster (where the O(strlen) time it takes to hash the string is instead used to walk the tree).

It's true that both hashing a string of k bits and a lexicographically compare over k bits is O(k), but the chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache.

Memoizing a hash code for a string is pretty cheap also, especially if you only dynamically allocate on the heap for long strings.

"chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache"

So a very common scenario for TRIEs/K-ary trees is for high-speed parsing - basically every byte read off the input transfers you to another state in the state machine.

Cache is moot as the state machine/tree is almost always in cache. The key (ha!) is input doesn't need to be cached, nor is any precomputed data required on the input side to be performant.

What would you be looking up in a radix tree while parsing? I don't think I've ever written one where prefix operations have been useful.

JSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member.

Any scenario where you decode {k,v} pairs benefits from this.

Why do you need prefixes for that? Sounds like the perfect usecase for a hash table or a precomputed perfect hash function.

You pay for computing a hash function over directly walking to the next node.

EDIT: Here you go. Some work I contributed a while ago when we were using Mongo. Replace hash table with a TRIE, deserialization performance goes up 40%. Because you don't need to decode a string, hash it, and then hit a hash table.

https://github.com/mongodb/mongo-csharp-driver/commit/0b7879...

Perfect hash functions are ridiculously cheap. Completely different beasts to those designed to operate as good hashers for all inputs.

How so? Perfect hash functions only work when all possible inputs are known.

Something odd about that commit message... You know that O(m) is equivalent to 5 * O(m) right? Any constant multiplier will have the same big-O value.

While it is true that asymptotically 5 * O(m) equals O(m), in practice 5 * O(m) is still 5x slower.

EDIT (reply threshold):

"That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way."

Now you're just being pedantic.

That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way.

Yeah, that will work, if everything is hot in cache there won't be a big difference between a radix style tree and a hash table. Obviously python doesn't fit that description usually.

Or precompute the hash and store the hash when a string type is immutable. This is what Java does and it gives hash tables an advantage over graphs (trees, automata) in lookups.

The advantages of trees lay elsewhere, such as persistence and ordering.

If you want persistence (in the functional sense) and ordering I'd rather implement a skip list personally. You can use your existing hash code as a randomiser to determine level promotion. If you're going to keep it around you may as well make use of it. Skip Lists also have the nice property that you can stick a immutable linked list facade on them (since the base layer is fully linked)

Python also does this.

One issue with that is that dicts can hold any hashable object, not just strings.

To get a comparable binary representation for arbitrary types, you need to use the hash method. So now you get the worst of both worlds - a hash call, and a tree lookup, and you need buckets for collisions.

You can't special case strings either - non-string objects can be equal to strings.

Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average). They have different uses; defaulting a dictionary to a hash is a valid language decision IMHO, its lightweight and it fits the bill. And on average it will be faster.

An explicit language construct for radix trees is an interesting idea, but once you really need trees you might be closer to needing a real RDBMS, or an in process extension such as sqlite.

> Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average).

Sure, but remember it also takes time to compute the actual hash value. That process itself is O(n) where n is length of the key. For large keys sizes and small set sizes the tree probably wins (for some definition of "large" and "small").

The critbit algorithm walks the tree while simultaneously moving through the key bytes/bits. It seems to me that for most modestly sized sets it has the advantage.

That's why C++ STL's std::map and std::set are typically implemented using (some flavor of) binary trees.

standard C++11 added std::unordered_map which is hash backed. Previously gcc and ms had the STL hash in the std namespace, but it was not part of the standard.

I always wondered why. In my coding experience, for most generic coding tasks, key-value dictionary backed by a hash was a better go-to construct. I wonder if it has something to do with processor branch prediction; a random guess would be that it would be hard to do b-tree branch prediction on a well balanced tree, while hash is constant.

Its a very good point that when it comes to hashing a very long key string this crit-bit tree structure has interesting properties. I wonder if this structure could be used to implement a good(better?) average case implementation of the LCS problem. http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...

DJB, if you are reading this, your site is such a treasure, could you please set up an rsync server so people can create online and offline mirrors?

http://cr.yp.to/mirrors.html

Are there any drawbacks? The implementation linked by agl does not seem too complicated, but at a first glance it almost sounds too good to be true.

I imagine it would be hard to implement efficiently in Java.

Reply on news.ycombinator.com