How could I improve this simple fibonacci function?

Getting Help
1

I wrote this simple function that iterates 1000 times and for each iteration, it calculates the Fibonacci Sequence 1,250 times and appends each number to a slice. My goal was to create a function that simulated doing some CPU work. Thank you!

func fibonacci() []int {
	var result []int
	var start = 1000
	for {
		var num = 1250
		var n1, n2, temp int = 0, 1, 0

		for {
			temp = n2
			n2 = n1 + n2
			n1 = temp

			result = append(result, n2)
			if num <= 1 {
				break
			}
			num--
		}
		if start <= 1 {
			break
		}
		start--
	}
	return result
}
2 Likes
2

Improve how? Is it too fast, too slow?

2 Likes
3

I’m learning Go and I’m wondering if it can be made faster? Is there a better way to write it where it would perform better?

2 Likes
4

Since you already know that you want 1250 elements, you could pre-allocate the slice.

result := make([]int, 0, 1250)

Or even

result := make([]int, 1250)

…
for {
  …
  result[1250 - num] = n2
  …
}

edit

I just realise, that you are repeating the appending 1000 times with the same numbers… So you need to adjust capacity/size and calculation of index accordingly.

2 Likes
5

Cheers, that alone made a significant improvement.

2 Likes
6

@NobbZ Prior to that optimization, my test was 340 req/sec and now its 1,245 req/sec. I’m curious why that made such an improvement?

2 Likes
7

Memory allocations are expensive, copying large chunks of memory even more.

And since slices are basically fat pointers with attached “size” and “capacity”, they work like this:

You start with a zero sized slice. When you append the first time, it gets allocated to a capacity of 10 (IIRC, actual value might be different, but not that much) and a size of one, the element gets inserted.
Size gets increased until insertion would exceed the capacity, then a new chunk of memory gets allocated with capacity doubled (20) and old content copied, new element added to the end.
Then 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, 20480, 40960, 81920, 163840, 327680, 655360, 1310720.

So you have to resize 18 times, copying around an overal of data of 1310710 elements. As an int has a size of 4 byte thats 5242840 Byte or ~5.1 MiB.

By preallocating all this copying can be omitted.

4 Likes
8

@NobbZ Thank you for the detailed explanation, it make perfect sense. Lots to learn about Go :slight_smile:

2 Likes
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.