11 ms·

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

229 points by eyegor 7y ago

asdfasgasdgasdg 7y ago
absl::btree_map and absl::btree_set are drop-in replacements for std::map and std::set that use b-trees under the covers. Worth noting that this simulation doesn't factor in pressure on the CPU cache, which means that even if you aren't under VM pressure, b-trees can still offer a speedup. They are also gentler to the allocator. https://abseil.io/docs/cpp/guides/container#b-tree-ordered-containers https://abseil.io/docs/cpp/guides/container#b-tree-ordered-c...
beagle3 7y ago
Constant speedup, but you need to optimize for page size; if you optimized for the wrong page size, you may get a lower constant, perhaps even < 1. And the computation is much less trivial. Still, an interesting and important observation - page sizes change every decade or two, and almost exclusively upwards, so this is worth pursuing if you need to squeeze more speed from your heap.
- swiftcoder 7y ago
  > 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)
  - devbug 7y ago
    Latency kills: memory latency, network latency, and storage latency. In that order.
    - jhayward 7y ago
      > Latency kills: memory latency, network latency, and storage latency. I think the point of the article is that > memory latency Is actually a hierarchy of its own, and non-linear depending on access patterns. Instruction fetch latency, branch mis-predict latency, cache hit/miss latency (L1 through L3), cache pressure, register pressure, TLB hit/miss, VM pressure, etc. all become significant at scale. Just knowing big-O/big-Ω characteristics aren't enough.
  - deleted 7y ago
    [deleted]
  - hinkley 7y ago
    Why would someone see 100% CPU and say there’s nothing to be done? CPU is the part we have the most control over. In my experience it’s the opposite where you can’t get people to engage you or their own brains. We aren’t CPU bound, nothing to do! I’m interested to know what you think that CPU is fully engaged doing if it’s not making progress toward a solution?
- kevingadd 7y ago
  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%.
- derefr 7y ago
  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.
purplezooey 7y ago
A bit of a specialized use case.
jmull 7y ago
Hm... this is interesting, but I’m wondering whether it makes more sense to compare b-heap to other block-oriented data structures? I’m thinking of b-tree and it’s variants.
- perennate 7y ago
  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 https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree
  - jmull 7y ago
    I mean in the context of block-oriented access, like VM as discussed in the article. That a block-aware data structure performs much better than a block-unaware one isn’t that surprising or interesting, at least to me. The question is: In the context of a block-oriented store, like a VM system, when is b-heap better or worse than b-tree and variants? Note, I said “and variants” deliberately because of course plain b-tree is pretty simple. Just comparing O between b-heap and b-tree isn’t enough because B-tree variants can have the same O characteristics, I think.
- proverbialbunny 7y ago
  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/performance-characteristics.html https://docs.scala-lang.org/overviews/collections/performanc... For more fun: https://youtu.be/sPhpelUfu8Q https://youtu.be/sPhpelUfu8Q
  - mruts 7y ago
    Unfortunately, Scala’s vector type actually sucks big time in regards to performance: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html http://www.lihaoyi.com/post/BenchmarkingScalaCollections.htm... Moreover if you want random access just use Arrays (especially now that 2.13 has immutable ones). The only use case for Vector is when you don’t know the collection size up front and need random access. Though even then it honestly might just be a better idea to build up a list and then convert it to an array.
Ciberth 7y ago
Out of pure curiousity: "... That is where it all went pear-shaped: that model is totally bogus today. ..." I agree that most concepts about operating systems are dated but where are the good resources that give an overview without being overwhelming?
mcnichol 7y ago
Can I get some clarity on pink bits? Haven't heard the term and googling around, I am certain the author isn't talking about what I am finding at the top.
- diamondo25 7y ago
  Hidden websites with lots of pink bits is exactly what you think it is. Images are served through CDNs and thus caches like varnish.
