Performance Challenge! Fastest Square Root & Power?

chigbeef_77

Chig Beef

Posted on March 1, 2024

Performance Challenge! Fastest Square Root & Power?

Intro

After looking through 1brc, I thought, dang, that would be great, but for all languages. And so I created my own challenge, that allows you to race people using the same language, and also people using different languages.

How It Works

All the information is on the GiHub, but I'll talk through it here as well.
Basically, you will be given a text file, and your job is to sum each row. With that sum you have to put it to the power of 3 halves. This is to take advantage of both powers and square root (if you decide to use them). We do this for every row, and then we display the min, max, and mean values to either standard out or a file.

Baseline

Now, before you upload your solution, I would suggest timing your code, to see whether it beats the baseline. The implementation for the baseline is in Go, so slower language don't have to beat it, but should come close. My simplest case code runs in 51 seconds, so we're already sub-minute! One thing I didn't like about 1brc was that they never got sub-second (by my knowledge), but this challenge should have the ability to be completed in such time.
All timings are done on my laptop, to keep everything the same. Your code won't be run once, it will be tested multiple times at different times of day as well as with nothing else running (no chrome).

Competition End

Why should the competition end? You can keep making submissions as far into the future as you'd like! However, at some point I will only be taking top 10 submissions after the challenge has died out.

Generating The Test File

Just remember, this test file is probably going to be 5GB, so make sure you have some space. But the file is one million rows and a thousand columns, create a billion entries.

Any Language

You can use any compiler, transpiler, interpreter, etc. with any version to run your project, just make sure to specify (as instructed in the GitHub) where to put information on what you used. You could even use Pogo, but you might have to implement lists into my transpiler first.

Have Fun!

Take your time, this shouldn't be going away anytime soon, so really work on your project, or don't. You could set a short deadline to get the project finished if you really want to challenge yourself. And lastly, maybe try it in your second programming language? This would be a great way to learn it more deeply (:

TL;DR, My Baseline Implementation

Most of you are going to want to go start coding, and I'll let you go, but some of you might want to see how I implemented my baseline implementation, and I'll be glad to show you. This implementation does not care about performance or memory.
Here's how it goes.

f, err := os.ReadFile("data.txt")
if err != nil {
    log.Fatal("generate a data file using 'generate.py' before running this")
}
file := strings.Split(string(f), "\r")
Enter fullscreen mode Exit fullscreen mode

We need to get our data, and we create a string slice where each entry is a line. Note the use of "\r", you can actually set this when you generate your data.txt to (almost) any character.

data := [][]uint16{}
for i, l := range file {
    // Get numbers in string form (["2", "7", ...])
    line := strings.Split(l, ",")

    data = append(data, []uint16{})
    for _, n := range line {
        num, err := strconv.Atoi(n)
        if err != nil {
            fmt.Println(err)
            fmt.Println(n)
            log.Fatal("issue with converting a string to a number, maybe check 'data.txt'?")
        }
        data[i] = append(data[i], uint16(num))
    }
}
// Data should be nice and full right now
Enter fullscreen mode Exit fullscreen mode

We want our data in the correct format, so we want to convert everything into integers, we can't square root strings.

var minVal float64 = 1 << 32 // Some large number
var maxVal float64 = 0       // Some small number
var meanVal float64 = 0
var totalVal float64 = 0
var count float64 = 0
Enter fullscreen mode Exit fullscreen mode

Here we have some values that we're going to use for our next section. minVal, maxVal, and meanVal should all make sense, this is what we'll be outputting. But we also have totalVal and count. These are used to calculate meanVal at the end.

var rawSum uint32 = 0
for _, n := range l {
    rawSum += uint32(n)
}
sum := uint16(rawSum)
// Now we have the sum of the line, we can start doing our extra caluclations.
Enter fullscreen mode Exit fullscreen mode

The above and future code is done for every line. We get the sum as a uint32 first because all the numbers are in uint16 range, and would otherwise overflow if we used uint16 for sum, and we don't want that. So instead we just drop the bits by converting to uint16 afterwards.

// y = x^(3/2)
val := math.Pow(float64(sum), 3)
val = math.Sqrt(val)
val = math.Floor(val)

// This is for the mean
totalVal += val
count++
Enter fullscreen mode Exit fullscreen mode

Now we can calculate that sum to the power of three halves, and update our totalVal and count.

// Find new min and max
if val < minVal {
    minVal = val
}
if val > maxVal {
    maxVal = val
}
Enter fullscreen mode Exit fullscreen mode

Lastly, we find out if we have to update minVal and maxVal.
And then we print the result!

meanVal = math.Floor(totalVal / count)

fmt.Println(
    "MIN",
    strconv.FormatFloat(minVal, 'f', 0, 64),
    "MAX",
    strconv.FormatFloat(maxVal, 'f', 0, 64),
    "MEAN",
    strconv.FormatFloat(meanVal, 'f', 0, 64),
)
Enter fullscreen mode Exit fullscreen mode

Done! And that gives us our 58 second time. You can already probably see heaps of improvements you could make, so implement them!

💖 💪 🙅 🚩
chigbeef_77
Chig Beef

Posted on March 1, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related