Hacker News new | ask | show | jobs
by xigoi 530 days ago
Is it worth making the algorithm slower just to have it work on extreme edge cases?
3 comments
jamietheriveter 530 days ago
> Is it worth making the algorithm slower just to have it work on extreme edge cases?

Yes! If an API has no documented (and preferably enforced) limits on its arguments, the caller has every right to assume the full range of the argument types is supported.

Else it is very much a bug.

“Be reasonable, dude” is ok when you order 1,000 beers. It’s not an appropriate response when calling a binary search API.

link
javcasas 530 days ago
Is it worth to make the algorithm faster at the cost of throwing surprise OutOfBounds exceptions in some extreme edge cases?

Maybe, but only if you - and only you,and not an attacker can control the case you are in.

link
xigoi 530 days ago
If an attacker can somehow make sure that there is an array with 2³⁰ elements, you have worse problems than a binary search crashing.
link
javcasas 530 days ago
Why do you think this algorithm only applies to arrays? Why do you think this algorithm doesn't apply to this sine lookup table that the compiler placed at the end of the memory in the microcontroller?
link
xigoi 530 days ago
Because the article is about binary searching an array. Obviously algorithms must be adapted to what they are used for.
link
javcasas 530 days ago
Sure, because my pre-computed table isn't an array. It's just a bunch of numbers in consecutive positions in memory. That has never been an array.

Also, what makes you think I'm not adapting the algorithm? I mean, I set the search indexes at the address of the beginning and end of the totally-not-an-array array so as to not have to do a relative memory read, because those are not supported in my microcontroller, or if they are supported, it's an extra cycle, and my timing budget is quite tight. Also, I don't do a div by 2, but a shift right by 1, same reason.

link
ajuc 530 days ago
It's as simple as replacing one NULL character with something else. Or 1 length field.
link
xigoi 530 days ago
If that happens, you’re going to get an out-of-bounds error no matter how you implement your binary search.
link
ajuc 530 days ago
In Java. In C you just access random memory values (or segfault).
link
xigoi 530 days ago
Yes, which doesn’t contradict my point.
link
ajuc 530 days ago
Well it's either that or document the domain.
link