- thwarted 7y ago
  > 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.
  - mcguire 7y ago
    It's hard to overstate the importance of adult content to progress in networking, specifically.
    - dclusin 7y ago
      Adult content & companies have always been quick to utilize new technologies. JPEG's, first online payments, massive video services, etc. Its presence is even felt in places you might not expect, like reddit and imgur. I remember reading somewhere at one point 50% of reddit's traffic was adult in nature. It took netflix until 2015 to beat out porn & piracy as total bandwidth consumer on the public internet[1]. 1 - https://learnbonds.com/news/netflix-inc-nflx-now-uses-more-bandwidth-than-porn/ https://learnbonds.com/news/netflix-inc-nflx-now-uses-more-b...
  - mcnichol 7y ago
    Thats exactly what I was finding...totally surprised. Learned something new.
    - 7y ago
totalperspectiv 7y ago
Isn't this just a version of a cache oblivious algorithm, using van emde boas ordering to make maximal usage of bytes per pull into the cache? Or is there more to it that I'm not seeing? Good link to a similar discussion: An Introduction to Cache-Oblivious Data Structures - https://news.ycombinator.com/item?id=16317613 https://news.ycombinator.com/item?id=16317613
malisper 7y ago
The tl;dr is that for many use cases, you can get order of magnitude improvements by optimizing constant factors. In their case, they made a disk optimized version of a binary heap by gathering nodes into pages. This is better because it's faster to read one 4kb page from disk, than it is to perform multiple 64b reads from disk. I think what's even more interesting are cases where algorithms with worse asymptotic complexity perform better than algorithms with a better asymptotic complexity. You see this all the time in the database world, since you are often better off optimizing for disk operations than for pure asymptotic complexity. The main example that comes to mind is that if you are performing a GROUP BY on a dataset that won't fit in memory, it's usually faster to calculate the GROUP BY with mergesort than it is with a hash-table. Hash tables are notoriously bad for disk performance. Every lookup or insert becomes one disk read or write. This is in contrast to mergesort where you can take two sorted files, and in one pass merge the two files together. This leads to a much smaller total number of disk reads and writes. Two other cases like this that come to mind are Fibonacci heaps vs binary heaps[0] and matrix multiplication algorithms[1]. [0] https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_considerations https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_consi... [1] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
- hinkley 7y ago
  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.
tempguy9999 7y ago
This article appeared in the ACM a while ago[0] and it didn't go down entirely well (some of the snarky comments I remember seem to be missing there, but some remain [see Edit below]). He just laid out the data to match the memory architecture and... that's it, really. Important but hardly a new field of computer science. [0] https://queue.acm.org/detail.cfm?id=1814327Data https://queue.acm.org/detail.cfm?id=1814327Data Edit: Here's the full comments: https://queue.acm.org/fullcomments.cfm?id=1814327 https://queue.acm.org/fullcomments.cfm?id=1814327
- joe_the_user 7y ago
  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.
  - rumanator 7y ago
    > Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. That's a theoretical problem that might happen sometime in the future. Meanwhile the author's approach brings a 10x speedup in real-world deployments? Why the snark? Theoretical work is vital to understand some problems but practical applications is where the real problem expresses itself, and where real-world constraints manifest hemselves.
    - tempguy9999 7y ago
      > Why the snark? Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't.
perl4ever 7y ago
"VM pressure, measured in the amount of address space not resident in primary memory" Ok, question from someone clueless without recent low-level programming experience - is this in fact a normal situation on modern systems? Because I had the general impression that exactly because the gulf between storage and memory speeds has widened so much, that virtual memory is more of a historical appendix than anything. My laptop has 8 GB of memory, which I think is fairly small these days, so how likely is it that I would be using approaching but less than 8MB more - between 100% and 100.01% of my memory? ...I went and looked for the date of this article, and it's almost 10 years old, so perhaps things have changed...
- kevingadd 7y ago
  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).
- dmytroi 7y ago
  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.
- scottlamb 7y ago
  > 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...
