See [4] for the methodology, source material and logs.  Out of curiosity
I've disassembled the compiled functions in fibn.el for comp-speed 2;
I'm not fluent enough in assembly to spot anything obviously wrong[5].


Let me know if there are things you would like me to try out in order to
investigate this.  


[1] Commit 92cf4bb8cc3da81f4877a734b9e9089ac4b89e85.

[2] Samsung NC10, 2GB RAM, 2GB HDD swap, on Debian Buster.

[3] Commit 9d8fc3a598090da518fcdd5c0503ed0f7faa41a9.

[4] .eln files compiled with:

    (dotimes (i 4) (rename-file (let ((comp-speed i)) (native-compile "fibn.el"))
                                (format "fibn-%d.eln" i)))

    Script used to collect measurements on branch native-comp: