-
Website
http://www.matasano.com/log -
Original page
http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/ -
Subscribe
All Comments -
Community
-
-
Top Commenters
-
Popular Threads
All Comments
It's not a "huge proclamation", nor am I the first person to make it; it's part of the standard C++ library.
Please follow up the post explaining binary radix trees in more detail.
Again thanks for the top post!
I just thought that was funny, is all. Maybe it's not. Appreciate the vote of confidence!
Excellent, interesting, and well-written post. Subscribed.
You don't need a netmask or full IP prefix to run Nessus 2 against a target IP address!
If you’re tracking down a botnet or a spamming operation or worm propagation, that netmask number is pretty important to you
Wouldn't NetFlow, cflow, sFlow, etc include the full IP prefix including src and dst network masks? Even IP CEF includes these and have the information exportable via tmstats. I think troubleshooting IP related information without a local route-server running Zebra, Quagga, or XORP is more difficult and exhaustive.
I do find Aguri interesting - thanks for the post! I'm looking forward to what it can be used for outside of products such as Arbor or open-source projects such as Ourmon.
the most popular general-purpose radix trie library (the one from CPAN) is actually stolen out of GateD. It’s a mess, by the way, and don’t use it
Are you talking about Dave Plonka's Net-Patricia module? I recall first reading about radix trees in TCP/IP Illustrated Volume 2 with some updated material from "Inside Cisco IOS Architecture". There hasn't been much in the literature lately on these topics.
if you’re an algorithms person you’re tired of me by now, and if you’re not, you’re tired of me by now
Actually I was hoping that you would cover multi-bit tries (mtries) and LC-tries, too.
Eh. Depends on what you want to do. In particular, though, trees of all sorts suffer from horrible data cache polution on modern processors, so if you're doing a simple lookup, hash tables are pretty much always more efficient.
For partial lookups hash tables are, of course, completely useless, and a trie of some sort is going to be necessary.
(1) You're don't have to settle for the general-purpose allocator when managing tree storage --- in fact, malloc may be really awful for that purpose, given malloc's mandate to maximize memory efficiency and block lookup, pitted against the program's desire to exploit the locality involved in hitting 16 closely-related node structures back to back.
(2) You don't HAVE to implement a tree structure using the same "struct" definition that Sedgewick wrote in That Book. If you think about the access patterns in a tree search, you can stripe the data in contiguous blocks.
There's an old paper that I read about the "Suez" software switch design, maybe 4-5 years ago, that went into some detail about cache-optimized tree structures for prefix lookups.
NetFlow V9 / IPFIX has included subnet masks. NetFlow probably gets them from the same place that the IP FIB (e.g. CEF) gets them from. I don't think BGP is required, but NetFlow could also stamp ASN's on a per-prefix basis if a full-table feeds your peer.
You rotate a splay tree to optimize search. You keep an LRU in an Aguri trie so you can pick nodes to aggregate. It's not JUST an LRU sort; it's also that (1) the trie is bounded in size, and (2) the bounds are deliberately chosen so that the inputs quickly overflow them. An Aguri trie that is "large enough" to contain all inputs is useless.
I assert without proof that sorted traversal is not that important.
So I don't agree that "Binary trees are a better default table implementation than hash tables."
On the other hand, I agree that tries rock, at least in theory. I still use hashes most of the time.
(2) See N comments ago where I addressed the received wisdom that trees are necessarily hard on memory and cache performance. No, your trees are.
(3) Account for the memory you burn on keeping load factor down. You're waving away collisions (that's how you claim O(1) for lookup) by spending memory on it. Are hash tables necessarily smaller than tries?
(4) Sorted traversal is less important than efficient access to ranges. Not all lookup problems fit the "dictionary" ADT. If you can only take one algorithm to the desert island, don't you take the one that supports more than one ADT?
I'm not "waving away" collisions --- I said you can expand the hash table, which keeps them to a constant level at a fairly low (amortized) cost, and can still tolerate relatively high load factors with a small average number of collisions. (Lua's tables use some hashing algorithm I still don't quite understand which they claim lets them support 100% load factors...).
Hash tables are not necessarily smaller than tries, for the reasons you point out. But they usually are.
And, yes, of course, if I could only ever use one of hash tables and binary search trees, I'd take binary search trees, for exactly the reason you point out. Although tries would be nicer.
I'm not trying to say that pretty much every linked list and tree library out there doesn't rip up your cache. They clearly do. But there's a lot of ways to mitigate the naive design that causes that; start by just not using malloc for your tree.
http://www.amazon.com/Network-Algorithmics-Inte...
Jeezes, no wonder we're still in the goddamn programming stone age!
http://www.cubic.org/docs/octree.htm
I personally prefer red-black trees since most of the code I've worked on didn't dynamically resize the underlying number of buckets and we'd eventually end up with some pathological data set that'd stuff beaucoup widgets in a single bucket. Or someone would write a hash function that didn't and we'd degenerate to a godawful linked list.
That said, there's one thing hash tables I see hash tables allowing you to do more naturally--incremental cleanup of the dataset. If you've got to visit the entire dataset once every, say, 30 iterations of the cleaner, it's pretty clear I must visit 1/30th of the available buckets. On the other hand, I've never found anything equally satisfying* for a tree since a naive solution is icky when an unfortunately chosen object is deleted between runs.
*elegant suggestions insanely appreciated.
I think you meant MRU where you said "LRU". Well the unpopular victim is always at the tail of the list, and at completion the most popular node is at the front of the list, so it is surely a Most Recently Used list. Or did I misunderstand you?
I like trees for an entirely different reason - they can be made to play nicely with functional programming. They can even be used to implement fairly efficient functional random access lists (http://citeseer.ist.psu.edu/okasaki95purely.html).
I would be intrigued to see someone comparing well tuned hash and tree lookup structures in software packages that are routinely used.
Something that might be of interest here, are cache oblivious data structures (http://www.daimi.au.dk/~large/ioS05/ABF.pdf). I stumbled onto the article a couple of months ago and gave it a cursory read-over (and remember being impressed); your article is definitely making me want to go back and read it more thoroughly.
Hint: look at how the old McKusick/Karels malloc works.
Bonus: implement the freelist using only one additional array element.
BTW, none of you better have a BSCS or higher. Tree implementation optimization is an undergraduate task at any non-correspondence school.
Sigh. If you're not doing prefix or neighbor lookups, then a tree is never a win in memory due to cache effects. It's especially not a win on a disk drive as you're causing more seeks.
This isn't wisdom whispered in halls, this is just plain measurable on any test.
And yes, I know about optimizing trees to deal with cache effects. I wrote a bone-head boggle solver that creates a ternary tree of all the words, so that I could quickly prune search paths. In part of the optimization of the algorithm, I measured cache misses (to disk, as I had serialized the tree and mapped it directly into memory from disk so that it wouldn't have to be re-run on every invocation). Part of what came up immediately was it was important to create the tree in a nice order so that after the first few comparisons, everything was under a page size. This is your point that you make above.
But, bottom line, if you have to traverse a tree structure to merely see whether or not a key exists (or just acquire the associated leaf data), it will always be slower, and worse on the entire system (due to cache effects) than a hash.
I like tries. I use tries. But they aren't always appropriate and you're doing your readers a disservice if you tell them any differently.
Wow. I must be really miscommunicating here if that's all you took away from that. It was an example to motivate your intuition.
But to go with it for a moment, yes, I am, as they have parallels. A cache miss in memory is akin to a head seek on a drive. To see why, just think about how the L2 cache is the same as the track cache. The L1 is equivalent to whether a sector is in the RAM cache or not. But this was merely an example. Discard it if it offends you so deeply.
The point is that cache misses are expensive on modern processors. Back when I started on the 6502 et al (1979), there was no difference. Nowadays, there's a massive difference between code that makes many memory accesses or few, and whether those memory accesses are spread out randomly or in order.
Try it. Make a large 2-d array of integers (say 1024x1024), and try walking the array in column order first versus row order first, and timing it.
Anyway, if you don't want your intuition motivated, well then, I guess I'm just going to have to beg you to measure the speed difference between walking a tree and looking up a key in hash.
And for the third time, there are times when hashes are completely worthless -- such as partial path lookups and needing to traverse neighbors (L/R/Parent) in an ordered collection. But for many things you're generally going to be better off with a hash.
Don't take my word for it. Go measure it.
You're obviously a smart guy. Why am I having such a hard time getting you past that idea?
My initial statement was pretty simple. You said "Binary trees are a better default table implementation than hash tables." and I said it depends. Take the below with that context, okay?
I don't understand what you mean by "insistent on defining 'tree structures' as 'structs with two child pointers' and 'memory' as 'what malloc returns'." Nothing I said is dependant upon a specific representation. Quite the contrary, I gave the serialied-to-disk example or a ternary tree to counter that possible issue. And as for memory being what malloc returns, all I can say is "huh?". You seem to think that RAM has different characteristics whether it's heap or stack? I'm horribly, horribly confused by what you are trying to get across here.
So...?
From my point of view a tree is something that requires a set of traversals. I would define a single "traversal step" as a load from memory and a branch decision (based on a comparison). Whether memory comes from heap or stack or is even purely on disk is immaterial to my argument. Whether it's a b-tree, radix tree, binary tree, or some hybrid is also immaterial.
So, I guess I just flat out don't understand your point. I'm saying in certain circumstances, a hash is a far better data stucture than a tree, whatever kind of tree that may be. Are you disagreeing with that? I just can't fathom how. Are you saying that a tree of some sort is *always* better than a hash? If so, why do you think ComSci profs teach it? Merely to confuse students?
I mean, in none of my comments have I been strident about this. I'm just trying to say that in your otherwise nice writeup, you gloss over a point that needs to be addressed more carefully for those who are not as versed in data structures as others. And by reading the comments, there are many who just aren't as well trained as we may hope. Don't mislead them. That's all I'm saying. Okay?
I'm specifically talking about tree structure layouts that minimize cache misses and overhead for links.
You don't even need to store links directly; you can use minimum-bit or succinct encodings. If you're concerned about optimizing a specific memory access pattern --- for instance, increasing the chance that all the traversal fetches are going to be in loaded cache lines --- you can tailor the memory layout to that as well.
It's true that "struct treenode { void *key; void *data; struct treenode *left; struct treenode *right; };" is not a particularly memory-efficient or cache-efficient layout. I'm just strongly objecting to tarring the whole concept of a tree with that naive implementation. Realtime network production code running at n mpps wouldn't use "struct treenode", or a hash table.
Todd H
You can check the errata on Sedgewick's site, but he only has errata for the third edition on; third edition is from, I think, 2000? and my apocryphal claim about his error would be from around 1995. So, long story short, if you crib your trie code from the current Sedgewick book, you might be aces.
The graph algorithms volume to new Sedgewick is also excellent.
Never fear, dude :^)
Ah cool - I found the libishiboo library at his (Dulai's) site. Looks like the code actually implements removal of nodes from the patricia trie too which is neat since I've never been able to find any good explanation of how to go about doing this (sedgewick leaves it as an exercise in his book).
Todd H
I've used code derived from Kneel's PATRICIA tree in production, so I'm pretty comfortable with it.
nice to see you writing again. This data structure you're describing sounds awfully similar to Binary Decision Diagrams. Basically if I did a binary expansion of that 32-bit IPv4 address and then gave each of those bits a variable name, I could do exactly the same thing you've described with a reduced, ordered BDD. The merging operation you have described is the reduction operation that transforms a binary decision tree into a decision diagram.
Cheers,
Ralf
Correct me if I'm wrong though (it's been a while since my algorithms study), but in response to the original question:
"I hand you an array of random integers. How can you tell if the number three is in it?"
Yes, linear search is bad, but isn't it the best way to answer the original question? If you're sorting the array, you're introducing additional complexity that still has to touch each element O(n). From what I remember, there can't be any sorting algorithm better than O(n).
If we sort the given array we've already spent at least O(n) but we now have to search the array (providing we didn't search while we were sorting). This assumes we're only looking for one element.
Now, if we can choose to get a sorted array of random integers, that all of course changes.
Anyway, that's all beside the point of Alguri. Never heard of it but I'll definitely check it out!
I first used Patricia Trees in creating silicon for routers [NP based Cisco routers] and later on IPS systems. The downfall is the changing of rules. Meaning, reorganizing the tree(s) is an art form [in a sense] and I had to fall onto a genetic algorithm to load the tree based on user settings when it came to 220 bit and beyond Patricia Trees. This seemed to solve the rule switching issue. To show you how bad the rule switching was on a 7200 NP based system (Cisco) it would take up to 120 seconds to reload the BPG table (back when that was hip]. Later in 2001 we all switched to creating devices with dual banked memory for Patricia Tree silicon.
Great topic by the way - would love to see more articles like this.
Maybe you should read the manual.
if (in_array(3)) {
echo "3 is in the array";
} else {
echo "3 is not in the array";
}
Problem solved. I didn't even have to read the rest of the post about aguri. That is a kind of cactus, right?
What if you have to write the in_array() function, jackass?
http://www.it-defense.de/itdefense2008_com/page...
(Scroll down to "Regular Exceptions".)
No slides online or anything yet, I don't think. If you're interested, I'll come back when they are.
I wonder if radix tries could be used also to improve the performance on keyword searches in PCAP files or sniffed traffic (like an Echelon functionality). This type of searches can be performed with NetworkMiner, see:
http://networkminer.wiki.sourceforge.net/Keywor...
I say that because tries are a classical approach to speeding up packet filtering. You can consider routing a special case of filtering, of course, in a single dimension. As you add dimensions, you start cross-producting multiple tries.
And, of course, radix tries (and edge-labelled PATRICIA tries in particular) are just a specialization of DFAs, which brings us back to pcap and optimizers and...