loeg 7y ago
For context, this is the same author who went on to write this tweetstorm (2019): https://twitter.com/bsdphk/status/1126199508449341440 https://twitter.com/bsdphk/status/1126199508449341440 , and doubling down on that, http://phk.freebsd.dk/sagas/israel/ http://phk.freebsd.dk/sagas/israel/ ("I stand by my point"). The buried "gem" is: > I detest the vast majority of [jews] which isn't much improved in context: > I also belive that jews everywhere in the world should be appaled and up in arms over the atrocities against UNs Human Rights being done in the name of their religion, and I detest the vast silent majority of them, who fail to do so. It's amazing to me how such a gifted and intelligent software engineer can also be so careless. Regardless of whether you feel that his remarks constitute anti-semitism (and I happen to think they do so clearly), the whole episode shows incredibly poor judgement with each new follow-up tweet and finally the long-form post that gives more context, but doesn't apologize, retract, or otherwise retreat from the initial mess.
- HackOfAllTrades 7y ago
  So, is it then impossible to criticize the collective political decisions of the Jewish State of Israel without be anti-semitic?
  - loeg 7y ago
    No, of course not. Criticism of the state of Israel is entirely separate from "detesting most jews."
    - gdy 7y ago
      More than a third of all Jews live in Israel and about a third voted for the winning party. So if one detests Israel's policy, one detests free democratic choice of a big share of Jewish population. It isn't 'most jews', for that conclusion one needs to look at the programs of losing parties and for polls of the Jewish diaspora in other countries about their support for Israel's policy.
      - loeg 7y ago
dgaudet 7y ago
for a long time i used a variation of this as an interview question for performance analysis positions at google. instead of focusing on I/O costs i was focusing on cache miss costs, but it's pretty much the same observation at a different scale. it's always seemed like an excellent educational example of the difference between theoretical and practical concepts in computer engineering, such as big-O and turing machine vs. practical problem sizes and hierarchical storage/cache capacities/costs.
Franciscouzo 7y ago
The problem is that the most used memory model for algorithms performance research is not true in the real world: O(1) memory access. In the real world memory access is not a O(1) operation, it takes a different amount of time to access memory in the different levels of cache. https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- jstimpfle 7y ago
  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.
  - CalChris 7y ago
    No, it isn't bounded by the access time of the last level in the hierarchy. You could miss in the TLB before you even get to the storage hierarchy. Your TLB miss may even require a page table walk with more misses. You could even get rescheduled because your quantum was exceeded. You probably think this never happened but it used to always happen. The Linux scheduler used to traverse a linked list of pages (because Linus didn't know any better). Once the number of processes being scheduled exceeded something like 64, it slowed to a crawl consuming most of the quanta just rescheduling.
    - jstimpfle 7y ago
      Yeah, there are finer points to consider to get at an actual bound, and there might be some quirks and infelicities on some platforms. But this is not about competing processes on the system. For matters of asymptotic Analysis the access time is still O(1), i.e. bounded by a constant. If it wasn't, what would it be?
- mruts 7y ago
  O(constant) = O(constant - 1) = O(1) They are all the same.
elif 7y ago
I have a less negative reaction than most commenters seem to. I am not phased by the snarky know-it-all attitude of the author, and it actually makes his point more concise and clear IMO. I also can't help but appreciate the annecdote of abstraction hiding exactly what needs to be shown for performance computing considerations.
martamoreno2 7y ago
I wonder if he does realize that CS uses this thing called O-notation, it's really useful. So a 10x factor by the very definition of complexity theory is a zero sum game. Nobody cares. You implementation might be faster if it is optimized for a certain architecture, CPU instructions, CPU cache and so forth. It literally doesn't mean anything, it has certainly nothing to do with being more "efficient" or with Knuth not being able to make it more efficient. Optimality is discussed in O-notation, not some contrived laboratory constant factors in front of it.
- kstrauser 7y ago
  People writing the AWS checks care a whole awful lot about that insignificant constant.
- deleted 7y ago
  [deleted]
kragen 7y ago
A lot of people seem to be missing that Varnish is a two-billion-dollar company, Fastly, largely but far from entirely as a result of PHK doing a good job of optimizing it. This is not a question of freshman homework quibbling.
inlined 7y ago
This reminds me of a mongo optimization problem I faced years ago. Given the query {x:A, y:B} where x is a scalar and Y is an array, it was 40x faster to index [x, y] than [y, x]. Both indexes will show a query plan that’s index only and will hit the same number of records. Locality of memory in that index (since Y had repeats) was hugely important.
LaserToy 7y ago
I mean, isn’t array vs linked list similar? In theory linked list has a lot of good applications, but in real life it doesn’t.
- nilsb 7y ago
  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.
