Kiểm tra điểm chuẩn fibonaci đệ quy / không đệ quy

Thứ Sáu, 26/08/2022

Tram Ho

Test benchmark fibonaci recursive/non recursive

Động cơ, lý do

Trước giờ mình vẫn có thắc mắc là đối với cùng 1 bài toán giữa recursive và non recursive thì cái nào sẽ là cách giải quyết hiệu quả hơn.
Nhân dịp mình có review code của các member trong team, mọi người có trao đổi về recursive/ non recursive nên mình quyết định tìm hiểu sâu hơn xem suy nghĩ từ đầu của mình đã đúng chưa.

Mình có tìm hiểu các tài liệu thì hầu như mọi người đều có chung nhận xét như sau:

Ưu điểm của đệ quy (recursive): Gọn gàng dễ hiểu, dễ viết code

Nhược điểm: Tốn không gian bộ nhớ, và thời gian xử lý do phải switch context giữa các lần gọi hàm.

Trên đây đều là những nhận xét mang tính lý thuyết. Với góc nhìn của một người hiện tại đang là một kỹ sư từng là học sinh chuyên lý, mình chỉ tin khi có kết quả thí nghiệm là những con số cụ thể.

Và thật may go giúp mình làm điều này khá dễ dàng bằng công cụ test benchmarks

Không nói nhiều nữa, chúng ta cùng vào chủ đề chính.

Test benchmarks với fibonaci recursive

Đầu tiên chúng ta thực hiện cài đặt thuật toán với cách tiếp cận là đệ quy.

Cài đặt test benchmark với đầu vào N = 10

<span class="token keyword">package</span> bench

<span class="token keyword">import</span> <span class="token punctuation">(</span>
	<span class="token string">"testing"</span>
<span class="token punctuation">)</span>

<span class="token keyword">func</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> n
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>

<span class="token keyword">func</span> <span class="token function">BenchmarkFibRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token comment">// run the FibRecursive function b.N times</span>
	<span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token function">FibRecursive</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>

package bench

import (

"testing"

)

func FibRecursive(n int) int {

if n < 2 {

return n

}

return FibRecursive(n-1) + FibRecursive(n-2)

}

func BenchmarkFibRecursive10(b *testing.B) {

// run the FibRecursive function b.N times

for n := 0; n < b.N; n++ {

FibRecursive(10)

}

Thực hiện test benchmark bằng lệnh sau

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Kết quả

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibRecursive10-12       4973802               239.1 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/hblab-ngocnd/csv-demo/bench  1.751s

goos: darwin

goarch: amd64

pkg: github.com/hblab-ngocnd/csv-demo/bench

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

BenchmarkFibRecursive10-12 4973802 239.1 ns/op 0 B/op 0 allocs/op

PASS

ok github.com/hblab-ngocnd/csv-demo/bench 1.751s

Nhận xét:
Lặp 4973802 lần, mỗi lần mất 239.1 ns tổng 1189236058.2 ns

Máy mình tận i7 lận, giờ mới để ý

Phân tích sâu hơn 1 tý

Phân tích thời gian chạy

Chạy lệnh

go tool pprof profile.out

Type: cpu
Time: Aug 25, 2022 at 3:12pm (+07)
Duration: 1.64s, Total samples = 1.23s (75.02%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top

Type: cpu

Time: Aug 25, 2022 at 3:12pm (+07)

Duration: 1.64s, Total samples = 1.23s (75.02%)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Dùng lệnh top để lấy những xử lý mất thời gian nhất, sắp xếp theo thứ tự giảm dần

Kết quả

Showing nodes accounting for 1.23s, 100% of 1.23s total
      flat  flat%   sum%        cum   cum%
     1.21s 98.37% 98.37%      1.21s 98.37%  github.com/hblab-ngocnd/csv-demo/bench.FibRecursive
     0.01s  0.81% 99.19%      1.22s 99.19%  github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibRecursive10
     0.01s  0.81%   100%      0.01s  0.81%  runtime/pprof.(*profMap).lookup
         0     0%   100%      0.01s  0.81%  runtime/pprof.(*profileBuilder).addCPUData
         0     0%   100%      0.01s  0.81%  runtime/pprof.profileWriter
         0     0%   100%      1.22s 99.19%  testing.(*B).launch
         0     0%   100%      1.22s 99.19%  testing.(*B).runN

Showing nodes accounting for 1.23s, 100% of 1.23s total

flat flat% sum% cum cum%

1.21s 98.37% 98.37% 1.21s 98.37% github.com/hblab-ngocnd/csv-demo/bench.FibRecursive

0.01s 0.81% 99.19% 1.22s 99.19% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibRecursive10

0.01s 0.81% 100% 0.01s 0.81% runtime/pprof.(*profMap).lookup

0 0% 100% 0.01s 0.81% runtime/pprof.(*profileBuilder).addCPUData

0 0% 100% 0.01s 0.81% runtime/pprof.profileWriter

0 0% 100% 1.22s 99.19% testing.(*B).launch

0 0% 100% 1.22s 99.19% testing.(*B).runN

Mất tổng thời gian chạy cho FibRecursive là 1.21s

Tiếp tục phân tích sâu hơn từng dòng lệnh đối với hàm FibRecursive

(pprof) list FibRecursive

Kết qủa:

Total<span class="token punctuation">:</span> <span class="token number">1.23</span>s
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github<span class="token punctuation">.</span>com<span class="token operator">/</span>hblab<span class="token operator">-</span>ngocnd<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token punctuation">.</span>BenchmarkFibRecursive10 in <span class="token operator">/</span>Users<span class="token operator">/</span>S16593<span class="token operator">/</span>Hblab<span class="token operator">/</span>Motify<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token operator">/</span>Figo_test<span class="token punctuation">.</span><span class="token keyword">go</span>
      <span class="token number">10</span>ms      <span class="token number">1.22</span>s <span class="token punctuation">(</span>flat<span class="token punctuation">,</span> cum<span class="token punctuation">)</span> <span class="token number">99.19</span><span class="token operator">%</span> of Total
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">11</span><span class="token punctuation">:</span>   <span class="token keyword">return</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">12</span><span class="token punctuation">:</span><span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">13</span><span class="token punctuation">:</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">14</span><span class="token punctuation">:</span><span class="token keyword">func</span> <span class="token function">BenchmarkFibRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">15</span><span class="token punctuation">:</span>   <span class="token comment">// run the FibRecursive function b.N times</span>
      <span class="token number">10</span>ms       <span class="token number">10</span>ms     <span class="token number">16</span><span class="token punctuation">:</span>   <span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>      <span class="token number">1.21</span>s     <span class="token number">17</span><span class="token punctuation">:</span>           <span class="token function">FibRecursive</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">18</span><span class="token punctuation">:</span>   <span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">19</span><span class="token punctuation">:</span><span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">20</span><span class="token punctuation">:</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">21</span><span class="token punctuation">:</span><span class="token operator">/</span><span class="token operator">/</span><span class="token keyword">func</span> <span class="token function">FibNonRecursive</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">22</span><span class="token punctuation">:</span><span class="token operator">/</span><span class="token operator">/</span> <span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github<span class="token punctuation">.</span>com<span class="token operator">/</span>hblab<span class="token operator">-</span>ngocnd<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token punctuation">.</span>FibRecursive in <span class="token operator">/</span>Users<span class="token operator">/</span>S16593<span class="token operator">/</span>Hblab<span class="token operator">/</span>Motify<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token operator">/</span>Figo_test<span class="token punctuation">.</span><span class="token keyword">go</span>
     <span class="token number">1.21</span>s      <span class="token number">1.99</span>s <span class="token punctuation">(</span>flat<span class="token punctuation">,</span> cum<span class="token punctuation">)</span> <span class="token number">161.79</span><span class="token operator">%</span> of Total
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>      <span class="token number">2</span><span class="token punctuation">:</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>      <span class="token number">3</span><span class="token punctuation">:</span><span class="token keyword">import</span> <span class="token punctuation">(</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>      <span class="token number">4</span><span class="token punctuation">:</span>   <span class="token string">"testing"</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>      <span class="token number">5</span><span class="token punctuation">:</span><span class="token punctuation">)</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>      <span class="token number">6</span><span class="token punctuation">:</span>
     <span class="token number">540</span>ms      <span class="token number">540</span>ms      <span class="token number">7</span><span class="token punctuation">:</span><span class="token keyword">func</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
      <span class="token number">40</span>ms       <span class="token number">40</span>ms      <span class="token number">8</span><span class="token punctuation">:</span>   <span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
     <span class="token number">200</span>ms      <span class="token number">200</span>ms      <span class="token number">9</span><span class="token punctuation">:</span>           <span class="token keyword">return</span> n
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">10</span><span class="token punctuation">:</span>   <span class="token punctuation">}</span>
     <span class="token number">430</span>ms      <span class="token number">1.21</span>s     <span class="token number">11</span><span class="token punctuation">:</span>   <span class="token keyword">return</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">FibRecursive</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">12</span><span class="token punctuation">:</span><span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">13</span><span class="token punctuation">:</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">14</span><span class="token punctuation">:</span><span class="token keyword">func</span> <span class="token function">BenchmarkFibRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">15</span><span class="token punctuation">:</span>   <span class="token comment">// run the FibRecursive function b.N times</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">16</span><span class="token punctuation">:</span>   <span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>

Total: 1.23s

ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibRecursive10 in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go

10ms 1.22s (flat, cum) 99.19% of Total

. . 11: return FibRecursive(n-1) + FibRecursive(n-2)

. . 12:}

. . 13:

. . 14:func BenchmarkFibRecursive10(b *testing.B) {

. . 15: // run the FibRecursive function b.N times

10ms 10ms 16: for n := 0; n < b.N; n++ {

. 1.21s 17: FibRecursive(10)

. . 18: }

. . 19:}

. . 20:

. . 21://func FibNonRecursive(n int) int {

. . 22:// if n < 2 {

ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.FibRecursive in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go

1.21s 1.99s (flat, cum) 161.79% of Total

. . 2:

. . 3:import (

. . 4: "testing"

. . 5:)

. . 6:

540ms 540ms 7:func FibRecursive(n int) int {

40ms 40ms 8: if n < 2 {

200ms 200ms 9: return n

. . 10: }

430ms 1.21s 11: return FibRecursive(n-1) + FibRecursive(n-2)

. . 12:}

. . 13:

. . 16: for n := 0; n < b.N; n++ {

Show kết quả graph bằng png, pdf dùng command:

(pprof) web

images

Kết thúc phân tích

(pprof) q

Phân tích về cấp phát bộ nhớ

go tool pprof memprofile.out

(pprof) top
Showing nodes accounting for 5140.68kB, 100% of 5140.68kB total
Showing top 10 nodes out of 30
      flat  flat%   sum%        cum   cum%
 1537.69kB 29.91% 29.91%  1537.69kB 29.91%  runtime.allocm
 1024.41kB 19.93% 49.84%  1024.41kB 19.93%  runtime.malg
  902.59kB 17.56% 67.40%  1553.21kB 30.21%  compress/flate.NewWriter
  650.62kB 12.66% 80.05%   650.62kB 12.66%  compress/flate.(*compressor).init
  512.88kB  9.98% 90.03%   512.88kB  9.98%  flag.(*FlagSet).Var
  512.50kB  9.97%   100%   512.50kB  9.97%  hash/crc32.simpleMakeTable (inline)
         0     0%   100%  1553.21kB 30.21%  compress/gzip.(*Writer).Write
         0     0%   100%   512.88kB  9.98%  flag.Var (inline)
         0     0%   100%   512.50kB  9.97%  hash/crc32.init
         0     0%   100%   512.88kB  9.98%  main.main

(pprof) top

Showing nodes accounting for 5140.68kB, 100% of 5140.68kB total

Showing top 10 nodes out of 30

flat flat% sum% cum cum%

1537.69kB 29.91% 29.91% 1537.69kB 29.91% runtime.allocm

1024.41kB 19.93% 49.84% 1024.41kB 19.93% runtime.malg

902.59kB 17.56% 67.40% 1553.21kB 30.21% compress/flate.NewWriter

650.62kB 12.66% 80.05% 650.62kB 12.66% compress/flate.(*compressor).init

512.88kB 9.98% 90.03% 512.88kB 9.98% flag.(*FlagSet).Var

512.50kB 9.97% 100% 512.50kB 9.97% hash/crc32.simpleMakeTable (inline)

0 0% 100% 1553.21kB 30.21% compress/gzip.(*Writer).Write

0 0% 100% 512.88kB 9.98% flag.Var (inline)

0 0% 100% 512.50kB 9.97% hash/crc32.init

0 0% 100% 512.88kB 9.98% main.main

(pprof) web

images

Test benchmarks với fibonaci non recursive

Cài đặt thuật toán với cách tiếp cận là khử đệ quy.

Cài đặt test benchmark với đầu vào N = 10 (giống bước trên)

<span class="token keyword">package</span> bench

<span class="token keyword">import</span> <span class="token punctuation">(</span>
	<span class="token string">"testing"</span>
<span class="token punctuation">)</span>

<span class="token keyword">func</span> <span class="token function">FibNonRecursive</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> n
	<span class="token punctuation">}</span>
	f1 <span class="token operator">:=</span> <span class="token number">0</span>
	f2 <span class="token operator">:=</span> <span class="token number">1</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		tmp <span class="token operator">:=</span> f2
		f2 <span class="token operator">=</span> f1 <span class="token operator">+</span> f2
		f1 <span class="token operator">=</span> tmp
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f2
<span class="token punctuation">}</span>

