Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: What's the best hashing function? |
| Date | 2015-09-18 19:45 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <mthife$5f6$1@dont-email.me> (permalink) |
| References | (9 earlier) <614f12fa-f874-479b-bf51-3f41fda410c9@googlegroups.com> <mtdsrs$sck$1@dont-email.me> <32f413cc-76e2-4e3c-97c1-0d9e8c529ce1@googlegroups.com> <mtggk4$1o5$1@dont-email.me> <a42cd14a-c042-45a2-9b05-6930acaf1fb1@googlegroups.com> |
On 18/09/15 18:25, supercat@casperkitty.com wrote:
> On Friday, September 18, 2015 at 3:07:36 AM UTC-5, David Brown wrote:
>> When greater efficiency gains can be achieved in other ways, compiler
>> writers try to do that as well.
>
> Unfortunately, the aforementioned style of "optimization" impairs many other
> opportunities for efficiency.
>
Can you give a concrete example?
>> If a program has undefined behaviour, it has a mistake, and the compiler
>> can do what it wants when that happens. This also means that the
>> compiler can assume that it will not happen, and generate code on that
>> basis. So in the "x(int a)" function above, the compiler can assume
>> that "a" is never zero, and optimise on that basis.
>
> Suppose you are tasked with writing a function which performs exactly like
> the following in all defined cases, but is is also required to either core
> dump or yield an arbitrary value in cases where the line marked with a *
> overflows.
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.)
>
> 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;
> }
>
> There are a few ways I know of to change the above code so as to meet the
> aforementioned requirements, but I don't know of any way which would meet
> the requirements and yet not incur a significant (greater than 25%) speed
> penalty on at least some systems.
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).
>
> To my mind, a good language should make it possible for a programmer to
> express three different semantics:
>
> 1. If the value is outside the range of "int", wrap it
That is one reasonable way to handle out-of-range values for int. C
specifically does not handle them this way, in order to give maximal
flexibility to the compiler. Languages such as Java /do/ specify
wrapping behaviour on ints - that requires two's complement integers.
>
> 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.
>
> 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.
>
> A programmer who doesn't care whether the value wraps or not shouldn't be
> required to write code which forces the compiler to make it wrap or forces
> the compiler to handle the result in arithmetically-correct fashion. I
> would suggest that in many cases, the optimizations that would be facilitated
> if programmers could afford to let compilers wrap when convenient would be
> far more useful than the kinds of optimizations that would be precluded by
> that. The examples I've generally seen given as to why compilers need full
> "freedom of Undefined Behavior" would generally work just as well if out-
> of-range computations could yield a "partially indeterminate result" [meaning
> that given `int i=INT_MAX; i++;` every rvalue conversion of i could,
> independently, yield a value that behaves as any number (not necessarily
> representable in any type) that is congruent to INT_MAX+1 mod
> 2^INT_BITS].
>
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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