Received-SPF: pass (google.com: best guess record for domain of linux-wireless-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= <toke@redhat.com>
To:     John Yates <john@yates-sheets.org>
Cc:     Johannes Berg <johannes@sipsolutions.net>,
        linux-wireless <linux-wireless@vger.kernel.org>,
        Kan Yan <kyan@google.com>,
        Make-Wifi-fast <make-wifi-fast@lists.bufferbloat.net>,
        Yibo Zhao <yiboz@codeaurora.org>,
        Rajkumar Manoharan <rmanohar@codeaurora.org>,
        Felix Fietkau <nbd@nbd.name>
Subject: Re: [Make-wifi-fast] [PATCH v5] mac80211: Switch to a virtual time-based airtime scheduler
In-Reply-To: <CAJnXXogQCKQSLT+8_NnEfFd7MLc0=YxShvb4hY2Y+BDJjybQTg@mail.gmail.com>
References: <20191222172423.131033-1-toke@redhat.com> <5bab549a72d526f4fd0f708f14b49a7af6e2c0b9.camel@sipsolutions.net> <87r20ck3x9.fsf@toke.dk> <CAJnXXoiyWKSLHqMzMcSzHBM-HhfYtcURW1hYd-3Yf7K00NTqgQ@mail.gmail.com> <87mub0k2cd.fsf@toke.dk> <CAJnXXogQCKQSLT+8_NnEfFd7MLc0=YxShvb4hY2Y+BDJjybQTg@mail.gmail.com>
Date:   Tue, 07 Jan 2020 11:43:47 +0100
Message-ID: <875zhnk0m4.fsf@toke.dk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Sender: linux-wireless-owner@vger.kernel.org
Precedence: bulk

John Yates <john@yates-sheets.org> writes:

> On Mon, Jan 6, 2020 at 10:54 AM Toke H=C3=B8iland-J=C3=B8rgensen <toke@re=
dhat.com> 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