<span class="token keyword">func</span> <span class="token function">BenchmarkFibNonRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token comment">// run the FibNonRecursive function b.N times</span>
	<span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token function">FibNonRecursive</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>

package bench

import (

"testing"

)

func FibNonRecursive(n int) int {

if n < 2 {

return n

}

f1 := 0

f2 := 1

for i := 2; i < n; i++ {

tmp := f2

f2 = f1 + f2

f1 = tmp

}

return f2

}

func BenchmarkFibNonRecursive10(b *testing.B) {

// run the FibNonRecursive function b.N times

FibNonRecursive(10)

}

Optimized

Do biến tmp được cấp phát trong vòng lặp làm tăng bộ nhớ khá nhiều, gây nên kết luận sai. Sau khi tìm hiểu được nguyên nhân thì mình sửa thành như sau

<span class="token keyword">package</span> bench

<span class="token keyword">import</span> <span class="token punctuation">(</span>
	<span class="token string">"testing"</span>
<span class="token punctuation">)</span>

<span class="token keyword">func</span> <span class="token function">FibNonRecursive</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> n
	<span class="token punctuation">}</span>
	f1 <span class="token operator">:=</span> <span class="token number">0</span>
	f2 <span class="token operator">:=</span> <span class="token number">1</span>
    tmp <span class="token operator">:=</span> <span class="token number">0</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		tmp <span class="token operator">=</span> f2
		f2 <span class="token operator">=</span> f1 <span class="token operator">+</span> f2
		f1 <span class="token operator">=</span> tmp
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f2
<span class="token punctuation">}</span>

