13
\$\begingroup\$

Fastest code is a scoring method on this site where the goal is to write code that is as fast as possible.

From the tag wiki:

The winner of a fastest-code challenge is determined by the runtime performance of the submissions. For fairness, all submissions should be benchmarked on the same machine, which usually means all submissions have to be tested by the host of the challenge. Alternatively, the submission can be compared to a reference program. For scoring by asymptotic time complexity, use instead.

What general tips do you have for making solutions more competitive at ? One tip per answer, please. Tips should ideally be broadly applicable, not language-specific.

\$\endgroup\$
8
  • \$\begingroup\$ Idk if this would qualify as an answer, but "use a language that is statically typed and compiled." Those generally are fast (I can't think of counterexamples rn) \$\endgroup\$
    – Seggan
    Jan 2, 2023 at 23:12
  • \$\begingroup\$ The Rust Performance Book contains many Rust-specific tips. \$\endgroup\$
    – alephalpha
    Jan 3, 2023 at 3:47
  • 2
    \$\begingroup\$ @Simd Ideally tips would be language agnostic. So the tip might be "For interpreted language try offloading as much of the work as possible to a compiled external library" maybe \$\endgroup\$
    – mousetail
    Jan 3, 2023 at 10:48
  • 1
    \$\begingroup\$ PyPy is a JIT-compiling run-time for Python in general, as opposed to the slow CPython interpreter that's normally used. Cython is Python-to-C, turning your Python program into input for an ahead-of-time compiler (and a runtime library; Python is more dynamic than C so I assume it still needs to do Python stuff.) So yeah, "use a fast run-time if the standard one isn't fast." Phrased generically but squarely aimed at Python as it seems somewhat unique in mainstream languages in that the standard implementation is a lot slower than others that exist; I guess they have limitations? (@Simd) \$\endgroup\$ Jan 3, 2023 at 14:18
  • 1
    \$\begingroup\$ @PeterCordes yea the tech @ simd mentioned is all very different from eachtother, it includes alternate runtimes, transpilers, and some are just libraries that are fast simply because they are written in C. Since comments have to be short I only tried to generalize one of those categories, but others could be applicable to other languages too. \$\endgroup\$
    – mousetail
    Jan 3, 2023 at 14:23

4 Answers 4

10
\$\begingroup\$

Use a fast hashing algorithm for your hashmap

Your language's default hashing algorithm is not always the fastest.

I'll focus on Rust, because it's the only fast language I'm familiar with. But the same applies to other languages.

Rust

Rust's default hashing algorithm is SipHash 1-3, which is high-quality, but relatively slow. Since HashDos attacks are not a concern for challenges, you can try the hashing algorithms from the following crates:

  • FxHash from rustc-hash. This is the hashing algorithm used by the Rust compiler. It is low-quality (so be careful when using it in real-world applications) but extremely fast. It is usually the fastest for small types with a fixed size, like u32 and u64.
  • AHash from ahash. This hashing algorithm uses the hardware's AES instruction set when available. It is both high-quality and fast. It is usually faster than FxHash for more complex types like String and Vec.

You should try both and see which one is faster for your use case.

Both crates provide drop-in replacements for std::collections::HashMap and std::collections::HashSet: FxHashMap and FxHashSet from rustc-hash, and AHashMap and AHashSet from ahash. Please read the documentation for each crate to see how to use them.

The documentation for ahash also contains a comparison between common hashing algorithms.

Other languages

wyhash and xxHash are two fast hashing algorithms I've heard of. They are written in C but ported to many other languages. Please see wyhash's README and this list for xxHash.

There might be other fast hashing algorithms that I'm not aware of.

\$\endgroup\$
9
\$\begingroup\$

Avoid Allocations

Allocating memory is slow. Often you can substantially improve performance by pre-allocating memory. Note that allocation is not just manually calling malloc or new, but many data structures internally allocate memory.

Consider for example this code:

fn main() {
    for i in 0..1000000 {
        let mut a:Vec<u32> = vec![];
        let mut b = 3;
        for i in 0..1000 {
            b+=b/2;
            a.push(b);
        }
        println!("{}",a[999]);
    }
}

This uses a Vec which will dynamically allocate memory. Multiple times each time the vector grows. On my machine this takes 2854 ms.

You can make this more efficient with static allocations:

fn main() {
    for i in 0..1000000 {
        let mut a = [0u32;1000];
        let mut b = 3;
        for i in 0..1000 {
            b+=b/2;
            a[i]=b;
        }
        println!("{}",a[999]);
    }
}

This uses a static array of 1000 elements. No allocations needed. This takes 2789ms on my machine. A small difference but a significant one. Difference can be a lot bigger with less optimized data structures.

\$\endgroup\$
1
  • 9
    \$\begingroup\$ Simply allocating all-in-one using Vec::with_capacity will save some time, while requiring no other changes to the code. \$\endgroup\$
    – corvus_192
    Jan 2, 2023 at 17:12
5
\$\begingroup\$

Here are a couple of tricks I've found that can help:

Bit Shifting

Instead of dividing (slow) you can sometimes replace the operation with a bit shift

1024 >> 1     // 512

This has the same effect as Math.floor( x / 2.0 )

Loop Unrolling

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. Wikipedia

for (int i=0; i<=5; i++) {
   printf("%d", i);
}

becomes:

printf("%d", 0);
printf("%d", 1);
printf("%d", 2);
printf("%d", 3);
printf("%d", 4);
printf("%d", 5);

Avoid Division

Similar to the approach with bit shifting avoid costly division by using mathmatics:

x / 3.0 == 5.5

multiply both sides by a factor of 3.0 to remove the division

x == 15.5

or alternatively instead of using sqrt() use pow() if applicable

Math.sqrt(x) == 5

x == 25

Branch Prediction

In computer architecture, a branch predictor[1][2][3][4][5] is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high performance in many modern pipelined microprocessor architectures such as x86. Wikipedia

This one will be highly dependent on the machine you are running your code, as well as if it has been compiled / optimized already, but generally the more homogenous the data or operations are, the faster:

function checkIfValueLessThanHalf(value) {
  if (value < 0.5) {
      return true
  } else {
      return false
  }
}

function checkIfValueLessThanHalfOptimized(value) {
    return value < 0.5
}

// random array filled with unsorted numbers
const unsorted = Array(10 ** 6).fill().map((_) => Math.random())

// same array but sorted
const sorted = [...unsorted].sort()

// run method on unsorted data
console.time()
unsorted.filter(checkIfValueLessThanHalf)
console.timeEnd()

// run method on sorted data
console.time()
sorted.filter(checkIfValueLessThanHalfOptimized)
console.timeEnd()

The above example isn't necessarily faster (because you need to include the .sort() operation, but depending on the data set size and cost of sorting this can change.

Note: running the code snippet above sequentially may produce different output as the V8 engine is doing optimizations under the hood as well, below are the two different code snippets which can be run in different contexts:

Try it online! (unsorted & if/else)

Try it online! (sorted & logical return)

Which return roughly 59.859ms and 35.960ms respectively for me over several runs.

Notable Mention

This is one of my favorite examples which was used in Quake which incorporates some ingenious tricks to derive approximations which worked for their use case:

Fast inverse square root method

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Your microbenchmark is broken. The .sort() is sorting the array in-place, so you are running the code on the same (sorted) array. And if you swap the order, the first one is always slower. \$\endgroup\$ Jan 4, 2023 at 1:21
  • 2
    \$\begingroup\$ Also, your "Fast inverse square root" link has nothing to do with "bit shifting" – it's just an example for another optimization one could do (and which might work in specific circumstances). \$\endgroup\$ Jan 4, 2023 at 1:26
  • \$\begingroup\$ @PaŭloEbermann thanks nice catch, just updated the answer! \$\endgroup\$
    – Asleepace
    Jan 4, 2023 at 19:41
1
\$\begingroup\$

Asynchronous execution

Note: some languages have this behaviour built in, like JavaScript.

Asynchronous programming is useful when you have two expensive operations, since they can be done at the same time. To give a primitive analogy of this:

You have two tasks:

  • Wash clothes in the washing machine.
  • Wash the dishes.

Without asynchronous programming, you would have something like this:

wash_clothes()
wash_dishes()

In this example, you would put the clothes in the washing machine, wait for the washing machine to be done, and only then wash the dishes! That's very inefficient, isn't it?


However, with asynchronous programming, you would have something like this:

await wash_clothes()
wash_dishes()

In this example, you would put the clothes in the washing machine, and you would wash the dishes while the washing machine is washing the clothes. Much more efficient!

As you can see, it can speed up code execution time.


A real world example is scraping from two websites and printing the HTML content of both. Without asynchronous programming, you would have to wait for one request to be finished before doing the other, but with asynchronous programming, you can send a request to the second website before the first website's request is finished!


Edit

Mousetail left a few comments saying that this only works well for IO-focused challenges and that multithreading is often quicker.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Only really works for IO focused challenges \$\endgroup\$
    – mousetail
    Jul 13, 2023 at 11:07
  • \$\begingroup\$ @mousetail but still a tip! \$\endgroup\$ Jul 13, 2023 at 11:09
  • \$\begingroup\$ Yea I voted it up but in general async will (almost) always be slower than multi-threading \$\endgroup\$
    – mousetail
    Jul 13, 2023 at 11:10
  • 2
    \$\begingroup\$ Actually, it’s the opposite; when you await the asynchronous operation, that function’s execution is completely halted until the operation completes. When you don’t await it, both can run at the same time. \$\endgroup\$
    – noodle man
    Jul 13, 2023 at 13:44
  • \$\begingroup\$ @noodleman I don't think so: ... These may be "outside" events such as the arrival of signals, or actions instigated by a program that take place concurrently with program execution, without the program blocking to wait for results. \$\endgroup\$ Jul 13, 2023 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.