sslotin's blog

By sslotin, 2 years ago, In English

I've been working on computational number theory for my book and recently wrote a few new articles on:

This is largely inspired by Jakube's tutorials and Nyaan' library implementations. Thank you!

If someone is interested, I may or may not try to optimize the sieve of Eratosthenes next: I believe it is possible to find all primes among the first $$$10^9$$$ numbers in well under a second.

Full text and comments »

  • Vote: I like it
  • +68
  • Vote: I do not like it

By sslotin, 3 years ago, In English

Tutorial: https://en.algorithmica.org/hpc/algorithms/matmul/

A version you can submit on CodeForces (it is optimized for a specific CPU that is very different from that of CF, so the speedup is smaller): https://github.com/sslotin/amh-code/blob/main/matmul/self-contained.cc

These blocking/vectorization techniques can also be applied to some dynamic programming algorithms, such as the Floyd-Warshall ("for-for-for") algorithm. Do you know any similar DP problems where the number of operations is larger than the number of states?

Full text and comments »

  • Vote: I like it
  • +223
  • Vote: I do not like it

By sslotin, history, 3 years ago, In English
  • Vote: I like it
  • +159
  • Vote: I do not like it

By sslotin, 3 years ago, In English

https://en.algorithmica.org/hpc/data-structures/segment-trees/

I wrote a SIMD-friendly segment tree ("wide segment tree") that is up to 10x faster than the Fenwick tree and the bottom-up segment tree:

The article also explains in detail how all the other popular segment tree implementations work and how to optimize them (fun fact: the Fenwick tree can be made 3x faster on large arrays if you insert "holes" in the array layout and make it ~0.1% larger). The article is long but hopefully accessible to beginners.

I only focused on the prefix sum case (partially to make the comparison with the Fenwick tree fair). While I have some ideas on generalizing it to more complex operations, and I will probably add I've added a separate section on implementing other operations, I highly encourage the community to try to efficiently implement mass assignment, RMQ, lazy propagation, persistency, and other common segment tree operations using wide segment trees.

Full text and comments »

  • Vote: I like it
  • +260
  • Vote: I do not like it

By sslotin, history, 3 years ago, translation, In English

https://en.algorithmica.org/hpc/data-structures/s-tree/

I announced this article a while ago but finally got to finish it just now.

Planned follow-ups: a 10-20x faster segment tree, std::priority_queue, and std::set.

Full text and comments »

  • Vote: I like it
  • +217
  • Vote: I do not like it

By sslotin, 3 years ago, In English

I've got an interesting math problem.

Here is a binary search variant that picks the element to compare against at random instead of always picking the middle one:

int lower_bound(int x) {
    int l = 0, r = n; // [l, r]
    while (l < r) {
        int m = l + rand() % (r - l); // <- note that r is never picked because there's no point
        if (a[m] >= x)
            r = m;
        else
            l = m + 1;
    }
    return l;
}

Assuming that the keys and queries are also drawn independently at random, as $$$n \to \infty$$$, how many times more comparisons does the random binary search perform compared to the normal one?

Edit: the binary search used to return a value instead of index. This is not correct if the the lower bound doesn't exist.

Full text and comments »

  • Vote: I like it
  • +148
  • Vote: I do not like it

By sslotin, 3 years ago, In English

Hi everyone! I'm writing a book on performance engineering, and a few days ago, I finished a draft of one of its main crown jewels: the SIMD programming chapter.

The main findings that are published:

  • You can compute array sums and other reductions such as the minimum 2x faster than std::accumulate or an auto-vectorized loop would.
  • You can sometimes copy and assign memory 2x faster than memcpy and memset respectively.
  • You can search array elements 10x times faster than std::find or manually.
  • You can count a value in an array 1.5x faster than std::count or manually.
  • You can calculate population counts of large vectors ~2x faster than with the intrinsic.
  • You can filter arrays 6-7x faster, which translates to e. g. a 6-7x faster quicksort (to be published).
  • You can calculate the index of the minimum element ~10x faster than std::min_element or manually.
  • UPD: you can calculate the prefix sum of an array ~2.5x faster than std::partial_sum or manually.

All speedup numbers are architecture-specific and may be different (usually larger) on CodeForces servers.

Enjoy — and as always, I'm happy to hear any comments and suggestions.

