Menneellää viikolla käytin suurimman osan ajasta algoritmin prosessointi kyvyn parantamiseen.
Minulla oli selvästi mielessä mitä ohjelmassa oli optimoitavaa jotta se toimisi vielä tehokkaammin.
Kaksi optimoinnin näkökulmaa jota lähdin tutkimaan:
- Helpompien taulujen ratkaisu tehokkuuden optimointi.
- Monimutkaisempien taulujen ratkaisujen tehokkuuden optimointi, jotta algoritmi pystyisi ratkaisemaan myös erittäin monimutkaiset taulut.
Suorituskyky testaukseen löysin sopivaksi työkaluksi pprof. Työkalun avulla kirjoitin kaksi testi skenaariota yllä mainittujen näkökulmien tutkimiseen.
Monimutkaisten taulujen ratkaisu kyvyn optimointiin:
var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
func TestPerformanceOne(t *testing.T) {
flag.Parse()
maxRuntimeMS := time.Duration(3000)
board := [16]t_cell{2, 5, 8, 9, 4, 1, 14, 7, 6, 10, 3, 15, 13, 0, 11, 12}
n := time.Now()
if *cpuprofile != "" {
f, err := os.Create(*cpuprofile)
if err != nil {
log.Fatal(err)
}
pprof.StartCPUProfile(f)
}
srh := NewSearch(&State{
size: BOARD_ROW_SIZE,
board: board,
complexity: 0,
})
node, _ := srh.IDAStar(maxRuntimeMS)
if *cpuprofile != "" {
pprof.StopCPUProfile()
}
dur := time.Since(n)
fmt.Printf("since n %s \n", dur)
fmt.Printf("complexity %d \n", node.state.complexity)
assert.True(t, node.state.isSuccess())
}board muuttujan ratkaisemiseen tarvitaan 48 siirtoa. Ratkaisun löytämiseen huonosti optimoidulla IDASearch algoritmillä menee noin 10 sekuntia.
Helpompien taulujen ratkaisukyvyn optimointiin testi:
func TestPerformanceAverage(t *testing.T) {
flag.Parse()
if *cpuprofile != "" {
f, err := os.Create(*cpuprofile)
if err != nil {
log.Fatal(err)
}
pprof.StartCPUProfile(f)
}
maxRuntimeMS := time.Duration(10600)
boards := [][16]t_cell{
{3, 4, 6, 5, 1, 7, 2, 14, 13, 15, 11, 8, 10, 0, 9, 12},
{3, 6, 8, 7, 5, 0, 9, 2, 1, 4, 14, 15, 13, 10, 12, 11},
}
perfList := make(map[int][]time.Duration)
for id, board := range boards {
for i := 0; i < 60; i++ {
n := time.Now()
srh := NewSearch(&State{
size: BOARD_ROW_SIZE,
board: board,
complexity: 0,
})
node, _ := srh.IDAStar(maxRuntimeMS)
dur := time.Since(n)
perfList[id] = append(perfList[id], dur)
assert.True(t, node.state.debugIsSuccess())
}
}
if *cpuprofile != "" {
pprof.StopCPUProfile()
}
for i, v := range perfList {
sum := time.Duration(0)
for _, j := range v {
sum += j
}
avg := sum / time.Duration(len(v))
fmt.Printf("board index %d ", i)
fmt.Printf("average %s \n", avg)
}
}Testaus suoritettiin siten, että testien ja golang kielen käyttämät cachet olivat puhtaita. Tämä saavutettiin komennolla go clean --cache ; go clean -testcache.
Loppu tuloksia analysoin pprof työkalun luomalla svg diagrammilla. Testien diagrammit ovat tallennettuina repository:n kansioon documentation/graphs.
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceOne" -cpuprofile once.prof ; go tool pprof -web once.prof
Testi: TestPerformanceOnce
Kuva diagrammista ennen hash
Diagrammista näkee, että oikean ratkaisun löytämiseen menee noin 8 sekuntia, josta 1.21 sekuntia käytetään hash funktiossa. Joka ei tee ohjelman kannalta mitään erikoista. Funktiota käytettiin board lista muuttujien vertailuun koska jokaisen board muuttujassa olevan alkion erillinen vertailu olisi turhan raskasta. Tämän takia päätin tehdä funktion joka käyttää base64 enkoodausta esittämään board muuttujasta uniikkia avainta jonka avulla voin helposti vertailla board muuttujia. base64 enkoodaus on kuitenkin hyvin hidas tähän käyttötarkoitukseen. Siitä syystä, että sitä kutsuttiin joka kerta kun algoritmi tarkasteli uutta polkua.
Keksin, että tehokkaampi tapa esittää board muuttuja avaimena olisi käyttää jo olemassa olevaa code funktiota joka luo int pohjaisen avaimen.
Kuva diagrammista jossa käytetään code funktiota hash funktion sijaan.
Diagrammista havaitaan, että code funktion suoritukseen menee vain 0.26 sekuntia kun taas hash funktion suorittamiseen meni 1.21 sekuntia.
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceOne" -cpuprofile once.prof ; go tool pprof -web once.prof
Testi: TestPerformanceOnce
Yllä olevista diagrammeista (hash funktio deprikaatioon liittyvät diagrammit) havaitaan, että iso osa suoritusajasta menee GetValidStates funktion suorittamisesta; noin 1.5 sekuntia.
Tiedostin, että ohjelmaan ei näillä näkymin tule muiden kuin 4x4 lautojen ratkaisevia implementaatiota. Joten suorituskyvyn parantamiseksi muutin kaikki board muuttujaa käsittelevät funktiota ottamaan vain 16:sta olion pituisia board muuttujia. Tämän päivityksen ansiosta suorituskyky parani noin viisitoista prosenttia. board muuttujan pituuden muuttaminen staattiseksi vaikutti positiivisesti myös muiden funktioiden suoritusaikaan.
Diagrammi päivityksen jälkeen:
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceOne" -cpuprofile once.prof ; go tool pprof -web once.prof
Testi: TestPerformanceOnce
code funktiossa laskettiin joka suorituksella BOARD_ROW_SIZE muuttujan bittien määrä sekä board muuttujan pituus. Muutin äsken mainitut dynaamiset arvot staattisiksi arvoiksi siten, että ne lasketaan vain kerran kun ohjelma ensimmäistä kertaa konstruktoidaan. Päivitys ei vaikuttanut merkittävästi sovelluksen suoritusaikaan näin pienellä suoritus ajalla. Päivitys paransi suoritusaikaa n 3 prosenttia.
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceOne" -cpuprofile once.prof ; go tool pprof -web once.prof
Testi: TestPerformanceOnce
On ilmiselvää, että IDA* algoritmi kutsuu heuristiikka funktiota useamman kerran yhden. Diagrammeista nähdään, että Calculate funktion suorittaminen on noin 30 prosenttia koko IDA* algoritmin suoritusajasta. Memoization tekniikka on juurikin tälläisiin tarkoituksiin erittäin hyödyllinen. Käytännössä SearchState struktuurin funktio Heuristic tarkistaa onko se laskenut vielä tietylle board muuttujalle heuristiikkaa jos se on laskenut palauttaa funktio arvon suoraan muistista mikäli arvoa ei ole vielä laskettu.
Päivitys paransi algoritmin suoritusaikaa lähes 50 prosenttia. (Vertaa aikaisempaan diagrammiin, 6s/3s)
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceAverage" -cpuprofile cpu.prof ; go tool pprof -web cpu.prof
Testi: TestPerformanceAverage
En ollut vieläkään tyytyväinen IDASearch funktion suoritusaikaan. Diagrammeja tarkastellesse minulle heräsi ajatus, että vaikka SearchState.states on oleellinen muuttuja ohjelman toiminnan kannalta se ei pidä sisällään mitään uniikkia tietoa koska kaikki State pointterit ovat jo SearchState.hasSeen muuttujan sisällä vaikkakin ei oikeassa järjestykssä. hasSeen arvot voidaan kuitenkin myöhemmin järjestää oikeaan järjestykseen State.complexity olion avulla.
Kuvassa nähdään kuinka kauan keskiarvoltaan (N = 60) kahden eri board muuttujan ratkaisemiseen meni kun SearchState.states oli käytössä.
Ilman SearchState.states muuttujaa.
Kuvankaappauksesta näkyy, helpommissa ratkaisuissa suorituskyky parani n 50 prosenttia.
Komento:
go clean --cache ; go clean -testcache ; go test -run "TestPerformanceOne" -cpuprofile once.prof ; go tool pprof -web once.prof
Testi: TestPerformanceOnce
Ennen.
Diagram! Minun lempilapsi ärsyttää jälleen. GetValidStates suorittamiseen menee noin 13 prosenttia IDASearch funktion suoritusajasta. Ratkaisu löyty jälleen turhan muuttujan heivaamisesta ojaan. Tällä kertaa listalta löytyi State struktuurin muuttujassa move elänyt struktuuri Move. Move struktuuri piti sisällään tiedon mihin suuntaan boardia oltiin siirtämässä. Tämä tieto on kuitenkin irrelevantti koska walking distance heuristiikka pitää kuitenkin laskea koko boardista. Move muuttuja oli jäänne niiltä ajoilta kun IDAStar käytti invert distance heuristiikkaa.
Simsalabim! Move on poistettu ja suorituskyky parani noin 14 prosenttia. (2.6s/3s)
Diagrammista nähdään, että GetValidState on enään 8.30 prosenttia IDASearch funktion suoritusajasta (ennen 13.6 prosenttia)
Viikko aloitetiin siitä, että testillä TestPerformanceOnce IDASearch funktion suoritusaika oli 8 sekuntia ja lopetettiin siihen, että suoritusaika on 3 sekuntia. Suoritusaika parani noin 270 prosenttia.
Viikolla tuli aika paljon opittua golang kielen sisäisistä toiminnallisuuksista ja suoritusajan optimoinnista.
- Siivotaan koodi
- Lisätään dokumentointia
- Hiotaan käyttöliittymästä komia
- Esitetään demossa siisti softa.
Kiitos ja anteeks.