Re: dev_get_by_index is not hashed: O(n)

From: Ben Greear (greearb@candelatech.com)
Date: Wed Aug 28 2002 - 02:49:57 EST


David S. Miller wrote:
> From: Ben Greear <greearb@candelatech.com>
> Date: Wed, 28 Aug 2002 00:13:31 -0700
>
> For machines with large numbers of interfaces (VLANs for instance),
> this could be a real performance drag.
>
> Have a look at our VLAN implementation before you jump to
> conclusions :-)

At the time I wrote the vlan code, I also wrote a patch to hash the
devices on both index and on name. It made ifconfig of 4k vlans
happen in 20 seconds instead of 25 minutes...but it was not accepted,
and I didn't push the matter...

I am not sure what part of vlan would make the lookup by index not
0(n), unless things have changed significantly since the patch was
accepted.

> And the route.c case you mention is only when the route
> cache lookup misses (ie. it happens rarely)

I wonder if the rest of the cases are as rare? I know I assumed
that it was not an expensive method to call, though that doesn't
mean everyone designed like that.

So, I still think it would be good to hash.

Ben

>

-- 
Ben Greear <greearb@candelatech.com>       <Ben_Greear AT excite.com>
President of Candela Technologies Inc      http://www.candelatech.com
ScryMUD:  http://scry.wanfear.com     http://scry.wanfear.com/~greear

- To unsubscribe from this list: send the line "unsubscribe linux-net" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html



This archive was generated by hypermail 2b29 : Sat Aug 31 2002 - 22:00:01 EST