8

Есть два кода реализующих один и тот же алгоритм: быстрое вычисления последовательности Фибоначчи. Алгоритм в оптимизации не нуждается.

Программы работают примерно одинаково по скорости (до определенных аргументов), но при аргументе в 100 млн. код на Go начинает ощутимо проигрывать Rust'у по памяти: практически в три раза - 150mb vs 50mb. Разумеется, я понимаю, что это говорит о том, что в Rust все очень хорошо с управлением памятью.

Вопрос: можно ли как-то оптимизировать код на Go по памяти или это предел для языка со сборщиком мусора и за автоматическим растовским перемещением значений не угнаться? Вопрос не холиварный, а исключительно практический.

P.S.: Пробовал использовать в Go sync.Pool для big.Int - не помогло. Или не получилось правильно.

// Fast doubling Fibonacci algorithm
package main

import (
    "errors"
    "flag"
    "fmt"
    "math/big"
    "os"
    "strconv"
    "time"
)
 
type Opts struct {
    fast, time, otime bool
}
 
func (opts *Opts) Usage() {
     fmt.Printf(
        ("fib 1.0\n" + 
        "Author: Garry G.\n\n" +
        "Calculating the nth number of the fibonacci sequence\n\n" +
         "Usage: %s [OPTIONS] arg arg1 arg2...\n") , 
     os.Args[0])
     flag.PrintDefaults()
}

func (opts *Opts) Parse() *Opts {
    flag.Usage = opts.Usage
    flag.BoolVar(&opts.fast, "fast", false, "Use the fast version of the calculation: false")
    flag.BoolVar(&opts.time, "time", false, "Output execution time: false")
    flag.BoolVar(&opts.otime, "otime", false, "Output only the execution time: false")
    flag.Parse()
    return opts
}


type BigIntOperators struct{}

func (b BigIntOperators) Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

func (b BigIntOperators) Sub(x, y *big.Int) *big.Int {
    return big.NewInt(0).Sub(x, y)
}
func (b BigIntOperators) Add(x, y *big.Int) *big.Int {
    return big.NewInt(0).Add(x, y)
}

type Fib struct {
    BigIntOperators
}

//  (Public) Returns F(n).
func (f *Fib) Calc(n uint, fast bool) (*big.Int, error) {
    var err error
    var fst *big.Int
    if n < 0 {
        err = errors.New("Negative arguments not implemented")
    } else {
        switch fast {
        case true:
            fst, _ = f.fib_fast(n)
        default:
            fst, _ = f.fib(n)
        }
    }

    return fst, err
}

func (f *Fib) fib(n uint) (*big.Int, *big.Int) {
    /* n-е по индексу (от 0) число Фибоначчи
    >> fib --fast 10
    55
    >>fib --otime 10000 100000 1000000
    1.0001ms => 10000
    70.004ms => 100000
    8.2204702s => 1000000
    */

    f0 := big.NewInt(0)
    f1 := big.NewInt(1)

    var i uint
    for i = 2; i <= n; i++ {
        f0.Add(f0, f1)
        f0, f1 = f1, f0

    }
    return f1,f0
}

// (Private) Returns the tuple (F(n), F(n+1)).
func (f *Fib) fib_fast(n uint) (*big.Int, *big.Int) {
    /* n-е по индексу (от 0) число Фибоначчи
    >> fib --fast 10
    55
    >>fib --otime --fast 10000 100000 1000000 10000000 100000000
    0s => 10000
    2.0001ms => 100000
    59.0034ms => 1000000
    2.4231386s => 10000000
    1m24.9398582s => 100000000
    */

    if n == 0 {
        return big.NewInt(0), big.NewInt(1)
    }

    a, b := f.fib_fast(n / 2)
    c := f.Mul(a, f.Sub(f.Mul(b, big.NewInt(2)), a))
    d := f.Add(f.Mul(a, a), f.Mul(b, b))
    
    if n%2 == 0 {
        return c, d
    } else {
        return d, f.Add(c, d)
    }
}


func main() {
    
    opts := &Opts{}
    opts.Parse()
    
    fib := &Fib{}
    if  flag.NArg() == 0 { 
        flag.Usage()
    } else {
        // итерируем по позиционным аргументам
        for _, s := range flag.Args() {
            n, err := strconv.Atoi(s)
            if err != nil {
                panic(err)
            }
            start := time.Now()
            result, err := fib.Calc(uint(n), opts.fast)
            if err != nil {
                panic(err)
            }
            duration := time.Since(start)

            if !opts.otime {
                fmt.Println(result)
            } 
            if opts.otime || opts.time {
                fmt.Printf("%s => %d\n", duration, n)
            }
        }
    }
}

