|
About ::
TODO ::
Blog ::
RSS ::
Old blog ::
Projects ::
GIT ::
Gallery ::
Notes
Mon, 05 Mar 2007
The fastest way of doing tree traversal. Better algorithm to do a socket lookup. 80484a9: 89 e9 mov %ebp,%ecx 80484ab: 89 d6 mov %edx,%esi 80484ad: 89 c3 mov %eax,%ebx 80484af: 83 e1 01 and $0x1,%ecx 80484b2: 8d 54 24 1c lea 0x1c(%esp),%edx 80484b6: 8d 76 00 lea 0x0(%esi),%esi 80484b9: 8d bc 27 00 00 00 00 lea 0x0(%edi),%edi 80484c0: 8b 14 8a mov (%edx,%ecx,4),%edx 80484c3: d1 ed shr %ebp 80484c5: 89 e9 mov %ebp,%ecx 80484c7: 83 e1 01 and $0x1,%ecx 80484ca: 85 d2 test %edx,%edx 80484cc: 75 f2 jne 80484c0C code:
struct trie_node
{
struct trie_node *ptr[2], *parent;
};
...
int bit = value & 1;
while (n) {
n = n->ptr[bit];
value >>= 1;
bit = value & 1;
}
return n;
6 operations per loop, just two times more than linked list and with only one
conditional branch!Its speed is about 60-80 nanoseconds, which is roughly 1.5 times slower than linked list traversal only because we need to calculate which dimension to take (additional shift and binary 'and' operations). Very fast, but still can not compete with hash table with 4-5 elements in each entry. So, there must be another algorithm. I've invented one (well, not exactly invented of course, but will implement at least), which is a bit memory hungry, but allows to get one element out of 32 bitfield in 4 lookups (with only one conditional branch per lookup). It is some kind of trie/tree extension, where each node becomes not binary one, but containing multiple fields, which in turn becomes just multidimensional instead of two-dimensional tree with above access type. Stay tuned (I need to complete paid work part first). /devel/other :: Link / Comments () |