News for hackers. Stuff that matters.
Re:B-Heap vs. Binary Heap (2010) by slx26 on Sunday March 18, 2018 @04:25AM (#16610962)
A great reminder that spatial locality can be critical to performance. But that's actually quite well-known, and maybe a more important lesson would be: don't take performance for granted, even in standard libraries of well stablished languages or algorithms, there might be much room for improvement for your use case (if you need it).

This said, the article feels quite arrogant. As other commenters say, the idea behind the optimization is nothing new, just some basic concepts well applied. Which is a job well done, but probably doesn't justify the tone (that at least I perceive) from the article.

Re:B-Heap vs. Binary Heap (2010) by meuk on Sunday March 18, 2018 @08:14AM (#16611582)
Agreed, an 'I was able to optimize this'-tone would be better suited than the current 'I am the only one who does this right'.

The author is misguided if he thinks that an algorithm being called 'optimal' will have the best result in his particular use case. It usually means that the algorithm has optimal asymptotic runtime. In particular, asymptotic analysis completely ignores caching issues.

That said, the technical details are still worth reading if you have the time. I also agree with the author that CS programs are somewhat losing touch with reality.

Re:B-Heap vs. Binary Heap (2010) by vanderZwan on Sunday March 18, 2018 @10:28AM (#16612058)
I read it as the opposite: he's calling out the educated programmers' arrogance for thinking that they have already figured things out because they know which algorithms are theoretically optimal, and that they don't need to bother looking at the actual use-case.

And he's not putting himself above falling into that trap either:

> So why are you, and I, still doing it wrong?

Also, this is an article that was published in an ACM magazine, under the header of "The Bike Shed" - which I would assume is a "provocative debate"-type of column. Keep both that target audience and intent behind the article in mind when evaluating the overall tone of it.

Re:B-Heap vs. Binary Heap (2010) by meuk on Sunday March 18, 2018 @10:35AM (#16612089)
But the article is named "you're doing it wrong", not "we're doing it wrong". I know enough people who would not fall in this trap. Maybe I misinterpreted the tone, but I think it has a slight air of arrogance -- but apart from that it's a fine article.
Re:B-Heap vs. Binary Heap (2010) by chucksmash on Sunday March 18, 2018 @11:06AM (#16612273)
"You're doing it wrong" was a pretty common meme in 2011, I wouldn't take too much from it being the title of the piece other than the author was trying to be playful.
Re:B-Heap vs. Binary Heap (2010) by meuk on Sunday March 18, 2018 @11:12AM (#16612296)
Ah, true, I didn't pick up on that. Maybe I did take the tone too seriously.
Re:B-Heap vs. Binary Heap (2010) by vanderZwan on Sunday March 18, 2018 @12:30PM (#16612716)
Well, historical context is easy to lose, especially with internet memes. I recently came across an older article[0] with this sentence in the middle:

> (The Imgur previously featured in this story doesn’t credit him at all, which is some bogus, Fat Jew-style shit.)

Being unaware that "Fat Jew" was the handle of someone who got internet famous but was caught stealing other people's jokes, I was really puzzled for a second what could have warranted that random anti-Semitic statement.

[0] https://news.avclub.com/ice-t-has-some-startling-information...

[1] https://www.reddit.com/r/wholesomebpt/comments/841k3c/ice_t_...

Re:B-Heap vs. Binary Heap (2010) by anas-hossam on Sunday March 18, 2018 @11:31AM (#16612389)
But the article is named "you're doing it wrong", not "we're doing it wrong". I know enough people who would not fall in this trap. Maybe I misinterpreted the tone, but I think it has a slight air of arrogance.
Re:B-Heap vs. Binary Heap (2010) by rocqua on Sunday March 18, 2018 @10:26AM (#16612045)
I find it interesting that he is really concerned with page-faults as opposed to cache misses. Most of the recent stuff I've read on performance focuses much more on the cache.

Usually, I've seen using swap-space met with derision. I'd only expect page-faults to really happen when using a memory-mapped file. Again on the note of caches, I'd expect more fanfare be made regarding the TLB when accessing a different page than actual page-misses.

Re:B-Heap vs. Binary Heap (2010) by pdpi on Sunday March 18, 2018 @11:16AM (#16612320)
He’s concerned with page faults because his workload involves disk access. The admonitions about cache locality matter more when your workload fits in RAM.

Also, he’s not using swap as such, he’s using memory-mapped IO. If you have to hit the disk, you have to hit the disk, might as well try to do it in an OS-aware fashion.

Re:B-Heap vs. Binary Heap (2010) by blattimwind on Sunday March 18, 2018 @10:36AM (#16612094)
The internal caches of the CPU are orders of magnitude faster than handling a page fault (which means: CPU traps, switch to kernel, VM lookup, issue I/O request, block for completion, switch to user).

TFA's context is a larger-than-memory data structure mapped from disk, where heap block size = page size.

Re:B-Heap vs. Binary Heap (2010) by jay-anderson on Sunday March 18, 2018 @11:41AM (#16612439)
> This said, the article feels quite arrogant.

Agreed. Its tone is very off-putting. From the article:

> Not just wrong as in not perfect, but wrong as in wasting half, or more, of your performance.

I wish articles would move away from this use of 'wrong'. Neither of those definitions are what I understand when I read 'wrong'. If you mean sub-optimal than use that word instead. Feels like much of the rest of the article is built around this misused terminology.