tweety's blog

By tweety, history, 4 years ago, In English

Hello fellow people of Codeforces

I hope everyone doing well in these uncertain and unprecedented times. I wanted to share this cool C++20 trick that I learned recently.

Check out this cool implementation of is_prime(n) to test if n integer is prime in O(1) runtime (without any runtime precomputation!)

bool is_prime(int n);

This code computes primes up to MAXN during compilation and stores them in a table right in the compiled binary. On a runtime is_prime(n) call, it queries the compiled table to find the result. Check this compiled assembly to find the sieve mask baked in the binary: https://godbolt.org/z/G6o84x.

This trick is achieved by passing the constructed Sieve as a template argument, which is always evaluated on compile-time. If you compile this code using older C++ standard, you will get the error:

error: a non-type template parameter cannot have type 'Sieve<MAXN>'

However, since C++20, non-type template parameter can have any LiteralType (note). In short, it is possible to compile-time compute an instance of any class with a constexpr constructor.

Here is a time test of compile-time vs run-time sieve computation:

main.cpp

Compiled with GCC 9.3.0 using the command g++ -std=c++2a main.cpp. This is the execution output on my laptop:

Runtime ans: 90. Elapsed (ms): 1008
Compiletime ans: 90. Elapsed (ms): 0

Of course no one re-computes sieve 1000 times, this is done here for the sole purpose of showing that the algorithm is not computing sieve in run time 1000 times.

While such tricks won't help you cheat pass Codeforces problems, they might will help your submission stand out for fastest runtimes. Hope you found this interesting!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice :) I wonder if you can do this in earlier versions of C++ by having just the is_prime array be compile-time computed (instead of the Sieve instance)

It might be worth it to try space-saving tricks like bit-packing and wheel sieve to increase max_N, the runtime penalty should be small, bit-packing should increase max_n by 8x, the simplest wheel sieve (omit all even numbers) should increase it further by 2x.

»
4 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

I think this can be done with C++14. Also you don't need a Wrapper class:

bool fast_is_prime(int n) {
    static constexpr Sieve<MAXN> s;
    return s.is_prime[n];
}

Runtime ans: 100. Elapsed (ms): 583
Compiletime ans: 100. Elapsed (ms): 0

See C++14 on ideone

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    That's cool! I thought declaring something as constexpr only hints the compiler to compute it during compilation and I had to pass a constexpr constructor as a template argument to force it to be computed compile-time. But seems like declaring static constexpr works too

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      constexpr on a function declaration is a hint that (under certain conditions) it may be evaluated at compile time and the result be stored in the read-only part of the binary. However, if you declare a "variable" constexpr the compiler is forced to compute the right-hand side of the assignment. You cannot change the value afterwards (constexpr implies const). If you want an actual variable you may use constinit from C++20. If you always want compile time evaluation of a function, you can declare it consteval with the latest standard. I'd say, these new keywords may be rarely of any use in competitive programming.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have more tricks up your sleeve? If so please make a series or something like that. I found this really helpful.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing, provide a new idea to cost compile-time instead of exec-time ! It may useful for particluar questions since CP only care about exec-time.

But: ‘constexpr’ loop iteration count has limit of 262144 (use ‘-fconstexpr-loop-limit=’ to increase the limit), and we can't use -fconstexpr-loop-limit= parameter in CP, sadly this ideal may can't put prime sieve in practice even ...._.._ provide C++14(So C++17 works) version of your idea.

»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Unless I’m misreading something, this post is about moving the computation into the compilation, not about how to actually write a prime sieve (which is what the paper is about).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
code

in this code i added another simple sieve struct, and compared both

a@a:~/Desktop/Cp$ ./a.out <- sample count 1e6
Runtime ans: 86783. Elapsed (ms): 29
Compiletime ans: 86783. Elapsed (ms): 13
a@a:~/Desktop/Cp$ g++ test.cpp <- sample count 1e7
a@a:~/Desktop/Cp$ ./a.out
Runtime ans: 877166. Elapsed (ms): 124
Compiletime ans: 877166. Elapsed (ms): 134

i don't think this is a satisfactory change ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Don't benchmark without optimizations turned on.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can see i am new to all this, i also don't have much backgroud in this. but i am trying to learn. please explain me breifly what you meant.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Compilers have different levels of optimizing code. If you add some flag like g++ -O2 or g++ -O3, then the compiler will try a lot harder to optimize the resulting machine code. Without flags the compiler will only do a very rough translation. That's easier to understand, if you want to debug the program, but the resulting program is not (very) fast.

        Compiler people have spend (and still do) a lot of time thinking about how the compiler can optimize your code (while still giving you the correct result). Notice this will not turn a $$$O(n^2)$$$ algorithm into completely different $$$O(n \log n)$$$ algorithm. It's more like a lot of micro optimizations in the machine code. The rough translation has a lot of overhead. The compiler will try to remove that overhead, for instance by carefully rearranging the registers to avoid unnecessary copies, it will try to evaluate more stuff at compile time, it will try to rearrange the code to make it more efficient to run, eliminate dead code, unroll loops, enables SIMD, ... This can result in speedups from 1.1x up to 10x. Notice some programs can be optimized more, and some less.

        Usually, when we run a final program, it is done in the optimized version. So does Codeforces and all other OJs. It doesn't make sense to benchmark the unoptimized versions of the program, when the thing that matters will be the optimized one instead.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you. I did get the basic idea what is going on here.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Try to swap sieve st and auto t1 = chrono::high_resolution_clock::now(). Make sure you know what you're really measuring.

    Also you have UB in your sieve struct.

»
4 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Hi! Can someone explain what is meant by "While such tricks won't help you cheat pass Codeforces problems". How come this trick wouldn't help with CF submissions? Will the time spent compiling be added onto runtime or something?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think that it's because MAXN can't be that big. If it's up to 300000, it usually don't make so much difference on execution time process the sieve on compilation or runtime.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can help you to pass some problems, provided that your compiler is good and your judge does not have a compile time limit. However, for the sieve problem, the difference is only significant when MaxN >= 1e8, which will often crash the compiler, or if it doesn't, result in an executable too large that linking will fail.

    For some other problems where MaxN = 1e4 and you found a O(n^2) solution with O(n) space complexity however, this trick may help you a lot.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

1. This trick works in C++14, and needs neither a wrapper class nor a wrapper function:

Code

You can check the assembly here. Starting from line 106, many mov statements are copying bytes to the addresses that should hold prime numbers. Apparently, the constexpr constructor has forced all instances of Sieve to be built in compile time, and the overloading of operator[] allows simple array syntax on the Sieve.

2. This trick may be useful for MaxN <= 1e5, but not higher.

Although compile-time evaluation may theoretically make it possible to compute the Sieve for up to MaxN = 1e9, constexpr evaluation does have a large cost during compile time and also on the binary size. Therefore, setting MaxN to 1e7 or greater may cause the compiler to either crash or report an error, even if -fconstexpr-loop-limit= is set to a large number, while runtime building of a sieve of 1e7 elements is always possible.