From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x843.google.com (mail-qt1-x843.google.com [IPv6:2607:f8b0:4864:20::843]) (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 403103B29E; Mon, 26 Nov 2018 21:17:45 -0500 (EST) Received: by mail-qt1-x843.google.com with SMTP id t13so20138249qtn.3; Mon, 26 Nov 2018 18:17:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=lQGKlZRZsoelj2V46Krz8MGee3DUpMGjTZ9LOJ50AEc=; b=GdhU8lrYu9uZyu/kFO41OAwFdwkU197il2ktdHMjSVY3UHMJdZ+4dJ1xEUVkhz73zJ GKrhdyOYSyzVr00lU6iEZNW0wn1EVOmhDIiTqcPMzxWltju5h4R8UkYcVr8e3YCOOjH3 1wl35TCcrYDRzzEJWJhlro1ZVjhRNRaqT+nkeoth2E5HBLbSWLuvWldTT/e2OaIeBAsM IfFbGycotfXnpSgoL5r/a/sAfhVXxiUUpq/7gk5HW1cbCRhc6a6sHK7MDUt9RX0Mp1zZ cYgo9hyV3T9aMYVw06MnibxgevTKVphSl+Voeej5uH3hIQc49FgRVNF2skMISfroJHma sXJQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=lQGKlZRZsoelj2V46Krz8MGee3DUpMGjTZ9LOJ50AEc=; b=okIr+uiceiKYQ/WgfgReMnNMPrR4gHrGva+0Wgj5K8HMuJ40uTCiEzZSQHPRtG03uK uMp4nwbC1rEwHNfpZYdEV9rI9xlFOXu0STs/ngQacvQHgVdtx1oLRh8Zpfbj9p8VwloC YS6lNToZMxpurjeP1gp+VxTdIt0NgiUUEIxyUTR7S7T91dk9V95cDtI7+SesTKqsR2fK GuaVIA5MNPnKBkSWrcN4G+LCfXi2yE6wPCpIUqYJGWnMjMXwQFhccPnq6UXjoEQfenMJ eaY2IGlC4gULXqh9W0ATZQythcLz6MjHs7qLDPZzmPu6o8nwbALrLWxwskw5WlyOwTWg FLkg== X-Gm-Message-State: AA+aEWb9jCJdMZkb9WY3f7QDjyfvsRUhcDZSFhFHyfpNKHCXzD3fNYSC FbwfrcOyX4dUt8fe1VKGPuGVLh6Zb+n1k4m1TdjZT0mF X-Google-Smtp-Source: AFSGD/XoTsKtZHujpVAoeygBvrbRljvqoCBDoC2c78XZZnkBorxp9ZCjRW97GDKLQNqnSircRUdFbxuO57VVak2oYic= X-Received: by 2002:a0c:a402:: with SMTP id w2mr29651483qvw.129.1543285064061; Mon, 26 Nov 2018 18:17:44 -0800 (PST) MIME-Version: 1.0 From: Dave Taht Date: Mon, 26 Nov 2018 18:17:32 -0800 Message-ID: To: bloat , codel@lists.bufferbloat.net Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: [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: Tue, 27 Nov 2018 02:17:45 -0000 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? --=20 Dave T=C3=A4ht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740