Kableliniai skaičiai greičiau ir kiti optimizavimai

Posted: 2018-06-16 in Darbeliai
Žymos:, , ,

Kai rašai kodą visokiems smulkiems įrenginiams, yra kelios taisyklės apie tai, kas vyksta greitai, o kas — lėtai. Esu skaitęs porą knygų, rašytų 80-aisiais, kur patyrę kompiuterastai svaigdavo apie visokius asemblerius, atminties taupymą, efektyvų registrų išnaudojimą neliečiant atminties ir taip toliau. Šiomis dienomis smulkūs įrenginiai, IoT ir apskritai įterptinis programavimas yra labai plati ir mažai matoma pasaulio pusė, kurioje galioja senosios taisyklės.

Kai kurios taisyklės yra tokios:

  • Sveikųjų skaičių sudėtis ir atimtis yra greitos operacijos
  • Bitų postūmio operacijos irgi greitos (bet ne visada)
  • Loginės and ir or bitų operacijos yra greitos
  • Loginė xor yra apylėtė
  • Daugyba yra lėtesnė, bet kartais nelabai
  • Dalyba yra lėta
  • Viskas, kas susiję su slankaus kablelio skaičiais, yra velniškai lėta

Be abejo, yra ganėtinai lėtos ir standartinės C bibliotekos, kurios dažnai naudojamos mikrovaldikliuose. Sakykim, iš printf serijos, kai reikia kažką atspausdinti į konsolę su visokiais skaičiukais ar kitais tipais. Galimybių daug, bet procesoriaus ciklų suvalgoma irgi nemažai.

Truputuką apie postūmio operacijas. Jos kartais gali pakeisti daugybą ir dalybą, kai dauginam/dalinam iš dvejeto laipsnių: 2, 4, 8 ir pan. Na, nes skaičiavimo sistema yra dvejetainė, čia viskas aišku. Bet niuansas yra toks, kad ne visi maži procesoriukai sugeba pastumti skaičių per kelis bitus vieno ciklo metu. Sakykim, tokie yra AVR procesoriai. ARM, tuo tarpu, stumdo skaičius per vieną ciklą. Plius, ARM Cortex-M valdikliukai yra 32 bitų, tai tokius skaičius ir stumdo. O AVR yra 8 bitų, didesnės apimties skaičius (16, 32 bitų) jis turi apdoroti per kelis kartus, kaip atskirus 8 bitų skaičius. Tai dar labiau sulėtina operacijas.

Tačiau jei imsim 8 bitų skaičiuką AVR procesoriuje, tai bitų postūmis per pozicijų turės O(n) našumą procesoriaus ciklų atžvilgiu. Kiek bitų stumiam, tiek ciklų. Todėl programuojant AVR procesoriukus verta turėt tai galvoje ir jei įmanoma, „apsukti“ bitų stūmimo operacijas, jei reikia jas kelias daryti paeiliui. Apie šitą AVR savybę kažkada ir Levas gerai parašė su konkrečiais pavyzdžiais. ARM tuo tarpu našumas yra O(1). T.y. jam nesvarbu, per kiek pozicijų stumiam skaičiuką, vienas ciklas ir done.

O šitas įrašas tai apie snprintf panaudojimą spausdinti kablelinius skaičius, floating point. Jeigu to reikia, aišku. Paprastai nereikia, bet maža kas. Kartais norisi. Plius, GCC tiek AVR, tiek ARM pagal nutylėjimą %f placeholderio neinterpretuoja, reikia specialiai papildomus flagus uždėt. Tada kažką ten papildomo iš C bibliotekų įdeda. Firmwarės išsipučia keliais kilobaitais (!), o spausdinimas numatomai lėtas.

Sakykim, jums mirtinai reikia spausdinti FP skaičius, bet firmwarė ir taip jau ant ribos, įjungti %f palaikymą — per brangu. Ką daryt?

Užsikurti laboratoriją:

STM32F107 procesoriukas | Darau, blė

Pati svarbiausia taisyklė: neišradinėti savų algoritmų. Ypač su floating point. Tai yra pointless. Galima nusigriauti kokią idėją arba imti labai elementarų variantą. Tad ką daryt…

Nugi ką daryt, skaidyt, be abejo, FP į dvi sveikas dalis. Nukenčia tikslumas! Bet nereikia pūsti firmwarės, o veikia kiek greičiau. Aš dabar dar be kodo pavyzdžių pateiksiu STM32F107 procesoriuko ciklų skaičius spausdinant su %f ir su mano paties naudojamu variantu:

========= Test the float printing =========

========= Test the number 24.500993729 =========
Standard representation, 5 dec. places: 24.50099
QuickInt representation, 5 dec. places: 24.50099

== Standard results: 7776.0800000 cycles avg
== QuickInt results: 3093.0000000 cycles avg