Full text and comments »

  • Vote: I like it
  • +503
  • Vote: I do not like it

By sslotin, 3 years ago, translation, In English

UPD (2021-10-13): I've just discovered that I published this post for Russian audience only :(

Hi everyone!

I'm writing a book about performance engineering: the art of optimizing algorithms beyond just asymptotic complexity.

The book walks through the main CPU optimization techniques such as caching, SIMD and pipelining while exploring many large case studies where we speed up some classic algorithm or a data structure, closely matching or even improving on the state-of-the-art.

You will probably not learn a single asymptotically faster algorithm there, but it will help you not to get TL when you are supposed to get AC, and sometimes get AC when you are supposed to get TL.

Among the stuff that you are probably most interested in:

I've only recently finished the research stage and I'm now writing it all up. I've already completed ~120 pages, which is ~30% of what I intend to. I plan to finish a new article every 2-3 days and post any relevant updates here on CodeForces and on my revived twitter.

I'm not sure what I'm going to do with the book when I'm done, but it is definitely going to be available online for free.

Happy to hear any comments and suggestions.

cc: dmkz, MrDindows

Full text and comments »

  • Vote: I like it
  • +391
  • Vote: I do not like it

By sslotin, 5 years ago, In English

There is a couple of things about sparse tables that a lot of people I think are doing slightly wrong (including the popular reference implementation by e-maxx).

First, you don't need to precalculate and store logarithms in an array. In fact, whichever procedure compiler will pick to calculate the logarithm is probably going to be much faster than looking it up somewhere in random access memory. The optimal way would be to use __builtin_clz ("count leading zeroes") which uses a separate instruction available on most modern x86's. This way you need just 2 memory reads instead of 3, so on large arrays this should be ~1.5x faster.

Second, memory layout and the order you iterate it matters when you're building the sparse table. There is a total of $$$2 \times 2 = 4$$$ ways to do it, and only one of them results in beautiful linear passes that work 1.5-2x faster.

It's easier to implement too:

int a[maxn], mn[logn][maxn];

int rmq(int l, int r) { // [l; r)
    int t = __lg(r - l);
    return min(mn[t][l], mn[t][r - (1 << t)]);
}

// somewhere in main:
memcpy(mn[0], a, sizeof a);
for (int l = 0; l < logn - 1; l++)
    for (int i = 0; i + (2 << l) <= n; i++)
        mn[l+1][i] = min(mn[l][i], mn[l][i + (1 << l)]);

Implementation was updated (tnx jef and plainstop):

original query implementation

Also, it's interesting that the last loop is not getting auto-vectorized by the compiler (because std::min is probably something overly complex), and replacing it with simple (x < y ? x : y) gets total speed up to ~3x if you include avx2, but I personally wouldn't do this because it looks cumbersome:

int x = mn[l][i];
int y = mn[l][i + (1 << l)];
mn[l+1][i] = (x < y ? x : y);