phkamp 7y ago
I guess it is that season again ? :-) This article seems to pop up about every other year, and pretty much garner the same general reactions every time. A lot of CS-majors immediately go in to defensive mode, starting to spew O(blablabla) formulas while thumbing their text-books. That actually just underscores the main point I tried to communicate in that article: CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance. The big-O has little to do with real-world performance any more, because of the layers of caching and mapping going on. In practice O(n²) can easily be faster than O(n) for all relevant n, entirely depending on ordering of access in the implementation. Also, CS-education tends to gloss over important footnotes. Take quicksorts worst-case performance, which even wikipedia describes as "rare". It is not. Sorted data are very, very common. Originally researchers were more careful about these issues, and they operated with several distinct big-O's. Re-read TAoCP about sorting on tape-drives for a classic example. Some pull out "Cache-Oblivious Algorithms", usually having never actually tried to implement, benchmark or use any of them. They are, as a rule, horribly complex, and seldom faster in practice, because they hide a very large performance constant in their complexity. More often than not, there are no available reference implementation, so people cannot easily try them out, and none of them are fast enough to compensate of the embuggerance of the software patents which cover them. There are usually one or two who claim that "Virtual Memory" is no longer a relevant concern and that one should just put "enough RAM" in the machine. Throwing hardware at the problem is a nice job if you can get it, and a nice hobby if you can afford it. However, even if the money is there, what about the energy consumption ? Our climate is rapidly deteriorating because of greenhouse gasses from our energy-production, and more and more algorithms run on battery-power. If I were writing a CS-thesis or CS-textbook today, it would be all about big-E() notation, and how it only weakly correlates with big-O() notation.
- ReaLNero 7y ago
  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?
andromaton 7y ago
Hey, I object to the ZX81 C64 and TRS-80 being called toys!
FullyFunctional 7y ago
The problems start in the first sentence. "Optimal" doesn't mean what Poul thinks, so he's attacking a straw-man. The data structure he poo-poos is CS 101 material. Anyone doing serious development knows better and uses structures appropriate for the underlying hardware (which fx. on an FPGA might be vastly different from an embedded process, and typically different from a workstation). Databases have used B-tree and variants for at least 50 years, not binary trees, so obviously we Know this. Much to do about absolutely nothing. EDIT: typos

229 points by eyegor 7y ago

absl::btree_map and absl::btree_set are drop-in replacements for std::map and std::set that use b-trees under the covers. Worth noting that this simulation doesn't factor in pressure on the CPU cache, which means that even if you aren't under VM pressure, b-trees can still offer a speedup. They are also gentler to the allocator. https://abseil.io/docs/cpp/guides/container#b-tree-ordered-containers https://abseil.io/docs/cpp/guides/container#b-tree-ordered-c...

beagle3 7y ago

Constant speedup, but you need to optimize for page size; if you optimized for the wrong page size, you may get a lower constant, perhaps even < 1. And the computation is much less trivial. Still, an interesting and important observation - page sizes change every decade or two, and almost exclusively upwards, so this is worth pursuing if you need to squeeze more speed from your heap.

swiftcoder 7y ago
> 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)
- devbug 7y ago
  Latency kills: memory latency, network latency, and storage latency. In that order.
  - jhayward 7y ago
    > Latency kills: memory latency, network latency, and storage latency. I think the point of the article is that > memory latency Is actually a hierarchy of its own, and non-linear depending on access patterns. Instruction fetch latency, branch mis-predict latency, cache hit/miss latency (L1 through L3), cache pressure, register pressure, TLB hit/miss, VM pressure, etc. all become significant at scale. Just knowing big-O/big-Ω characteristics aren't enough.
- deleted 7y ago
  [deleted]
- hinkley 7y ago
  Why would someone see 100% CPU and say there’s nothing to be done? CPU is the part we have the most control over. In my experience it’s the opposite where you can’t get people to engage you or their own brains. We aren’t CPU bound, nothing to do! I’m interested to know what you think that CPU is fully engaged doing if it’s not making progress toward a solution?
kevingadd 7y ago
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%.
derefr 7y ago
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.

purplezooey 7y ago

A bit of a specialized use case.

jmull 7y ago

Hm... this is interesting, but I’m wondering whether it makes more sense to compare b-heap to other block-oriented data structures? I’m thinking of b-tree and it’s variants.

