Algorithms for Modern Hardware

https://en.algorithmica.org/hpc/

by throwaway2037 • 2 years ago

308 72 2 years ago

en.algorithmica.org

throwaway20373• 2 years ago

This is a wild quote:

<< Among the cool things that we will speed up:

    2x faster GCD (compared to std::gcd)
    8-15x faster binary search (compared to std::lower_bound)
    5-10x faster segment trees (compared to Fenwick trees)
    5x faster hash tables (compared to std::unordered_map)
    2x faster popcount (compared to repeatedly calling popcnt)
    35x faster parsing series of integers (compared to scanf)
    ?x faster sorting (compared to std::sort)
    2x faster sum (compared to std::accumulate)
    2-3x faster prefix sum (compared to naive implementation)
    10x faster argmin (compared to naive implementation)
    10x faster array searching (compared to std::find)
    15x faster search tree (compared to std::set)
    100x faster matrix multiplication (compared to “for-for-for”)
    optimal word-size integer factorization (~0.4ms per 60-bit integer)
    optimal Karatsuba Algorithm
    optimal FFT

If true, why haven't these appeared in the C++ STL?

EDIT: Formatting only

janwas• 2 years ago

I am inclined to believe those numbers :)

That's an interesting question. One partial answer is that the hash table speedup likely involves an interface change, replacing "insert single item" with batching. This is a generally helpful principle, but unfortunately does not match some existing abstractions.

userbinator• 2 years ago

C++ STL is generic and cross-platform, but I suspect they are doing specific optimisations (x86 Asm), and it's very easy to beat a compiler that way.

adrianN2• 2 years ago

It’s not that easy to beat compilers, they know how to generate processor specific instructions too.

josephg2• 2 years ago

About a decade ago I wrote a fast rope library in C, with support for arbitrary inserts & deletes at arbitrary locations in large strings. I benchmarked it, and I was shocked to discover that my library was ~20x faster than the SGI C++ rope library that shipped with my compiler.

I assumed I must be doing something wrong. Eventually took a look and found the SGI rope library constructs a tree where each heap allocated leaf node only contains a single character from the document. No wonder its so inefficient. I'm somewhat horrified by the idea that anyone is using that implementation in their software.

Sometimes I think about how much money people would pay to make their computer run 20x faster. Our society spends a truckload of money on computing hardware - but most of that hardware is wasted running wildly inefficient programs. Modern computers should do basically everything instantly. Its weird to me that we'll pay thousands of dollars for faster CPUs then write new software in python, electron or a docker container running in a VM.

reaperman2• 2 years ago

Sometimes I think about how much money people would pay to make their computer run 20x faster.

I think people who can reliably do this are paid $250-750k/year at top paying companies.

falsandtru• 2 years ago

Sometimes I think about how much money people would pay to make their computer run 20x faster.

Bottlenecks that can make a computer 20x faster are very rare. First, pay $1m for a specialist to find the bottlenecks. However, it is even rarer that it is a bottleneck of the entire service. Rather, it is more likely to be an accidental drop in performance. Thus, basically performance monitoring is the best use of money.

Its weird to me that we'll pay thousands of dollars for faster CPUs then write new software in python, electron or a docker container running in a VM.

There are more labor costs and lost commercial opportunities due to delays in development.

Kamq2• 2 years ago

It should also be noted that you can also get a significant speed up by writing situation specific code, instead of handling the general case, if your problem allows it.

This kind of guarantees that custom code, written competently, will always be able to outpace standard library code. The standard library is one of the few things that probably always needs to handle the general case.

bobajeff• 2 years ago

Its weird to me that we'll pay thousands of dollars for faster CPUs then write new software in python, electron or a docker container running in a VM.

Python has a REPL, Duck typing and hooks for many libraries including gui libraries.

Electron is basically a browser you can program via JavaScript with everything you'll ever need to make a gui application.

They both make a lot of sense when you consider the alternatives. However, I do wonder why there isn't yet an option to AOT compile python and electron projects into fast executables.

hughesjj• 2 years ago

Isn't stl notoriously slow relative to most c++ implementations given equivalent functionality?

I've always understood stl to prefer rock solid safety+stability+compatibility (+ a bit of dogfooding) with the widest applicable domain (scale etc) over pure, unadulterated performance, but I haven't coded in c++ since college so I know nothing

kccqzy• 2 years ago

