From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x133.google.com (mail-lf1-x133.google.com [IPv6:2a00:1450:4864:20::133]) (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 A110D3B29E; Mon, 26 Nov 2018 23:17:22 -0500 (EST) Received: by mail-lf1-x133.google.com with SMTP id e26so15341550lfc.2; Mon, 26 Nov 2018 20:17:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=imImAXLhHoAGsPqD3MhjqOZ0y9I14J30tMKhW7IGCRk=; b=h369+6ww0EUfBEO7uiRx+E0KWOA0CyA+rrhu6sKaZH+4sAXnFDGJku0bDhPCWgUYIg risRV1F8ZmMD7yn4OwXhmbw8QExlV4lLYxk3+lN1v8OyAs4GFkeHJTpvIQDAwqgJRNb+ 7bDBn0PHH6gWXnO+HNK5CQjGgyDSYoo+bBaiKOE4m6wu+dAYxX1vuM3R4UlOTvgeG0lh j58bBZAW84f/YrQPVgzao1XZPe0uVb9kaWB97wQPAgg+thmNWFAPQA92639q4As99fff jNWWbLEc+Cwyds3P+eXr0tyvU29BpNUmEEF3tHLuWjX8ZQqYBPQkiRlQp3fjxzIoqrgT E5sA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=imImAXLhHoAGsPqD3MhjqOZ0y9I14J30tMKhW7IGCRk=; b=YKvGHCeQ+Coz40KTF0tsA6Zw7bFKgpJZVQJm+zYglLsOWHGXFEXgvlMVuKtwiQ+Xs/ 6VhoEoHU9WBHNLmDBHAvfb6JKT2ds2om4lDOI9AVFWqyTVZNZEbwUVcoVWanKqdetind do0I6V68OXprYPPxxD9bupgGWv+sNuakA9RoKjaW/FXgRrowPWHZ/M6Wom404LjezNpo bGpD0IIpW3wy6Hq7V6a5WCHDtMe1Ax0P90AccbNpz0dqVE6wwn5m7DzihgETPgDQEcnP qRuRk41zhy3yixkIKI1BE3qzZNBAbeU/tPis7gni6spFJTwboT7owlFEOOq3j7dLSLOF J+7g== X-Gm-Message-State: AA+aEWb6agKgc69rBI/pGR83A/aIr48EKZDj4FS745SPPj3UkI1p7Bql VM0kmNIeDZB2WioFLO2G1o4= X-Google-Smtp-Source: AFSGD/UYHBLrDsOTnefQxtGyrGbddM1zFgAbtKdPOXu5j1RKU6IunNZ3LDKUzPGLJFHYi28kBFIYaw== X-Received: by 2002:a19:660a:: with SMTP id a10mr5444860lfc.146.1543292241461; Mon, 26 Nov 2018 20:17:21 -0800 (PST) Received: from jonathartonsmbp.lan (83-245-236-220-nat-p.elisa-mobile.fi. [83.245.236.220]) by smtp.gmail.com with ESMTPSA id p4-v6sm357015ljc.60.2018.11.26.20.17.20 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 26 Nov 2018 20:17:20 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\)) From: Jonathan Morton In-Reply-To: <20181126200805.1393645e@xeon-e3> Date: Tue, 27 Nov 2018 06:17:19 +0200 Cc: Dave Taht , codel@lists.bufferbloat.net, bloat Content-Transfer-Encoding: quoted-printable Message-Id: <5CA2D845-508D-421C-AF38-E2B5AE0E54B2@gmail.com> References: <20181126200805.1393645e@xeon-e3> To: Stephen Hemminger X-Mailer: Apple Mail (2.3445.9.1) 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:17:22 -0000 >> "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. That paper describes an improved variant of cuckoo hashing, using a = queue to help resolve collisions with better time complexity. The proof = relies on (among other things) a particular grade of hash function being = used. SHA1 is described as being suitable since it offers = cryptographic-level performance=E2=80=A6 We actually need two hashes = with independent behaviour on the same input, one for each table. If we were to assume table sizes up to 64K, using both halves of a good = 32-bit hash might be suitable. It may be that plain old Jenkins hash = would work in that context. Supplement that with a 64-entry queue with = linear search (in software) or constant-time CAM search (in hardware). - Jonathan Morton