(Testing performed on my laptop; didn't run it on CF or other online judges.)

Full text and comments »

  • Vote: I like it
  • +112
  • Vote: I do not like it

By sslotin, 5 years ago, In English

http://algorithmica.org/en/b-tree

Hi, it's me again. A couple of days ago I published a post about speeding up binary search by rearranging memory in a way that allows prefetching, which is basically a way of trading off memory bandwidth for latency.

As noted in the comments, it had a noisy neighbors issue when tested on online judges, as different solutions evaluating on the same machine could compete for the same memory bandwidth. The speedup was like 2x-3x (and very volatile) on Codeforces while on my laptop and my dedicated server it was 4-5x, depending on the array sizes.

And so I rewrited it using B-tree layout instead, and it worked, because it bluntly requires 4x less memory reads. It is still quite volatile on CF—compare this (6.6x) and this (5.1x)—but I've never seen it drop below 3x on adequate array sizing (yes, the title is a bit clickbaity; I think the average speedup is around 5x).

There are two implementations:

  1. One is straightforward and uses nothing fancy
  2. The other is compute-optimized with AVX2 instructions and is ~30% faster, but doesn't work with older hardware (notably ideone and Yandex.Contest servers)

For more details, check the article.

Also, it would be really cool if someone could figure out a way to make compiler produce an autovectorized version of the faster one, so that it could be more easily extendable. It's weird and annoying that the compiler can't produce these 3 lines of code.

Full text and comments »

  • Vote: I like it
  • +63
  • Vote: I do not like it

By sslotin, 5 years ago, translation, In English

https://algorithmica.org/en/eytzinger

This will probably be an hour-long read about the CPU memory model that explains 10 lines of code at the very end.

The following code is 4 to 5 times faster than calling std::lower_bound over a sorted array:

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

const int n = (1<<20);
const int block_size = 16;
alignas(64) int a[n], b[n+1];

int eytzinger(int i = 0, int k = 1) {
    if (k <= n) {
        i = eytzinger(i, 2 * k);
        b[k] = a[i++];
        i = eytzinger(i, 2 * k + 1);
    }
    return i;
}

int search(int x) {
    int k = 1;
    while (k <= n) {
        __builtin_prefetch(b + k * block_size);
        k = 2 * k + (b[k] < x);
    }
    k >>= __builtin_ffs(~k);
    return k;
}

tl;dr: it uses a segment tree-like cache-friendly array reordering that allows trading off memory bandwidth for latency via prefetching. Because of this, its running time could be volatile on some online judges due to "noisy neighbor" effects (see comments below).

This is technically not a drop-in replacement, since it requires some preprocessing, but I can't recall a lot of scenarios where you obtain a sorted array but can't spend linear time on preprocessing.

This method could also be used to speedup heaps, segment trees, and other static binary tree structures.

Full text and comments »

  • Vote: I like it
  • +214
  • Vote: I do not like it

By sslotin, history, 6 years ago, In English

This is my repo. There are many like it, but this one is mine. My repo is my best friend. It is my life. I must master it as I must master my life. Without me, my repo is useless. Without my repo, I am useless. I must maintain my repo true. I must commit faster than my collaborator who is trying to open issue. I must assign issue to him before he assigns issue to me. I will...

I will keep my repo clean and ready, even as I am clean and ready. We will become part of each other. We will...

Before Codeforces, I swear this creed. My repo and myself are the defenders of good solutions. We are the masters of our problemset. We are the saviors of my rating. So be it, until there is no WA, but AC. Amen.

Maintainer's Creed

Hi. I am sharing my algorithms repository to the community and calling you to test / enrich it. It is designed to be minimalistic and copy-pastable. I use it during live contests. Most of the code is not designed to be standalone — you need to copy and tweak it a bit.

Full text and comments »

  • Vote: I like it
  • +46
  • Vote: I do not like it

By sslotin, history, 7 years ago, In English

So, I scraped stats.ioinformatics.org for some data to estimate the correlation between CF rating and place you get at IOI. I guess many will find these plots interesting.

I only considered contestants who had  ≥ 5 rated contests during last 2 years before 1st of August of the relevant year. Years 2013-2017 had more than 120 such contestants, but IOI '12 had only 55 and earlier IOIs had even less, so I didn't go any further.

By "normalized # of inversions" I mean this: , i. e. actual number of inversions divided by maximum possible. This is some kind of measure of a contest being close to a standard CF round.

For more details, check out the code: https://gist.github.com/sslotin/ae9557f68bb7e7aea1d565e2229a81c9

Full text and comments »

  • Vote: I like it
  • +78
  • Vote: I do not like it

By sslotin, history, 7 years ago, In English

Most of ICPC veterans I know joined companies like Google, Facebook, Yandex or some younger tech startups (1, 2, 3) or stayed at university, getting their scientific degrees and training some high school / university students in the process. That's all quite boring. I recently found out about some unusual careers of former olympians. By "unusual" I mean something like this:

Nikolai Durov — won ICPCs of 2000 & 2001 and also performed really well at some IOIs and IMOs. He co-founded VK and Telegram. (I don't think I really needed to introduce him)

Jakub Pachocki — 2nd place at ICPC '12 and 1st at GCJ of the same year. Last month I saw him at The International presenting a Dota 2 bot by a really cool ML project

Leonid Volkov — 14th place (bronze) at ICPC '01. He went into politics and now he is the chief of staff of Alexei Navalny's campaign (he is quite a trending oppositioner in Russia)

Just for fun, what other examples do you know of?

Full text and comments »

  • Vote: I like it
  • +89
  • Vote: I do not like it