Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #70906

Re: What's the best hashing function?

Show all headers | View raw

On 18/09/15 20:47, supercat@casperkitty.com wrote:
> On Friday, September 18, 2015 at 12:45:15 PM UTC-5, David Brown wrote:
>> Can you give a concrete example?
> 
> The code below.
> 
>> Most (all?) C compilers would simply use the processors most obvious
>> instructions for the calculations of delta.  Whether that causes a core
>> dump or an incorrect value on overflow is up to the hardware.  (It may,
>> possibly, cause some other undefined behaviour on overflow - perhaps a
>> program crash without a core dump.  You have no way to specify that
>> behaviour in C.  So if you absolutely require a core dump, write code
>> that asks for that specifically on the OS you are using.)
> 
> Most C compilers will do that, but the Standard allows C compilers to
> infer that programs will never receive inputs that would trigger Undefined
> Behavior, and some compilers very aggressively try to remove any code which
> would only be relevant in such cases, even if such code would otherwise have
> preventing the program from doing something unacceptable.
> 
>>>     int maxdiff(int *base, unsigned int n)
>>>     {
>>>       int ret = INT_MIN;
>>>       while(n--)
>>>       {
>>>         int delta = base[1]-base[0]; /// *** THIS LINE
>>>         if (delta > ret)
>>>           ret = delta;
>>>         base+=2;
>>>       }
>>>       return ret;
>>>     }
> 
> Given e.g.
> 
>     int main(void)
>     {
>       int a[2];
>       scanf("%d %d", a, a+1);
>       if (a[0] > -2000000000 || a[1] < 2000000000)
>         printf("WOW");
>       return maxdiff(a, 1) > 0;
>     }
> 
> a compiler could legitimately decide that the printf should be made
> unconditional since any inputs which would cause the "if" test to be false
> would cause Undefined Behavior in the "maxdiff" call.  I don't think that
> compilers are *yet* sophisticated enough to make that particular inference
> given the above code, but I don't think it's safe to assume that compilers
> won't make such inferences given that some people are investing a lot of
> effort into making them do precisely that.

Your claim was that "the aforementioned style of optimization impairs
many other opportunities for efficiency".  Do you have any examples that
demonstrate this claim, or that make it at all reasonable?

> 
> There are a lot of scenarios such as graphics decoding where programs will
> receive input from untrustworthy sources, and they must ensure that the
> effect of malformed or maliciously-crafted output will be limited to the
> production of harmless garbage output, but there is no particular requirement
> as to how the values in that output should be computed.  A good language
> should avoid forcing programmers or executable code to invest a large
> amount of effort to limit the consequences of malformed input in cases where
> the platform's natural way of handling such inputs would satisfy requirements.
> 
>> I can't make sense of that.  As far as I can see, the code will already
>> fulfil the requirements (with the modification I gave above).
> 
> On most compilers, it will, but I know of no clean and efficient way to write
> the code in such a way that an implementation would not be allowed to launch
> nuclear missiles in the event that two array values differed by more than
> INT_MAX.

It's easy - don't pass two values that would go outside the range.  If
you think that might be a possibility, use a "long" or "long long".  If
you have to write something that is so portable that you can't be sure
that "long long" is actually longer than "int", and you have to use a
bit of tests on signs and values before the subtraction.

Or you accept that garbage in means garbage out.

> 
>> 1. If the value is outside the range of "int", wrap it
> 
> One could avoid UB by writing the code as "(int)(long)(p[0]-p[1])) > ret";

No, that would not work - the casts are in the wrong places.

	if ((((long) p[0]) - p[1]) > INT_MAX) {
		ret = INT_MAX;
	} else {
		delta = base[1] - base[0];
		if (delta > ret) ret = delta;
	}

