HN user
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 :)
When you add prefetching (that is, compare against the middle element and fetch both the middle of the left half and the middle of the right half ahead of time) you are essentially doing radix-4 search, just with fewer actual comparisons.
(You can prefetch k layers ahead for radix-2^k search, but searching in small arrays will become more expensive this way.)
I didn't benchmark it, but I guess on mid-to-large arrays it would actually work somewhat slower than prefetching because it is more instruction-heavy, and, more importantly, prefetches are "cancelable": if the memory bus is too busy with actual requests, they will be skipped, while in explicit radix-k search you would have to wait for all (k-1) elements even if the middle element happened to be already cached and you already know which elements you need next.
That said, it could probably work with small arrays where caching is not a concern and especially if you optimize for latency and not throughput. You can also try to do the comparisons with SIMD (Wojciech Mula tried something similar and got a small boost: http://0x80.pl/articles/simd-search.html).
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.
Author here.
For a perfect drop-in replacement of std::lower_bound, the best you can do without breaking anything is to make the search branchless and maybe add some prefetching [1]. Some compilers actually try to implement std::lower_bound this way, but these things can sometimes break from version to version because there are no semantics to reliably make compiler use predication instead of branching.
Your intuitions are very much correct: you can get rid of pointers in a B-tree and make it static and implicit and fast, especially if you use SIMD to search for the lower bound within a node [2], but it would technically not be a replacement to std::lower_bound as we need to build an additional structure (even though it's very hard to imagine a scenario where you obtain a sorted array but can’t afford to spend linear time on preprocessing). C++23 has since added std::flat_set, which seems to be an appropriate place to implement it (in the article I compared against std::lower_bound because neither I nor the vast majority of the readers knew what std::flat_set was).
You can also add pointers back to support insertion and deletion with a moderate penalty to performance [3], but this dynamic B-tree is also technically not a replacement to std::set because of the extra pointer invalidations when a node merges or splits (even though in most cases you don't need pointer stability). You can fix it by, e.g., storing separate pairs of pointers so that each iterator knows where its key is in the tree and vice versa. That would add some overhead (especially in terms of memory) but make it compliant with the standard and still quite a bit faster and lighter than std::set.
The three articles combined are like 50 pages long so for a tl;dr version you might be interested in a talk I did at CppCon [4]. You can also extend the trick for heaps, ropes, segment trees, and other tree-like structures. There is a lot of work to be done here.
[1] https://en.algorithmica.org/hpc/data-structures/binary-searc...
[2] https://en.algorithmica.org/hpc/data-structures/s-tree/
Actually, during the Medvedev presidency, there were serious efforts to negotiate visa-free travel and reduced tariffs (which is the essence of what everybody wants, not full integration). If these things were granted, the revolution / civil war in Ukraine, primarily motivated by one part of the country mostly trading with Russia and the other with the EU, probably wouldn't have happened.
The EU is primarily a trade bloc, and it is in natural competition with the Eurasian Economic Union: countries can have tariff-free trade with either one bloc or the other, but not both at the same time. The current scramble over Ukraine is primarily motivated by the EU and the EAEU economically benefiting from the country being in their respective trade zone.
Also available on YouTube: https://www.youtube.com/watch?v=1RIPMQQRBWk
This is a tricky part. The middle element is still part of the search range if we go "left" (≥). After we compare against it, the search range length becomes either floor(n/2) or ceil(n/2), in the latter case including the middle element (we will never compare against it again, but it still needs to be the first element of the search range).
To avoid additional checks and branching, we can just always make the next search range length ceil(n/2), effectively adding that middle element to the search range in case we go "right" (<).
Author here. There is a newer and significantly expanded version of the article: https://en.algorithmica.org/hpc/data-structures/binary-searc...
You don't need to hack Yandex. The entire monorepostory is synced on every intern's laptop, and you can do whatever your want with the files. I always wondered how it hasn't been leaked before to be honest.
The mobilization only includes people who formerly served in the military (at least 1-2 years of training). A certain percentage of them are "reservists" who work normal jobs but are summoned for a month-long military training every year to be ready in the case of war, and so they will probably be prioritized (at least according to Putin & Shoigu).
This is not cannon fodder. Russia is running out of willing soldiers, not soldiers in general.
Interestingly, the disdain for democracy in both Russia and China is strongly motivated by "we've already tried giving people freedom and it didn't work".
https://en.wikipedia.org/wiki/Warlord_Era
https://en.wikipedia.org/wiki/1993_Russian_constitutional_cr...
The world had already A/B tested "damage the economy so that it would never be a threat again" and "help transition to democracy" with Germany. The latter worked better.
IMO the main reason these companies don't release their models is not ethical concerns but money:
- NVIDIA sells GPUs and interconnect needed for training large models. Releasing a pretrained LM would hurt sales, while only publishing a teaser paper boosts them.
- Google, Microsoft, and Amazon offer ML-as-a-service and TPU/GPU hardware as a part of their cloud computing platforms. Russian and Chinese companies also have their clouds, but they have low global market share and aren't cost-efficient, so nobody would use them to train large LMs anyway.
- OpenAI are selling their models as an API with a huge markup over inference costs; they are also largely sponsored by the aforementioned companies, further aligning their interests with them.
Companies that release large models are simply those who have nothing to lose by doing so. Unfortunately, you need a lot of idle hardware to train them, and companies that have it tend to also launch a public cloud with it, so there is a perpetual conflict of interests here.
There is "Programmers village" ("Поселок программистов") in Kirov Oblast in deep Russia.
It is not exactly a rural community: it's just 20 or so families of remote tech workers (mostly freelancers) living a few kilometers from a small old town with dirt cheap land and local labor (like "buy a two-story house with one month's SF salary" kind of cheap). It was founded before the pandemic by a guy who used to work as an SWE at Yandex and grew tired of living in Moscow.
I wonder if something like this exists elsewhere.
Flushing the cache is easy: just read 4MB (or whatever your L3 cache size is) of some dummy data and pretty much everything you had cached before would be kicked out.
At the same time, resetting the branch predictor AFAIK can only be done by powering the CPU off and on again.
I briefly talk about noise reduction in the "Getting Accurate Results" section: https://en.algorithmica.org/hpc/profiling/noise/
I don't follow my own advice in much of the rest of the book, though (because I mostly focus on at least double-digit performance improvements).
The e-book/printed editions will most likely be sold on a “pay what you want” basis, and in either case, the web version will always be available online in full.
I will get out of Russia in a few months and then figure out the best way to deliver a hard copy.
I've already implemented a 32-byte version. But, as mentioned in the article, it's not faster (in terms of throughput) because it needs to fetch two cache lines.
That's because it is in bytes, representing cache sizes. But I agree, a clarification is needed
Probably not a lot, but the idea of using 2k and 2k + 1 as indices for children is used in a lot of basic data structures taught in CS courses, e. g. for binary heaps.
Hmm... using blend is actually a good suggestion. You can pre-shuffle elements [1 3 5 7] [2 4 6 8], do a comparison against the search key, and then blend the low 16 bits of the first register with the high 16 bits of the second. Will add that to the article, thanks!
By the time I realized it needs correcting, I was already like 15 graphs in and really didn't want to remake them.
It's called superscalar processing. CPUs can execute more than one instruction concurrently on each pipeline stage if there is no dependency between them. In the prefix sum, we can fetch and add the next element simultaneously with the accumulator of the previous iteration is being written back.
A single CPU core usually can't saturate the memory bandwidth (because it would require more pending memory operations than the scheduler can handle). If you use all cores, it will approach the theoretical limit.
It is not technically legal to use SIMD on most floating-point loops, including the inner product in matrix multiplication, because rounding errors are not commutative. C compilers don't vectorize such loops either unless you pass the -ffast-math flag. I'm sure the JIT compiler of JVM has a similar option.
(read the article I linked below, it's all explained there)
Author here. I wrote a separate section trying to answer this question: https://en.algorithmica.org/hpc/complexity/languages/
tl;dr: to some extent, but mostly no
Leonid Volkov, a Russian oppositionist and the chief of staff of Alexei Navalny's 2018 campaign. The Russian government wants to arrest him for being a key member of the Anti-Corruption Foundation, which it brands as "extremist" (he fled to Lithuania, along with others).
He got an ICPC bronze medal in 2001, and before getting into politics, he was at an IT company for about 10 years, working his way up from a software engineer to the CEO. The company now has 9k employees and $200M revenue.
https://en.wikipedia.org/wiki/Leonid_Volkov_(politician) https://en.wikipedia.org/wiki/Anti-Corruption_Foundation