<span class="token keyword">func</span> <span class="token function">BenchmarkFibNonRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token comment">// run the FibNonRecursive function b.N times</span>
	<span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token function">FibNonRecursive</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>

package bench

import (

"testing"

)

if n < 2 {

return n

}

f1 := 0

f2 := 1

tmp := 0

tmp = f2

f2 = f1 + f2

f1 = tmp

}

return f2

}

// run the FibNonRecursive function b.N times

FibNonRecursive(10)

}

Phân tích

Tiếp tục chạy lệnh tương tự

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Kết quả:

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibNonRecursive10-12           223505781                5.321 ns/op           0 B/op          0 allocs/op
PASS
ok      github.com/hblab-ngocnd/csv-demo/bench  4.895s

goos: darwin

goarch: amd64

pkg: github.com/hblab-ngocnd/csv-demo/bench

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

BenchmarkFibNonRecursive10-12 223505781 5.321 ns/op 0 B/op 0 allocs/op

PASS

ok github.com/hblab-ngocnd/csv-demo/bench 4.895s

có 223505781 phép toán mỗi phép toán mất 5.321 ns tổng 1189274260.7 ns

Optimized

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibNonRecursive10-12           238679884                4.987 ns/op           0 B/op          0 allocs/op
PASS
ok      github.com/hblab-ngocnd/csv-demo/bench  1.936s

goos: darwin

goarch: amd64

pkg: github.com/hblab-ngocnd/csv-demo/bench

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

BenchmarkFibNonRecursive10-12 238679884 4.987 ns/op 0 B/op 0 allocs/op

PASS

ok github.com/hblab-ngocnd/csv-demo/bench 1.936s

Chạy lệnh

go tool pprof profile.out

(pprof) top

Type: cpu
Time: Aug 25, 2022 at 3:43pm (+07)
Duration: 1.85s, Total samples = 1.48s (79.92%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1480ms, 100% of 1480ms total
      flat  flat%   sum%        cum   cum%
     980ms 66.22% 66.22%      980ms 66.22%  github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)
     360ms 24.32% 90.54%     1460ms 98.65%  github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10
     120ms  8.11% 98.65%      120ms  8.11%  runtime.asyncPreempt
      20ms  1.35%   100%       20ms  1.35%  runtime.nanotime1
         0     0%   100%       20ms  1.35%  runtime.nanotime
         0     0%   100%       20ms  1.35%  testing.(*B).StopTimer
         0     0%   100%     1480ms   100%  testing.(*B).launch
         0     0%   100%     1480ms   100%  testing.(*B).runN
         0     0%   100%       20ms  1.35%  time.Since

Type: cpu

Time: Aug 25, 2022 at 3:43pm (+07)

Duration: 1.85s, Total samples = 1.48s (79.92%)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Showing nodes accounting for 1480ms, 100% of 1480ms total

flat flat% sum% cum cum%

980ms 66.22% 66.22% 980ms 66.22% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)

360ms 24.32% 90.54% 1460ms 98.65% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10

120ms 8.11% 98.65% 120ms 8.11% runtime.asyncPreempt

20ms 1.35% 100% 20ms 1.35% runtime.nanotime1

0 0% 100% 20ms 1.35% runtime.nanotime

0 0% 100% 20ms 1.35% testing.(*B).StopTimer

0 0% 100% 1480ms 100% testing.(*B).launch

0 0% 100% 1480ms 100% testing.(*B).runN

0 0% 100% 20ms 1.35% time.Since

Mất tổng thời gian chạy cho FibNonRecursive là 980ms

Optimized

