Performance Challenge! Fastest Square Root & Power?
Tags: performance, programming, rootpowerperf, rpp
Published: 2024-03-01 09:31:31

## Intro
After looking through [1brc](https://github.com/gunnarmorling/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](https://github.com/Chig-Beef/RootPowerPerf), 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](https://dev.to/chigbeef_77/compiling-python-to-go-pogo-pt1-3lah), 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.
```golang
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")
```
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.
```golang
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
```
We want our data in the correct format, so we want to convert everything into integers, we can't square root strings.
```golang
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
```
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.
```golang
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.
```
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.
```golang
// 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++
```
Now we can calculate that sum to the power of three halves, and update our `totalVal` and `count`.
```golang
// Find new min and max
if val < minVal {
	minVal = val
}
if val > maxVal {
	maxVal = val
}
```
Lastly, we find out if we have to update `minVal` and `maxVal`.
And then we print the result!
```golang
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),
)
```
Done! And that gives us our 58 second time. You can already probably see heaps of improvements you could make, so implement them!