Earlier quoted context omitted.
Python 2 was bigint by default. Not even going to deconstruct your argument past that
I didn't say it wasn't...?
I didn't say you didn't say it wasn't
Nearly All Binary Searches and Mergesorts Are Broken (2006)
91–95 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#92I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…
If you don't mind me asking how did you get into Systems Programming? (Or how would you recommend someone getting into it?)
I liked xv6. https://pdos.csail.mit.edu/6.828/2016/xv6.html
https://pdos.csail.mit.edu/6.828/2016/xv6/book-rev9.pdf
https://pdos.csail.mit.edu/6.828/2012/xv6/xv6-rev7.pdf
The labs are very informative: https://pdos.csail.mit.edu/6.828/2016/labs/lab3/
I also worked through the 6.824 Distributed Systems course, which is a lot of fun:
https://pdos.csail.mit.edu/6.824/
Lab 4 is fiendishly difficult, but you end up learning a lot.
Beyond all that, there's no substitute for just diving in and breaking stuff. Just go with whatever area you find the most fun. Maybe that's compiling and modifying the Linux kernel, or maybe it's tweaking a software rasterizer like https://github.com/blitzcode/rust-exp.
I got into systems programming mainly as a consequence of being a game developer -- when you write your own engines, you're forced to consider a hundred low-level details like memory layout, pipelining, threading, simulation, adding a scripting interface for your designers, cursing AMD when you run into GPU driver bugs, etc. There are a lifetime worth of interesting problems to solve in that area.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#93Earlier quoted context omitted.
For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.
Here's some code you can compile, it shows the problem: #include #include int main() { printf("size_t bytes: %u\n", sizeof(size_t)); size_t high = SIZE_MAX; size_t low = high-1; size_t mid_correct = low+(high-low)/2; size_t mid_incorrect = (low+high)/2; printf("low: %.ju\n", low); printf("high: %.ju\n", high); printf("low+high: %.ju\n", low+high); printf("(low+high)/2 -- incorrect: %.ju\n", mid_incorrect); printf("lo…
This is a great illustration of the actual bug.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#94Earlier quoted context omitted.
For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.
> size_t is guaranteed to be large enough for the target architecture I'm not sure if you've misunderstood this (some of the other comments mentioning type certainly have) but size_t being large enough for the purpose of indexing an array is absolutely not the issue. The issue, illustrated by the glibc code pishpash shared, is that a size_t (or any other integer type) is not necessarily large enough to hold the sum o…
Right, my comment wasn't intended to imply that simply changing the type was a fix for the bug. Just that the best practice is to use size_t for the index types, you still have to perform the calculation in a way that won't overflow.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#95Earlier quoted context omitted.
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
It doesn't, by itself, fix the bug identified in the article (though it does avoid a memory safety issue). But it's still important. Indexes should never be signed, any more than pointers should.
Why not? Indices are not pointers, so that's a poor argument by itself. Indices are offsets to pointers. If you can see any use for a negative offset off a pointer, that's your negative index use case. A nice example use is implementing IIR filters in a way that looks like the common mathematical form:
y = a[0]*y[-1] + a[1]*y[-2] + b[0]*x[-1] + b[1]*x[-2]