The standard library has a bunch of requirements that a random third party library likely does not have. Like ABI compatibility (most people recompile from source often so it isn't needed). Like exception safety (most people turn off exceptions anyways so they don't need such safety).

Some parts of the standard library like std::vector is already good enough. Other parts like std::unordered_set are rarely used in industry unless low-dependency is a requirent.

38362936482• 2 years ago

Because the STL makes a bunch of guarantees that can't be broken. Like that an object won't ever move within a hashmap, even on edits. Or that std::set has to use buckets and linked lists.

Basically they've overspecified their datastructures and we're now paying the price

deadlypointer• 2 years ago

Std::set is using red black trees, did you mean std unordered set?

foofie• 2 years ago

Basically they've overspecified their datastructures and we're now paying the price

I strongly disagree, and I'm perplexed how anyone can describe fundamental traits such as object lifetimes of fundamental infrastructure such as standard data structures of being over specified.

Just imagine the shit show it would be if upgrading your compiler broke your code because std::set started leading your code to throw exceptions because they sneaked a major breaking change such as moving objects that should not be moved.

It's also perplexing how breaking backward compatibility is depicted as a perfectly acceptable thing to do to a major programming language while completely ignoring the ability to release code as a third-party library. If the new implementation of a std::set alternative is any good, people would be lining up around the block to adopt it. I mean,it's already a standard practice in game development to use custom data structure implementations with custom allocators. Why is this not an option, but breaking half of the world's code suddenly is?

ribit3• 2 years ago

One also needs to look at the context of these quotes. For example, for the binary search they change the array layout to improve cache locality. This is not really helpful if you have to work with sorted arrays (as many binary search algorithms do). If instead you have the freedom to optimize the data structure itself (and you do the search often enough to amortize the construction), you might as well build some variant of a B-tree which is going to be much faster than binary search anyway.

adrianN2• 2 years ago

I'd like to see a benchmark showing a B-tree beating an array with the correct layout. I think you only want a tree if you also want to update the array.

sereja5• 2 years ago

Author here. I published most of these in one batch two years ago, and this is a relatively short time for compilers and libraries to catch up (when Daniel Lemire publishes something, it also usually takes a few years before it makes its way to the standard libraries, and he is much more involved in the downstreaming process than I am).

In my opinion, the main challenges are:

1. Lack of suitably narrow abstractions. E.g., my "binary search" implementation requires building a small static structure (6-7% of the original array size), and although it is extremely hard to imagine a practical use case where you get a sorted array but can't spend linear time on its preprocessing, it's technically not a drop-in replacement for std::lower_bound.

2. Backwards compatibility. E.g., std::set has a requirement that a node deletion should not invalidate other iterators, which makes it harder to implement it as a B-tree, which has to move a lot of keys around after a node merge/split.

3. Performance regressions. Sometimes a change can make a program 2x faster in most use cases but 1.5x slower in some specific one. If the hardware handling that use case was already at 90% capacity, it will now start to fail after the upgrade, while a 2x improvement on other use cases is just "nice" and doesn't offset it.

4. Vagueness of "better". There are about 10 blog posts on the internet now claiming they have designed the fastest hash table in the world—and every one of them is right because they are using different benchmarks tailored to their specific data set and their specific hardware.

5. Desire to implement things more generically in the middle-end of a compiler instead of the standard library, which is much harder to do. You don't want to hand code the optimal SIMD procedure for calculating the sum of an array for each CPU microarchitecture; you want the compiler to do it automatically for everything that resembles a simple "for" loop. This also leads to a diffusion of responsibility, with compiler people and library maintainers arguing over the appropriate place for an optimization to be implemented.

6. Lack of incentives. Most people who can implement these optimizations work for big tech and would look better in their performance review by contributing to their employer's library (e.g., Abseil for Google, Folly for Meta), or at least to a library with a less Kafkaesque review process like Boost, rather than the standard library.