Type: cpu
Time: Aug 26, 2022 at 3:20am (+07)
Duration: 1.85s, Total samples = 1.51s (81.53%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1.51s, 100% of 1.51s total
Showing top 10 nodes out of 20
      flat  flat%   sum%        cum   cum%
     0.90s 59.60% 59.60%      0.90s 59.60%  github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)
     0.55s 36.42% 96.03%      1.47s 97.35%  github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10
     0.02s  1.32% 97.35%      0.02s  1.32%  runtime.asyncPreempt
     0.02s  1.32% 98.68%      0.02s  1.32%  runtime.libcCall
     0.01s  0.66% 99.34%      0.02s  1.32%  runtime.kevent
     0.01s  0.66%   100%      0.02s  1.32%  runtime.pthread_cond_wait
         0     0%   100%      0.03s  1.99%  runtime.findrunnable
         0     0%   100%      0.02s  1.32%  runtime.mPark (inline)
         0     0%   100%      0.03s  1.99%  runtime.mcall
         0     0%   100%      0.02s  1.32%  runtime.netpoll

Type: cpu

Time: Aug 26, 2022 at 3:20am (+07)

Duration: 1.85s, Total samples = 1.51s (81.53%)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Showing nodes accounting for 1.51s, 100% of 1.51s total

Showing top 10 nodes out of 20

flat flat% sum% cum cum%

0.90s 59.60% 59.60% 0.90s 59.60% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)

0.55s 36.42% 96.03% 1.47s 97.35% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10

0.02s 1.32% 97.35% 0.02s 1.32% runtime.asyncPreempt

0.02s 1.32% 98.68% 0.02s 1.32% runtime.libcCall

0.01s 0.66% 99.34% 0.02s 1.32% runtime.kevent

0.01s 0.66% 100% 0.02s 1.32% runtime.pthread_cond_wait

0 0% 100% 0.03s 1.99% runtime.findrunnable

0 0% 100% 0.02s 1.32% runtime.mPark (inline)

0 0% 100% 0.03s 1.99% runtime.mcall

0 0% 100% 0.02s 1.32% runtime.netpoll

Mất tổng thời gian chạy cho FibNonRecursive là 0.90s

(pprof) list FibNonRecursive

<span class="token punctuation">(</span>pprof<span class="token punctuation">)</span> list FibNonRecursive
Total<span class="token punctuation">:</span> <span class="token number">1.48</span>s
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github<span class="token punctuation">.</span>com<span class="token operator">/</span>hblab<span class="token operator">-</span>ngocnd<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token punctuation">.</span>BenchmarkFibNonRecursive10 in <span class="token operator">/</span>Users<span class="token operator">/</span>S16593<span class="token operator">/</span>Hblab<span class="token operator">/</span>Motify<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token operator">/</span>Figo_test<span class="token punctuation">.</span><span class="token keyword">go</span>
     <span class="token number">360</span>ms      <span class="token number">1.46</span>s <span class="token punctuation">(</span>flat<span class="token punctuation">,</span> cum<span class="token punctuation">)</span> <span class="token number">98.65</span><span class="token operator">%</span> of Total
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">32</span><span class="token punctuation">:</span>   <span class="token keyword">return</span> f2
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">33</span><span class="token punctuation">:</span><span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">34</span><span class="token punctuation">:</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">35</span><span class="token punctuation">:</span><span class="token keyword">func</span> <span class="token function">BenchmarkFibNonRecursive10</span><span class="token punctuation">(</span>b <span class="token operator">*</span>testing<span class="token punctuation">.</span>B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">36</span><span class="token punctuation">:</span>   <span class="token comment">// run the FibNonRecursive function b.N times</span>
     <span class="token number">110</span>ms      <span class="token number">160</span>ms     <span class="token number">37</span><span class="token punctuation">:</span>   <span class="token keyword">for</span> n <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>N<span class="token punctuation">;</span> n<span class="token operator">++</span> <span class="token punctuation">{</span>
     <span class="token number">250</span>ms      <span class="token number">1.23</span>s     <span class="token number">38</span><span class="token punctuation">:</span>           <span class="token function">FibNonRecursive</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">39</span><span class="token punctuation">:</span>   <span class="token punctuation">}</span>
         <span class="token punctuation">.</span>       <span class="token number">70</span>ms     <span class="token number">40</span><span class="token punctuation">:</span><span class="token punctuation">}</span>
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github<span class="token punctuation">.</span>com<span class="token operator">/</span>hblab<span class="token operator">-</span>ngocnd<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token punctuation">.</span>FibNonRecursive in <span class="token operator">/</span>Users<span class="token operator">/</span>S16593<span class="token operator">/</span>Hblab<span class="token operator">/</span>Motify<span class="token operator">/</span>csv<span class="token operator">-</span>demo<span class="token operator">/</span>bench<span class="token operator">/</span>Figo_test<span class="token punctuation">.</span><span class="token keyword">go</span>
     <span class="token number">980</span>ms      <span class="token number">980</span>ms <span class="token punctuation">(</span>flat<span class="token punctuation">,</span> cum<span class="token punctuation">)</span> <span class="token number">66.22</span><span class="token operator">%</span> of Total
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">22</span><span class="token punctuation">:</span>   <span class="token keyword">if</span> n <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">23</span><span class="token punctuation">:</span>           <span class="token keyword">return</span> n
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">24</span><span class="token punctuation">:</span>   <span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">25</span><span class="token punctuation">:</span>   f1 <span class="token operator">:=</span> <span class="token number">0</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">26</span><span class="token punctuation">:</span>   f2 <span class="token operator">:=</span> <span class="token number">1</span>
     <span class="token number">980</span>ms      <span class="token number">980</span>ms     <span class="token number">27</span><span class="token punctuation">:</span>   <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">28</span><span class="token punctuation">:</span>           tmp <span class="token operator">:=</span> f2
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">29</span><span class="token punctuation">:</span>           f2 <span class="token operator">=</span> f1 <span class="token operator">+</span> f2
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">30</span><span class="token punctuation">:</span>           f1 <span class="token operator">=</span> tmp
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">31</span><span class="token punctuation">:</span>   <span class="token punctuation">}</span>
         <span class="token punctuation">.</span>          <span class="token punctuation">.</span>     <span class="token number">32</span><span class="token punctuation">:</span>   <span class="token keyword">return</span> f2

