You're doing it wrong: B-heap 10x faster than binary heap (2010)

From comment in link: "So you reinvented the T-tree, plus some Straw Man graphs and some comments on how you're smarter than the entire CS field. Congrats?"

Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant.

"Cache oblivious" are one seemingly better approach since they're optimal to some degree on a wide range of cache structures - but no theoretically as fast purely in-memory structures, if they are somehow in a single memory type.

"Architecture aware" trees are yet another scheme, if the program can discover the architecture.

Of course, a lot of algorithms are going to GPUs and how these structures relate to GPU processing is another thing I'd be curious about.

I suspect that the paper would have gone down much better if it wasn't phrased in such a snarky way. If he had just presented his results as b-heap is faster under VM pressure it would have just been accepted.

Well, his irritating writing style aside, he’s pinpointing one instance of a much larger problem in software development: the pervasive belief that “just enough” understanding is the right amount of understanding. I can’t count how many times I’ve been shot down in design meetings when I even bring up efficiency with “optimization is the root of all evil”. In most organizations, nothing matters except time to market (including user experience, efficiency and even accuracy) because “how long did it take to program” is the easiest thing for lazy managers to measure. Until organizations stop hiring people with only a vague notion of what they’re doing to deliver software, software will continue to get slower, buggier, and more unpredictable.

It seems like the majority of your comment focuses on your distaste on Big-O complexity, a tool used for algorithm analysis.

> CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance.

Do you have any constructive advice? How would you relax the model assumptions?

What do you use to estimate algorithm speed?

I dropped out of a not very good program, but even in my time there we did learn that O(N^2) can (and almost certainly will) be faster than O(N) on most architectures due to data locality and large constants hidden by Big O notation.

I'm not asking this to be snarky, again I'm a dropout and don't have a ton of insight into this sort of thing - do most CS programs not cover this in at least some detail at some point?

This is applicable to any system that does paging and stores and retrieves data from those pages, whether that system be a Database or an OS...

Best algorithm performance article I've read on HN for a long time!

I think the problem was most companies ran internal data centers and were unflinching to the cost of internal bloat.

IMO for a multitude of reasons this has hidden the cost of these deoptimizations due to the virtualized abstraction.

I believe with public cloud dropping a comprehensive bill on the doorstep of these enterprises, compute will become a utility that will be optimized once again with virtualization at the heart of it all.

Why do you think quicksort's worst-case performance occurs when the data is already sorted?

Hm, maybe it's been too long since I had some AlgoDat lectures, but I recall we learned that memory hierarchy was rather important, and that having data in cache can make a huge difference. Of course for the undergrad course, learning proper analysis was more important, since the whole thing about big-O is how often $STUFF happens relative to the input size (or at least that was my big take away). That $STUFF is swappable, and in the lecture we usually used "number of compares". The idea was that a student could later analyze for other things, e.g. for loads, cache-misses, page-faults, cycles or a combination thereof. You're saying yourself: "they operated with several distinct big-O's.".

So, what did you do then? From a theoretical/CS point-of-view, you're just optimizing for less VM paging. There is nothing wrong about it, quite the opposite: You're demonstrating knowledge of your machines architecture, and use it to keep memory latency low - which is both a good thing. But this isn't new, or unheard of. I recently looked something up w.r.t. tree data structures, and the 1997 8th edition of Cormen, Leiserson and Rivest even mentions how bad it is to access data from a spinning disk, and how that should be reduced (I didn't read that section in detail, because that was not what I was interested in).

However, maybe sometimes people forget that, or the application of their knowledge is bad (e.g. optimize for "number of compares" when memory latency is dominant). With regards to that, I really liked the article: I do a lot of runtime analysis for assembler code across various platforms, and as such I am painfully aware how complex even decades old pipelines are - it's a pain that developers tend to forget about this.

On the one hand I find (parts of) the linked article funny, on the other hand it's painful that you assume all other people to be ignorant, when this is not the case.

