Make std::vector 5x Faster with LibRapid

Pencilcaseman — Sat, 11 Feb 2023 21:50:54 +0000

(We're currently looking for a cloud instance sponsorship. If you'd like to support LibRapid in this way, please contact us!)

LibRapid GitHub Repository

LibRapid provides a cohesive ecosystem of classes, functions and tools to accelerate developement and improve the performance of your code.

For example, take the STL code below. It's very clunky and verbose, and isn't very nice to read or work with. How could this be simplified by using LibRapid?

We could use LibRapid's Array class!

As you can see, the code is much clearer and more concise, and even formats the output nicely. Additionally, it's FAST.

Running the same code (approximately 15,000 times) with much larger matrices (1000 x 1000) gives the following times:

STL      : 1.589ms
LibRapid : 284.405µs
Speedup  : 558.71%

- MSVC 19.33
- Default settings
- LibRapid Optimise Small Arrays: OFF
- Ryzen 9 3950x
- Windows 10 Pro

Swapping from std::vector to LibRapid for Array-based calculations has resulted in shorter, simpler code, a cleaner output and a speedup of over 500% over the standard library implementation!

Code

Here is the code for the benchmarks. Feel free to copy-paste it and play around with it :)

Check out the LibRapid GitHub Page for instructions on setting up LibRapid

#include <librapid>
namespace lrc = librapid;

int main() {
    {
        // LibRapid Benchmark
        int64_t elements = 1000;
        lrc::Array<double> aa(lrc::Shape({elements, elements}));
        lrc::Array<double> bb(lrc::Shape({elements, elements}));
        lrc::Array<double> cc(lrc::Shape({elements, elements}));
        lrc::Array<double> res(lrc::Shape({elements, elements}));

        double benchTime = 5;
        int64_t iters    = 0;

        double start = lrc::now();
        while (lrc::now() - start < benchTime) {
            res = aa * bb - cc;
            ++iters;
        }
        double end = lrc::now();
        fmt::print("Elapsed: {} over {} iterations\n", lrc::formatTime(end - start), iters);
        fmt::print("Average: {}\n", lrc::formatTime((end - start) / (double)iters));
    }

    {
        // STL Benchmark

        int64_t elements = 1000;
        std::vector<std::vector<double>> aa(elements, std::vector<double>(elements, 3));
        std::vector<std::vector<double>> bb(elements, std::vector<double>(elements, 3));
        std::vector<std::vector<double>> cc(elements, std::vector<double>(elements, 3));
        std::vector<std::vector<double>> res(elements, std::vector<double>(elements, 3));

        double benchTime = 5;
        int64_t iters    = 0;

        double start = lrc::now();
        while (lrc::now() - start < benchTime) {
            for (int64_t i = 0; i < elements; ++i) {
                for (int64_t j = 0; j < elements; ++j) {
                    res[i][j] = aa[i][j] * bb[i][j] - cc[i][j];
                }
            }
            ++iters;
        }
        double end = lrc::now();

        fmt::print("Elapsed: {}\n", lrc::formatTime(end - start));
        fmt::print("Average: {}\n", lrc::formatTime((end - start) / (double)iters));
    }

    return 0;
}

Optimising Code - The Devil Lies In the Details

Maximilian — Thu, 02 Dec 2021 20:45:18 +0000

Optimising code for high performance can be exhausting; where can you squeeze that last bit of speed out of your code? How can you be faster than that one piece of code you found online?

For that, let's take a look at the following example of our Rust crate:

pub fn new(values: &Vec<f64>) -> MathVector {
    let mut len: f64 = 0;
    for i in values {
        len += i * i;
    }
    MathVector { values:    values.clone(),
                 dimension: values.len(),
                 length:    len.sqrt() }
}

Among other things - like the for loop for example - one thing is the problem. Can you spot it? The answer is: len.sqrt(). Getting the square root of a number is performance-wise extremely expensive - how should we get rid of it? You might guess, that we could implement something like the infamous "Fast inverse square root" algorithm from Quake III. This has one problem though: It's inaccurate. And for something like mathematical applications, this is sometimes very unwanted. So we need to solve this in another way.
I got it: Why don't we calculate it only when the value is actually needed? Let's do it!
But firstly, we need to find a value for this field which cannot be occupied by pure chance. 0 is no candidate, as a vector may have the length 0. But what about a negative length? That sounds good. You are not able to have a negative length of a vector because of the nature of mathematics; the length of a vector is calculated by the sum of the squares of all values, and then taking the square root. As the value of a square root is - by definition - never negative, we can say with confidence that a negative number is ideal. Let's take -1. In case of Rust though, we don't need to worry about that; we can just use a option<T> to represent the absence of a value.
Now we need to generate a new getter for the field length, which only calculates it when actually needed. The code looks like this:

pub fn length(self: &mut Self) -> f64 {
    match self.length {
        None      => { let mut len: f64 = 0f64; 
                       for i in &self.values {
                           len += i * i;
                       }
                       len = len.sqrt();
                       self.length = Some(len);
                       return len;
                     }
        Some(len) => { return len; }

        }
}

As you can clearly see, we check if the length is already set using the logic from our thought; if so, we can just return that. If it is None (or -1 in other implementations), we just calculate the length, store it and return the newly calculated length.
And that's it! With just a few more lines of code, we removed unneccessary computations by calculating something only when it is needed. Feel inspired to apply that whereever you can!

DEV Community: LibRapid

Make std::vector 5x Faster with LibRapid

(We're currently looking for a cloud instance sponsorship. If you'd like to support LibRapid in this way, please contact us!)

LibRapid GitHub Repository

Code

Optimising Code - The Devil Lies In the Details