undefined | Better HN

0 pointshiAndrewQuinn8mo ago0 comments

Very good! Looks good to me. One small callout:

        mid = left + (right - left) // 2

This implementation detail is to my knowledge unnecessary in Python because Python's built-in int type has arbitrary-precision integers. It's intended to avoid buffer overflows in languages like C.

Imagine, say, that left is 1 and right is 2^63 - 1. In Python left + right will just give you 2^63, no big deal. In C, left + right will overflow and produce undefined behavior; in practice it usually gives you I think -2^63, which is obviously going to screw up the bsearch a bit. It isn't wrong, just slightly less idiomatic for the language.

Python's interpreter may or may not be able to recognize and refactor the slight inefficiency of the extra arithmetic operation out. I will only point out that most of the time when we write our own bsearch it's because we want to optimize something really fundamental to the codebase. Any time you have to whip up your own algorithm it's prima facie evidence that that part of the code might be good to profile.

0 comments

naniwaduni8mo ago

Even in languages like C, it's mostly voodoo in practice unless you're using undersized indices anyway—you surely don't have anywhere near SIZE_MAX/2 elements.

The underlying problem is sloppy use of int for indices. The roundabout calculation will still overflow at twice the size.

namibj8mo ago

For scalar code that's fair, but keep in mind that with `gather`, you can vectorize it, and there you do worry about integer width as more width means fewer lanes. Though tbf you probably should use B+ Tree structures chunked to your bulk/cache fetch "line/page" size, and vectorized higher-than-radix-2 search within each node.

inhumantsar8mo ago

IIRC you're correct, but the comment is a red herring.

In Python, the double slash (or type casting) is necessary as a single slash will yield a float by default. Double slash returns an int.

j / k navigate · click thread line to collapse