{"id":33793,"date":"2019-10-31T21:54:42","date_gmt":"2019-10-31T18:54:42","guid":{"rendered":"https:\/\/prohoster.info\/blog\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\/"},"modified":"2019-10-31T21:54:42","modified_gmt":"2019-10-31T18:54:42","slug":"bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","status":"publish","type":"post","link":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","title":{"rendered":"Bitmap-indeksid Go-s: otsimine metsiku kiirusel","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h2>Sissejuhatav s\u00f5na<\/h2>\n<p>\nEsitasin selle ettekande inglise keeles konverentsil GopherCon Venemaa 2019 Moskvas ja vene keeles kohtumisel Nizhni Novgorodis. R\u00e4\u00e4gin bitmap-indeksist \u2014 v\u00e4hem levinud, kui B-puu, kuid mitte v\u00e4hem huvitav. Jagatud <noindex><a rel=\"nofollow\" href=\"https:\/\/youtu.be\/WvlUH6MjUuI?list=PL3xVZC4USRNSO_kb2lh_J_no6C-KJ7Phg\">salvestus<\/a><\/noindex> ettekandest konverentsil inglise keeles ja tekstiline t\u00f5lge vene keeles.<\/p>\n<p>K\u00e4sitleme, kuidas bitmap-indeks t\u00f6\u00f6tab, millal on see parem, millal halvem kui teised indeksid ja millal on see neist oluliselt kiirem; n\u00e4eme, millistes populaarsetes andmebaasis\u00fcsteemides juba on bitmap-indekseid; proovime kirjutada oma Go-s. Ja \u201emagustoiduks\u201c kasutame valmis raamatukogusid, et luua oma superkiire spetsialiseeritud andmebaas.<\/p>\n<p>Loodan t\u00f5eliselt, et mu t\u00f6\u00f6 leidub teile kasulik ja huvitav. L\u00e4hme!<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>Sissejuhatus<\/h2>\n<p>\n<center><div class=\"youtube-placeholder\" data-id=\"WvlUH6MjUuI\" onclick=\"loadVideo(this)\">\r\n        <img decoding=\"async\" src=\"https:\/\/img.youtube.com\/vi\/WvlUH6MjUuI\/hqdefault.jpg\" alt=\"M\u00e4ngi videot\" loading=\"lazy\" width=\"480\" height=\"360\" style=\"width:100%;height:auto;\">\r\n        <div class=\"play-button\"><\/div>\r\n    <\/div><\/center><br \/>\n<noindex><a rel=\"nofollow\" href=\"http:\/\/bit.ly\/bitmapindexes\">http:\/\/bit.ly\/bitmapindexes<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/mkevac\/gopherconrussia2019\">https:\/\/github.com\/mkevac\/gopherconrussia2019<\/a><\/noindex><\/p>\n<p>Tere k\u00f5igile! On kuus \u00f5htul, me k\u00f5ik oleme \u00fcliv\u00e4sinud. Suurep\u00e4rane aeg r\u00e4\u00e4kida igavast andmebaasi indeksite teooriast, eks? \u00c4rge muretsege, mul on siin ja seal paar rida algkoodi. \ud83d\ude42<\/p>\n<p>T\u00f5siselt r\u00e4\u00e4kides, ettekande on informatsiooni t\u00e4is, kuid meie aega pole palju. Seega alustame.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/e778e13727700f0335a4b5558a0d8db3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nT\u00e4na r\u00e4\u00e4gin j\u00e4rgmistest teemadest:<\/p>\n<ul>\n<li>mis on indeksid;\n<\/li>\n<li>mis on bitmap-indeks;\n<\/li>\n<li>kus seda kasutatakse ja kus ei kasutata ning miks;\n<\/li>\n<li>lihtne rakendus Go-s ja natuke v\u00f5itlust kompilaatoriga;\n<\/li>\n<li>veidi v\u00e4hem lihtne, kuid palju t\u00f5husam rakendus Go-assembleril;\n<\/li>\n<li>\"probleemid\" bitmap-indeksitega;\n<\/li>\n<li>olemasolevad rakendused.\n<\/li>\n<\/ul>\n<h2>Mis siis on indeksid?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/b80e5b990c44814afe9150a9a82351fd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nIndeks on eraldiseisev andmestruktuur, mida hoiame ja uuendame peamise andmekogumi lisana. Seda kasutatakse otsingu kiirendamiseks. Ilma indeksiteta n\u00f5uaks otsing andmete t\u00e4ielikku l\u00e4bimist (protsess, mida nimetatakse full scaniks), ja selle protsessi algoritmiline keerukus on lineaarne. Kuid andmebaasid sisaldavad tavaliselt tohutul hulgal andmeid, ning lineaarne keerukus \u2014 see on liiga aeglane. Ideaalis tahaksime saavutada logaritmilise v\u00f5i konstantse.<\/p>\n<p>See on tohutu keeruline teema, t\u00e4is n\u00fcansse ja kompromisse, kuid vaadates aastate jooksul eri andmebaaside arengut ja uurimist, olen valmis v\u00e4itma, et andmebaasi indeksite loomiseks on vaid m\u00f5ned laialdaselt kasutatavad l\u00e4henemisviisid.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/08a74dbb365035cd99bc94d72644a1b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nEsimene l\u00e4henemine h\u00f5lmab otsingupiirkonna hierarhilist v\u00e4hendamist, jagades otsingupiirkonna v\u00e4iksemateks osadeks.<\/p>\n<p>Tavaliselt teeme seda erinevat t\u00fc\u00fcpi puude abil. N\u00e4iteks v\u00f5ib tuua suure kasti materjalidega teie riidekapis, mis sisaldab v\u00e4iksemaid kaste, mis on jaotatud erinevate teemade j\u00e4rgi. Kui vajate materjale, siis otsite kindlasti materjalide sildiga kastist, mitte k\u00fcpsiste sildiga kastist, eks?<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/423fac47c748980b18af434644af4dae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nTeine l\u00e4henemine on kohe vajaliku elemendi v\u00f5i elementide r\u00fchma eristamine. Teeme seda hash-map'ide v\u00f5i p\u00f6\u00f6rdindeksite abil. Hash-map'ide kasutamine sarnaneb eelnevale n\u00e4itele, ainult et teie kapis on hulk v\u00e4ikseid kaste l\u00f5plike esemete kogumitega.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/088fed0a2a0feea4a23edbf0ca654805.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nKolmas l\u00e4henemine on vabaneda otsingu vajadusest. Selle teeme Bloom-filtrite v\u00f5i cuckoo-filtrite abil. Esimesed annavad vastuse kohe, vabastades teid otsimise kohustusest.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/493bc4f20baacc0a5dc0faf15cc46285.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nViimane l\u00e4henemine on t\u00e4ielikult kasutada k\u00f5iki v\u00f5imeid, mida t\u00e4nap\u00e4evane riistvara meile pakub. Just seda teeme bitmap-inde\u0445ite abil. Jah, nende kasutamisel tuleb meil m\u00f5nikord kogu indeks l\u00e4bi k\u00e4ia, kuid teeme seda \u00fclimalt efektiivselt.<\/p>\n<p>Kuidas ma juba \u00fctlesin, on andmebaasi indeksite teema ulatuslik ja t\u00e4is kompromisse. See t\u00e4hendab, et m\u00f5nikord saame kasutada mitut l\u00e4henemist korraga: kui peame otsingut veelgi kiiremaks muutma v\u00f5i kui on vaja katab k\u00f5iki v\u00f5imalikke otsingut\u00fc\u00fcpe.<\/p>\n<p>T\u00e4na r\u00e4\u00e4gin ma k\u00f5ige v\u00e4hem tuntud l\u00e4henemisest - bitmap-inde\u0445itest.<\/p>\n<h2>Kes ma olen, et sellest teemast r\u00e4\u00e4kida?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/42a9d17a507c392bc202254a92dfaf41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nT\u00f6\u00f6tan meeskonnajuhina Badoos (v\u00f5ib-olla tunnete paremini meie teist toodet - Bumble). Meil on \u00fcle 400 miljoni kasutaja \u00fcle kogu maailma ja palju funktsioone, mis aitavad leida neile parima kaaslase. Teeme seda kohandatud teenuste abil, mis kasutavad sealhulgas ka bitmap-inde\u0445ite.<\/p>\n<h2>Mis siis on bitmap-indeks?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/14f20f3697a20c02f6b3510dc7f0ae4d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmap-indeksid, nagu nimigi \u00fctleb, kasutavad bitmape v\u00f5i bits\u00fcste, et rakendada otsinguindeksit. K\u00f5rgselt vaadatuna koosneb see indeks \u00fchest v\u00f5i mitmest sellisest bitmapist, mis esindavad teatud entiteete (nt inimesi) ja nende omadusi v\u00f5i parameetreid (vanus, silmade v\u00e4rv jne), ning algoritmist, mis kasutab bititehteid (AND, OR, NOT) otsingu p\u00e4ringule vastamiseks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/f815720330a51b1f0798e45d23160d3b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMeile \u00f6eldakse, et bitmap-indeksid sobivad k\u00f5ige paremini ja on v\u00e4ga t\u00f5husad olukordades, kus otsingu k\u00e4igus \u00fchendatakse p\u00e4ringud paljude v\u00e4hekaariliste veergudega (kujuta ette \u201esilmade v\u00e4rv\u201d v\u00f5i \u201epereliikmeid\u201d v\u00f5rreldes millegagi nagu \u201ekaugus linna keskpunktist\u201d). Kuid hiljem n\u00e4itan ma, et need toimivad suure kaardinaalsusega veergude puhul samuti suurep\u00e4raselt.<\/p>\n<p>Vaatame lihtsaimat bitmap-indeksi n\u00e4idet.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/33fe23476e0931c10345d7175b83d68b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKujutage ette, et meil on nimekiri Moskva restoranidest, millel on binaarsed omadused nagu need:<\/p>\n<ul>\n<li>l\u00e4hedal metroo (near metro);\n<\/li>\n<li>on privaatne parkla (has private parking);\n<\/li>\n<li>on terrass (has terrace);\n<\/li>\n<li>on v\u00f5imalik broneerida laud (accepts reservations);\n<\/li>\n<li>sobib taimetoitlastele (vegan friendly);\n<\/li>\n<li>kallis (expensive).\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/fcbad539ea12f79a9d06966ce308637e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAndke igale restoranile j\u00e4rjekorranumber alates 0 ja reserveerime m\u00e4lu 6 bitmapi jaoks (\u00fcks igas omaduses). Seej\u00e4rel t\u00e4idame need bitmaps s\u00f5ltuvalt sellest, kas restoran omab antud omadust v\u00f5i mitte. Kui restoranil 4 on terrass, siis bit nr 4 bitmapsis \u201eon terrass\u201d seatakse 1 (kui terrassi pole, siis 0).<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/3709c426617d4364f392ee6b68f92b00.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nN\u00fc\u00fcd on meil k\u00f5ige lihtsam v\u00f5imalik bitmap-indeks, ja me saame seda kasutada k\u00fcsimustele vastamiseks, nagu:<\/p>\n<ul>\n<li>\u201eN\u00e4ita mulle restorane, mis sobivad taimetoitlastele\u201d;\n<\/li>\n<li>\u201eN\u00e4ita mulle odavaid restorane terrassiga, kus on v\u00f5imalik broneerida laud\u201d.\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/90acb0f890686bd52c3db1fc667f0b0b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/0fd0b7fe9f7b7039022ad5c79fe873bc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKuidas? Vaatame. Esimene p\u00e4ring on v\u00e4ga lihtne. K\u00f5ik, mida me vajame, on v\u00f5tta bitmap \u201esobib taimetoitlastele\u201d ja muuta see restoranide nimekirjaks, kelle bitid on seatud.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ef4a5cfd658ff4ef8bc0c638c4522d11.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/9cc175bae55c16018fdf5ff95517a61a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTeine p\u00e4ring on veidi keerulisem. Peame kasutama BIT operatsiooni NOT bitimapis \"kallis\", et saada odavate restoranide nimekiri, seej\u00e4rel AND-ime selle \"saab broneerida\" bitimapiga ja AND-ime tulemuse \"on terrass\" bitimapiga. Tulemuseks olev bitimap sisaldab nimekirja asutustest, mis vastavad k\u00f5igile meie kriteeriumidele. Sel juhul on see ainult restoran \"Noorus\".<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/f1cdda0cbf7f15278553899cf876c17e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/126b50e0f622b6e36c461cd74e708c38.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSiin on palju teooriat, kuid \u00e4rge muretsege, me n\u00e4eme varsti koodi.<\/p>\n<h2>Kus kasutatakse bitmap-indekseid?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/406132236c71a4f66ae79957b6e633b3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKui te \"googeldaksite\" bitmap-indekseid, siis 90% vastustest oleksid vahetult seotud Oracle DB-ga. Kuid teised andmebaasid toetavad kindlasti ka sellist \u00e4gedat funktsiooni, eks? <\/p>\n<p>Vaatame \u00fcle peamised kahtlusalused.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/d18d66451a8a26b0ddf121f8ec0204cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMySQL ei toeta veel bitmap-indekseid, kuid on olemas ettepanek selle funktsiooni lisamiseks (<noindex><a rel=\"nofollow\" href=\"https:\/\/dev.mysql.com\/worklog\/task\/?id=1524\">https:\/\/dev.mysql.com\/worklog\/task\/?id=1524<\/a><\/noindex>).<\/p>\n<p>PostgreSQL ei toeta bitmap-indekseid, kuid kasutab lihtsaid bitimappe ja bitoperatsioone mitmete teiste indeksite otsingutulemuste \u00fchendamiseks.<\/p>\n<p>Tarantoolil on bitset-indeksid, mis toetavad lihtsat otsingut nende kaudu.<\/p>\n<p>Redis'il on lihtsad bitiv\u00e4ljad<noindex><a rel=\"nofollow\" href=\"https:\/\/redis.io\/commands\/bitfield\"> (https:\/\/redis.io\/commands\/bitfield<\/a><\/noindex>) ilma v\u00f5imaluseta nende kaudu otsida.<\/p>\n<p>MongoDB ei toeta veel bitmap-indekseid, kuid ka selle jaoks on olemas ettepanek selle funktsiooni lisamiseks. <noindex><a rel=\"nofollow\" href=\"https:\/\/jira.mongodb.org\/browse\/SERVER-1723\">https:\/\/jira.mongodb.org\/browse\/SERVER-1723<\/a><\/noindex><\/p>\n<p>Elasticsearch kasutab bitimappe sees.<noindex><a rel=\"nofollow\" href=\"https:\/\/www.elastic.co\/blog\/frame-of-reference-and-roaring-bitmaps\"> (https:\/\/www.elastic.co\/blog\/frame-of-reference-and-roaring-bitmaps<\/a><\/noindex>).<\/p>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/232d335963603d6e6dec98839fc9f486.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<ul>\n<li>Kuid meie majas on uus naaber: Pilosa. See on uus mitte-relationaalne andmebaas, mis on kirjutatud Go keeles. See sisaldab ainult bitmap-indekseid ja p\u00f5hineb t\u00e4ielikult nende peal. R\u00e4\u00e4gime temast hiljem.\n<\/li>\n<\/ul>\n<h2>T\u00e4itmine Go keeles<\/h2>\n<p>\nAga miks bitmap-indekseid nii harva kasutatakse? Enne sellele k\u00fcsimusele vastamist tahaksin n\u00e4idata teile v\u00e4ga lihtsa bitmap-indeksi rakendust Go keeles.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ae7f4c1a4a740fe709b05dfaee27ac9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitimapid koosnevad tegelikult lihtsalt andmeplokkidest. Go-s kasutame selleks baitide slice'e.<\/p>\n<p>Meil on \u00fcks bitimap \u00fche restorani omaduse jaoks, ja iga bit bitimapis n\u00e4itab, kas konkreetses restoranis on see omadus v\u00f5i mitte.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/1ab628ee15887d6b3c6c99855aa610c8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMe vajame kahte abifunktsiooni. \u00dcks neist kasutatakse meie bitmapside t\u00e4itmiseks juhuslike andmetega. Juhuslike, kuid teatud t\u00f5en\u00e4osusega, et restoranil on iga omadus. N\u00e4iteks arvan, et Moskvas on v\u00e4ga v\u00e4he restorane, kus ei saa lauda broneerida, ja mulle tundub, et umbes 20% asutustest sobivad taimetoitlastele.<\/p>\n<p>Teine funktsioon muundab bitmapi restoranide nimekirjaks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ab9c87a0ba63750116e2e7968f842a9a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/498cf7a33611d99b90197d4ee82e2834.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEt vastata p\u00e4ringule \"N\u00e4ita mulle odavaid restorane, kus on terrass ja kus saab lauda broneerida\", vajame kahte bititegevust: NOT ja AND.<\/p>\n<p>Saame meie koodi veidi lihtsustada, kasutades keerukamat operaatori AND NOT.<\/p>\n<p>Meil on igasuguste nende tegevuste jaoks funktsioonid. M\u00f5lemad l\u00e4bivad viipeid, v\u00f5tavad vastavad elemendid iga\u00fches ning \u00fchendavad need bititegevuse abil ja panevad tulemuse tulemuslikku viipesse.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ec5652a34f0370dfb03df199f341f153.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJa n\u00fc\u00fcd saame kasutada meie bitmapsid ja funktsioone, et vastata otsingup\u00e4ringule.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/cf9500ccfe75995a6008191c16729689.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJ\u00f5udlus ei ole nii k\u00f5rge, isegi hoolimata sellest, et funktsioonid on v\u00e4ga lihtsad ja me oleme oluliselt kokku hoidnud, kuna ei tagastanud igal funktsiooni kutsumisel uut tulemuslikku viipi.<\/p>\n<p>P\u00e4rast m\u00f5ningast profilimist pprof-iga m\u00e4rkasin, et Go kompilaator j\u00e4ttis \u00fche v\u00e4ga lihtsa, kuid \u00e4\u00e4rmiselt olulise optimeerimise vahele: funktsiooni inlining.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/9092f5ba3940d0a4f3fbfa90b364d716.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nFakt on selles, et Go kompilaator kardab kohutavalt viipeid, mis l\u00e4bivad viipeid, ja keelab kategooriliselt inlining funktsioonide jaoks, mis sisaldavad selliseid silke.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/d1bddd62b61b367dd1f680f223fa0ce7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAga mina ei karda ja saan petta kompilaatorit, kasutades goto silmuse asemel, nagu vanad head ajad.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/5b1c3cb26b923972686047910ecd1c31.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/1ca31d12dc90931b674c6a86a4ea23bd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nJa nagu n\u00e4ete, kompilaator on n\u00fc\u00fcd r\u00f5\u00f5muga inlining meie funktsiooni! L\u00f5puks \u00f5nnestub meil kokku hoida umbes 2 mikrosekundit. Pole paha!<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/bdd6735d16082573e600bffe2cdd5662.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nTeine kitsaskoht on lihtne n\u00e4ha, kui vaatate assembleri v\u00e4ljundit hoolikalt. Kompilaator lisas meie k\u00f5ige kuumema silmuse sisse viipi piiride kontrolli. Fakt on selles, et Go on turvaline keel, kompilaator kardab, et minu kolm argumenti (kolm viipi) on erineva suurusega. Siis v\u00f5ib teoreetiliselt tekkida niinimetatud puhveri \u00fclevool (buffer overflow).<\/p>\n<p>L\u00e4hme rahustame kompilatsiooniprogrammi, n\u00e4idates talle, et k\u00f5ikide l\u00f5ikude suurused on samad. Saame seda teha, lisades meie funktsiooni algusesse lihtsa kontrolli.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/59b4ce687a11dd653e9f12fc3130d89a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSeda n\u00e4hes suudab kompilatsiooniprogramm r\u00f5\u00f5muga kontrolli m\u00f6\u00f6da lasta ning me s\u00e4\u00e4stame l\u00f5puks veel 500 nanosekundit.<\/p>\n<h2>Suured partiid<\/h2>\n<p>\nOlgu, oleme suutnud meie lihtsast rakendusest mingitki j\u00f5udlust v\u00e4lja pigistada, kuid see tulemus on tegelikult palju halvem, kui praeguse riistvara puhul v\u00f5imalik oleks.<\/p>\n<p>K\u00f5ik, mida me teeme, on p\u00f5hised bititegevused ning meie protsessorid t\u00e4idavad neid v\u00e4ga t\u00f5husalt. Kuid kahjuks \u201etoidame\u201d oma protsessorit v\u00e4ga v\u00e4ikeste t\u00f6\u00f6osadega. Meie funktsioonid teostavad toimingud baitide kaupa. Saame koodi v\u00e4ga lihtsalt timmida, et see t\u00f6\u00f6taks 8-baidiste t\u00fckkidega, kasutades UInt64 l\u00f5ike.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/8d1b60ba4b7046c836601631cadd0b6a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nNagu n\u00e4ete, kiirendas see v\u00e4ike muudatus meie programmi kaheksa korda, suurendades partiid kaheksa korda. Kasutame, v\u00f5ib \u00f6elda, lineaarset kasu.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/0fc663412d04dd38b927de5c8776f69d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Assemblerskeemide rakendamine<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/b3ef133167b89da983356b1c7389aecd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAga see pole veel l\u00f5pp. Meie protsessorid saavad t\u00f6\u00f6tada 16, 32 ja isegi 64 baitiste t\u00fckkidega. Selliseid \u201elaiade\u201d toimingute nimetatakse single instruction multiple data (SIMD; \u00fcks k\u00e4sk, palju andmeid), ja protsessi, millega kodeerimist selliselt muudetakse, et see kasutaks selliseid toiminguid, nimetatakse vektoriseerimiseks.<\/p>\n<p>Kahjuks ei ole Go kompilaator vektoriseerimises just kiitust v\u00e4\u00e4rt. Praeguseks on ainus viis Go koodi vektoriseerimiseks luua ja sisestada andmed k\u00e4sitsi Go assembleriga.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/91278be45df67e1f9572d68fab7ebad1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nGo assembler on kummaline olend. Teate kindlasti, et assembler on midagi, mis on tugevalt seotud arvuti arhitektuuriga, mille jaoks te kirjutate, kuid Go puhul pole see nii. Go assembler sarnaneb rohkem IRL (intermediate representation language) v\u00f5i vahekeelele: see on praktiliselt platvormidevaheline. Rob Pike tegi sellel teemal suurep\u00e4rase <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/watch?v=KINIAgRpkDA\">ettekanne<\/a><\/noindex> esituse m\u00f5ned aastat tagasi GopherConil Denveris.<\/p>\n<p>Lisaks sellele kasutab Go ebatavalist Plan 9 formaati, mis erineb \u00fcldtunnustatud AT&amp;T ja Intel formaatidest.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/526f75eb18edfc2f851f2725e9d6f69e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSaab kindlalt \u00f6elda, et Go assembleri k\u00e4sitsi kirjutamine ei ole just k\u00f5ige l\u00f5busam tegevus.<\/p>\n<p>Aga \u00f5nneks on olemas juba kaks k\u00f5rgema taseme t\u00f6\u00f6riista, mis aitavad meid Go assembleri kirjutamisel: PeachPy ja avo. M\u00f5lemad t\u00f6\u00f6riistad genereerivad Go assemblerit k\u00f5rgema taseme koodist, mis on kirjutatud vastavalt Pythonis ja Go-s.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/b8a7aa2c585b805e9b1f2ada186b84e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNeed this utilities simplifies tasks like register allocation, writing loops, and overall simplifies the entry into the world of assembly programming in Go.<\/p>\n<p>We'll be using avo, so our programs will be almost typical Go programs.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/128e4adef14e5f2cf00fb5b6302ef58e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHere's what the simplest example of an avo program looks like. We have a main() function that defines an Add() function inside it, which is responsible for adding two numbers. There are helper functions to get parameters by name and to acquire one of the free and suitable CPU registers. Each CPU operation has a corresponding function in avo, as seen with ADDQ. Finally, we see a helper function to store the resulting value.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/01ccaa6aa6d394ef598ea2dbc9257d87.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBy calling go generate, we will execute the program on avo and ultimately two files will be generated:<\/p>\n<ul>\n<li>add.s with the resulting code in Go assembly;\n<\/li>\n<li>stub.go with function headers to link the two worlds: Go and assembly.\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/72a9443776ecf45eef6fb97a4e08acba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNow that we've seen what avo does and how it works, let's take a look at our functions. I have implemented both scalar and vector (SIMD) versions of the functions.<\/p>\n<p>First, let's look at the scalar versions.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ec31dbb8b97b9d7c1012a120fa18cdaf.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAs in the previous example, we request a free and appropriate general-purpose register, and we don\u2019t need to compute offsets and sizes for the arguments. All of that is handled by avo for us.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/88085e927dd943ea0f808a28fb3ccf9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPreviously we used labels and goto (or jumps) to boost performance and trick the Go compiler, but now we do it from the get-go. The thing is, loops are a higher-level concept. In assembly, we only have labels and jumps.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/9a4181248eb279d89c1445a820b06649.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nThe remaining code should already be familiar and clear. We emulate a loop with labels and jumps, take a small part of data from our two slices, combine them using a bitwise operation (AND NOT in this case) and then place the result in the resulting slice. That's it.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/19275ead27f63092fc6596bed38a8d03.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHere\u2019s what the final code in assembly looks like. We didn't need to calculate offsets and sizes (highlighted in green) or track the used registers (highlighted in red).<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ed68528a6f852634a5b536670c6315f0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKui v\u00f5rrelda assembleri rakenduse j\u00f5udlust parima Go rakenduse j\u00f5udlusega, siis n\u00e4eme, et need on samad. Ja see on ootusp\u00e4rane. Me ei teinud midagi erilist \u2014 me lihtsalt taasesitasime seda, mida teeks Go kompilaator.<\/p>\n<p>Kahjuks ei saa me sundida kompilaatorit inline'ima meie assembleris kirjutatud funktsioone. Go kompilaatoril puudub praegu see v\u00f5imalus, kuigi palve selle lisamiseks on eksisteerinud juba \u00fcsna kaua.<\/p>\n<p>Seet\u00f5ttu ei suuda me saada mingit kasu v\u00e4ikestest funktsioonidest assembleris. Peame kas kirjutama suuri funktsioone, kasutama uut math\/bits paketti v\u00f5i v\u00e4ltima assemblerit.<\/p>\n<p>Vaadakem n\u00fc\u00fcd meie funktsioonide vektorkoopiaid.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/7f67c3cc855908fb47c7900d6e5d7f54.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nK\u00e4esolevas n\u00e4ites otsustasin rakendada AVX2, seega kasutame 32-bitiste t\u00fckkidega t\u00f6\u00f6tavaid operatsioone. Koodistruktuur on v\u00e4ga sarnane skalaari variandile: parameetrite laadimine, palve anda meile tasuta \u00fcldregister jne.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/021e0424a0d733ec7db9edeb98ce1f65.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n\u00dcks uuendus on seotud sellega, et laiemad vektorioperatsioonid kasutavad spetsiaalseid laiu registreid. 32-bitiste t\u00fckkide puhul on need registrid, mille eelotsik on Y. Just seet\u00f5ttu n\u00e4ete koodis funktsiooni YMM(). Kui oleksin kasutanud AVX-512 64-bitiste t\u00fckkidega, siis oleks eelotsik Z.<\/p>\n<p>Teine uuendus tuleneb sellest, et otsustasin kasutada optimeerimist, mida nimetatakse ts\u00fckli lahtimurdmiseks (loop unrolling), see t\u00e4hendab, et tegin kaheksa ts\u00fckli operatsiooni k\u00e4sitsi, enne kui h\u00fcppasin ts\u00fckli algusesse. See optimeerimine v\u00e4hendab koodis harude (branch) arvu ning on piiratud vaba registreid, mis on saadaval.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/f54631d9e8c69f6f70ecace3133ae1e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAga kuidas on j\u00f5udlusega? See on suurep\u00e4rane! Saime kiiruskasvu ligikaudu seitsme v\u00f5rra v\u00f5rreldes parima lahendusega Go-s. Muljetavaldav, kas pole?<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/d7e85c933eecb243cfb49225b4d92c6c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAga isegi seda rakendust oleks potentsiaalselt v\u00f5imalik kiirendada, kasutades AVX-512, prefet\u0161imist v\u00f5i JIT (just-in-time compiler) p\u00e4ringute planeerimise jaoks. Kuid see on juba t\u00e4iesti eraldi ettekande teema.<\/p>\n<h2>Bitmap-indeksite probleemid<\/h2>\n<p>\nN\u00fc\u00fcd, kui oleme vaadanud Go lihtsat bitmap-indeksi rakendust ja palju efektiivsemat assembleris, r\u00e4\u00e4gime l\u00f5puks sellest, miks bitmap-indeksid on nii harva kasutusel.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/83d36a5c92ba90fd680fe8afb6cfc11f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVanades teadusartiklites mainitakse bitmap-indeksite kolme probleemi, kuid uuemad teadusartiklid ja mina v\u00e4idame, et need on juba aegunud. \u00c4rme s\u00fcvene s\u00fcgavale igasse neist probleemidest, vaid k\u00e4sitleme neid pinnapealselt.<\/p>\n<h2>Suure kardinaalsuse probleem<\/h2>\n<p>\nNii \u00fctlevad meile, et bitmap-indeksid sobivad ainult v\u00e4ikese kardinaalsusega v\u00e4ljadele, st v\u00e4ljadele, millel on v\u00e4he v\u00e4\u00e4rtusi (nt sugu v\u00f5i silmade v\u00e4rv), ja p\u00f5hjus on see, et tavaline esitus nende v\u00e4ljade puhul (\u00fcks bitt v\u00e4\u00e4rtuse kohta) suurte kardinaalsuste korral koosneb liiga suurest mahust ning pealegi on need bitmap-indeksid halvasti (harva) t\u00e4idetud.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/0787efc4d2cb4ea4d404ca7888b33697.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/44ab4bc7c25d14fe2f53caf5d9da399d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nM\u00f5nikord v\u00f5ime kasutada teistsugust esitust, n\u00e4iteks standardset, mida me kasutame arvude esitlemiseks. Kuid alles tihendamisalgoritmide ilmumine muutis k\u00f5ike. Viimase paarik\u00fcmne aasta jooksul on teadlased ja uurijad v\u00e4lja m\u00f5elnud palju tihendamisalgoritme bitmapide jaoks. Nende peamine eelis on see, et bitmapide dekopeerimine pole bititegevuste l\u00e4biviimiseks vajalik \u2013 me saame teostada bititegevusi otse tihendatud bitmapide peal.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/ecb54fbf15aa11271bbbab01ecbda880.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nViimasel ajal on hakanud ilmuma ka h\u00fcbriidmeetodeid, nagu n\u00e4iteks roaring bitmapid. Need kasutavad samaaegselt kolme erinevat esitusviisi bitmapide jaoks \u2013 otseselt bitmapid, massiivid ja nn bitituksid \u2013 ja tasakaalustavad nende vahel, et maksimeerida j\u00f5udlust ja minimeerida m\u00e4lutarvet.<\/p>\n<p>Saate kohtuda roaring bitmapidega k\u00f5ige populaarsemates rakendustes. Juba on olemas tohutult palju teostusi erinevates programmeerimiskeeltes, sealhulgas rohkem kui kolm teostust Go jaoks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/de2adfebc431ff48c996247b453f02ae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVeel \u00fcks l\u00e4henemine, mis v\u00f5ib aidata meil toime tulla suure kardinaalsusega, nimetatakse r\u00fchmitamiseks (binning). Kujutage ette, et teil on v\u00e4li, mis esindab inimese pikkust. Pikkus on ujuvpunktiga arv, kuid meie, inimesed, ei m\u00f5tle sellele niimoodi. Meie jaoks pole vahet 185,2 cm ja 185,3 cm pikkuse vahel.<\/p>\n<p>Sellega saame sarnased v\u00e4\u00e4rtused r\u00fchmitada r\u00fchmadesse, mille vahemik on 1 cm.<\/p>\n<p>Ja kui me teame, et v\u00e4ga v\u00e4hesel inimesel on pikkus alla 50 cm v\u00f5i \u00fcle 250 cm, siis saame p\u00f5him\u00f5tteliselt muuta v\u00e4ljad, millel on l\u00f5pmatu kardinaalsus, v\u00e4ljadeks, mille kardinaalsus on umbes 200 v\u00e4\u00e4rtust.<\/p>\n<p>Muidugi, vajadusel saame teha t\u00e4iendavat filtreerimist ka hiljem.<\/p>\n<h2>Suur l\u00e4bilaskev\u00f5ime probleem<\/h2>\n<p>\nJ\u00e4rgmine probleem bitmap-indeksite puhul on see, et nende uuendamine v\u00f5ib olla v\u00e4ga kulukas.<\/p>\n<p>Andmebaasid peavad v\u00f5imaldama andmete v\u00e4rskendamist hetkel, kui potentsiaalselt sada muud p\u00e4ringut otsivad neid andmeid. Me vajame lukke, et v\u00e4ltida andmete \u00fcheaegse juurdep\u00e4\u00e4su probleeme v\u00f5i muid jagatud juurdep\u00e4\u00e4su probleeme. Ja seal, kus on \u00fcks suur lukustus, tekib probleem \u2014 lukustuskonkurents, kui see lukustus muutub kitsaskohaks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/0ae1bf925542d286f8b7b245c160a35e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSeda probleemi saab lahendada v\u00f5i v\u00e4ltida andmete \u0161ardimise v\u00f5i versiooniindeksite kasutamise kaudu.<\/p>\n<p>\u0160ardimine on lihtne ja teadaolev m\u00f5isted. Saate \u0161ardida bitmap-indeksi nii, nagu \u0161ardite k\u00f5iki teisigi andmeid. \u00dche suure lukustuse asemel saate hulga v\u00e4ikeseid lukustusi ja seega v\u00e4ltida lukustuskonkurentsi.<\/p>\n<p>Teine viis probleemi lahendamiseks on versiooniga indeksite kasutamine. Te v\u00f5ite omada \u00fchte indeksikoorust, mida kasutate otsimiseks v\u00f5i lugemiseks, ja \u00fchte \u2013 kirjutamiseks v\u00f5i uuendamiseks. Ja igal teatud ajavahemikul (n\u00e4iteks iga 100 ms v\u00f5i 500 ms) teete nende koopiad ja vahetate neid. Loomulikult on see l\u00e4henemine rakendatav ainult siis, kui teie rakendus suudab t\u00f6\u00f6tada pisut hilinenud otsingute indeksiga.<\/p>\n<p>Nende kahte l\u00e4henemist saab kasutada samaaegselt: teil v\u00f5ib olla \u0161arditud versiooniga indeks.<\/p>\n<h2>T\u00e4psemad p\u00e4ringud<\/h2>\n<p>Viimane probleem bitmap-indeksite puhul on see, et nagu meile \u00f6eldakse, sobivad need halvasti keerukamate p\u00e4ringut\u00fc\u00fcpide jaoks, n\u00e4iteks \u201evahemiku\u201d p\u00e4ringud.<\/p>\n<p>T\u00f5epoolest, kui sellele m\u00f5elda, ei sobi bitilised operatsioonid nagu AND, OR jne v\u00e4ga h\u00e4sti p\u00e4ringute jaoks, nagu \u201eN\u00e4ita mulle hotelle, mille toa hind on vahemikus 200 kuni 300 dollarit \u00f6\u00f6 kohta.\u201d<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/7bc2e129cad46fb5875c2b3018c39ff7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNaive ja v\u00e4ga m\u00f5ttetu lahendus oleks v\u00f5tta tulemused iga dollari v\u00e4\u00e4rtuse jaoks ja liita need bitiliselt operatsiooniga OR.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/b9f8fc7945caa1866f8e0cfa8a04bd98.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVeidi paremini lahenduseks oleks r\u00fchmitamine. N\u00e4iteks 50 dollari kaupa. See kiirendaks meie protsessi 50 korda.<\/p>\n<p>Aga probleem lahendatakse lihtsalt esitusviisi kasutamisega, mis on loodud spetsiaalselt selliste p\u00e4ringute jaoks. Teadust\u00f6\u00f6s nimetatakse seda vahemiku kodeeritud bitmapideks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/644a420628b21f220a7af1ff15c4031f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSellises esitusviisis me ei t\u00e4hista lihtsalt \u00fchte bitti m\u00f5ne v\u00e4\u00e4rtuse jaoks (n\u00e4iteks 200), vaid t\u00e4histame seda v\u00e4\u00e4rtust ja k\u00f5ike, mis on k\u00f5rgem. 200 ja k\u00f5rgem. Sama kehtib 300 kohta: 300 ja k\u00f5rgem. Ja nii edasi.<\/p>\n<p>Seda esitusviisi kasutades saame vastata sellisele otsingup\u00e4ringule, l\u00e4bides indeksi vaid kaks korda. Esiteks saame hotellide nimekirja, kus hind on alla 300 dollari, ja seej\u00e4rel eemaldame need, kus hind on alla 199 dollari. Valmis.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/cc2bb58d7d7a51495c62ec7da81e2d12.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTe \u00fcllatute, kuid isegi geop\u00e4ringud on v\u00f5imalikud bitmap-indeksite kasutamisega. Nipp on kasutada geoesitust, mis \u00fcmbritseb teie koordinaati geomeetrilise kujundiga. N\u00e4iteks Google'i S2. Kujund tuleb olla v\u00f5imalik esitada kolmest v\u00f5i enamast \u00fcksteisega ristuvatest joonest, mida saab nummerdada. Nii saame meie geop\u00e4ringu muuta mitmeks \u201evahepealseks\u201c p\u00e4ringuks (leitud numeeritud joonte j\u00e4rgi).<\/p>\n<h2>Valmis lahendused<\/h2>\n<p>\nLoodan, et ma pakkusin teile veidi huvi ja teil on n\u00fc\u00fcd uus kasulik t\u00f6\u00f6riist oma arsenalis. Kui kunagi tekib vajadus midagi sellist teha, teate, millise suuna poole vaadata.<\/p>\n<p>Kuid mitte k\u00f5igil ei ole aega, kannatlikkust ja ressursse bitmap-indeksite loomiseks nullist. Eriti edasij\u00f5udnud, mis kasutavad n\u00e4iteks SIMD-d.<\/p>\n<p>\u00d5nneks on olemas mitmeid valmislahendusi, mis aitavad teid.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/817b47cb189a758756b602ec9cf319e1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Roaring bitmaapid<\/h2>\n<p>\nEsiteks on see roaring bitmaps teek, millest olen juba r\u00e4\u00e4kinud. See sisaldab k\u00f5iki vajalikke konteinerite ja bititegevuste komplekse, mida vajate t\u00e4ieliku bitmap-indeksi loomiseks.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/57f61a51485c174666b52dc2063fabe8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKahjuks ei kasuta praegu \u00fckski Go teostus SIMD-d, mist\u00f5ttu on Go teostused v\u00e4hem j\u00f5udlikud, v\u00f5rreldes n\u00e4iteks C-teostustega.<\/p>\n<h2>Pilosa<\/h2>\n<p>\nTeine toode, mis v\u00f5ib teid aidata, on andmebaas Pilosa, millel on sisuliselt ainult bitmap-indeksid. See on suhteliselt uus lahendus, kuid see v\u00f5idab s\u00fcdameid tohutu kiirus.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/d3870a979e1e73d093fe5d5e9bb71cd8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPilosa kasutab endas roaring bitmaapeid ja annab teile v\u00f5imaluse neid kasutada, lihtsustades ja seletades k\u00f5iki neid asju, millest ma eespool r\u00e4\u00e4kisin: r\u00fchmitamine, vahemiku kodeeritud bitmaps, v\u00e4lja m\u00f5isted jne.<\/p>\n<p>Vaadake kiire \u00fcle Pilosa kasutamise n\u00e4ide, et vastata k\u00fcsimusele, mis on teile juba tuttav.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/dfee7abfd653cc19d9aa8b64c64f3e4e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nN\u00e4ide sarnaneb v\u00e4ga sellele, mida olete varem n\u00e4inud. Loome kliendi Pilosa serverisse, loome indeksit ja vajalikud v\u00e4ljad, seej\u00e4rel t\u00e4idame oma v\u00e4ljad juhuslike andmetega t\u00f5en\u00e4osustega ja l\u00f5puks teeme tuttava p\u00e4ringu.<\/p>\n<p>P\u00e4rast seda kasutame NOT v\u00e4ljal \"expensive\", seej\u00e4rel ristame tulemuse (v\u00f5i AND-ime) v\u00e4lja \"terrace\" ja v\u00e4lja \"reservations\". Ja l\u00f5puks saame l\u00f5pptulemuse.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/8d66c6d68019c2297b6c15b700f06a3a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nLoodan siiralt, et peagi ilmuvad sellised uued indeksit\u00fc\u00fcbid nagu bitmap-indeksid ka andmebaasidesse nagu MySQL ja PostgreSQL.<br \/>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/7a8e33d576c7fb6376a173ee038b4206.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Kokkuv\u00f5te<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmap-indeksid Go-s: otsimine metsiku kiirusel\" src=\"\/wp-content\/uploads\/2019\/05\/c62caa9ad6f2d96056c80326f4fa9a0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKui te pole veel magama j\u00e4\u00e4nud, siis ait\u00e4h. Peasin k\u00e4sitlema paljusid teemasid l\u00fchidalt piiratud aja t\u00f5ttu, kuid loodan, et ettekande sisu oli kasulik ja v\u00f5ib-olla isegi motiveeriv.<\/p>\n<p>Bitmap-indeksite olemasolust tasub teada isegi siis, kui need ei ole praegu teile vajalikud. Las need olla veel \u00fcks t\u00f6\u00f6riist teie t\u00f6\u00f6riistakastis.<\/p>\n<p>Vaatasime erinevaid nippe Go j\u00f5udluse parandamiseks ja neid asju, millega Go kompilaator praegu eriti h\u00e4sti toime ei tule. See on t\u00f5eliselt kasulik teadmine iga Go programmeerija jaoks.<\/p>\n<p>See on k\u00f5ik, mida soovisin jagada. Ait\u00e4h!<br \/>\n<br \/>Allikas: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/company\/badoo\/blog\/451938\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441 \u044d\u0442\u0438\u043c \u0434\u043e\u043a\u043b\u0430\u0434\u043e\u043c \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 GopherCon Russia 2019 \u0432 \u041c\u043e\u0441\u043a\u0432\u0435 \u0438 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c \u2014 \u043d\u0430 \u043c\u0438\u0442\u0430\u043f\u0435 \u0432 \u041d\u0438\u0436\u043d\u0435\u043c \u041d\u043e\u0432\u0433\u043e\u0440\u043e\u0434\u0435. \u0420\u0435\u0447\u044c \u0432 \u043d\u0451\u043c \u0438\u0434\u0451\u0442 \u043e bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u0435 \u2014 \u043c\u0435\u043d\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u043e\u043c, \u0447\u0435\u043c B-tree, \u043d\u043e \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c. \u0414\u0435\u043b\u044e\u0441\u044c \u0437\u0430\u043f\u0438\u0441\u044c\u044e \u0432\u044b\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u0438 \u0442\u0435\u043a\u0441\u0442\u043e\u0432\u043e\u0439 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u043e\u0439 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c. \u041c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c, [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":25469,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-33793","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"et_EE\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47Bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432 Go: \u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u0434\u0438\u043a\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:54:42+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T18:54:42+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Bitmap-indeksid Go-s: leidmine metsiku kiirusena | ProHoster","description":"Sissejuhatav s\u00f5na, mida ma esitasin.","canonical_url":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"et_EE","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432 Go: \u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u0434\u0438\u043a\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 | ProHoster","og:description":"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.","og:url":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:54:42+00:00","article:modified_time":"2019-10-31T18:54:42+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"33793","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 16:43:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:33:25","updated":"2026-01-21 16:43:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/33793","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/comments?post=33793"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/33793\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media\/25469"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media?parent=33793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/categories?post=33793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/tags?post=33793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}