(pprof) list FibNonRecursive

Total: 1.48s

ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go

360ms 1.46s (flat, cum) 98.65% of Total

. . 32: return f2

. . 33:}

. . 34:

. . 35:func BenchmarkFibNonRecursive10(b *testing.B) {

. . 36: // run the FibNonRecursive function b.N times

110ms 160ms 37: for n := 0; n < b.N; n++ {

250ms 1.23s 38: FibNonRecursive(10)

. . 39: }

. 70ms 40:}

ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go

980ms 980ms (flat, cum) 66.22% of Total

. . 22: if n < 2 {

. . 23: return n

. . 24: }

. . 25: f1 := 0

. . 26: f2 := 1

980ms 980ms 27: for i := 2; i < n; i++ {

. . 28: tmp := f2

. . 29: f2 = f1 + f2

. . 30: f1 = tmp

. . 31: }

Optimized

<span class="token punctuation">(</span>pprof<span class="token punctuation">)</span> list FibNonRecursive
Total: <span class="token number">1</span>.51s
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 <span class="token keyword">in</span> /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go
     550ms      <span class="token number">1</span>.47s <span class="token punctuation">(</span>flat, cum<span class="token punctuation">)</span> <span class="token number">97.35</span>% of Total
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">33</span>:   <span class="token builtin class-name">return</span> f2
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">34</span>:<span class="token punctuation">}</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">35</span>:
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">36</span>:func BenchmarkFibNonRecursive10<span class="token punctuation">(</span>b *testing.B<span class="token punctuation">)</span> <span class="token punctuation">{</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">37</span>:   // run the FibNonRecursive <span class="token keyword">function</span> b.N <span class="token builtin class-name">times</span>
     190ms      200ms     <span class="token number">38</span>:   <span class="token keyword">for</span> n :<span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> n <span class="token operator">&lt;</span> b.N<span class="token punctuation">;</span> n++ <span class="token punctuation">{</span>
     360ms      <span class="token number">1</span>.26s     <span class="token number">39</span>:           FibNonRecursive<span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">40</span>:   <span class="token punctuation">}</span>
         <span class="token builtin class-name">.</span>       10ms     <span class="token number">41</span>:<span class="token punctuation">}</span>
ROUTINE <span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span><span class="token operator">==</span> github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive <span class="token keyword">in</span> /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go
     900ms      900ms <span class="token punctuation">(</span>flat, cum<span class="token punctuation">)</span> <span class="token number">59.60</span>% of Total
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">23</span>:           <span class="token builtin class-name">return</span> n
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">24</span>:   <span class="token punctuation">}</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">25</span>:   f1 :<span class="token operator">=</span> <span class="token number">0</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">26</span>:   f2 :<span class="token operator">=</span> <span class="token number">1</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">27</span>:   tmp :<span class="token operator">=</span> f2
     900ms      900ms     <span class="token number">28</span>:   <span class="token keyword">for</span> i :<span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i++ <span class="token punctuation">{</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">29</span>:           tmp <span class="token operator">=</span> f2
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">30</span>:           f2 <span class="token operator">=</span> f1 + f2
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">31</span>:           f1 <span class="token operator">=</span> tmp
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">32</span>:   <span class="token punctuation">}</span>
         <span class="token builtin class-name">.</span>          <span class="token builtin class-name">.</span>     <span class="token number">33</span>:   <span class="token builtin class-name">return</span> f2

(pprof) list FibNonRecursive

Total: 1.51s

550ms 1.47s (flat, cum) 97.35% of Total

. . 33: return f2

. . 34:}

. . 35:

