[Snort-devel] The performance of Splay Tree and HASH

tanminger at ...1390... tanminger at ...1390...
Fri May 24 03:35:03 EDT 2002

  The testing environment:
    CPU: P4 1.6G
    MEM: 256M DDR
    OS : Red Hat Linux 7.3  kernel 2.4.18

  Do 10,000,000 find, insert and remove operations, with only one node.
Using Splay Tree cost 2.017 seconds, and using HASH cost 1.224 seconds.

  Splay Tree: 14874489 operations/s
  HASH      : 24514670 operations/s

  Ming Tan
  tanminger at ...1390...

>On 24 May 2002 tanminger at ...1390... wrote:
>>   I have made a simple testing, and found the performance of HASH is 
>> faster than Splay Tree, even if there is only one node in the Splay Tree
>> and HASH.
>>   I check the source of Splay Tree, comparing the root node in Splay 
>> need several function calls, it cost more CPU cycle than calculate the 
>> hash key.
>>   Using HASH maybe cause the DoS attack by sending special packets, but 
>> can we using the HASH function based some random number?
>My testing also showed that a hash table outperformed a splay tree.  I
>agree with tanminger that seeding the hash function with a random value
>can stop bucket overload attacks.
>I did my testing many months ago.  tanminger (Sorry, your email doesn't
>have your full name so I don't know what else to call you), do you have
>numbers that you can post?
>Todd Lewis
>tlewis at ...255...
>"Bonsoir, Monet.  Work, work.  It is the most beautiful thing there is
>       in the world."  -- Clemenceau
>Become a BN3 affiliate! $2 per lead, $65 per sale!
>      http://es.bn3.com/aff.jx

----- Peking University Alumni Email System,  http://mail.pku.edu ----     

More information about the Snort-devel mailing list