From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-f194.google.com (mail-pg1-f194.google.com [209.85.215.194]) by dpdk.org (Postfix) with ESMTP id 40DA298 for ; Mon, 16 Jul 2018 19:50:49 +0200 (CEST) Received: by mail-pg1-f194.google.com with SMTP id m19-v6so7797256pgv.3 for ; Mon, 16 Jul 2018 10:50:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=networkplumber-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=Mdqo5vtSYSA2nllBTzW8wfcNKEPMnKHVJNN7ijjhlLY=; b=ZSfIpjZQINoqoEvHOXmmFg6CUlFO8MtTizbpFuwFRg+c7cpy2lCHVjUS8WmfSxuipK CFqMt73PzUCOWAQ7nEeSmarpkMPKZmMAmIlT+lMW2FmLrB+E5PO8Qoz3ih8VJGcCfOWy VFkD0XXT/uprR/Xz2+1vYRtIwMbXI7Za6reUybkdElmq1zUDoqo7V1GfSOChWXWkW+cn W/LyA+hR3541/yT+SnYnPzL5prLmCq1Y0imnQNzk4TnbUgZQwaE/J6syNeBLqjJuOVuQ VZxibTYHR42AwpYAke+RHbrJxUBuFF6wSy2NXGRgHtrZwZe7fR4rBzjmYnqEh1oRncqa AnmQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Mdqo5vtSYSA2nllBTzW8wfcNKEPMnKHVJNN7ijjhlLY=; b=lGMAXmgWsfVKH654bAXj+DR8QLrUIpxeijCyl6h11ZAhD/DaGQ/33MAnEEVb7NIssH RcZomda+LRqlW3o6RzgquJO8fqsaWyz/P+hSLtJzT/8ri0Q6rJ5OUNNQqnRspkbxN8zU xqdzI83bPDpZZMQ1RTJ6Y08iQmlYvIITwu6iCeN6+C4d0XMRZ+MTogCuze1BD/yWyLyi 3dETw5MiS2UnFrism1vBtWXHwwiSqNXtoY1RFWxOxnkxbtVyGZhiDZuLlLOt7WTr0+RH akygmkgTrbs43gTmR5sWMiYpDl3QFr27HPc9n+h9GhQ5o1PvWAmcgzq9NvjYVKyy4wGx PksQ== X-Gm-Message-State: AOUpUlGy74HZQgLCON65I0WJ/KCg7ba+q95kdd2u2A13SFqMBb7Pcr95 jD2zxJ8oLvkhIoHU2rQf1eKdFg== X-Google-Smtp-Source: AAOMgpdtkfDBbNmlKvX6w/AA5FLlr84AVYe4SLzKhHFiko51akDnUgvVjFTUa2VEd5uxj+/Ridl8/A== X-Received: by 2002:a65:504c:: with SMTP id k12-v6mr16278617pgo.435.1531763448447; Mon, 16 Jul 2018 10:50:48 -0700 (PDT) Received: from xeon-e3 (204-195-22-127.wavecable.com. [204.195.22.127]) by smtp.gmail.com with ESMTPSA id p62-v6sm50562289pfb.58.2018.07.16.10.50.48 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 16 Jul 2018 10:50:48 -0700 (PDT) Date: Mon, 16 Jul 2018 10:50:46 -0700 From: Stephen Hemminger To: Alex Kiselev Cc: "dev@dpdk.org" , Bruce Richardson Message-ID: <20180716105046.6cd95b7d@xeon-e3> In-Reply-To: <873586679.20180716203445@therouter.net> References: <20180711175356.035761B462@dpdk.org> <20180711133025.256a8ae1@xeon-e3> <873586679.20180716203445@therouter.net> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Subject: Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 16 Jul 2018 17:50:49 -0000 On Mon, 16 Jul 2018 20:34:45 +0300 Alex Kiselev wrote: > > On Wed, 11 Jul 2018 20:53:46 +0300 > > Alex Kiselev wrote: > > >> librte_lpm: Improve lpm6 performance > > >> Rework the lpm6 rule subsystem and replace > >> current rules algorithm complexity O(n) > >> with hashtables which allow dealing with > >> large (50k) rule sets. > > > > Wouldn't it make more sense to use something like tree, and use left/right > > in the rules entry. That way the memory is spread and scales with the number > > of rules. > I guess you are trying to propose using a radix tree. I agree, it uses memory > more efficient than hashtable. But, it would require to add a new dpdk library implementing a > radix tree, then we can talk about using it as a lpm rule storage. > I solved this problem several years ago by using the standard BSD red-black tree. This was used by Vyatta/Brocade/ATT and submitted to DPDK but never merged. The BSD red-black tree is in the libbsd-dev package in Linux. The issue which seemed to block merging was the dependency on additional packages. Since DPDK already depends on libnuma not sure why that was an issue.