Regarding big-E: That's also not new, but probably not as popular as it should/could be. I recall a friend mentioning that part of her PhD research was energy complexity of sorting algorithms. That was ~2008.

The next biggest lie that everyone believes is that everything is premature optimization. For a while I saw this even when our customers were unhappy with the speed of the app. Probably the first bad case of cognitive dissonance I encountered in the field.

The one after that is that all performance work decreases code comprehension. There are plenty of techniques that do both, and these, as I discovered, fly below the radar of the anti-perf crowd.

That’s the difference between a data structures and algorithms class versus a systems class: in the former the constant in front of the Big O doesn’t matter while in the matter it does. Any good CS curriculum would have both courses.

> if you need to squeeze more speed from your heap

Everyone needs to "squeeze more speed from their heap". CPU-bound problems are quite rare in modern software - despite the legions of software engineers who will stare at a CPU profile that says 100% utilisation, and declare "it's CPU bound, nothing to be done".

(this is a pet peeve of mine, in case you couldn't tell)

In addition to optimizing for page size, you want to optimize for cache line alignment to minimize the amount of false sharing that happens in the CPU cache. If you're reading these data structures (safely) from multiple threads, ensuring your blocks are (say) 4080 bytes in a 4096 page can dramatically increase performance because otherwise the address bits used by the cache might line up across multiple blocks.

The last time I had to optimize a b-tree based k/v store getting this right literally could boost performance in test cases by 40%.

Is there any reason to not just produce a larger binary that contains a code path for every possible (well, probable) page size? Only one code path will be taken at runtime, so it's not like it'll harm cache locality.

This could mean 'address space reserved but not committed'. Committed address space is often much smaller than reserved address space - think of how the stack starts out with very little actual memory in use, and then grows as unused pages are first touched. That mechanism ensures that spinning up a temporary thread with a shallow stack doesn't eat up 8mb of physical memory instantly.

The pages are also zeroed on-demand when committed, which ensures thread creation doesn't first require 8mb of pages to be zeroed (There are workarounds for that as well).

Yes, but users rarely see real amount of virtual memory used (reserved, committed, etc). For example Chrome rendering process right now on my machine uses 267 MB of physical memory, 478 MB of committed virtual memory, and 2.1 GB of virtual address space.

So as you can imagine, total address space reserved on a machine can easily go into terabyte range. But that doesn't matter because every process get it's own lookup table.

> Ok, question from someone clueless without recent low-level programming experience - is this in fact a normal situation on modern systems?

Great question. Where I work, it's common to have swap disabled (or only use zram-backed swap, so pages may be stored compressed in RAM but never actually get sent to SSD much less spinning disk) and mlock the executables into RAM. So in my experience it's uncommon for memory accesses to wait for secondary storage (because we've decided to avoid it).

On the other hand, I think the author's definition is poor:

> "VM pressure, measured in the amount of address space not resident in primary memory"

By this definition, the systems I just described have lots of VM pressure. Thread stacks contribute: there might be 64 kiB on up to 4 MiB of address space reserved for a thread's stack (plus a 4 KiB guard page) but none of that is actually backed by real physical RAM until it's first accessed. So often the thread stacks will only occupy 4 KiB of actual RAM (one page).

I'd say however a more useful definition of memory pressure is based on time spent waiting for something to be paged in. See also the recent Linux "pressure stall information" work. By this definition, those non-backed-pages don't contribute to memory pressure much. (Minor page faults, which find a page of physical RAM to match the virtual page and write zeroes to it, are typically fast unless physical RAM is actually hard to find or (at least on Linux) there's heavy contention on the process's mmap_sem.)

> Because I had the general impression that ... that virtual memory is more of a historical appendix than anything.

Virtual memory is still useful for lots of things besides using SSD or disk to extend RAM: allocating address space before backing RAM (as I just described for thread stacks; also iirc ASAN/TSAN take advantage of this), zram-backed swap, and memory-mapped file I/O come to mind.

I think what the author says here is not terribly common:

> A 300GB backing store, memory mapped on a machine with 16GB or less RAM is quite typical. The user paid for 64bit of address-space, and I am not afraid to use it.

It's common for the author's application because he's designed it that way. He doesn't supply any data to make us think it's common in other applications so his advice may not be generally applicable. And he's also not using what I'd consider to be a correct definition of memory pressure. So plenty of reasons to suspect true memory pressure is an "extreme corner case" for most people (in applications other than Varnish), despite his saying "this is pretty much the real-world behavior seen."

I'm unsure from a quick skim if the B-heap he's describing is large and resides in the memory-mapped on-disk pages or if it's small and resides in anonymous pages. If the latter, it may be better to simply mlock() it in RAM so it you can guarantee there are no page faults while it's accessed.

I'd hate to have this discussion with the author because he sounds insufferably arrogant. Another commenter pointed out that this "paper" (I'd say rant) didn't go over well with the ACM crowd, and no wonder why...

Everyone here saying paging is uncommon on modern systems with large RAM is correct, but there is another factor. TLB misses are expensive and since they involved MMU misses their effect is pretty analogous to paging. So slowdowns still exist but they're not quite as pronounced since each miss only costs you a few main memory accesses rather than going all the way to secondary storage. They do happen rather more often than paging though due to the small size of the TLB.

From https://en.wikipedia.org/wiki/Translation_lookaside_buffer

These are typical performance levels of a TLB:

size: 12 bits – 4,096 entries

hit time: 0.5 – 1 clock cycle

miss penalty: 10 – 100 clock cycles

miss rate: 0.01 – 1% (20–40% for sparse/graph applications)

If a TLB hit takes 1 clock cycle, a miss takes 30 clock cycles, and the miss rate is 1%, the effective memory cycle rate is an average of 1 × 0.99 + (1 + 30) × 0.01 = 1.30 (1.30 clock cycles per memory access).

Poul-Henning Kamp is rather famous for writing code that uses mmap and a straightforward data structure for giant blobs of data and arguing that the kernel memory manager should handle the details. To my knowledge, most people dealing with data larger than memory use more active techniques.

The log(n) that dominates in search algorithms relates to the height of the tree. The larger block size doesn’t just improve the locality of reference for finding a node, it also substantially reduces the height of the tree.

Memory access time is bounded by a constant time - given by the last level in the hierarchy (which would be the SSD or HD in this case). So, access time is indeed O(1).

What's not true in the real world is that the actual value of the constant can be ignored. Memory or disk access on the one hand, and simple arithmetic operations on the other, are both O(1) but the difference is significant.

O(constant) = O(constant - 1) = O(1)

They are all the same.

Hidden websites with lots of pink bits is exactly what you think it is. Images are served through CDNs and thus caches like varnish.

> Today Varnish is used by all sorts, from FaceBook, Wikia and SlashDot to obscure sites you have surely never heard about, many of which serve mostly pink bits, lots of pink bits.

Adult content.

I think binary heap -> B-heap is analogous to balanced binary tree -> B-tree. It applies a similar idea, but provides O(1) lookup for the minimum element, O(1) average insert, and O(n) search [1], instead of O(log n) min-lookup, O(log n) insert, and O(log n search) [2]. So a B-tree would not perform well in applications where a heap is desirable.

[1] https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree

Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations.

Modern languages like Scala's Vector type is an rrb-tree under the hood: https://docs.scala-lang.org/overviews/collections/performanc...

For more fun: https://youtu.be/sPhpelUfu8Q

Indeed, this is why for C++ people are generally told to use std::vector (i.e. arrays) when some other data structure may in theory be more appropriate.

People writing the AWS checks care a whole awful lot about that insignificant constant.