iphash vs iptreemap

iphash vs iptreemap

[Nishit Shah]

Hi,
	If I have list of only IP Addresses, which set type is better to use
in terms of Matching speed and memory ? iphash or iptreemap ?
	Does the decision depends of number of IP Addresses ?

Rgds,
Nishit Shah

Re: iphash vs iptreemap

[Jozsef Kadlecsik]

Hi,

On Thu, 19 Jun 2008, Nishit Shah wrote:

> 	If I have list of only IP Addresses, which set type is better to use
> in terms of Matching speed and memory ? iphash or iptreemap ?

Good questions! I'd say iptree(map) is faster. But if the IP addresses are 
random, then iphash can use less memory than iptree(map), if the probes 
parameter of the hash is small.

> 	Does the decision depends of number of IP Addresses ?

Not really, the number of addresses are a neutral factor. But if you 
create an iphash with small hashsize (compared to the IP addresses 
planned to store), it can be slow when adding the IP addresses due to 
rehashing if it has to grow the hash. 

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

RE: iphash vs iptreemap

[Nishit Shah]

Thanks Sir,

		Is it a way to find memory usage by both of them ?
		How much difference in terms of memory do we have ?

Rgds,
Nishit Shah.	

-----Original Message-----
From: Jozsef Kadlecsik [mailto:kadlec@blackhole.kfki.hu] 
Sent: Thursday, June 19, 2008 3:00 PM
To: Nishit Shah
Cc: netfilter@vger.kernel.org
Subject: Re: iphash vs iptreemap

Hi,

On Thu, 19 Jun 2008, Nishit Shah wrote:

> 	If I have list of only IP Addresses, which set type is better to use
> in terms of Matching speed and memory ? iphash or iptreemap ?

Good questions! I'd say iptree(map) is faster. But if the IP addresses are 
random, then iphash can use less memory than iptree(map), if the probes 
parameter of the hash is small.

> 	Does the decision depends of number of IP Addresses ?

Not really, the number of addresses are a neutral factor. But if you 
create an iphash with small hashsize (compared to the IP addresses 
planned to store), it can be slow when adding the IP addresses due to 
rehashing if it has to grow the hash. 

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

RE: iphash vs iptreemap

[Jozsef Kadlecsik]

On Thu, 19 Jun 2008, Nishit Shah wrote:

> 		Is it a way to find memory usage by both of them ?
> 		How much difference in terms of memory do we have ?

Both could be figured out by testing only, which as far as I know hasn't 
been done by anyone.

This reminds me to add statistics parameters to the next version of ipset 
in order to get the required data easily...

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

RE: iphash vs iptreemap

[Nishit Shah]

Hi,
	Can you suggest me guidelines for doing the same (i.e which things
to look out while tests are running or type of tests)? 
      can /proc/slabinfo help to identify the memory usage ?

	Also, what is significant of --gc parameter in iptreemap ?
	Does it make difference in testing ? 

Rgds,
Nishit Shah

-----Original Message-----
From: Jozsef Kadlecsik [mailto:kadlec@blackhole.kfki.hu] 
Sent: Thursday, June 19, 2008 3:27 PM
To: Nishit Shah
Cc: netfilter@vger.kernel.org
Subject: RE: iphash vs iptreemap

On Thu, 19 Jun 2008, Nishit Shah wrote:

> 		Is it a way to find memory usage by both of them ?
> 		How much difference in terms of memory do we have ?

Both could be figured out by testing only, which as far as I know hasn't 
been done by anyone.

This reminds me to add statistics parameters to the next version of ipset 
in order to get the required data easily...

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

RE: iphash vs iptreemap

[Jozsef Kadlecsik]

On Thu, 19 Jun 2008, Nishit Shah wrote:

> 	Can you suggest me guidelines for doing the same (i.e which things
> to look out while tests are running or type of tests)? 

You can test the speed by adding IP addresses to the sets and then test 
them one-by-one and measure the elapsed time. (It's worth to test entries 
missing from the set as well!) Unfortunately you cannot exclude the 
userspace-kernel communication overhead.

>       can /proc/slabinfo help to identify the memory usage ?

The hash types use a fixed size hash (which is resized if required), so 
you can calculate the required memory directly from the hash size.

The iptree types use slab caches, so /proc/slabinfo can be used.
 
> 	Also, what is significant of --gc parameter in iptreemap ?
> 	Does it make difference in testing ? 

It governs how often garbage collector is run to release empty leaves 
and branches. Of course it has an effect on the current memory usage.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

RE: iphash vs iptreemap

[Nishit Shah]

> 	Also, what is significant of --gc parameter in iptreemap ?
> 	Does it make difference in testing ? 

It governs how often garbage collector is run to release empty leaves 
and branches. Of course it has an effect on the current memory usage.

Just a clarification here. 

What I understand is, If I don't have entries with --timeout values in
iptreemap (as currently --timeout is not supported in iptreemap), do we
really need --gc ? Can't we do it on ADD/UPDATE/DELETE/FLUSH events on set ?

Rgds,
Nishit Shah. 

RE: iphash vs iptreemap

[Jozsef Kadlecsik]

On Thu, 19 Jun 2008, Nishit Shah wrote:

> > 	Also, what is significant of --gc parameter in iptreemap ?
> > 	Does it make difference in testing ? 
> 
> It governs how often garbage collector is run to release empty leaves 
> and branches. Of course it has an effect on the current memory usage.
> 
> Just a clarification here. 
> 
> What I understand is, If I don't have entries with --timeout values in
> iptreemap (as currently --timeout is not supported in iptreemap), do we
> really need --gc ? 

Yes, because it still does garbage collection which can accumulate by 
adding and deleting entries.

> Can't we do it on ADD/UPDATE/DELETE/FLUSH events on set ?

You mean garbage collection? Flushing does, the others not :-).

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary