* [PATCH 1/2] iproute2: Improve list add.
@ 2012-05-22 22:37 Pravin B Shelar
2012-06-11 22:01 ` Stephen Hemminger
0 siblings, 1 reply; 2+ messages in thread
From: Pravin B Shelar @ 2012-05-22 22:37 UTC (permalink / raw)
To: shemminger, netdev; +Cc: jpettit, jesse, Pravin B Shelar
ip command reads entire list of devices on every flush command.
While adding device record to list is does list traversal O(n).
This is time consuming for large batch commands.
Following patch improves list add operation to O(1).
Reported-by: Justin Pettit <jpettit@nicira.com>
Signed-off-by: Pravin B Shelar <pshelar@nicira.com>
---
ip/ipaddress.c | 16 ++++++++++++----
1 file changed, 12 insertions(+), 4 deletions(-)
diff --git a/ip/ipaddress.c b/ip/ipaddress.c
index 9ab65ec..7080c41 100644
--- a/ip/ipaddress.c
+++ b/ip/ipaddress.c
@@ -714,6 +714,7 @@ int print_addrinfo_secondary(const struct sockaddr_nl *who, struct nlmsghdr *n,
struct nlmsg_list
{
struct nlmsg_list *next;
+ struct nlmsg_list *last;
struct nlmsghdr h;
};
@@ -744,17 +745,24 @@ static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n,
{
struct nlmsg_list **linfo = (struct nlmsg_list**)arg;
struct nlmsg_list *h;
- struct nlmsg_list **lp;
- h = malloc(n->nlmsg_len+sizeof(void*));
+ h = malloc(n->nlmsg_len+sizeof(void*)+sizeof(void*));
if (h == NULL)
return -1;
memcpy(&h->h, n, n->nlmsg_len);
h->next = NULL;
- for (lp = linfo; *lp; lp = &(*lp)->next) /* NOTHING */;
- *lp = h;
+ if (!*linfo) {
+ /* First element. */
+ h->last = h;
+ *linfo = h;
+ } else {
+ struct nlmsg_list *last = (*linfo)->last;
+
+ last->next = h;
+ (*linfo)->last = h;
+ }
ll_remember_index(who, n, NULL);
return 0;
--
1.7.10
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [PATCH 1/2] iproute2: Improve list add.
2012-05-22 22:37 [PATCH 1/2] iproute2: Improve list add Pravin B Shelar
@ 2012-06-11 22:01 ` Stephen Hemminger
0 siblings, 0 replies; 2+ messages in thread
From: Stephen Hemminger @ 2012-06-11 22:01 UTC (permalink / raw)
To: Pravin B Shelar; +Cc: netdev, jpettit, jesse
On Tue, 22 May 2012 15:37:19 -0700
Pravin B Shelar <pshelar@nicira.com> wrote:
> ip command reads entire list of devices on every flush command.
> While adding device record to list is does list traversal O(n).
> This is time consuming for large batch commands.
> Following patch improves list add operation to O(1).
>
> Reported-by: Justin Pettit <jpettit@nicira.com>
> Signed-off-by: Pravin B Shelar <pshelar@nicira.com>
> ---
> ip/ipaddress.c | 16 ++++++++++++----
> 1 file changed, 12 insertions(+), 4 deletions(-)
>
This no longer applies, after a similar patch I just accepted
from Eric.
commit 62e2e540919d31147165dabd35431c0649122c96
Author: Eric Dumazet <edumazet@google.com>
Date: Sat Jun 9 13:55:55 2012 +0200
ip: speedup ip link
ip link has quadratic behavior because store_nlmsg()
has a head list pointer and search the end of list.
Provides a head/tail to cut time.
Time with 128000 net devices, to do "ip link show dev xxx"
Before: 2m3.594s
After: 0m2.830s
Signed-off-by: Eric Dumazet <edumazet@google.com>
If that doesn't fix your problem go ahead and resubmit.
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2012-06-11 22:01 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-05-22 22:37 [PATCH 1/2] iproute2: Improve list add Pravin B Shelar
2012-06-11 22:01 ` Stephen Hemminger
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).