LWN: Comments on "Trees I: Radix trees"

Trees I: Radix trees

Naarayanan — Wed, 25 Sep 2019 19:37:52 +0000

How do you iterate/traverse through a radix tree and print out its contents to the console. Can we use gang_lookup() or is there any other API for that?

Trees I: Radix trees

aaabr — Thu, 28 May 2015 18:44:14 +0000

How well would this apply to large addresses (i.e IPv6)? It has 64 slots, so will it be able to hold addresses much larger than 64 bits? Thank you

Trees I: Radix trees

puchuu — Mon, 22 Jul 2013 10:25:37 +0000

Judy author sold himself and his ideas to HP. Why linux should collect HP patents? (see USA patent 6735595)

Also the fastest hash table in the world is "burst trie", not judy arrays. Linux can use fork of "burst trie" idea named "hat trie" in future. It is more memory efficient. These ideas are free, no patents.

Judy licensing

bcl — Thu, 23 Oct 2008 21:31:54 +0000

LGPL according to the article linked above

Judy licensing

iler — Wed, 18 Jul 2007 07:59:28 +0000

Another reason, besides simlpicity, is licensing.

Is Judy GPLed ?

Trees I: Radix trees

wahern — Fri, 30 Jun 2006 23:22:19 +0000

The author/inventor put it well himself when he said, "Well I cannot describe Judy in 10 minutes -- what possessed me?"

Source: http://judy.sourceforge.net/doc/10minutes.htm

Simplicity is often a very valuable quality, especially in software development.

Trees I: Radix trees

ncm — Sun, 19 Mar 2006 08:09:44 +0000

The designer of Judy trees has expressed wonder at why anybody ever talks about binary trees (e.g. red-black trees) any more, since his measurements indicate that no matter what you do, their performance always stinks compared to modern cache-aware techniques. The only reasonable explanation is the same as the reason university graduates, once, all knew ancient Greek, and had studied geometry but not calculus.

Node size and cache-line ping pong on SMP

jzbiciak — Fri, 17 Mar 2006 21:27:45 +0000

I wonder what's magic about 64, other than that it's 6 bits? On a 32-bit architecture, that's 256 bytes of storage for the 64 pointers. On a machine like the Athlon, cache lines are 64 bytes, which means each node of the tree occupies 4 cache lines. In an SMP context, is there an advantage to sizing the nodes down to occupy a single cache line, or is there a sort of hashing benefit to having each node require multiple cache lines? e.g. Would I get more pingponging or less if the nodes were smaller? Does the answer change based on # of CPUs?