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;
MIME-Version: 1.0
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>
In-Reply-To: <87mub0k2cd.fsf@toke.dk>
From:   John Yates <john@yates-sheets.org>
Date:   Mon, 6 Jan 2020 17:19:58 -0500
Message-ID: <CAJnXXogQCKQSLT+8_NnEfFd7MLc0=YxShvb4hY2Y+BDJjybQTg@mail.gmail.com>
Subject: Re: [Make-wifi-fast] [PATCH v5] mac80211: Switch to a virtual
 time-based airtime scheduler
To:     =?UTF-8?B?VG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2Vu?= <toke@redhat.com>
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>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8BIT
Sender: linux-wireless-owner@vger.kernel.org
Precedence: bulk

On Mon, Jan 6, 2020 at 10:54 AM Toke Høiland-Jørgensen <toke@redhat.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 accumulation!
- 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!)

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.  Otherwise
one tends to get multiple partial products and double width additions.  Still,
better than nearly any flavor of 64 bit divide.

/john