Аналогичный код на Rust:

extern crate num_bigint;

use std::time::{Instant};
use clap::Clap;
use num_traits::{Zero, One};
use num_bigint::BigUint;
use std::mem::replace;

#[derive(Clap, Debug)]
#[clap(name = "fib")]
#[clap(
    version = "1.0", 
    author = "Author: Garry G.", 
    about="Calculating the nth number of the fibonacci sequence")
]
struct Opts {
    #[clap(short, long, about="Use the fast version of the calculation: false")]
    fast: bool,
    #[clap(short, long, about="Output execution time: false")]
    time: bool,
    #[clap(short, long, about="Output only the execution time: false")]
    otime: bool,
    #[clap(required=true, multiple=true, about="Ordinal number of the number")]
    input: Vec<usize>,
}


struct Fib;
 
impl Fib {
    /// (Public) Returns F(n).
    pub fn calc(n: usize, fast:bool) -> BigUint {
        if fast { 
            Self::fib_fast(n).0
        } else {
            Self::fib(n).0
        }    
    }
    
    /// Returns the tuple (F(n), F(n+1)).
    fn fib(n: usize) -> (BigUint, BigUint) {
        /* n-е по индексу (от 0) число Фибоначчи 
        >> target\release\fib 10
        55
        >> target\release\fib --otime 10000 100000 1000000
        860.139µs => 10000
        71.889642ms => 100000
        9.80835748s => 1000000
        */
        
        let mut f0: BigUint = Zero::zero();
        let mut f1: BigUint = One::one();
        for _ in 0..n {
            let f2 = f0 + &f1;
            // This is a low cost way of swapping f0 with f1 and f1 with f2.
            f0 = replace(&mut f1, f2);
        }
        (f0,f1)
    }


    /// Returns the tuple (F(n), F(n+1)).
    fn fib_fast(n: usize) -> (BigUint, BigUint) {
        /* n-е по индексу (от 0) число Фибоначчи 
        >> target\release\fib --fast 10
        55
        >> target\release\fib --otime --fast 10000 100000 1000000 10000000 100000000
        75.482µs => 10000
        2.012551ms => 100000
        62.328494ms => 1000000
        1.84259102s => 10000000
        56.118505675s => 100000000
        */
        
        if n == 0 {
            return (0u64.into(), 1u64.into());
        }
        let (a, b) = Self::fib_fast(n / 2);
        let c = &a * (&b * 2u64 - &a);
        let d = (&a * &a) + (&b * &b);
        if n % 2 == 0 {
            (c, d)
        } else {
            let r = &c + &d;
            (d, r)
        }
    }
}


fn main() {
    
    let opts = Opts::parse();
    
    for n in opts.input {
        let start = Instant::now();
        let result = Fib::calc(n, opts.fast);
        let duration = start.elapsed();      
        if !opts.otime {
            println!("{}", result);
        }
        if opts.otime || opts.time {
            println!("{:?} => {:}", duration, n);
        }
    }
}

2
  • 1
    а как вы измеряли потребление памяти? профайлером смотрели? 17 июн 2021 в 12:04
  • 1
    Внутри кода есть таймер. У программы есть опции --time и --otime для вывода времени исполнения. 17 июн 2021 в 17:27

2 ответа 2

9

давайте измерим потребление памяти вашего кода. Для этого написал простой бенчмарк

func BenchmarkFib(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fib := &Fib{}
        _, err := fib.Calc(100_000_000, true)
        if err != nil {
            b.Errorf("i = %d - %v", i, err.Error())
        }
    }
}
➜  fib go test  -bench . -count 1 -benchmem -cpuprofile=cpu.out -memprofile=mem.out -trace=trace.out
goos: darwin
goarch: amd64
pkg: github.com/so/awesomeProject/questions/fib
BenchmarkFib-8             1    21829623107 ns/op   243377256 B/op       603 allocs/op
PASS
ok      github.com/so/awesomeProject/questions/fib  22.275s
➜  fib ll
total 7024
-rw-r--r--  1 user  staff    26K Jun 17 15:38 cpu.out
-rwxr-xr-x  1 user  staff   3.2M Jun 17 15:38 fib.test
-rw-r--r--  1 user  staff   227B Jun 17 15:37 fib_banchmark_test.go
-rw-r--r--  1 user  staff   2.9K Jun 17 15:07 main.go
-rw-r--r--  1 user  staff   1.9K Jun 17 15:38 mem.out
-rw-r--r--  1 user  staff   216K Jun 17 15:38 trace.out

