James Harris said:
James Harris said:
On Dec 23, 6:43Â pm, Ben Bacarisse <
[email protected]> wrote:
...
size_t binsearch(int a[], size_t length, int key)
Why use size_t instead of unsigned int or unsigned long int,
especially as you add it to sum in the test harness which is long int?
Why not use unsigned for sum in the test harness?
int is better yet because the output will then be same across machines.
Using *any* unsigned type means the "not found" -1 return becomes a
value that can vary from implementation to implementation.
You mean -1 may have a strange value on a 1s-complement machine? On a
2s-complement machine wouldn't it always be all bits set even if
assigned to an unsigned variable?
No, the machine representation of -1 has no bearing on the result of the
C code[1]. What I mean is just that a return of -1 has a value of
SIZE_MAX and that varies from implementation to implementation. It's a
good value to return in a real binary search because a valid index can't
ever be (quite) that large -- the largest C-supported object of SIZE_MAX
bytes can have indexes no higher than SIZE_MAX - 1.
However, it's not a good return for a portable test program like this
because the sum of the returns will vary from machine to machine.
Alternatively, changing the simple sum to something like this:
size_t idx = binsearch(data, length, key)
sum += idx == (size_t)-1 ? -1 : idx;
could have made the output more portable.
The thing is, when you add it to sum in the main routine if sum
(defined as long int) was the same width as size_t the calculation
would, AFAICS, be correct. But say size_t was unsigned 32-bit and long
int was signed 64-bit. Wouldn't that add 4 billion and odds rather
than subtract one?
Yes, that's an example of the problem, but in the first case (where the
sizes coincide) you won't necessarily end up subtracting one. C does
not define the effect of integer overflow -- it's up to the
implementation -- so while "wrapping round" (thereby effectively
subtracting one) is common,it can't be relied on.
...
Understood. When I came to code this in 32-bit assembler I realised
that, since high and low can never have their top bits set, the simple
form would do. In general it seems that as long as they index multi-
byte quantities the sum cannot overflow.
Yes. Viewed from the C end, though, you can't be sure that sizeof(int)
is greater than 1.
It's a non-issue, though. In case anyone is interested, gcc -O3 seems
to have realised this and generated the shorter code.
Clever of it. That's yet another reason to reply on the optimiser. You
can write code that does assume that sizeof(int) > 1 and the compiler
can re-write when it knows that's true.
I wanted to spend some time on this in part to get familiar with
calling between asm and gcc (for which, if anyone else is interested
I've copied below a useful link that I found) but the rest will have
to remain a mystery for now. The bottom line, for me, is that, at
least for this test case, the code generated by gcc -O3 is very good
indeed. Looking at its asm output I can see both a number of standard
compiler optimisations and that it has recognised a number of
potential issues and dealt with them very well.
At least I now have two-way calling working between Nasm and C - and a
new respect for gcc!
http://www.cs.lmu.edu/~ray/notes/nasmexamples/
I am glad it was not wasted effort. I had assumed that most people
would look at what gcc does, scratch their head a bit and conclude that
there's really not much room for improvement. It's the kind of function
optimisers do very well at (as Jacob pointed out). I rather hoped 88888
Dihedral, in particular, would have a go, but I think I was wrong to
assume that his replies carry any real meaning.
[1] Except that it might have some bearing on what implementation-
defined behaviour is chosen for integer overflow.