========= Test the number -94.009437561 =========
Standard representation, 5 dec. places: -94.00944
QuickInt representation, 5 dec. places: -94.00943

== Standard results: 7170.0800000 cycles avg
== QuickInt results: 3293.0000000 cycles avg

========= Test the number 211885.093750000 =========
Standard representation, 5 dec. places: 211885.09375
QuickInt representation, 5 dec. places: 211885.09375

== Standard results: 9377.0800000 cycles avg
== QuickInt results: 3308.0000000 cycles avg

========= Test the number -4877651.000000000 =========
Standard representation, 5 dec. places: -4877651.00000
QuickInt representation, 5 dec. places: -4877651.00000

== Standard results: 9489.0800000 cycles avg
== QuickInt results: 3496.0000000 cycles avg

========= Test the number 0.000000000 =========
Standard representation, 5 dec. places: 0.00000
QuickInt representation, 5 dec. places: 0.00000

== Standard results: 2664.0800000 cycles avg
== QuickInt results: 3251.0000000 cycles avg

Įdomu, kad mano variantas dauguma atvejų bent dvigubai spartesnis ciklų požiūriu. Išskyrus nuliuką, ten turbūt koks tai paoptimizavimas yra 🙂 Pas mane jo nėr.

Aha, o ką aš dariau? Maždaug taip: pradžiai iš FP padarau sveiką skaičių, atspausdinu su %li. Tada dauginu likutį iš 100000 ir po taško spausdinu su %lu. Tiesa, jei likutis neigiamas, reikia dar iš vieneto daugint. Arba būtų galima „apversti“ kitaip, bet patingėjau. Gaunasi penki skaičiukai po kablelio. Tikslumas kai kuriais atvejais skiriasi, bet spausdinimui to pakanka, bent jau man taip atrodo.

Kodas toks. Pora makrosų:

#define __QFFMT__ "%li.%05lu\n"
#define __QF__(f) (int32_t)f, (uint32_t)(((f<0)?-1.0:1.0)* (f - (int32_t)f)*100000)

Naudojimas:

snprintf(buf, BUF_SZ, "QuickInt representation, 5 dec. places: "__QFFMT__"\r\n", __QF__(test[fnum]));

Čia toks visiškai elementarus ir nemoksliškas metodas. Yra visai gerų metodų, kaip gerokai greičiau paversti sveikus skaičius iš dvejetainių į dešimtainius, tik reikia tam atminties skirti ir su buferiais pažaisti. Yra ir kažkoks neseniai sugalvotas algoritmas Grisu3, naudojamas JSON bibliotekose Arduino. Senieji drakonai (Dragon3, Dragon4) naudojami ir C bibliotekose. Patiems skaičiavimams atlikti yra galimybė naudojant „netikrus“ kablelinius skaičius vienam kintamajame laikant sveiką skaičių, kitame — mantisę.

Apskritai slankaus kablelio skaičiai yra bjaurus reikalas. Kažkada aš buvau visai gerai į juos įsigilinęs ir netgi dešimtainių skaičių emuliavimą po kablelio kažkiek įkirtęs. Realiai juk kablelinio dvejetainio skaičiaus į dešimtainį paversti neįmanoma, kapitaliai neatitinka skaičiavimo sistemos. Koks nors 0,9 į floating point negali būti atvaizduojamas. Geriausiu atveju bus ten kažkas 0,9000000xxxxxxxxx. Apgaudinėja mus, trumpai tariant. Bet ką daryt.

Tai tiek blevyzgų šiam kartui.

Reklama
Komentarai
  1. 80-ju sapnas parašė:

    nelinkiu susapnuoti kosmaro, kai procesoriui reikia triju itampu, kai jis yra tik 8 bitu, jo daznis 2.4Mhz, kai 16 kByte RAM atminties plokste yra A4 formato dydzio, kai norint irasyti programa i EEPROMa ji reikia islupti is lizdo, pakisti po UV lempa ir tik tada, istacius i programatoriu, kuriam reikia 24V, irasyti 2kByte porcija. Stai todel ir programavo chebra tik su asembleriu, ir tai buvo visai normalu.

Parašykite komentarą

Įveskite savo duomenis žemiau arba prisijunkite per socialinį tinklą:

WordPress.com Logo

Jūs komentuojate naudodamiesi savo WordPress.com paskyra. Atsijungti /  Keisti )

Google photo

Jūs komentuojate naudodamiesi savo Google paskyra. Atsijungti /  Keisti )

Twitter picture

Jūs komentuojate naudodamiesi savo Twitter paskyra. Atsijungti /  Keisti )

Facebook photo

Jūs komentuojate naudodamiesi savo Facebook paskyra. Atsijungti /  Keisti )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.