From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk1-x744.google.com (mail-qk1-x744.google.com [IPv6:2607:f8b0:4864:20::744]) (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 20D983CB62; Thu, 29 Nov 2018 12:17:56 -0500 (EST) Received: by mail-qk1-x744.google.com with SMTP id y16so1506500qki.7; Thu, 29 Nov 2018 09:17:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :content-transfer-encoding; bh=SaHnu4xBRY19p4ny5auufmiRTCTq4WuPPMExCTJc+rM=; b=fkcBrTYExSBPuR3r57Fq1+G8XE41MCHJEKma+kpYteXivT0QznCFeL4Trp9kNijskB 1zbg6i5lMpmXIeXI9z1eLcavD1moMpXQJYfETcR1euoS6PeAsps1FDQ8ChFAk81NNeBv 7e1Kx4nzqZpC1EagPcXf/39vETwf8x1YqHlN/p95F8kI6WWq0ovglZ7yCyGechG8rmx/ ha3OPMPZozC11EZSqytZrDQsaWNd+2h34FKFp2CuN9J392TKWPYtFStB7bVB+Of2+dUU Yiu5wX9zaqEB3B+zzMy2AINK+V4rpRFxhhC9OZORtzQT/RRP5zT5Pz2fZfBZOkzo8Tko 2OpQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:content-transfer-encoding; bh=SaHnu4xBRY19p4ny5auufmiRTCTq4WuPPMExCTJc+rM=; b=dh0f12rpGkWrzEOSoF91aaGjGhKn0QyAIPQQJQkSZhdovbsWEcwXTPGUWFnKwsSlik zU9Hj4u7qJ7rGdwh3KJ9EbGLRjZ7iOMSLALbcXVECtMTnSw31WahFXWov/ZQlFezbcCR QGGI6otP3rMFzOyAoNhzWlTmXpOXv6sQ8hElv/9QSJPtcIwkfvOPTw0VWIDF1cUE58BV iNfQXGzTD0a3qI+VjcKDoX6qv2FqVienlELMzvILkVAp2feVxmRFl8kH9WwwOGFsvGor NyhYMLPxJDgL5APVzzWkHnmJlAnBTCX5BEOX7nIspp0VG9rXyjfNpr0AqZRiQuXOPU8H qT5w== X-Gm-Message-State: AA+aEWZxmbrIm5tkpCpNwUhisUnzE3gVrDpVIMuL/42L9Y3kLD+kc+Tb jdQn0nLDfojs0BdDOlPm4tLWzpm3exTCuM+s/BNQloai X-Google-Smtp-Source: AFSGD/VRVdRNW2kPllRbnbHW1BWH1dszTMUJPFx+uddQCNj99Itpw2v7NAujIrrPEavNTL8YXqOR/fdlWsTgTPcaUu4= X-Received: by 2002:a37:39cd:: with SMTP id g196mr2186718qka.237.1543511874887; Thu, 29 Nov 2018 09:17:54 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Dave Taht Date: Thu, 29 Nov 2018 09:17:41 -0800 Message-ID: To: bloat , codel@lists.bufferbloat.net Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: Re: [Bloat] 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: Thu, 29 Nov 2018 17:17:56 -0000 His thesis is more clear: https://sites.google.com/site/yuriyarbitman/Home/de-amortizedcuckoohashing He did exclude the cost of a resize, but, still... I find the core idea very attractive. We swapped an email and he said: > In general, I would say that a cryptographic hash function will do. > If you want to use a non-cryptographic hash function, then the > question is what provable random properties it has. This is also > discussed in the thesis and in the paper. On Mon, Nov 26, 2018 at 6:17 PM 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? > > > -- > > Dave T=C3=A4ht > CTO, TekLibre, LLC > http://www.teklibre.com > Tel: 1-831-205-9740 --=20 Dave T=C3=A4ht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740