From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x234.google.com (mail-qk0-x234.google.com [IPv6:2607:f8b0:400d:c09::234]) (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 677B13B29E for ; Sat, 2 Dec 2017 02:57:27 -0500 (EST) Received: by mail-qk0-x234.google.com with SMTP id c13so16007375qke.2 for ; Fri, 01 Dec 2017 23:57:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=IRpD75PHYo36a5ro0bcWrQZI/AWedhgQdhhfdIKWMoU=; b=anzwDoF3x62f/98iOc9NVmsjwZJ2NwPfzQ0q85EQUB7jfxDBNEKdUExUygqbVW6gZW V0rDtQisKMTh6bG/Ym6OrFvD5UQa4g5Kvfyvn6+4XI2Gg8CWOGw+uSU1a8HI+ZFS6N7L g84rsjeFKh64g+OlAkLEDXa0KQFSuXEfu5Sdjg/YCgVlwqU06s5jS/thD/wl9BMz/8S2 Os3RquwqCBMpG0TIiJqzhXOCQDlKSopXfBSCZb0u4yAi1L72Cm059ICzCiWJ2HGLE9Aa mtnOFUmhoSmXb90pzzw7AJrP5usk8rYiwapTfL0f0tj1bbw7rhcVfB0mE1+gER1wqI+L a54A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=IRpD75PHYo36a5ro0bcWrQZI/AWedhgQdhhfdIKWMoU=; b=sp3l3tIpjlW0QBfM0B0ZIEE2T0Td1ODrwqfrdKUc+HD//UuOuf1CCaawMqVQ3FRtTU feGv6iAqLsCG9ONSttXd92qAes5Ya37GtN7gYJocq+XXJLlmMsHN1Zj9bznpYLWOOjst wICIzPE8yMAzcGRHpgQJxpqj0KHNxgV8/itUF+YIAh1PGvJPVs3GJJ1B5A8xhOX4SrQa eC4p0tsi1QLtldA75cFSb3L8CX8SRdXXovYwvos0Vk0LDUR/XjyIHI4mewz30L7TGX9N WCrWz5sOcZjOGbKfntc3ZfR+LIKUeqekQ6jO36VdassEM5JrpJSuCrjoLJezPnUhl9gf +S8g== X-Gm-Message-State: AKGB3mKUvs2jyV7yZq8H43wI5CIr8xL7Q32Xv6JwrKK5EG5BMnndV2WT 51r7MnxvjKVxX5NamW/gfH3W2nc5gAmwJfaPQw8= X-Google-Smtp-Source: AGs4zMaHLYqk6i29YQbLeAlKKbWb3Ehi/8mYLKHWHKSqG8O5JtsJfp2X3n/gHPTI3KbKtlQe1ttwtqoTTCiyAc293tc= X-Received: by 10.55.192.221 with SMTP id v90mr10837647qkv.52.1512201447064; Fri, 01 Dec 2017 23:57:27 -0800 (PST) MIME-Version: 1.0 Received: by 10.140.102.179 with HTTP; Fri, 1 Dec 2017 23:57:26 -0800 (PST) Received: by 10.140.102.179 with HTTP; Fri, 1 Dec 2017 23:57:26 -0800 (PST) In-Reply-To: References: From: Jonathan Morton Date: Sat, 2 Dec 2017 09:57:26 +0200 Message-ID: To: Dave Taht Cc: Cake List Content-Type: multipart/alternative; boundary="001a11479aa414c8d0055f56d6d8" Subject: Re: [Cake] cake_heap* could use some comments X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 02 Dec 2017 07:57:27 -0000 --001a11479aa414c8d0055f56d6d8 Content-Type: text/plain; charset="UTF-8" These are standard heap algorithms whose operation should be easily recognisable. The build loop runs over the set of non-leaf nodes, implicitly accessing both children which are automatically at double the index. The timeout is simply there to elide the overhead of maintaining the heap when hard dropping hasn't been necessary for a while. - Jonathan Morton --001a11479aa414c8d0055f56d6d8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

These are standard heap algorithms whose operation should be= easily recognisable.=C2=A0 The build loop runs over the set of non-leaf no= des, implicitly accessing both children which are automatically at double t= he index.

The timeout is simply there to elide the overhead of maintai= ning the heap when hard dropping hasn't been necessary for a while.

- Jonathan Morton

--001a11479aa414c8d0055f56d6d8--