(I hope I haven't made a mistake there myself...)


> that would be required to either yield a value or raise an implementation-
> defined signal, and either course of action would meet requirements, but on
> some platforms casting the result of the subtraction to "int" before the
> compare could add considerable expense.  Optimal machine code on the TMS
> 320C50 would be three cycles per iteration without the cast to "int", but
> optimal code with the cast would be five cycles per iteration, adding an
> extra 66% overhead.  I'm not sure if the compiler would find the optimal
> code, but it it couldn't find that it could still do the job in six cycles
> without the cast, and eight with, meaning the cast would add 33% overhead.
> 

I don't see why the compiler could not reduce this all to a subtraction
and a check for overflow - or on a DSP like the TMS perhaps a saturating
operation could be used.

And of course since the requirement was to allow an arbitrary value in
the case of overflow, there is no need to make such checks - just write
the simple code and let the compiler use a simple subtraction.

And again, you have given no hint as to why you think disabling the
compiler's ability to use undefined behaviour for optimisation hinders
it from doing other optimisations that you feel are more valid.

>>> 2. Use the arithmetically correct value, even if it exceeds the range of "int"
>>
>> That makes no sense.  If the value is out of range, you can't use it.
>> If you need to use ranges beyond those of int, make an appropriate cast.
> 
> The code could easily modified to use the arithmetically-correct result, even
> when it exceeds the range of "int", by adding a cast to "long" or "long long".
> On some platforms, that would be very expensive, but on others it would be
> cheaper than wrapping arithmetic.

No, it could not use longer than int - it is storing the value in an int
variable.  You asked for "delta" to be int, so that's what you get.  The
compiler does not get to arbitrarily change types.

> 
>>>
>>> 3. If the value is outside the range of "int", wrap it or not as convenient
>>
>> That is pretty much the behaviour of C compilers - they generally ignore
>> the possibility of the calculation going out of range, and use
>> instructions that work correctly when you are in range.  The compiler is
>> allowed to do that precisely because the behaviour is undefined as far
>> as C is concerned.
> 
> That's the behavior of most C compilers, but you neglect a fourth behavior,
> which some compilers aggressively pursue:
> 
> 4. Assume that no inputs will be received which would cause overflow, and
>    use such inferences to eliminate "dead code" elsewhere.

And that is perfectly reasonable.  Garbage in, garbage out.  The
compiler can't do better than that, so why should it limit the speed of
the code for good input in order to try to make a little less mess when
given bad input?  It is the programmer's responsibility to either give
the function good input, or to write the function to check its inputs.

> 
> There are many cases where almost every behavior except #4 would be
> acceptable but I know of no way to prevent #4 without writing the code in
> such a way as to force #1 or #2.

If #4 is not acceptable, the function is not properly specified.

> 
> Also, there are many cases where it's necessary that overflows be detected,
> but the exact semantics of the trapping aren't terribly important.  If there
> were a standard means by which code could say "I need to determine if any
> overflows occur within this block of code, and I don't care exactly how much
> of the code executes if an overflow occurs", it would often be possible for a
> compiler to support such semantics much more cheaply than it would be able
> to support the strict-overflow-checking semantics offered by some other
> languages, or run "manual" overflow-checking code which was written using
> existing features of the C language in a way that would avoid Undefined
> Behavior.  If C wants to compete against Java, it should make it easier to
> write robust code which is more performant than comparably-robust code in
> Java.  Well-designed semantics could achieve that.
> 

So now you want the compiler to guess when you want to check for
overflows, and guess what you consider acceptable implementations, and
guess where you want to make this extra effort?  There are languages
that will do that sort of overflow checking (and indeed there are
compiler switches for gcc that will help you do it in C, at least on
some platforms).  But languages that do such checking are a lot slower
than C because of such hand-holding.  In C, you do the checking yourself
when you need it (it's not hard), which you rarely do.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 09:35 -0700
  Re: What's the best hashing function? "D. Aaron Sawyer" <aaron@110.net> - 2015-09-16 14:22 -0300
    Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 10:59 -0700
      Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 19:44 +0100
        Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 12:32 -0700
          Re: What's the best hashing function? Bartc <bc@freeuk.com> - 2015-09-16 20:40 +0100
            Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 13:11 -0700
            Re: What's the best hashing function? "James Harris" <james.harris.1@gmail.com> - 2015-09-16 21:16 +0100
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 13:47 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:14 -0700
              Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:08 -0500
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-17 00:13 +0100
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-20 01:13 -0700
          Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-16 13:10 -0700
          Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 22:17 +0100
            Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:33 -0700
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:48 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:58 -0700
                Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:13 -0500
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:17 +0200
                Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-17 08:53 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-17 11:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 10:07 +0200
                Re: What's the best hashing function? Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 09:20 +0100
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 09:25 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 19:45 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 11:47 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 21:49 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 14:50 -0700
                Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-19 00:23 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 11:13 +0200
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-19 11:03 +0100
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 12:38 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-21 11:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-22 10:23 +0200
                Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-22 02:31 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:28 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:18 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:24 +0200
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:48 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:56 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 02:09 -0700
            Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 14:49 -0700
              Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:56 +0000
              Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 23:37 +0100
        Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 13:02 -0700
          Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 21:57 +0100
            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 14:16 -0700
          Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:57 +0000
            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:20 -0700

csiph-web