на выходе получили профили потребления CPU, памяти, трейс вызовов.

визуализируем память

➜  fib go tool pprof -http :8080 fib.test mem.out
Serving web UI on http://localhost:8080

на картинке видно, что очень много памяти уходит на аллокации. целых 219Мб! введите сюда описание изображения

оптимизируем слудеющий участок кода. В итоге новой аллокации нет, как при big.NewInt(0).Sub(x, y)

func (b BigIntOperators) Mul(x, y *big.Int) *big.Int {
    return x.Mul(x, y)
}

func (b BigIntOperators) Sub(x, y *big.Int) *big.Int {
    return x.Sub(x, y)
}
func (b BigIntOperators) Add(x, y *big.Int) *big.Int {
    return x.Add(x, y)
}

проверяем еще раз

➜  fib go test  -bench . -count 1 -benchmem -cpuprofile=cpu.out -memprofile=mem.out -trace=trace.out
goos: darwin
goarch: amd64
pkg: github.com/so/awesomeProject/questions/fib
BenchmarkFib-8        428538          2753 ns/op         392 B/op         33 allocs/op
PASS
ok      github.com/so/awesomeProject/questions/fib  1.767s

сразу видим, что количество аллокаций и операций уменьшились в разы. Также и время выполнения. Давайте посмотрим на профайлер.

введите сюда описание изображения

Итого сэкономили 100Мб памяти почти. Уменьшили время выполнения.

Ну и сама структура bigint требует памяти тоже. https://golang.org/src/math/big/nat_test.go

7
  • 1
    Спасибо за развернутый ответ и визуализацию. Сам собирался так сделать, но практики использования гошных инструментариев пока нет. Но не понял ваш способ оптимизации. Все операции заменены в вашем примере на Mul. В любом случае, даже если это просто ошибка, в случае замены левого операнда операции на первый аргумент функции мы получаем неверные вычисления. 17 июн 2021 в 17:32
  • 1
    спасибо за замечание. вы правы. я заменил на Mul потому что копипаст. я исправил код. и обновил вопрос. результат почти тот же) 17 июн 2021 в 17:37
  • 1
    умножения лучше делать вот так x.Mul(x, y) потому что в данном случае не выделяется новая память как при big.NewInt(0) хотя результат будет одинаковым. в этом и выигрыш. 17 июн 2021 в 17:39
  • 1
    Я заменил только Mul на func (b BigIntOperators) Mul(x, y *big.Int) *big.Int { return x.Mul(x, y) } Получается такая калькуляция: fib --fast 10 Ответ: 78498455793758376998704133944362479386624 17 июн 2021 в 17:41
  • 1
    я вас не понял. это вопрос? 17 июн 2021 в 18:02
2

Я бы предположил, что разница не в том, как Go и Rust управляют памятью, а в том, как в них реализованы большие целые.

Для примера добавил в ваш код на Go поддержку целых из GMP. На маленьких целых считает гораздо медленнее, чем встроенные в Go, зато на больших в разы быстрее.

// Fast doubling Fibonacci algorithm
package main

import (
    "errors"
    "flag"
    "fmt"
    "math/big"
    "os"
    "strconv"
    "time"

    "github.com/ncw/gmp"
)

type Opts struct {
    gmp, fast, time, otime bool
}

func (opts *Opts) Usage() {
    fmt.Printf(
        ("fib 1.0\n" +
            "Author: Garry G.\n\n" +
            "Calculating the nth number of the fibonacci sequence\n\n" +
            "Usage: %s [OPTIONS] arg arg1 arg2...\n"),
        os.Args[0])
    flag.PrintDefaults()
}

func (opts *Opts) Parse() *Opts {
    flag.Usage = opts.Usage
    flag.BoolVar(&opts.fast, "fast", false, "Use the fast version of the calculation: false")
    flag.BoolVar(&opts.gmp, "gmp", false, "Use Gnu Multiprecision library: false")
    flag.BoolVar(&opts.time, "time", false, "Output execution time: false")
    flag.BoolVar(&opts.otime, "otime", false, "Output only the execution time: false")
    flag.Parse()
    return opts
}