perennate 7y ago
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 https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree
- jmull 7y ago
  I mean in the context of block-oriented access, like VM as discussed in the article. That a block-aware data structure performs much better than a block-unaware one isn’t that surprising or interesting, at least to me. The question is: In the context of a block-oriented store, like a VM system, when is b-heap better or worse than b-tree and variants? Note, I said “and variants” deliberately because of course plain b-tree is pretty simple. Just comparing O between b-heap and b-tree isn’t enough because B-tree variants can have the same O characteristics, I think.
proverbialbunny 7y ago
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/performance-characteristics.html https://docs.scala-lang.org/overviews/collections/performanc... For more fun: https://youtu.be/sPhpelUfu8Q https://youtu.be/sPhpelUfu8Q
- mruts 7y ago
  Unfortunately, Scala’s vector type actually sucks big time in regards to performance: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html http://www.lihaoyi.com/post/BenchmarkingScalaCollections.htm... Moreover if you want random access just use Arrays (especially now that 2.13 has immutable ones). The only use case for Vector is when you don’t know the collection size up front and need random access. Though even then it honestly might just be a better idea to build up a list and then convert it to an array.

Ciberth 7y ago

Out of pure curiousity: "... That is where it all went pear-shaped: that model is totally bogus today. ..." I agree that most concepts about operating systems are dated but where are the good resources that give an overview without being overwhelming?

mcnichol 7y ago

Can I get some clarity on pink bits? Haven't heard the term and googling around, I am certain the author isn't talking about what I am finding at the top.

diamondo25 7y ago
Hidden websites with lots of pink bits is exactly what you think it is. Images are served through CDNs and thus caches like varnish.
thwarted 7y ago
> 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.
- mcguire 7y ago
  It's hard to overstate the importance of adult content to progress in networking, specifically.
  - dclusin 7y ago
    Adult content & companies have always been quick to utilize new technologies. JPEG's, first online payments, massive video services, etc. Its presence is even felt in places you might not expect, like reddit and imgur. I remember reading somewhere at one point 50% of reddit's traffic was adult in nature. It took netflix until 2015 to beat out porn & piracy as total bandwidth consumer on the public internet[1]. 1 - https://learnbonds.com/news/netflix-inc-nflx-now-uses-more-bandwidth-than-porn/ https://learnbonds.com/news/netflix-inc-nflx-now-uses-more-b...
- mcnichol 7y ago
  Thats exactly what I was finding...totally surprised. Learned something new.
  - 7y ago

totalperspectiv 7y ago

Isn't this just a version of a cache oblivious algorithm, using van emde boas ordering to make maximal usage of bytes per pull into the cache? Or is there more to it that I'm not seeing? Good link to a similar discussion: An Introduction to Cache-Oblivious Data Structures - https://news.ycombinator.com/item?id=16317613 https://news.ycombinator.com/item?id=16317613

malisper 7y ago

The tl;dr is that for many use cases, you can get order of magnitude improvements by optimizing constant factors. In their case, they made a disk optimized version of a binary heap by gathering nodes into pages. This is better because it's faster to read one 4kb page from disk, than it is to perform multiple 64b reads from disk. I think what's even more interesting are cases where algorithms with worse asymptotic complexity perform better than algorithms with a better asymptotic complexity. You see this all the time in the database world, since you are often better off optimizing for disk operations than for pure asymptotic complexity. The main example that comes to mind is that if you are performing a GROUP BY on a dataset that won't fit in memory, it's usually faster to calculate the GROUP BY with mergesort than it is with a hash-table. Hash tables are notoriously bad for disk performance. Every lookup or insert becomes one disk read or write. This is in contrast to mergesort where you can take two sorted files, and in one pass merge the two files together. This leads to a much smaller total number of disk reads and writes. Two other cases like this that come to mind are Fibonacci heaps vs binary heaps[0] and matrix multiplication algorithms[1]. [0] https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_considerations https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_consi... [1] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...

hinkley 7y ago
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.

tempguy9999 7y ago