. . 36:func BenchmarkFibNonRecursive10(b *testing.B) {

. . 37: // run the FibNonRecursive function b.N times

190ms 200ms 38: for n := 0; n < b.N; n++ {

360ms 1.26s 39: FibNonRecursive(10)

. . 40: }

. 10ms 41:}

900ms 900ms (flat, cum) 59.60% of Total

. . 23: return n

. . 24: }

. . 25: f1 := 0

. . 26: f2 := 1

. . 27: tmp := f2

900ms 900ms 28: for i := 2; i < n; i++ {

. . 29: tmp = f2

. . 30: f2 = f1 + f2

. . 31: f1 = tmp

. . 32: }

. . 33: return f2

(pprof) list web

images

Optimized

images

(pprof) q

Phân tích về cấp phát bộ nhớ

go tool pprof memprofile.out

(pprof) top

Type: alloc_space
Time: Aug 25, 2022 at 3:43pm (+07)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 5811.98kB, 100% of 5811.98kB total
Showing top 10 nodes out of 26
      flat  flat%   sum%        cum   cum%
 2050.25kB 35.28% 35.28%  2050.25kB 35.28%  runtime.allocm
 1184.27kB 20.38% 55.65%  1184.27kB 20.38%  runtime/pprof.StartCPUProfile
  902.59kB 15.53% 71.18%  1553.21kB 26.72%  compress/flate.NewWriter
  650.62kB 11.19% 82.38%   650.62kB 11.19%  compress/flate.(*compressor).init
  512.20kB  8.81% 91.19%   512.20kB  8.81%  runtime.malg
  512.05kB  8.81%   100%  1696.32kB 29.19%  runtime.main
         0     0%   100%  1553.21kB 26.72%  compress/gzip.(*Writer).Write
         0     0%   100%  1184.27kB 20.38%  main.main
         0     0%   100%  1025.12kB 17.64%  runtime.mcall
         0     0%   100%  1025.12kB 17.64%  runtime.mstart

Type: alloc_space

Time: Aug 25, 2022 at 3:43pm (+07)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Showing nodes accounting for 5811.98kB, 100% of 5811.98kB total

Showing top 10 nodes out of 26

flat flat% sum% cum cum%

2050.25kB 35.28% 35.28% 2050.25kB 35.28% runtime.allocm

1184.27kB 20.38% 55.65% 1184.27kB 20.38% runtime/pprof.StartCPUProfile

902.59kB 15.53% 71.18% 1553.21kB 26.72% compress/flate.NewWriter

650.62kB 11.19% 82.38% 650.62kB 11.19% compress/flate.(*compressor).init

512.20kB 8.81% 91.19% 512.20kB 8.81% runtime.malg

512.05kB 8.81% 100% 1696.32kB 29.19% runtime.main

0 0% 100% 1553.21kB 26.72% compress/gzip.(*Writer).Write

0 0% 100% 1184.27kB 20.38% main.main

0 0% 100% 1025.12kB 17.64% runtime.mcall

0 0% 100% 1025.12kB 17.64% runtime.mstart

Optimized

Type: alloc_space
Time: Aug 26, 2022 at 3:20am (+07)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 3746.37kB, 100% of 3746.37kB total
Showing top 10 nodes out of 21
      flat  flat%   sum%        cum   cum%
 1537.69kB 41.04% 41.04%  1537.69kB 41.04%  runtime.allocm
 1184.27kB 31.61% 72.66%  1184.27kB 31.61%  runtime/pprof.StartCPUProfile
 1024.41kB 27.34%   100%  1024.41kB 27.34%  runtime.malg
         0     0%   100%  1184.27kB 31.61%  main.main
         0     0%   100%  1184.27kB 31.61%  runtime.main
         0     0%   100%   512.56kB 13.68%  runtime.mcall
         0     0%   100%  1025.12kB 27.36%  runtime.mstart
         0     0%   100%  1025.12kB 27.36%  runtime.mstart0
         0     0%   100%  1025.12kB 27.36%  runtime.mstart1
         0     0%   100%  1537.69kB 41.04%  runtime.newm

Type: alloc_space

Time: Aug 26, 2022 at 3:20am (+07)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Showing nodes accounting for 3746.37kB, 100% of 3746.37kB total

Showing top 10 nodes out of 21

flat flat% sum% cum cum%

1537.69kB 41.04% 41.04% 1537.69kB 41.04% runtime.allocm

1184.27kB 31.61% 72.66% 1184.27kB 31.61% runtime/pprof.StartCPUProfile

1024.41kB 27.34% 100% 1024.41kB 27.34% runtime.malg

0 0% 100% 1184.27kB 31.61% main.main

0 0% 100% 1184.27kB 31.61% runtime.main

0 0% 100% 512.56kB 13.68% runtime.mcall

0 0% 100% 1025.12kB 27.36% runtime.mstart

0 0% 100% 1025.12kB 27.36% runtime.mstart0

