# How could I improve this simple fibonacci function?

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

Improve how? Is it too fast, too slow?

2 Likes

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

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

Cheers, that alone made a significant improvement.

2 Likes

@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

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

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

2 Likes

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