This article appeared in the ACM a while ago[0] and it didn't go down entirely well (some of the snarky comments I remember seem to be missing there, but some remain [see Edit below]). He just laid out the data to match the memory architecture and... that's it, really. Important but hardly a new field of computer science. [0] https://queue.acm.org/detail.cfm?id=1814327Data https://queue.acm.org/detail.cfm?id=1814327Data Edit: Here's the full comments: https://queue.acm.org/fullcomments.cfm?id=1814327 https://queue.acm.org/fullcomments.cfm?id=1814327

joe_the_user 7y ago
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.
- rumanator 7y ago
  > Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. That's a theoretical problem that might happen sometime in the future. Meanwhile the author's approach brings a 10x speedup in real-world deployments? Why the snark? Theoretical work is vital to understand some problems but practical applications is where the real problem expresses itself, and where real-world constraints manifest hemselves.
  - tempguy9999 7y ago
    > Why the snark? Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't.

perl4ever 7y ago

"VM pressure, measured in the amount of address space not resident in primary memory" Ok, question from someone clueless without recent low-level programming experience - is this in fact a normal situation on modern systems? Because I had the general impression that exactly because the gulf between storage and memory speeds has widened so much, that virtual memory is more of a historical appendix than anything. My laptop has 8 GB of memory, which I think is fairly small these days, so how likely is it that I would be using approaching but less than 8MB more - between 100% and 100.01% of my memory? ...I went and looked for the date of this article, and it's almost 10 years old, so perhaps things have changed...

kevingadd 7y ago
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).
dmytroi 7y ago
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.
scottlamb 7y ago
> 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...

loeg 7y ago

For context, this is the same author who went on to write this tweetstorm (2019): https://twitter.com/bsdphk/status/1126199508449341440 https://twitter.com/bsdphk/status/1126199508449341440 , and doubling down on that, http://phk.freebsd.dk/sagas/israel/ http://phk.freebsd.dk/sagas/israel/ ("I stand by my point"). The buried "gem" is: > I detest the vast majority of [jews] which isn't much improved in context: > I also belive that jews everywhere in the world should be appaled and up in arms over the atrocities against UNs Human Rights being done in the name of their religion, and I detest the vast silent majority of them, who fail to do so. It's amazing to me how such a gifted and intelligent software engineer can also be so careless. Regardless of whether you feel that his remarks constitute anti-semitism (and I happen to think they do so clearly), the whole episode shows incredibly poor judgement with each new follow-up tweet and finally the long-form post that gives more context, but doesn't apologize, retract, or otherwise retreat from the initial mess.

HackOfAllTrades 7y ago
So, is it then impossible to criticize the collective political decisions of the Jewish State of Israel without be anti-semitic?
- loeg 7y ago
  No, of course not. Criticism of the state of Israel is entirely separate from "detesting most jews."
  - gdy 7y ago
    More than a third of all Jews live in Israel and about a third voted for the winning party. So if one detests Israel's policy, one detests free democratic choice of a big share of Jewish population. It isn't 'most jews', for that conclusion one needs to look at the programs of losing parties and for polls of the Jewish diaspora in other countries about their support for Israel's policy.
    - loeg 7y ago

dgaudet 7y ago

for a long time i used a variation of this as an interview question for performance analysis positions at google. instead of focusing on I/O costs i was focusing on cache miss costs, but it's pretty much the same observation at a different scale. it's always seemed like an excellent educational example of the difference between theoretical and practical concepts in computer engineering, such as big-O and turing machine vs. practical problem sizes and hierarchical storage/cache capacities/costs.

Franciscouzo 7y ago

The problem is that the most used memory model for algorithms performance research is not true in the real world: O(1) memory access. In the real world memory access is not a O(1) operation, it takes a different amount of time to access memory in the different levels of cache. https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

jstimpfle 7y ago
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.
- CalChris 7y ago
  No, it isn't bounded by the access time of the last level in the hierarchy. You could miss in the TLB before you even get to the storage hierarchy. Your TLB miss may even require a page table walk with more misses. You could even get rescheduled because your quantum was exceeded. You probably think this never happened but it used to always happen. The Linux scheduler used to traverse a linked list of pages (because Linus didn't know any better). Once the number of processes being scheduled exceeded something like 64, it slowed to a crawl consuming most of the quanta just rescheduling.
  - jstimpfle 7y ago
    Yeah, there are finer points to consider to get at an actual bound, and there might be some quirks and infelicities on some platforms. But this is not about competing processes on the system. For matters of asymptotic Analysis the access time is still O(1), i.e. bounded by a constant. If it wasn't, what would it be?
