3 ms·

The article doesn't seem to consider real life practicality enough. For example, what speed up do you get with this, over caching the most frequently accessed

The article doesn't seem to consider real life practicality enough. For example, what speed up do you get with this, over caching the most frequently accessed million data items using a constant time lookup? The answer of course, is it heavily depends on your problem space and data size and characteristics. Caching is somewhat discussed, and I get that the topic is not data structures and algorithms; However it seems impossible to say when this approach would be useful in general without more practical considerations. How easy would it be maintain or enhance this kind of code? Would you get emails like "...we have a few bugs in the 16-way interleaved multithreaded binary search code, who wants quickly get those cleaned up...".

asdfasgasdgasdg 7y ago
> The article doesn't seem to consider real life practicality enough. It considers it plenty for an article in the category "neat trick/wrinkle of processor caches and pipelining you may not have known/thought about to its limit." If you're actually doing binary searches on sets large enough to where this would matter, most often some kind of hash based solution is going to be preferable anyway, because of its much higher degree of cache efficiency and better asymptotic performance. That's not this article's purpose, though. Not every article is a tutorial.
- WhitneyLand 7y ago
  Who said it should be a tutorial? I agree on that point it's not a how to, and a tutorial is probably a contradiction for the topic. That doesn't mean it can't discuss practicalities. Plenty of advanced papers, blog posts, documentation, experiments, whatever, discuss engineering realities because they feel like it. The reality is some things are less intuitive and require more outside the problem thinking than others. If someone is writing about how binary trees work alone, not concurrent programming as well as is done here, there's little point to considering applications because it's simply useful to know and apply the concept so often. However this one is an edge case, and even when you need it I would doubt many seasoned engineers wouldn't still benefit from contextual considerations from the author.
dmurray 7y ago
> How easy would it be maintain or enhance this kind of code? Would you get emails like "...we have a few bugs in the 16-way interleaved multithreaded binary search code, who wants quickly get those cleaned up...". Harder than the naive binary search, but that's a good thing, because the guy who maintains the library code to do these parallel searches likes hard problems in low level programming.

asdfasgasdgasdg 7y ago

> The article doesn't seem to consider real life practicality enough. It considers it plenty for an article in the category "neat trick/wrinkle of processor caches and pipelining you may not have known/thought about to its limit." If you're actually doing binary searches on sets large enough to where this would matter, most often some kind of hash based solution is going to be preferable anyway, because of its much higher degree of cache efficiency and better asymptotic performance. That's not this article's purpose, though. Not every article is a tutorial.

WhitneyLand 7y ago
Who said it should be a tutorial? I agree on that point it's not a how to, and a tutorial is probably a contradiction for the topic. That doesn't mean it can't discuss practicalities. Plenty of advanced papers, blog posts, documentation, experiments, whatever, discuss engineering realities because they feel like it. The reality is some things are less intuitive and require more outside the problem thinking than others. If someone is writing about how binary trees work alone, not concurrent programming as well as is done here, there's little point to considering applications because it's simply useful to know and apply the concept so often. However this one is an edge case, and even when you need it I would doubt many seasoned engineers wouldn't still benefit from contextual considerations from the author.

dmurray 7y ago

> How easy would it be maintain or enhance this kind of code? Would you get emails like "...we have a few bugs in the 16-way interleaved multithreaded binary search code, who wants quickly get those cleaned up...". Harder than the naive binary search, but that's a good thing, because the guy who maintains the library code to do these parallel searches likes hard problems in low level programming.