7. Things still being in the research stage. For example, I recently discovered (but haven't published yet) a new GCD algorithm that seems to yield another ~2x improvement over binary GCD (~4x over std::gcd), and so the guy who recently pushed it in libc++ has in a certain sense wasted work.

I haven't rerun benchmarks myself, but I believe some relatively decoupled parts of the STL have actually since been upgraded in some compilers (std::lower_bound is now branchless, std::gcd now uses binary GCD, std::accumulate and similar reductions now use instruction-level parallelism when they see it) although in all these cases I didn't discover but at most only popularized them.

vlovich1233• 2 years ago

For the binary search index speed up, is that documented somewhere? The English version talks about Eytzinger layout but I think you’re referring to something else since that’s not an ancillary array size.

Great job on this book. Lots of great content that can be used as reference.

chubot• 2 years ago

The API design of STL is often over-constrained.

That is, The style is very kitchen-sink and generalized, which means implementers have little flexibility.

Every “real” C++ codebase I’ve worked on has its own data structures for most things. And that’s a feature of C++, not a bug.

For example, don’t use std::unordered_map for anything performance sensitive. It’s a shockingly slow hash table because the interface constrains it to allocate a lot.

The STL isn’t designed for optimum performance. It’s easy to do better by satisfying your app’s requirements and nothing else.

vlovich1233• 2 years ago

There’s also other reasons. For example, take binary search:

* prefetch + cmov. These should be part of the STL but languages and compilers struggle to emit the cmov properly (Rust’s been broken for 6 years: https://github.com/rust-lang/rust/issues/53823). Prefetch is an interesting one because while you do optimize the binary search in a micro benchmark, you’re potentially putting extra pressure on the cache with “garbage” data which means it’s a greedy optimization that might hurt surrounding code. Probably should have separate implementations as binary search isn’t necessarily always in the hot path.

* Eytzinger layout has additional limitations that are often not discussed when pointing out “hey this is faster”. Adding elements is non-trivial since you first have to add + sort (as you would for binary search) and then rebuild a new parallel eytzinger layout from scratch (i.e. you’d have it be an index of pointers rather than the values themselves which adds memory overhead + indirection for the comparisons). You can’t find the “insertion” position for non-existent elements which means it can’t be used for std::lower_bound (i.e. if the element doesn’t exist, you just get None back instead of Err(position where it can be slotted in to maintain order).

Basically, optimizations can sometimes rely on changing the problem domain so that you can trade off features of the algorithm against the runtime. These kinds of algorithms can be a bad fit for a standard library which aims to be a toolbox of “good enough” algorithms and data structures for problems that appear very very frequently. Or they could be part of the standard library toolkit just under a different name but you also have to balance that against maintenance concerns.

derefr• 2 years ago

Is there a statically-compiled language where the subset of methods of an API or ADT that ever get referenced, determines at link time which implementation of the API or ADT gets linked + WPOed against?

Because it seems “obvious” to enable programs that don’t depend on the over-constraining parts of things like std::unordered_map, to specialize the implementation they’re using so that it doesn’t employ the overhead-laden parts required to make those uncalled methods function. And “just have two copies of the code and pick between them based on control-flow info” seems like a very trivial way to do it for at least some low-hanging-fruit cases.

edward28• 2 years ago

Step 1. Throw more compute at it.

signa11• 2 years ago

imho, probably preceded by

   step-0 sit quietly in a room with paper and pencil, and ... T.H.I.N.K

pikrzyszto• 2 years ago

And then you get hit by Universal Scaling Law (or Universal Law of Computational Scalability) - see the section on https://en.wikipedia.org/wiki/Neil_J._Gunther

You can't throw more compute at a problem ad infinitum.

reaperman2• 2 years ago

Previous postings (including 30 days ago, but this one seems to be from 'tosh 8 hours ago and then manipulated by mods for a "second chance" post getting merged with a different posting by 'throwaway2037 from 2 days ago, and I'm happy for that):

March 7, 2022 - 62 comments - https://news.ycombinator.com/item?id=30583808

Feb 17, 2022 - 49 comments - https://news.ycombinator.com/item?id=30376140

Feb 12, 2022 - 44 comments - https://news.ycombinator.com/item?id=30311112

Nov 1, 2022 - 33 comments - https://news.ycombinator.com/item?id=33427349

nayemrahman• 2 years ago

Nice!

srijansriv• 2 years ago

obligatory mention of cp-alogs: https://cp-algorithms.com/index.html

quibono• 2 years ago

Love cp-algos. Great quality, also love the sample code.

One of my favourite write-ups: https://cp-algorithms.com/string/z-function.html

someuser0123091• 2 years ago

Does anyone know if there is any research around designing a compiler + language that produces optimal code? Besides superoptimization that is.

Specifically, in what way should a language be designed to aid the compiler in finding the optimal code?

For example for the matrix multiplication, why can't the compiler find the optimal code? Why are BLAS written in assembly for each CPU architecture? Isn't this a question of having a high level CPU spec (how many ports, instruction latency, throughput) and then using a constraint solver to find the optimal code?

TrueDuality• 2 years ago

Compiler optimization is an extremely hard problem. Unsolvable by our current standards and usually the compiler has less knowledge than the author of the code and has to make assumptions about the hardware it is going to run on. Language design feeds heavily into the types of optimizations that are even possible to reason about.

So yes there has been an enormous amount of research into both the programming language design side of this equation, the compiler design, and the area in the middle. Probably hundreds of thousands of research papers since the 50s or 60s.

Compilers and automated systems, in the general case at least, still can't out compete a domain expert that is familiar with the specific hardware being targeted, a good profiler, and the time to fiddle with the raw assembly.

nyrikki• 2 years ago

Different hardware cache-hits differently for one.

Level 3 BLAS functions like matrix on matrix products perform O(N^3) operations on O(N^2) data.

The main way BLAS boosts Level 3 functions is cache optimization which is hardware dependent.

But optimization problems in general are not trivial for computers.

charleshn• 2 years ago

Why are BLAS written in assembly for each CPU architecture?

On that specific subject of SIMD portability, embedded DSL like Highway developed by Google [0] can help. Hopefully it'll gain traction and usage.

[0] https://github.com/google/highway

pornel• 2 years ago

With a typical workflow of “just compile this source code”, this is an impossible task, because performance of algorithm implementations depends on the actual data they process (think how SQL plans queries based on table stats). Profile-guided optimization already improves performance significantly despite merely informing some heuristics. A truly optimal compiler would need to design algorithms for specific data sets (basically what people do when they profile the code).

However, there are some takes beyond the “Algol68 on PDP11” design of most languages. There’s Intel’s SPMD C compiler that extends the language to make auto-vectorization a first-class feature.

There is Halide lang specifically for image processing, which separates the goal from the algorithms used to archive it.

naasking• 2 years ago

This strikes me as akin to asking why can't an algorithm find the lowest cost path to visit a set of nodes, aka the traveling salesman problem.

A language that helps the compiler has the usual properties we already know: provide as much info as possible with types, and restrict the set of allowable expressions to make the search tractable (like CUDA, ownership and alias analysis, and so on).

rigelbm• 2 years ago

The proposed ToC looks amazing, and I can't wait to get my hands in this book. One thing that seems omitted though, which can have significant impact in performance, is I/O. That would have been a nice add-on.

vlovich1233• 2 years ago

Great. Unfortunately the English version is missing most of the algorithms (or it hasn’t been written yet).

Of course nothing can be complete, but I had the following pieces of feedback (plan on opening a GitHub issue later):

The compiler flags section is missing the following:

* Os - optimize for size

* LTO

* Compiling -ffunction-section -fdata-sections & then linking with —-gc-sections (arguably this one just reduces the size of the binary through dead code elimination)

Other:

PGO should probably be mentioned in the flags and targets section as “we’ll describe this in situational optimizations“ (not sure why it’s written there but whatever).

AutoFDO isn’t discussed which is important since it makes running FDO actually feasible in production.

Cold annotations and hot/cold code splitting (hot/cold code splitting isn’t even discussed).

sereja5• 2 years ago

The Russian version is more about algorithm design 101 and 102 (similar to cp-algorithms.com). I used to do competitive programming, and I co-founded an educational nonprofit where I also taught it for a few years. I organized my lecture notes and put it on a website, which is now used as a textbook by most CS students in Russian-speaking countries.

I do intend to translate it someday, but it has nothing to do with performance engineering :)

begueradj• 2 years ago

Amazing book !

torginus• 2 years ago

After noticing the Quake 3 Rsqrt algorithm in here, I cannot help but question the quality of this whole site. As in - is it grounded in any actual practical reality of writing code for modern hardware?

For reference, Quake style Rsqrt hasn't been practical on x86 for more than a decade, as Intel processors internally separate integer and float SSE registers, and converting between the two is costly.

Instead, they have a built-in intrinsic of _mm_rsqrt_ps which does a limited precision rsqrt in hardware.

vectri• 2 years ago

The rsqrt page mentions hardware implementations

https://en.algorithmica.org/hpc/arithmetic/rsqrt/

In fact, it is so good that it has been implemented in hardware, so the algorithm is no longer relevant by itself for software engineers, but we are nonetheless going to walk through it for its intrinsic beauty and great educational value.

Algorithms for Modern Hardware

Related Stories