From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x641.google.com (mail-pl1-x641.google.com [IPv6:2607:f8b0:4864:20::641]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 421E33B29E for ; Mon, 26 Nov 2018 23:08:14 -0500 (EST) Received: by mail-pl1-x641.google.com with SMTP id 101so8652902pld.6 for ; Mon, 26 Nov 2018 20:08:14 -0800 (PST) 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=wWL1HJhZuzBWR2d5ODy8r/bVDf37M/PXFmoguXgElE4=; b=yhwY542YaMkzioElVLEajS7rCMKtY+TNEiQwkJBTfjrA0E0YANsQLX39ulbBKw73XD yHVFQ06j4ZCZg15lgBGyapqJHzc7H+g4IOwols440NS8V2jV061Fkdu1NRRM+D1rfcv1 Ol9n+CJ6G4aNCDbyvhDmhWC7uOa2TFpJRqYcONeDSfAGjrdQNvVlDxDw6AXsElzRKKQD 5T/07vFIyp93duWVdBOnkrx9wXNhMp4J0ZwyDuNa0uW7syWOQGq7ap+wkW8HwfvQkIvE H5iAhA0pXlEaPZ0HTahpSqnbZkooe5916nzJtFM6ZPUbz0jCUkQlIVBVeHCRf0vEYh6B UxTw== 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=wWL1HJhZuzBWR2d5ODy8r/bVDf37M/PXFmoguXgElE4=; b=hdeiqjAcjfpTeNl7jVSYhSwHaiesKZcE8oLIMVXhitZiyOEd4i1BjYvMIDtT1QLH8A brb1lvHwC9WtkL8GN4HD5WZnoradcPW8Y88lFsz3V0KMk4URx8aU+4paDKQumIMp69OO i1u81nHsLB00n8H7QvS0Ywq+hU7e8i1dJj45CxplTG6NBKOd+w/0c8dsHkf8cW4RaMvO vkatt3cfuLOwURQQbF52R9PWmRYLF2Ism9cudsUf4j6nEgIFgf2bGwjq3vuKOPGahgsZ avd6cT2LIUZcBP3UAlDQLUTJAptqWjcdh5qDZTj3ju4W5cg+sGEEZY50xmiJK0i67geD DPbQ== X-Gm-Message-State: AA+aEWZR8gg0P8gZEAK7xXwz1cWfp3IoTYlGULCRG/aGsIvx3AUUb/4Z Gv8GVg5M5YUm38RXf3mWE9X/gw== X-Google-Smtp-Source: AFSGD/VzvuedZ70dHd49+BuljNFHbQ2oojvBHJw/vhf3LPKauPise9uQAOk1VAhtEq7/hjH/6WA45g== X-Received: by 2002:a17:902:b406:: with SMTP id x6mr24007828plr.329.1543291693282; Mon, 26 Nov 2018 20:08:13 -0800 (PST) Received: from xeon-e3 (204-195-22-127.wavecable.com. [204.195.22.127]) by smtp.gmail.com with ESMTPSA id c23sm2394330pfi.83.2018.11.26.20.08.12 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 26 Nov 2018 20:08:13 -0800 (PST) Date: Mon, 26 Nov 2018 20:08:05 -0800 From: Stephen Hemminger To: Dave Taht Cc: bloat , codel@lists.bufferbloat.net Message-ID: <20181126200805.1393645e@xeon-e3> In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Subject: Re: [Bloat] [Codel] found another good use for a queue today, possibly X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 27 Nov 2018 04:08:14 -0000 On Mon, 26 Nov 2018 18:17:32 -0800 Dave Taht wrote: > I had been investigating various hashing schemes for speeding up the > babeld routing protocol daemon, and dealing with annoying bursty cpu > behavior (resizing memory, bursts of packets, thundering herds of > retractions), and, although it's a tough slog of a read, this adds a > queue to cuckoo hashing to good effect in flattening out insertion > time. > > https://arxiv.org/pdf/0903.0391.pdf > > But for all I know it's dependent on angels dancing on saddles mounted > on unicorns. I skip to the graphs for insertion time and go back to > the text for another round... > > "polylog(n)-wise Independent Hash Function". OK, my google-foo fails > me: The authors use sha1, would something lighter weight suit? > > The current favorite in DPDK land seems to be Cuckoo hashing. It has better cache behavior than typical chaining.