From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S1751550AbcGHIMJ (ORCPT <rfc822;w@1wt.eu>);
	Fri, 8 Jul 2016 04:12:09 -0400
Received: from mx2.suse.de ([195.135.220.15]:57743 "EHLO mx2.suse.de"
	rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP
	id S1751016AbcGHIL3 (ORCPT <rfc822;linux-kernel@vger.kernel.org>);
	Fri, 8 Jul 2016 04:11:29 -0400
Date: Fri, 8 Jul 2016 10:11:26 +0200 (CEST)
From: Jiri Kosina <jikos@kernel.org>
X-X-Sender: jkosina@pobox.suse.cz
To: Craig Gallek <kraigatgoog@gmail.com>
cc: Eric Dumazet <eric.dumazet@gmail.com>, Jamal Hadi Salim <jhs@mojatatu.com>,
        Phil Sutter <phil@nwl.cc>, netdev <netdev@vger.kernel.org>,
        LKML <linux-kernel@vger.kernel.org>
Subject: Re: [RFC PATCH v2] net: sched: convert qdisc linked list to
 hashtable
In-Reply-To: <CAEfhGizOVjafBpH8K0+57cyN_ySKqChYRw8jrfV=ODM5nmnvmA@mail.gmail.com>
Message-ID: <alpine.LNX.2.00.1607081008460.24757@cbobk.fhfr.pm>
References: <CAEfhGizOVjafBpH8K0+57cyN_ySKqChYRw8jrfV=ODM5nmnvmA@mail.gmail.com>
User-Agent: Alpine 2.00 (LNX 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Thu, 7 Jul 2016, Craig Gallek wrote:

> This sort of seems like it's just side-stepping the problem.  Given
> that the size of this hash table is fixed, the lookup time of this
> operation is still going to approach linear as the number of qdiscs
> increases.  

That's true; however the primary goal here is not to actually ultimately 
improve speed of qdisc lookup per se, but rather to make it possible to 
unhide the qdiscs which are currently omitted as the linked list takes too 
long to walk. The static hashtable is going help here.

Thanks,

-- 
Jiri Kosina
SUSE Labs