On Wed, 30 Nov 2022 at 05:50, David Rowley <dgrowleyml@gmail.com> wrote:
>
> I spent a bit more time trying to figure out why the compiler does
> imul instead of bit shifting and it just seems to be down to a
> combination of signed-ness plus the overflow check. See [1]. Neither
> of the two compilers I tested could use bit shifting with a signed
> type when overflow checking is done, which is what we're doing in the
> new code.
>
Ah, interesting. That makes me think that it might be possible to get
some performance gains for all bases (including 10) by separating the
overflow check from the multiplication, and giving the compiler the
best chance to decide on the optimal way to do the multiplication. For
example, on my Intel box, GCC prefers a pair of LEA instructions over
an IMUL, to multiply by 10.
I like your previous idea of using an unsigned integer for the
accumulator, because then the overflow check in the loop doesn't need
to be exact, as long as an exact check is done later. That way, there
are fewer conditional branches in the loop, and the possibility for
the compiler to choose the fastest multiplication method. So something
like:
// Accumulate positive value using unsigned int, with approximate
// overflow check. If acc >= 1 - INT_MIN / 10, then acc * 10 is
// sure to exceed -INT_MIN.
unsigned int cutoff = 1 - INT_MIN / 10;
unsigned int acc = 0;
while (*ptr && isdigit((unsigned char) *ptr))
{
if (unlikely(acc >= cutoff))
goto out_of_range;
acc = acc * 10 + (*ptr - '0');
ptr++;
}
and similar for other bases, allowing the coding for all bases to be
kept similar.
I think it's probably best to consider this as a follow-on patch
though. It shouldn't delay getting the main feature committed.
Regards,
Dean