0 0% 100% 1025.12kB 27.36% runtime.mstart1

0 0% 100% 1537.69kB 41.04% runtime.newm

(pprof) web

images

Optimized

images

So sánh và kết luận với trường hợp N = 10

func BenchmarkFib10(b *testing.B) {
	// run the FibRecursive function b.N times
	for n := 0; n &lt; b.N; n++ {
		FibRecursive(10)
	}
	for n := 0; n &lt; b.N; n++ {
		FibNonRecursive(10)
	}
	for n := 0; n &lt; b.N; n++ {
		FibNonRecursiveOptimized(10)
	}
}

func BenchmarkFib10(b *testing.B) {

// run the FibRecursive function b.N times

for n := 0; n < b.N; n++ {

FibRecursive(10)

}

for n := 0; n < b.N; n++ {

FibNonRecursive(10)

}

for n := 0; n < b.N; n++ {

FibNonRecursiveOptimized(10)

}

Type: cpu
Time: Aug 26, 2022 at 3:55am (+07)
Duration: 1.54s, Total samples = 1.22s (79.30%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1.22s, 100% of 1.22s total
Showing top 10 nodes out of 18
      flat  flat%   sum%        cum   cum%
     1.15s 94.26% 94.26%      1.16s 95.08%  github.com/hblab-ngocnd/csv-demo/bench.FibRecursive
     0.02s  1.64% 95.90%      1.21s 99.18%  github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFib10
     0.02s  1.64% 97.54%      0.02s  1.64%  github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursiveOptimized (inline)
     0.01s  0.82% 98.36%      0.01s  0.82%  github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)
     0.01s  0.82% 99.18%      0.01s  0.82%  runtime.(*spanSet).push
     0.01s  0.82%   100%      0.01s  0.82%  runtime.asyncPreempt
         0     0%   100%      0.01s  0.82%  runtime.(*mcache).releaseAll
         0     0%   100%      0.01s  0.82%  runtime.(*mcentral).uncacheSpan
         0     0%   100%      0.01s  0.82%  runtime.ReadMemStats
         0     0%   100%      0.01s  0.82%  runtime.ReadMemStats.func1

Type: cpu

Time: Aug 26, 2022 at 3:55am (+07)

Duration: 1.54s, Total samples = 1.22s (79.30%)

Entering interactive mode (type "help" for commands, "o" for options)

(pprof) top

Showing nodes accounting for 1.22s, 100% of 1.22s total

Showing top 10 nodes out of 18

flat flat% sum% cum cum%

1.15s 94.26% 94.26% 1.16s 95.08% github.com/hblab-ngocnd/csv-demo/bench.FibRecursive

0.02s 1.64% 95.90% 1.21s 99.18% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFib10

0.02s 1.64% 97.54% 0.02s 1.64% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursiveOptimized (inline)

0.01s 0.82% 98.36% 0.01s 0.82% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline)

0.01s 0.82% 99.18% 0.01s 0.82% runtime.(*spanSet).push

0.01s 0.82% 100% 0.01s 0.82% runtime.asyncPreempt

0 0% 100% 0.01s 0.82% runtime.(*mcache).releaseAll

0 0% 100% 0.01s 0.82% runtime.(*mcentral).uncacheSpan

0 0% 100% 0.01s 0.82% runtime.ReadMemStats

0 0% 100% 0.01s 0.82% runtime.ReadMemStats.func1

images

Tiêu chí	Recursive	Non Recursive	Non Recursive Optimized
Time	`1.16s`	`0.01s`	`0.02s`
Memory	`5140.68kB`	`5811.98kB`	`3746.37kB`

Lưu ý : Tiêu chí về memory so sánh là chưa hợp lý

Updated

Đúng với nhận xét ban đầu, sau khi optimized Non Recursive có thời gian chạy thấp hơn và tốn ít bộ nhớ hơn so với Recursive

Bạn hãy test thử xem let try !!!

Tài liệu tham khảo

Happy codding !!!

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo

Kiểm tra điểm chuẩn fibonaci đệ quy / không đệ quy

Test benchmark fibonaci recursive/non recursive

Động cơ, lý do

Test benchmarks với fibonaci recursive

Phân tích thời gian chạy

Phân tích về cấp phát bộ nhớ

Test benchmarks với fibonaci non recursive

Phân tích

Phân tích về cấp phát bộ nhớ

So sánh và kết luận với trường hợp N = 10

Tài liệu tham khảo

TikTok trở thành nền tảng mảng xã hội lớn thứ hai ở Nam Phi

Mất giá nhanh nhất sau 9 tháng ra mắt, iPhone 14 Pro Max tiếp tục phá đáy tại Việt Nam

Hướng dẫn sử dụng ngôn ngữ R cho người mới bắt đầu

10 plugin cần thiết của SublimeText dành cho các lập trình viên JavaScript