mruts 7y ago
O(constant) = O(constant - 1) = O(1) They are all the same.

elif 7y ago

I have a less negative reaction than most commenters seem to. I am not phased by the snarky know-it-all attitude of the author, and it actually makes his point more concise and clear IMO. I also can't help but appreciate the annecdote of abstraction hiding exactly what needs to be shown for performance computing considerations.

martamoreno2 7y ago

I wonder if he does realize that CS uses this thing called O-notation, it's really useful. So a 10x factor by the very definition of complexity theory is a zero sum game. Nobody cares. You implementation might be faster if it is optimized for a certain architecture, CPU instructions, CPU cache and so forth. It literally doesn't mean anything, it has certainly nothing to do with being more "efficient" or with Knuth not being able to make it more efficient. Optimality is discussed in O-notation, not some contrived laboratory constant factors in front of it.

kstrauser 7y ago
People writing the AWS checks care a whole awful lot about that insignificant constant.
deleted 7y ago
[deleted]

kragen 7y ago

A lot of people seem to be missing that Varnish is a two-billion-dollar company, Fastly, largely but far from entirely as a result of PHK doing a good job of optimizing it. This is not a question of freshman homework quibbling.

inlined 7y ago

This reminds me of a mongo optimization problem I faced years ago. Given the query {x:A, y:B} where x is a scalar and Y is an array, it was 40x faster to index [x, y] than [y, x]. Both indexes will show a query plan that’s index only and will hit the same number of records. Locality of memory in that index (since Y had repeats) was hugely important.

LaserToy 7y ago

I mean, isn’t array vs linked list similar? In theory linked list has a lot of good applications, but in real life it doesn’t.

nilsb 7y ago
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.

phkamp 7y ago

I guess it is that season again ? :-) This article seems to pop up about every other year, and pretty much garner the same general reactions every time. A lot of CS-majors immediately go in to defensive mode, starting to spew O(blablabla) formulas while thumbing their text-books. That actually just underscores the main point I tried to communicate in that article: CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance. The big-O has little to do with real-world performance any more, because of the layers of caching and mapping going on. In practice O(n²) can easily be faster than O(n) for all relevant n, entirely depending on ordering of access in the implementation. Also, CS-education tends to gloss over important footnotes. Take quicksorts worst-case performance, which even wikipedia describes as "rare". It is not. Sorted data are very, very common. Originally researchers were more careful about these issues, and they operated with several distinct big-O's. Re-read TAoCP about sorting on tape-drives for a classic example. Some pull out "Cache-Oblivious Algorithms", usually having never actually tried to implement, benchmark or use any of them. They are, as a rule, horribly complex, and seldom faster in practice, because they hide a very large performance constant in their complexity. More often than not, there are no available reference implementation, so people cannot easily try them out, and none of them are fast enough to compensate of the embuggerance of the software patents which cover them. There are usually one or two who claim that "Virtual Memory" is no longer a relevant concern and that one should just put "enough RAM" in the machine. Throwing hardware at the problem is a nice job if you can get it, and a nice hobby if you can afford it. However, even if the money is there, what about the energy consumption ? Our climate is rapidly deteriorating because of greenhouse gasses from our energy-production, and more and more algorithms run on battery-power. If I were writing a CS-thesis or CS-textbook today, it would be all about big-E() notation, and how it only weakly correlates with big-O() notation.

ReaLNero 7y ago
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?

andromaton 7y ago

Hey, I object to the ZX81 C64 and TRS-80 being called toys!

FullyFunctional 7y ago

The problems start in the first sentence. "Optimal" doesn't mean what Poul thinks, so he's attacking a straw-man. The data structure he poo-poos is CS 101 material. Anyone doing serious development knows better and uses structures appropriate for the underlying hardware (which fx. on an FPGA might be vastly different from an embedded process, and typically different from a workstation). Databases have used B-tree and variants for at least 50 years, not binary trees, so obviously we Know this. Much to do about absolutely nothing. EDIT: typos