[PATCH] Use saturated arithmetic for overflow detection.

[Ondřej Bílka]

On Wed, Oct 30, 2013 at 11:44:18AM -0700, Paul Eggert wrote:
> On 10/30/2013 10:45 AM, Ondřej Bílka wrote:
> 
> > -  if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
> > -        / (3 * sizeof (re_dfastate_t *)))
> > -       < ndests),
> > -      0))
> > -    goto out_free;
> > +  size_t allocated = (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX;
> > +  size_t needed_memory = MUL_S (MUL_S (ndests, 3), sizeof (re_dfastate_t *));
> > 
> > -  if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
> > -             + ndests * 3 * sizeof (re_dfastate_t *)))
> > -    dest_states = (re_dfastate_t **)
> > -      alloca (ndests * 3 * sizeof (re_dfastate_t *));
> > +  if (__libc_use_alloca (ADD_S (allocated, needed_memory)))
> > +    dest_states = (re_dfastate_t **) alloca (needed_memory);
> 
> This is slower than the original, since it has four conditional jumps
> (MUL_S, MUL_S, ADD_S, __libc_use_alloca) instead of two (<,
> __libc_use_alloca)..
>
These jumps can be predicted almost perfectly as overflows do not happen. 
Here factors like that original comparison needs to load a large
constant in register start play role in evaluation.

And that I wrote code in wrong order, should be
MUL_S (ndests, 3 * sizeof (re_dfastate_t *))

> All in all it's not clear that this approach is an improvement
> overall, as the performance penalty may not be worth the increase in
> clarity, and both approaches seem about equally error-prone.