type BigIntOperators struct{}

func (b BigIntOperators) Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

func (b BigIntOperators) Sub(x, y *big.Int) *big.Int {
    return big.NewInt(0).Sub(x, y)
}
func (b BigIntOperators) Add(x, y *big.Int) *big.Int {
    return big.NewInt(0).Add(x, y)
}

type Fib struct {
    BigIntOperators
}

//  (Public) Returns F(n).
func (f *Fib) Calc(n uint, fast bool) (*big.Int, error) {
    var err error
    var fst *big.Int
    if n < 0 {
        err = errors.New("Negative arguments not implemented")
    } else {
        switch fast {
        case true:
            fst, _ = f.fib_fast(n)
        default:
            fst, _ = f.fib(n)
        }
    }

    return fst, err
}

func (f *Fib) fib(n uint) (*big.Int, *big.Int) {
    /* n-е по индексу (от 0) число Фибоначчи
       >> fib --fast 10
       55
       >>fib --otime 10000 100000 1000000
       1.0001ms => 10000
       70.004ms => 100000
       8.2204702s => 1000000
    */

    f0 := big.NewInt(0)
    f1 := big.NewInt(1)

    var i uint
    for i = 2; i <= n; i++ {
        f0.Add(f0, f1)
        f0, f1 = f1, f0

    }
    return f1, f0
}

// (Private) Returns the tuple (F(n), F(n+1)).
func (f *Fib) fib_fast(n uint) (*big.Int, *big.Int) {
    /* n-е по индексу (от 0) число Фибоначчи
       >> fib --fast 10
       55
       >>fib --otime --fast 10000 100000 1000000 10000000 100000000
       0s => 10000
       2.0001ms => 100000
       59.0034ms => 1000000
       2.4231386s => 10000000
       1m24.9398582s => 100000000
    */

    if n == 0 {
        return big.NewInt(0), big.NewInt(1)
    }

    a, b := f.fib_fast(n / 2)
    c := f.Mul(a, f.Sub(f.Mul(b, big.NewInt(2)), a))
    d := f.Add(f.Mul(a, a), f.Mul(b, b))

    if n%2 == 0 {
        return c, d
    } else {
        return d, f.Add(c, d)
    }
}

func gmp_fib(n uint) (*gmp.Int, *gmp.Int) {
    if n == 0 {
        return gmp.NewInt(0), gmp.NewInt(1)
    }

    a, b := gmp_fib(n / 2)
    c := gmp.NewInt(0).Mul(a, gmp.NewInt(0).Sub(gmp.NewInt(0).Mul(b, gmp.NewInt(2)), a))
    d := gmp.NewInt(0).Add(gmp.NewInt(0).Mul(a, a), gmp.NewInt(0).Mul(b, b))

    if n%2 == 0 {
        return c, d
    } else {
        return d, c.Add(c, d)
    }
}

func main() {

    opts := &Opts{}
    opts.Parse()

    fib := &Fib{}
    if flag.NArg() == 0 {
        flag.Usage()
    } else {
        // итерируем по позиционным аргументам
        for _, s := range flag.Args() {
            n, err := strconv.Atoi(s)
            if err != nil {
                panic(err)
            }
            start := time.Now()
            var result interface{}

            if opts.gmp {
                result, _ = gmp_fib(uint(n))
            } else {
                result, err = fib.Calc(uint(n), opts.fast)
            }
            if err != nil {
                panic(err)
            }
            duration := time.Since(start)

            if !opts.otime {
                fmt.Println(result)
            }
            if opts.otime || opts.time {
                fmt.Printf("%s => %d\n", duration, n)
            }
        }
    }
}

Результаты:

Workstation:try-fib$ ./fib --fast --otime 100 10000 1000000 100000000
7.1µs => 100
29.6µs => 10000
14.6968ms => 1000000
18.2803134s => 100000000
Workstation:try-fib$ ./fib --gmp --otime 100 10000 1000000 100000000
45.6µs => 100
106.2µs => 10000
5.2981ms => 1000000
1.0782738s => 100000000

Видите, как различаются времена счёта для 100 миллионов? Так что не в языке дело, ИМХО.

1
  • 1
    Спасибо. У меня тоже было предположение, что встроенная библиотека может быть не очень эффективно реализована, но я не знал про альтернативу. В Rust вот вообще в std работа с длинной арифметикой не встроена - только внешние либы. Попробую тоже поиграться с gmp. 20 июн 2021 в 22:50

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.