From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-1.mimecast.com (us-smtp-delivery-1.mimecast.com [205.139.110.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 4F1F13B29D for ; Tue, 7 Jan 2020 05:43:54 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1578393833; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=HreyvVESVBdgkhYgE7YdIkJiIbgwH2Igij/MagPRtS8=; b=D0d1EmY9Ra2u1d9e/iAzjtxODXXYFcdERbXJ0Y/KuKoCToeyod3S6QABAcRxWl2ZvHe32t kPqAfFwRxwIm7+avF0SZh2Oagtjl+UQttmH/EmM6A6l18K8Kle7vJSph5YFQl7rEEsZw84 c+FGt/wk+8ZWiBJ7PuzJLh8rIyxJcjw= Received: from mail-wr1-f70.google.com (mail-wr1-f70.google.com [209.85.221.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-336-OnnumbjZP9eLI1zPTvD0Uw-1; Tue, 07 Jan 2020 05:43:50 -0500 Received: by mail-wr1-f70.google.com with SMTP id c6so19097449wrm.18 for ; Tue, 07 Jan 2020 02:43:50 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=HreyvVESVBdgkhYgE7YdIkJiIbgwH2Igij/MagPRtS8=; b=HArVV/FINv2MzYPwia0LGrT+A+78ND40+MaoT1NGXsLd50y5MgeEcZ9UZ6owgP6XJb lR8WDtfTjta7CHWdWGomylF/l9vR3wh6jFn9GhgGSA7enK9mZ2mTamDHEZiTezIDBfAF FvD4IwuGiVe+BBeal9zQBNUifXFGgxcaD+9IZ/w/cppUdQspJyxISKiTsmhiToNRKzhi kT84k/oXxI7oDw4epdhLsAvPaSnYEcK9Ueaj5VZejl4j8d7coHcZWtHHegVbVKgWvY/9 gbhOH2QeH3Fh3JTsvyht5UWygZ+DlC3ZsbpbjHTR80B7vf4nINZq3BvCOniqbU/K6YGo rrrA== X-Gm-Message-State: APjAAAXYLqL2dC4O4ZOsnAJpQIWG1VLhkvyHelTXmJ2bU84vwc68nM7f khie1xwA9VOUYXuk8wqHAGgyzEjb97khJiQHlWHD7euPsOW5xvYcmk6wyvkrDsAf+67ZDdKzYsb QWpOKRPl3PdONFC9NqZHRmzzcwyhHJWURSj4= X-Received: by 2002:a7b:c85a:: with SMTP id c26mr39479733wml.107.1578393829491; Tue, 07 Jan 2020 02:43:49 -0800 (PST) X-Google-Smtp-Source: APXvYqwhqAe0MIUxLCEBxHeY/zXx0E6R+L+jUAUk8pqHkZQb/JZCT90nDRxmSPx5pmZtbaYuiI5qpA== X-Received: by 2002:a7b:c85a:: with SMTP id c26mr39479708wml.107.1578393829109; Tue, 07 Jan 2020 02:43:49 -0800 (PST) Received: from alrua-x1.borgediget.toke.dk ([2a0c:4d80:42:443::2]) by smtp.gmail.com with ESMTPSA id b10sm78630008wrt.90.2020.01.07.02.43.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 07 Jan 2020 02:43:47 -0800 (PST) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id 74051180960; Tue, 7 Jan 2020 11:43:47 +0100 (CET) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= To: John Yates Cc: Johannes Berg , linux-wireless , Kan Yan , Make-Wifi-fast , Yibo Zhao , Rajkumar Manoharan , Felix Fietkau In-Reply-To: References: <20191222172423.131033-1-toke@redhat.com> <5bab549a72d526f4fd0f708f14b49a7af6e2c0b9.camel@sipsolutions.net> <87r20ck3x9.fsf@toke.dk> <87mub0k2cd.fsf@toke.dk> X-Clacks-Overhead: GNU Terry Pratchett Date: Tue, 07 Jan 2020 11:43:47 +0100 Message-ID: <875zhnk0m4.fsf@toke.dk> MIME-Version: 1.0 X-MC-Unique: OnnumbjZP9eLI1zPTvD0Uw-1 X-Mimecast-Spam-Score: 0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Make-wifi-fast] [PATCH v5] mac80211: Switch to a virtual time-based airtime scheduler X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 07 Jan 2020 10:43:54 -0000 John Yates writes: > On Mon, Jan 6, 2020 at 10:54 AM Toke H=C3=B8iland-J=C3=B8rgensen wrote: >> Yeah, we'd be doing the accumulation in 64bit values in any case; we're >> talking about mainly multiplication here (the whole point of the >> reciprocal stuff is to get the division out of the fast path). So how >> big of an impact is one (or two) extra 64-bit multiplications going to >> have on a 32bit platform? > > Top line: usually replacing 64 bit divide with multiply is a massive > win. > > Many platforms make (32 bits * 32 bits) -> 64 bits quite cheap: > - x86 has this as a single instruction: eax * edx -> eax:edx > - arm has much the same, plus a variant that tacks ona 64 bit accumulati= on! > - mips leaves the 64 bit product in a dedicated register; retrieval > requires 2 instructions > - ppc, being more "RISCy", has two instruction: mullo and mulhi > (performs multiply twice!) Ah, this is very useful, thanks :) > Best case is when the compiler can recognize a 64 bit multiply as really > > widen_32_to_64(left) x widen_32_to_64(right) -> 64_bit_product > > In such a case only one of the above multiply cases is necessary. Otherw= ise > one tends to get multiple partial products and double width additions. S= till, > better than nearly any flavor of 64 bit divide. So going back to the original patch, we don't really need to use 64-bit divides to compute the reciprocals; not sure what I was thinking there. That leaves us with a single 32-bit divide whenever a station is scheduled or unscheduled, and two 64-bit multiplications in ieee80211_register_airtime(). If we assume no more than 8ms of airtime is being reported at a time, we can use 2^19 as the divisor and keep the multiplication in 32 bits without overflowing, which would keep the rounding error <10% for weights <2^15. This should be enough for single-station weights, at least. I think it could also be sufficient for the weight_sum for most uses, actually, so we could start out with that and only revert to 64-bit multiplication if it turns out people are pushing the weighted fairness stuff to a point where this breaks? Johannes, WDYT? Also, what is a good place to document this? -Toke