{"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\/pl\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","title":{"rendered":"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h2>Wst\u0119pne s\u0142owo<\/h2>\n<p>\nWyg\u0142osi\u0142em t\u0119 prezentacj\u0119 w j\u0119zyku angielskim na konferencji GopherCon Rosja 2019 w Moskwie, a w j\u0119zyku rosyjskim podczas meetupu w Ni\u017cnym Nowogrodzie. M\u00f3wi ona o indeksie bitmapowym \u2014 mniej rozpowszechnionym ni\u017c B-drzewo, ale nie mniej interesuj\u0105cym. Dziel\u0119 si\u0119 <noindex><a rel=\"nofollow\" href=\"https:\/\/youtu.be\/WvlUH6MjUuI?list=PL3xVZC4USRNSO_kb2lh_J_no6C-KJ7Phg\">nagrywaniem<\/a><\/noindex> wyst\u0105pienia na konferencji w j\u0119zyku angielskim oraz transkrypcj\u0105 tekstow\u0105 w j\u0119zyku rosyjskim.<\/p>\n<p>Przyjrzymy si\u0119, jak dzia\u0142a indeks bitmapowy, kiedy jest lepszy, kiedy gorszy od innych indeks\u00f3w i w jakich przypadkach jest znacznie szybszy; zobaczymy, w jakich popularnych systemach baz danych ju\u017c istniej\u0105 indeksy bitmapowe; spr\u00f3bujemy napisa\u0107 w\u0142asny w Go. A na \"deser\" skorzystamy z gotowych bibliotek, aby stworzy\u0107 nasz\u0105 super szybk\u0105 specjalistyczn\u0105 baz\u0119 danych.<\/p>\n<p>Bardzo mam nadziej\u0119, \u017ce moje prace oka\u017c\u0105 si\u0119 dla was pomocne i interesuj\u0105ce. Zaczynajmy!<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>Wprowadzenie<\/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=\"Odtwarzaj wideo\" 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>Cze\u015b\u0107 wszystkim! Jest sz\u00f3sta wieczorem, wszyscy jeste\u015bmy bardzo zm\u0119czeni. Doskona\u0142y czas, aby porozmawia\u0107 o nudnej teorii indeks\u00f3w baz danych, prawda? Nie martwcie si\u0119, b\u0119d\u0119 mia\u0142 kilka linijek kodu \u017ar\u00f3d\u0142owego tu i tam. \ud83d\ude42<\/p>\n<p>Bez \u017cart\u00f3w, ten referat jest przepe\u0142niony informacjami, a mamy ma\u0142o czasu. Dlatego zaczynajmy.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/e778e13727700f0335a4b5558a0d8db3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDzi\u015b b\u0119d\u0119 m\u00f3wi\u0142 o nast\u0119puj\u0105cych kwestiach:<\/p>\n<ul>\n<li>czym s\u0105 indeksy;\n<\/li>\n<li>czym jest indeks bitmapowy;\n<\/li>\n<li>gdzie jest u\u017cywany, a gdzie NIE jest u\u017cywany i dlaczego;\n<\/li>\n<li>prosta implementacja w Go i troch\u0119 walki z kompilatorem;\n<\/li>\n<li>nieco mniej prosta, ale znacznie bardziej wydajna implementacja w assemblerze Go;\n<\/li>\n<li>\"problemy\" indeks\u00f3w bitmapowych;\n<\/li>\n<li>istniej\u0105ce realizacje.\n<\/li>\n<\/ul>\n<h2>Czym s\u0105 wi\u0119c indeksy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/b80e5b990c44814afe9150a9a82351fd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nIndeks to oddzielna struktura danych, kt\u00f3r\u0105 przechowujemy i aktualizujemy w uzupe\u0142nieniu do danych podstawowych. S\u0142u\u017cy do przyspieszania wyszukiwania. Bez indeks\u00f3w wyszukiwanie wymaga\u0142oby pe\u0142nego przeszukiwania danych (proces ten nazywany jest pe\u0142nym skanowaniem) i ten proces ma liniow\u0105 z\u0142o\u017cono\u015b\u0107 algorytmiczn\u0105. Ale bazy danych zwykle zawieraj\u0105 ogromne ilo\u015bci danych, a liniowa z\u0142o\u017cono\u015b\u0107 \u2014 to zbyt wolno. Idealnie chcieliby\u015bmy uzyska\u0107 z\u0142o\u017cono\u015b\u0107 logarytmiczn\u0105 lub sta\u0142\u0105.<\/p>\n<p>To ogromny skomplikowany temat, przepe\u0142niony niuansami i kompromisami, ale po obejrzeniu dziesi\u0105tek lat rozwoju i bada\u0144 r\u00f3\u017cnych baz danych, mog\u0119 z przekonaniem stwierdzi\u0107, \u017ce istnieje tylko kilka szeroko stosowanych podej\u015b\u0107 do tworzenia indeks\u00f3w baz danych.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/08a74dbb365035cd99bc94d72644a1b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPierwsze podej\u015bcie polega na hierarchicznym zmniejszeniu obszaru wyszukiwania, podzieleniu go na mniejsze cz\u0119\u015bci.<\/p>\n<p>Zazwyczaj robimy to, u\u017cywaj\u0105c r\u00f3\u017cnego rodzaju drzew. Przyk\u0142adem mo\u017ce by\u0107 du\u017ca skrzynka z materia\u0142ami w twojej szafie, w kt\u00f3rej znajduj\u0105 si\u0119 mniejsze skrzynki z materia\u0142ami, podzielonymi wed\u0142ug r\u00f3\u017cnych temat\u00f3w. Je\u015bli potrzebujesz materia\u0142\u00f3w, to na pewno b\u0119dziesz ich szuka\u0107 w skrzynce z napisem \u201eMateria\u0142y\u201d, a nie w tej oznaczonej jako \u201eCiastka\u201d, prawda?<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/423fac47c748980b18af434644af4dae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDrugie podej\u015bcie polega na od razu zidentyfikowaniu potrzebnego elementu lub grupy element\u00f3w. Robimy to za pomoc\u0105 map hash lub indeks\u00f3w odwrotnych. U\u017cycie map hash jest bardzo podobne do poprzedniego przyk\u0142adu, tylko zamiast skrzynki z skrzynkami masz w szafie stos ma\u0142ych skrzynek z gotowymi przedmiotami.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/088fed0a2a0feea4a23edbf0ca654805.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nTrzecie podej\u015bcie to pozbycie si\u0119 potrzeby wyszukiwania. Robimy to za pomoc\u0105 filtr\u00f3w Bloom lub filtr\u00f3w cuckoo. Te pierwsze daj\u0105 odpowied\u017a natychmiast, uwalniaj\u0105c ci\u0119 od konieczno\u015bci wyszukiwania.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/493bc4f20baacc0a5dc0faf15cc46285.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nOstatnie podej\u015bcie polega na pe\u0142nym wykorzystaniu wszystkich mo\u017cliwo\u015bci, kt\u00f3re daje nam nowoczesny sprz\u0119t. Dok\u0142adnie to robimy w indeksach bitmapowych. Tak, korzystaj\u0105c z nich, czasami musimy przeszuka\u0107 ca\u0142y indeks, ale robimy to super efektywnie.<\/p>\n<p>Jak ju\u017c powiedzia\u0142em, temat indeks\u00f3w baz danych jest obszerny i pe\u0142en kompromis\u00f3w. To oznacza, \u017ce czasami mo\u017cemy stosowa\u0107 kilka podej\u015b\u0107 jednocze\u015bnie: je\u015bli musimy jeszcze bardziej przyspieszy\u0107 wyszukiwanie lub je\u015bli konieczne jest obj\u0119cie wszystkich mo\u017cliwych typ\u00f3w wyszukiwania.<\/p>\n<p>Dzi\u015b opowiem o najmniej znanym podej\u015bciu spo\u015br\u00f3d wymienionych \u2014 o indeksach bitmapowych.<\/p>\n<h2>Kim jestem, \u017ceby m\u00f3wi\u0107 na ten temat?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/42a9d17a507c392bc202254a92dfaf41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPracuj\u0119 jako lider zespo\u0142u w Badoo (mo\u017ce znasz nasz inny produkt \u2014 Bumble). Mamy ju\u017c ponad 400 milion\u00f3w u\u017cytkownik\u00f3w na ca\u0142ym \u015bwiecie i wiele funkcji, kt\u00f3re pomagaj\u0105 im znale\u017a\u0107 najlepsza par\u0119. Robimy to za pomoc\u0105 w\u0142asnych us\u0142ug, kt\u00f3re wykorzystuj\u0105 r\u00f3wnie\u017c indeksy bitmapowe.<\/p>\n<h2>Czym zatem jest indeks bitmapowy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/14f20f3697a20c02f6b3510dc7f0ae4d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nIndeksy bitmap, jak sugeruje nazwa, wykorzystuj\u0105 bitmapy lub zestawy bit\u00f3w do zaimplementowania indeksu wyszukiwania. Z lotu ptaka ten indeks sk\u0142ada si\u0119 z jednego lub kilku takich bitmap, reprezentuj\u0105cych r\u00f3\u017cne encje (takie jak ludzie) oraz ich cechy lub parametry (wiek, kolor oczu itd.), a tak\u017ce z algorytmu wykorzystuj\u0105cego operacje bitowe (AND, OR, NOT) do odpowiadania na zapytania wyszukiwania.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/f815720330a51b1f0798e45d23160d3b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nM\u00f3wi si\u0119, \u017ce indeksy bitmap s\u0105 najlepiej dopasowane i bardzo wydajne w przypadkach, gdy wyszukiwanie \u0142\u0105czy zapytania dotycz\u0105ce wielu kolumn o niskiej kardynalno\u015bci (wyobra\u017a sobie \u00abkolor oczu\u00bb lub \u00abstan cywilny\u00bb w por\u00f3wnaniu do czego\u015b takiego jak \u00abodleg\u0142o\u015b\u0107 od centrum miasta\u00bb). Ale p\u00f3\u017aniej poka\u017c\u0119, \u017ce doskonale dzia\u0142aj\u0105 r\u00f3wnie\u017c w przypadku kolumn o wysokiej kardynalno\u015bci.<\/p>\n<p>Rozwa\u017cmy najprostszy przyk\u0142ad indeksu bitmap.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/33fe23476e0931c10345d7175b83d68b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nWyobra\u017a sobie, \u017ce mamy list\u0119 restauracji w Moskwie z binarnymi w\u0142a\u015bciwo\u015bciami jak te:<\/p>\n<ul>\n<li>blisko metra (near metro);\n<\/li>\n<li>ma prywatny parking (has private parking);\n<\/li>\n<li>ma taras (has terrace);\n<\/li>\n<li>przyjmuje rezerwacje (accepts reservations);\n<\/li>\n<li>przyjazne dla wegetarian (vegan friendly);\n<\/li>\n<li>droga (expensive).\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/fcbad539ea12f79a9d06966ce308637e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNadajmy ka\u017cdej restauracji numer porz\u0105dkowy zaczynaj\u0105c od 0 i zarezerwujmy pami\u0119\u0107 na 6 bitmap (po jednej dla ka\u017cdej cechy). Nast\u0119pnie wype\u0142nimy te bitmapy w zale\u017cno\u015bci od tego, czy restauracja posiada dan\u0105 cech\u0119, czy nie. Je\u015bli restauracja 4 ma taras, to bit nr 4 w bitmapie \u00abma taras\u00bb zostanie ustawiony na 1 (je\u015bli tarasu nie ma, to na 0).<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/3709c426617d4364f392ee6b68f92b00.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTeraz mamy najprostszy mo\u017cliwy indeks bitmap, kt\u00f3ry mo\u017cemy wykorzysta\u0107 do odpowiadania na zapytania takie jak:<\/p>\n<ul>\n<li>\u00abPoka\u017c mi restauracje przyjazne dla wegetarian\u00bb;\n<\/li>\n<li>\u00abPoka\u017c mi niedrogie restauracje z tarasem, kt\u00f3re przyjmuj\u0105 rezerwacje\u00bb.\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/90acb0f890686bd52c3db1fc667f0b0b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/0fd0b7fe9f7b7039022ad5c79fe873bc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJak? Przejd\u017amy do tego. Pierwsze zapytanie jest bardzo proste. Wszystko, co musimy zrobi\u0107, to wzi\u0105\u0107 bitmap\u0119 \u00abprzyjazne dla wegetarian\u00bb i przekszta\u0142ci\u0107 j\u0105 w list\u0119 restauracji, kt\u00f3rych bity s\u0105 ustawione.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ef4a5cfd658ff4ef8bc0c638c4522d11.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/9cc175bae55c16018fdf5ff95517a61a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDrugi zapytanie jest nieco bardziej skomplikowane. Musimy u\u017cy\u0107 operacji bitowej NOT na bitmapie \u201edrogi\u201d, aby uzyska\u0107 list\u0119 niedrogich restauracji, a nast\u0119pnie po\u0142\u0105czy\u0107 j\u0105 z bitmap\u0105 \u201emo\u017cna zarezerwowa\u0107 stolik\u201d i ponownie po\u0142\u0105czy\u0107 wynik z bitmap\u0105 \u201ejest weranda\u201d. Powsta\u0142a bitmapa b\u0119dzie zawiera\u0107 list\u0119 miejsc, kt\u00f3re spe\u0142niaj\u0105 wszystkie nasze kryteria. W tym przyk\u0142adzie jest to tylko restauracja \u201eM\u0142odo\u015b\u0107\u201d.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/f1cdda0cbf7f15278553899cf876c17e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/126b50e0f622b6e36c461cd74e708c38.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJest tu du\u017co teorii, ale nie martwcie si\u0119, niebawem zobaczymy kod.<\/p>\n<h2>Gdzie s\u0105 u\u017cywane indeksy bitmapowe?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/406132236c71a4f66ae79957b6e633b3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJe\u015bli \u201ezguglujecie\u201d indeksy bitmapowe, 90% odpowiedzi b\u0119dzie w jaki\u015b spos\u00f3b zwi\u0105zanych z Oracle DB. Ale inne systemy baz danych tak\u017ce z pewno\u015bci\u0105 wspieraj\u0105 tak \u015bwietn\u0105 funkcj\u0119, prawda? Nie do ko\u0144ca. <\/p>\n<p>Przejd\u017amy do listy g\u0142\u00f3wnych podejrzanych.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/d18d66451a8a26b0ddf121f8ec0204cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMySQL jeszcze nie wspiera indeks\u00f3w bitmapowych, ale jest propozycja dodania tej opcji (<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 nie wspiera indeks\u00f3w bitmapowych, ale wykorzystuje proste bitmapy i operacje bitowe do \u0142\u0105czenia wynik\u00f3w wyszukiwania z wieloma innymi indeksami.<\/p>\n<p>Tarantool ma indeksy bitset, wspiera prost\u0105 wyszukiwark\u0119 po nich.<\/p>\n<p>Redis ma proste pola bitowe<noindex><a rel=\"nofollow\" href=\"https:\/\/redis.io\/commands\/bitfield\"> (https:\/\/redis.io\/commands\/bitfield<\/a><\/noindex>) bez mo\u017cliwo\u015bci ich wyszukiwania.<\/p>\n<p>MongoDB jeszcze nie wspiera indeks\u00f3w bitmapowych, ale tak\u017ce jest propozycja dodania tej opcji <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 u\u017cywa bitmap w \u015brodku<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=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/232d335963603d6e6dec98839fc9f486.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<ul>\n<li>Ale w naszym domu pojawi\u0142 si\u0119 nowy s\u0105siad: Pilosa. To nowa nierelacyjna baza danych, napisana w Go. Zawiera tylko indeksy bitmapowe i wszystko na nich opiera. Porozmawiamy o niej nieco p\u00f3\u017aniej.\n<\/li>\n<\/ul>\n<h2>Implementacja w Go<\/h2>\n<p>\nAle dlaczego indeksy bitmapowe s\u0105 tak rzadko u\u017cywane? Zanim odpowiem na to pytanie, chcia\u0142bym zaprezentowa\u0107 Wam implementacj\u0119 bardzo prostego indeksu bitmapowego na Go.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ae7f4c1a4a740fe709b05dfaee27ac9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmapy zasadniczo przedstawione s\u0105 jako kawa\u0142ki danych. W Go u\u017cyjmy w tym celu tablic bajt\u00f3w.<\/p>\n<p>Mamy jeden bitmap na jedn\u0105 cech\u0119 restauracji, a ka\u017cdy bit w bitmapie m\u00f3wi o tym, czy dana restauracja ma t\u0119 cech\u0119, czy nie.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/1ab628ee15887d6b3c6c99855aa610c8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPotrzebujemy dw\u00f3ch funkcji pomocniczych. Jedna z nich b\u0119dzie u\u017cywana do wype\u0142nienia naszych bitmap losowymi danymi. Losowymi, ale z okre\u015blon\u0105 prawdopodobie\u0144stwem, \u017ce restauracja ma ka\u017cd\u0105 z cech. Na przyk\u0142ad uwa\u017cam, \u017ce w Moskwie jest bardzo ma\u0142o restauracji, w kt\u00f3rych nie mo\u017cna zarezerwowa\u0107 stolika, a wydaje mi si\u0119, \u017ce oko\u0142o 20% lokali nadaje si\u0119 dla wegetarian.<\/p>\n<p>Druga funkcja przekszta\u0142ci bitmap\u0119 w list\u0119 restauracji.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ab9c87a0ba63750116e2e7968f842a9a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/498cf7a33611d99b90197d4ee82e2834.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAby odpowiedzie\u0107 na zapytanie \u201ePoka\u017c mi niedrogie restauracje, kt\u00f3re maj\u0105 taras i w kt\u00f3rych mo\u017cna zarezerwowa\u0107 stolik\u201d, potrzebujemy dw\u00f3ch operacji bitowych: NOT i AND.<\/p>\n<p>Mo\u017cemy nieco upro\u015bci\u0107 nasz kod, korzystaj\u0105c z bardziej z\u0142o\u017conej operacji AND NOT.<\/p>\n<p>Mamy funkcje dla ka\u017cdej z tych operacji. Obie przechodz\u0105 przez slice'y, pobieraj\u0105 odpowiednie elementy z ka\u017cdego, \u0142\u0105cz\u0105 je operacj\u0105 bitow\u0105 i umieszczaj\u0105 wynik w wynikowym slice'ie.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ec5652a34f0370dfb03df199f341f153.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA teraz mo\u017cemy skorzysta\u0107 z naszych bitmap i funkcji, aby odpowiedzie\u0107 na zapytanie wyszukiwania.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/cf9500ccfe75995a6008191c16729689.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nWydajno\u015b\u0107 nie jest zbyt wysoka, nawet pomimo tego, \u017ce funkcje s\u0105 bardzo proste i znacznie zaoszcz\u0119dzili\u015bmy, nie zwracaj\u0105c nowego wynikowego slice'a przy ka\u017cdym wywo\u0142aniu funkcji.<\/p>\n<p>Po przeprofilowaniu z pprof zauwa\u017cy\u0142em, \u017ce kompilator Go pomin\u0105\u0142 jedn\u0105 bardzo prost\u0105, ale bardzo wa\u017cn\u0105 optymalizacj\u0119: zagnie\u017cd\u017canie funkcji.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/9092f5ba3940d0a4f3fbfa90b364d716.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nChodzi o to, \u017ce kompilator Go okropnie boi si\u0119 p\u0119tli, kt\u00f3re dzia\u0142aj\u0105 na slice'ach, i kategorycznie odmawia zagnie\u017cd\u017cania funkcji, kt\u00f3re zawieraj\u0105 takie p\u0119tle.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/d1bddd62b61b367dd1f680f223fa0ce7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle ja si\u0119 nie boj\u0119 i mog\u0119 oszuka\u0107 kompilator, korzystaj\u0105c z goto zamiast p\u0119tli, jak w dawnych dobrych czasach.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/5b1c3cb26b923972686047910ecd1c31.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/1ca31d12dc90931b674c6a86a4ea23bd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nI jak widzicie, teraz kompilator z przyjemno\u015bci\u0105 zagnie\u017cd\u017ca nasz\u0105 funkcj\u0119! W efekcie udaje nam si\u0119 zaoszcz\u0119dzi\u0107 oko\u0142o 2 mikrosekundy. Niez\u0142y wynik!<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/bdd6735d16082573e600bffe2cdd5662.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDrugie w\u0105skie gard\u0142o mo\u017cna \u0142atwo dostrzec, je\u015bli uwa\u017cnie przyjrze\u0107 si\u0119 wynikowi asemblera. Kompilator doda\u0142 sprawdzanie granic slice'a bezpo\u015brednio wewn\u0105trz naszej najgor\u0119tszej p\u0119tli. Chodzi o to, \u017ce Go to j\u0119zyk bezpieczny, kompilator obawia si\u0119, \u017ce moje trzy argumenty (trzy slice'y) maj\u0105 r\u00f3\u017cne rozmiary. W\u00f3wczas istnieje teoretyczna mo\u017cliwo\u015b\u0107 wyst\u0105pienia tak zwanego przepe\u0142nienia bufora (buffer overflow).<\/p>\n<p>Uspok\u00f3jmy kompilator, pokazuj\u0105c mu, \u017ce wszystkie slajdy maj\u0105 ten sam rozmiar. Mo\u017cemy to osi\u0105gn\u0105\u0107, dodaj\u0105c prost\u0105 kontrol\u0119 na pocz\u0105tku naszej funkcji.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/59b4ce687a11dd653e9f12fc3130d89a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nWidz\u0105c to, kompilator ch\u0119tnie pomija kontrol\u0119, a my oszcz\u0119dzamy dodatkowe 500 nanosekund.<\/p>\n<h2>Du\u017ce partie<\/h2>\n<p>\nOk, uda\u0142o nam si\u0119 wydoby\u0107 pewn\u0105 wydajno\u015b\u0107 z naszej prostej implementacji, ale ten wynik jest zdecydowanie gorszy, ni\u017c mo\u017cna by osi\u0105gn\u0105\u0107 z obecnym sprz\u0119tem.<\/p>\n<p>Wszystko, co robimy, to podstawowe operacje bitowe, a nasze procesory wykonuj\u0105 je bardzo efektywnie. Niestety, \"karmimy\" nasz procesor bardzo ma\u0142ymi kawa\u0142kami pracy. Nasze funkcje wykonuj\u0105 operacje bajt po bajcie. Mo\u017cemy bardzo \u0142atwo dostroi\u0107 nasz kod, aby pracowa\u0142 z 8-bajtowymi kawa\u0142kami, u\u017cywaj\u0105c slajd\u00f3w UInt64.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/8d1b60ba4b7046c836601631cadd0b6a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nJak wida\u0107, ta ma\u0142a zmiana przyspieszy\u0142a nasz program o\u015bmiokrotnie dzi\u0119ki zwi\u0119kszeniu partii o\u015bmiokrotnie. Zysk, mo\u017cna powiedzie\u0107, jest liniowy.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/0fc663412d04dd38b927de5c8776f69d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Implementacja w asemblerze<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/b3ef133167b89da983356b1c7389aecd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle to jeszcze nie koniec. Nasze procesory mog\u0105 pracowa\u0107 z kawa\u0142kami o rozmiarze 16, 32, a nawet 64 bajt\u00f3w. Takie \"szerokie\" operacje nazywane s\u0105 single instruction multiple data (SIMD; jedna instrukcja, wiele danych), a proces przekszta\u0142cania kodu w taki spos\u00f3b, by u\u017cywa\u0142 takich operacji, nazywa si\u0119 wektoryzacj\u0105.<\/p>\n<p>Niestety, kompilator Go nie jest najlepszy w wektoryzacji. Na chwil\u0119 obecn\u0105 jedynym sposobem wektoryzacji kodu w Go jest zrobienie tego r\u0119cznie, u\u017cywaj\u0105c asemblera Go.<\/p>\n<p><img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/91278be45df67e1f9572d68fab7ebad1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAsembler Go to dziwna bestia. Z pewno\u015bci\u0105 wiesz, \u017ce asembler to co\u015b, co jest mocno zwi\u0105zane z architektur\u0105 komputera, dla kt\u00f3rego piszesz, ale w Go tak nie jest. Asembler Go jest bardziej podobny do IRL (intermediate representation language) lub j\u0119zyka po\u015bredniego: jest praktycznie niezale\u017cny od platformy. Rob Pike zaprezentowa\u0142 \u015bwietn\u0105 <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/watch?v=KINIAgRpkDA\">referat<\/a><\/noindex> prezentacj\u0119 na ten temat kilka lat temu na GopherCon w Denver.<\/p>\n<p>Dodatkowo Go u\u017cywa niezwyk\u0142ego formatu Plan 9, r\u00f3\u017cni\u0105cego si\u0119 od uznawanych format\u00f3w AT&amp;T i Intel.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/526f75eb18edfc2f851f2725e9d6f69e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMo\u017cna \u015bmia\u0142o powiedzie\u0107, \u017ce pisanie asemblera Go r\u0119cznie to nie jest zbyt przyjemne zaj\u0119cie.<\/p>\n<p>Ale na szcz\u0119\u015bcie ju\u017c istniej\u0105 dwie zaawansowane narz\u0119dzia, kt\u00f3re pomagaj\u0105 nam w pisaniu asemblera Go: PeachPy i avo. Obie narz\u0119dzia generuj\u0105 asembler Go z bardziej zaawansowanego kodu napisanego odpowiednio w Pythonie i Go.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/b8a7aa2c585b805e9b1f2ada186b84e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTe narz\u0119dzia u\u0142atwiaj\u0105 takie rzeczy, jak przydzia\u0142 rejestr\u00f3w (wyb\u00f3r rejestru procesora), pisanie p\u0119tli i og\u00f3lnie u\u0142atwiaj\u0105 proces wej\u015bcia w \u015bwiat programowania w assemblerze w Go.<\/p>\n<p>B\u0119dziemy u\u017cywa\u0107 avo, dzi\u0119ki czemu nasze programy b\u0119d\u0105 niemal zwyk\u0142ymi programami w Go.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/128e4adef14e5f2cf00fb5b6302ef58e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOto jak wygl\u0105da najprostszy przyk\u0142ad programu avo. Mamy funkcj\u0119 main(), kt\u00f3ra definiuje wewn\u0105trz siebie funkcj\u0119 Add(), kt\u00f3rej celem jest dodanie dw\u00f3ch liczb. Istniej\u0105 tutaj funkcje pomocnicze do uzyskiwania parametr\u00f3w po nazwie i do uzyskania jednego z dost\u0119pnych odpowiednich rejestr\u00f3w procesora. Dla ka\u017cdej operacji procesora istnieje odpowiadaj\u0105ca funkcja w avo, jak wida\u0107 po ADDQ. Na koniec widzimy funkcj\u0119 pomocnicz\u0105 do przechowywania wyniku.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/01ccaa6aa6d394ef598ea2dbc9257d87.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nWywo\u0142uj\u0105c go generate, uruchomimy program w avo i w efekcie zostan\u0105 wygenerowane dwa pliki:<\/p>\n<ul>\n<li>add.s z rezultatem kodu w assemblerze Go;\n<\/li>\n<li>stub.go z nag\u0142\u00f3wkami funkcji do po\u0142\u0105czenia dw\u00f3ch \u015bwiat\u00f3w: Go i assemblera.\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/72a9443776ecf45eef6fb97a4e08acba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTeraz, gdy widzieli\u015bmy, co i jak robi avo, przyjrzyjmy si\u0119 naszym funkcjom. Zaimplementowa\u0142em zar\u00f3wno wersje skalarne, jak i wektorowe (SIMD) funkcji.<\/p>\n<p>Najpierw sp\u00f3jrzmy na wersje skalarne.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ec31dbb8b97b9d7c1012a120fa18cdaf.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJak w poprzednim przyk\u0142adzie, prosimy o dost\u0119pny i odpowiedni rejestr og\u00f3lnego przeznaczenia, nie musimy oblicza\u0107 przesuni\u0119\u0107 i rozmiar\u00f3w dla argument\u00f3w. Wszystko to avo robi za nas.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/88085e927dd943ea0f808a28fb3ccf9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nWcze\u015bniej u\u017cywali\u015bmy etykiet i goto (lub skok\u00f3w) w celu zwi\u0119kszenia wydajno\u015bci i oszukania kompilatora Go, ale teraz robimy to od samego pocz\u0105tku. Chodzi o to, \u017ce p\u0119tle to poj\u0119cie wy\u017cszego poziomu. W assemblerze mamy tylko etykiety i skoki.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/9a4181248eb279d89c1445a820b06649.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPozosta\u0142y kod powinien by\u0107 ju\u017c znany i zrozumia\u0142y. Emulujemy p\u0119tl\u0119 etykietami i skokami, bierzemy ma\u0142\u0105 cz\u0119\u015b\u0107 danych z naszych dw\u00f3ch slajd\u00f3w, \u0142\u0105czymy je operacj\u0105 bitow\u0105 (AND NOT w tym przypadku) i nast\u0119pnie umieszczamy wynik w rezultacie. I to wszystko.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/19275ead27f63092fc6596bed38a8d03.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOto jak wygl\u0105da ostateczny kod w assemblerze. Nie musieli\u015bmy oblicza\u0107 przesuni\u0119\u0107 i rozmiar\u00f3w (pod\u015bwietlone na zielono) ani monitorowa\u0107 u\u017cywanych rejestr\u00f3w (pod\u015bwietlone na czerwono).<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ed68528a6f852634a5b536670c6315f0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJe\u015bli por\u00f3wnamy wydajno\u015b\u0107 implementacji w assemblerze z wydajno\u015bci\u0105 najlepszej implementacji w Go, zobaczymy, \u017ce s\u0105 one r\u00f3wne. I jest to oczekiwane. W ko\u0144cu nie zrobili\u015bmy nic specjalnego \u2014 tylko powt\u00f3rzyli\u015bmy to, co robi\u0142by kompilator Go.<\/p>\n<p>Niestety, nie mo\u017cemy zmusi\u0107 kompilatora do zainline\u2019owania naszych funkcji napisanych w assemblerze. Kompilator Go nie ma obecnie takiej opcji, chocia\u017c pro\u015bba o jej dodanie trwa ju\u017c do\u015b\u0107 d\u0142ugo.<\/p>\n<p>W\u0142a\u015bnie dlatego nie mo\u017cemy uzyska\u0107 \u017cadnych korzy\u015bci z ma\u0142ych funkcji w assemblerze. Musimy pisa\u0107 albo du\u017ce funkcje, albo u\u017cywa\u0107 nowego pakietu math\/bits, albo ca\u0142kowicie unika\u0107 assemblera.<\/p>\n<p>Teraz przyjrzyjmy si\u0119 wersjom wektorowym naszych funkcji.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/7f67c3cc855908fb47c7900d6e5d7f54.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nW tym przyk\u0142adzie zdecydowa\u0142em si\u0119 zastosowa\u0107 AVX2, dlatego b\u0119dziemy korzysta\u0107 z operacji dzia\u0142aj\u0105cych na 32-bajtowych kawa\u0142kach. Struktura kodu jest bardzo podobna do wersji skalarnych: \u0142adowanie parametr\u00f3w, pro\u015bba o udost\u0119pnienie wolnego og\u00f3lnego rejestru itd.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/021e0424a0d733ec7db9edeb98ce1f65.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJednym z nowo\u015bci jest to, \u017ce szersze operacje wektorowe wykorzystuj\u0105 specjalne szerokie rejestry. W przypadku 32-bajtowych kawa\u0142k\u00f3w s\u0105 to rejestry z prefiksem Y. Dlatego w kodzie widzisz funkcj\u0119 YMM(). Gdybym wykorzysta\u0142 AVX-512 z 64-bitowymi kawa\u0142kami, prefiks by\u0142by Z.<\/p>\n<p>Drug\u0105 nowo\u015bci\u0105 jest to, \u017ce zdecydowa\u0142em si\u0119 na optymalizacj\u0119 zwan\u0105 rozpakowywaniem p\u0119tli (loop unrolling), czyli wykonanie o\u015bmiu operacji p\u0119tli r\u0119cznie, zanim wr\u00f3cimy na pocz\u0105tek p\u0119tli. Ta optymalizacja zmniejsza liczb\u0119 rozga\u0142\u0119zie\u0144 w kodzie i jest ograniczona liczb\u0105 dost\u0119pnych wolnych rejestr\u00f3w.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/f54631d9e8c69f6f70ecace3133ae1e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA co z wydajno\u015bci\u0105? Jest doskona\u0142a! Osi\u0105gn\u0119li\u015bmy przyspieszenie o oko\u0142o siedem razy w por\u00f3wnaniu do najlepszego rozwi\u0105zania w Go. Imponuj\u0105ce, prawda?<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/d7e85c933eecb243cfb49225b4d92c6c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle nawet t\u0119 implementacj\u0119 potencjalnie mo\u017cna by przyspieszy\u0107, korzystaj\u0105c z AVX-512, prefetchingu lub JIT (just-in-time compiler) dla planisty zapyta\u0144. Ale to ju\u017c na pewno temat na osobny referat.<\/p>\n<h2>Problemy indeks\u00f3w bitmapowych<\/h2>\n<p>\nTeraz, kiedy ju\u017c om\u00f3wili\u015bmy prost\u0105 implementacj\u0119 indeksu bitmapowego w Go oraz znacznie bardziej wydajn\u0105 w assemblerze, porozmawiajmy wreszcie o tym, dlaczego indeksy bitmapowe s\u0105 tak rzadko stosowane.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/83d36a5c92ba90fd680fe8afb6cfc11f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nW starszych pracach naukowych wymienia si\u0119 trzy problemy indeks\u00f3w bitmapowych, ale nowsze badania, w tym moje, twierdz\u0105, \u017ce s\u0105 one ju\u017c nieaktualne. Nie b\u0119dziemy zg\u0142\u0119bia\u0107 ka\u017cdego z tych problem\u00f3w, ale przeanalizujemy je pobie\u017cnie.<\/p>\n<h2>Problem wysokiej kardynalno\u015bci<\/h2>\n<p>\nM\u00f3wi si\u0119, \u017ce indeksy bitmapowe nadaj\u0105 si\u0119 tylko do p\u00f3l o niskiej kardynalno\u015bci, czyli takich, kt\u00f3re maj\u0105 ma\u0142o warto\u015bci (jak na przyk\u0142ad p\u0142e\u0107 czy kolor oczu), poniewa\u017c tradycyjne przedstawienie takich p\u00f3l (jeden bit na warto\u015b\u0107) w przypadku wysokiej kardynalno\u015bci zajmie zbyt du\u017co miejsca, a ponadto te indeksy bitmapowe b\u0119d\u0105 s\u0142abo (rzadko) wype\u0142nione.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/0787efc4d2cb4ea4d404ca7888b33697.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/44ab4bc7c25d14fe2f53caf5d9da399d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nCzasami mo\u017cemy u\u017cy\u0107 innego przedstawienia, na przyk\u0142ad standardowego, kt\u00f3re stosujemy do reprezentacji liczb. Ale to w\u0142a\u015bnie pojawienie si\u0119 algorytm\u00f3w kompresji wszystko zmieni\u0142o. Przez ostatnie dziesi\u0119ciolecia naukowcy i badacze wymy\u015blili wiele algorytm\u00f3w kompresji dla bitmap. Ich g\u0142\u00f3wn\u0105 zalet\u0105 jest to, \u017ce nie trzeba dekompresowa\u0107 bitmap do wykonywania operacji bitowych\u2014mo\u017cemy przeprowadza\u0107 operacje bitowe bezpo\u015brednio na skompresowanych bitmapach.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/ecb54fbf15aa11271bbbab01ecbda880.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOstatnio zacz\u0119\u0142y si\u0119 r\u00f3wnie\u017c pojawia\u0107 hybrydowe podej\u015bcia, takie jak na przyk\u0142ad roaring bitmapy. Wykorzystuj\u0105 one jednocze\u015bnie trzy r\u00f3\u017cne reprezentacje bitmap\u2014same bitmapy, tablice i tzw. bit runs\u2014i r\u00f3wnowa\u017c\u0105 si\u0119 mi\u0119dzy nimi, aby zmaksymalizowa\u0107 wydajno\u015b\u0107 i zminimalizowa\u0107 zu\u017cycie pami\u0119ci.<\/p>\n<p>Mo\u017cna spotka\u0107 roaring bitmapy w najpopularniejszych aplikacjach. Istnieje ju\u017c wiele implementacji w r\u00f3\u017cnych j\u0119zykach programowania, w tym ponad trzy implementacje dla Go.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/de2adfebc431ff48c996247b453f02ae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nInne podej\u015bcie, kt\u00f3re mo\u017ce pom\u00f3c w radzeniu sobie z wysok\u0105 kardynalno\u015bci\u0105, to grupowanie (binning). Wyobra\u017amy sobie, \u017ce mamy pole reprezentuj\u0105ce wzrost cz\u0142owieka. Wzrost to liczba zmiennoprzecinkowa, ale nie my\u015blimy o nim w ten spos\u00f3b. Dla nas nie ma r\u00f3\u017cnicy mi\u0119dzy wzrostem 185,2 cm a 185,3 cm.<\/p>\n<p>Mo\u017cemy wi\u0119c pogrupowa\u0107 podobne warto\u015bci w grupy w granicach 1 cm.<\/p>\n<p>A je\u015bli dodatkowo wiemy, \u017ce bardzo ma\u0142o ludzi ma wzrost poni\u017cej 50 cm i powy\u017cej 250 cm, to zasadniczo mo\u017cemy przekszta\u0142ci\u0107 pole o niesko\u0144czonej kardynalno\u015bci w pole o kardynalno\u015bci wynosz\u0105cej oko\u0142o 200 warto\u015bci.<\/p>\n<p>Oczywi\u015bcie, w razie potrzeby mo\u017cemy dokona\u0107 dodatkowej filtracji p\u00f3\u017aniej.<\/p>\n<h2>Problem z du\u017c\u0105 przepustowo\u015bci\u0105<\/h2>\n<p>\nKolejny problem zwi\u0105zany z indeksami bitmapowymi polega na tym, \u017ce ich aktualizacja mo\u017ce by\u0107 bardzo kosztowna.<\/p>\n<p>Bazy danych musz\u0105 umo\u017cliwia\u0107 aktualizacj\u0119 danych w momencie, gdy setki innych zapyta\u0144 przeszukuj\u0105 te dane. Potrzebujemy blokad, aby unikn\u0105\u0107 problem\u00f3w z r\u00f3wnoczesnym dost\u0119pem do danych lub innych problem\u00f3w zwi\u0105zanych z wsp\u00f3\u0142dzielonym dost\u0119pem. A tam, gdzie jest jedna du\u017ca blokada, wyst\u0119puje problem \u2013 contention lock, kiedy ta blokada staje si\u0119 w\u0105skim gard\u0142em.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/0ae1bf925542d286f8b7b245c160a35e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nProblem ten mo\u017cna rozwi\u0105za\u0107 lub obej\u015b\u0107 poprzez sharding lub u\u017cycie wersjonowanych indeks\u00f3w.<\/p>\n<p>Sharding to prosta i powszechnie znana metoda. Mo\u017cesz shardowa\u0107 indeks bitmapowy tak, jak shardujesz ka\u017cde inne dane. Zamiast jednej du\u017cej blokady otrzymujesz wiele ma\u0142ych blokad i w ten spos\u00f3b unikasz contention lock.<\/p>\n<p>Drugim sposobem rozwi\u0105zania problemu jest u\u017cycie wersjonowanych indeks\u00f3w. Mo\u017cesz mie\u0107 jedn\u0105 kopi\u0119 indeksu, kt\u00f3rej u\u017cywasz do wyszukiwania lub odczytu, i jedn\u0105 \u2013 do zapisywania lub aktualizacji. Co pewien czas (np. co 100 ms lub 500 ms) duplikujesz je i zamieniasz miejscami. Oczywi\u015bcie, podej\u015bcie to ma zastosowanie tylko w przypadkach, gdy Twoja aplikacja mo\u017ce dzia\u0142a\u0107 z nieco op\u00f3\u017anionym indeksem wyszukiwania.<\/p>\n<p>Te dwa podej\u015bcia mo\u017cna stosowa\u0107 jednocze\u015bnie: mo\u017cesz mie\u0107 shardowany wersjonowany indeks.<\/p>\n<h2>Bardziej z\u0142o\u017cone zapytania<\/h2>\n<p>Ostatnim problemem indeks\u00f3w bitmapowych jest to, \u017ce, jak m\u00f3wi\u0105, nie nadaj\u0105 si\u0119 one dobrze do bardziej z\u0142o\u017conych typ\u00f3w zapyta\u0144, na przyk\u0142ad zapyta\u0144 \"w przedziale\".<\/p>\n<p>Rzeczywi\u015bcie, je\u015bli si\u0119 zastanowi\u0107, operacje bitowe typu AND, OR itd. nie nadaj\u0105 si\u0119 do zapyta\u0144 typu \"Poka\u017c mi hotele z cen\u0105 pokoju od 200 do 300 dolar\u00f3w za noc\".<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/7bc2e129cad46fb5875c2b3018c39ff7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNaivnym i bardzo nierozs\u0105dnym rozwi\u0105zaniem by\u0142oby wzi\u0119cie wynik\u00f3w dla ka\u017cdej warto\u015bci dolara i po\u0142\u0105czenie ich operacj\u0105 bitow\u0105 OR.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/b9f8fc7945caa1866f8e0cfa8a04bd98.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNieco lepszym rozwi\u0105zaniem by\u0142oby zastosowanie grupowania. Na przyk\u0142ad w grupy po 50 dolar\u00f3w. Przyspieszy\u0142oby to nasz proces pi\u0119\u0107dziesi\u0119ciokrotnie.<\/p>\n<p>Jednak problem ten mo\u017cna \u0142atwo rozwi\u0105za\u0107, korzystaj\u0105c z reprezentacji stworzonej specjalnie dla tego typu zapyta\u0144. W pracach naukowych nazywa si\u0119 to bitmapami kodowanymi na podstawie zakresu.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/644a420628b21f220a7af1ff15c4031f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nW takiej reprezentacji nie ustawiamy jednego bitu dla jakiej\u015b warto\u015bci (na przyk\u0142ad 200), ale ustawiamy t\u0119 warto\u015b\u0107 oraz wszystko, co jest powy\u017cej. 200 i wy\u017cej. To samo dotyczy 300: 300 i wy\u017cej. I tak dalej.<\/p>\n<p>Korzystaj\u0105c z tej reprezentacji, mo\u017cemy odpowiedzie\u0107 na takie wyszukiwanie, przeszukuj\u0105c indeks tylko dwa razy. Najpierw uzyskujemy list\u0119 hoteli, w kt\u00f3rych cena pokoju wynosi mniej ni\u017c 300 dolar\u00f3w, a nast\u0119pnie eliminujemy te, w kt\u00f3rych cena pokoju wynosi mniej ni\u017c 199 dolar\u00f3w. Gotowe.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/cc2bb58d7d7a51495c62ec7da81e2d12.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMo\u017cesz by\u0107 zaskoczony, ale nawet zapytania geograficzne s\u0105 mo\u017cliwe przy u\u017cyciu indeks\u00f3w bitmapowych. Sztuczka polega na wykorzystaniu reprezentacji geograficznej, kt\u00f3ra otacza twoje wsp\u00f3\u0142rz\u0119dne kszta\u0142tem geometrycznym. Na przyk\u0142ad S2 od Google. Kszta\u0142t powinien by\u0107 mo\u017cliwy do przedstawienia w postaci trzech lub wi\u0119cej przecinaj\u0105cych si\u0119 linii, kt\u00f3re mo\u017cna ponumerowa\u0107. Dzi\u0119ki temu mo\u017cemy przekszta\u0142ci\u0107 nasze zapytanie geograficzne w kilka zapyta\u0144 \u201epo przedziale\u201d (po tych ponumerowanych liniach).<\/p>\n<h2>Gotowe rozwi\u0105zania<\/h2>\n<p>\nMam nadziej\u0119, \u017ce troch\u0119 ci\u0119 zainteresowa\u0142em i masz w swoim arsenale jeszcze jedno przydatne narz\u0119dzie. Je\u015bli kiedykolwiek b\u0119dziesz musia\u0142 zrobi\u0107 co\u015b podobnego, b\u0119dziesz wiedzia\u0142, w kt\u00f3r\u0105 stron\u0119 patrze\u0107.<\/p>\n<p>Niemniej jednak nie wszyscy maj\u0105 czas, cierpliwo\u015b\u0107 i zasoby, aby stworzy\u0107 bitmapowe indeksy od podstaw. Szczeg\u00f3lnie bardziej zaawansowane, z wykorzystaniem SIMD, na przyk\u0142ad.<\/p>\n<p>Na szcz\u0119\u015bcie istnieje kilka gotowych rozwi\u0105za\u0144, kt\u00f3re mog\u0105 ci pom\u00f3c.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/817b47cb189a758756b602ec9cf319e1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Roaring bitmaps<\/h2>\n<p>\nPo pierwsze, istnieje ta sama biblioteka roaring bitmaps, o kt\u00f3rej ju\u017c wspomnia\u0142em. Zawiera wszystkie niezb\u0119dne kontenery i operacje bitowe, kt\u00f3re b\u0119d\u0105 potrzebne do stworzenia pe\u0142noprawnego indeksu bitmapowego.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/57f61a51485c174666b52dc2063fabe8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNiestety, jak na razie \u017cadna z realizacji w Go nie korzysta z SIMD, co oznacza, \u017ce realizacje w Go s\u0105 mniej wydajne ni\u017c realizacje w C, na przyk\u0142ad.<\/p>\n<h2>Pilosa<\/h2>\n<p>\nInny produkt, kt\u00f3ry mo\u017ce ci pom\u00f3c, to baza danych Pilosa, kt\u00f3ra w zasadzie opiera si\u0119 tylko na indeksach bitmapowych. To stosunkowo nowe rozwi\u0105zanie, ale zdobywa serca z niesamowit\u0105 szybko\u015bci\u0105.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/d3870a979e1e73d093fe5d5e9bb71cd8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPilosa wykorzystuje wewn\u0119trznie roaring bitmaps i daje ci mo\u017cliwo\u015b\u0107 ich wykorzystania, upraszcza i obja\u015bnia wszystkie te rzeczy, o kt\u00f3rych m\u00f3wi\u0142em wcze\u015bniej: grupowanie, bitmapy kodowane na podstawie zakresu, poj\u0119cie pola itd.<\/p>\n<p>Zobaczmy szybko przyk\u0142ad u\u017cycia Pilosa w odpowiedzi na ju\u017c znane pytanie.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/dfee7abfd653cc19d9aa8b64c64f3e4e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPrzyk\u0142ad jest bardzo podobny do tego, co widzia\u0142e\u015b wcze\u015bniej. Tworzymy klienta dla serwera Pilosa, tworzymy indeks oraz niezb\u0119dne pola, a nast\u0119pnie wype\u0142niamy nasze pola losowymi danymi z prawdopodobie\u0144stwami i w ko\u0144cu wykonujemy znane zapytanie.<\/p>\n<p>Nast\u0119pnie u\u017cywamy NOT na polu \u00abexpensive\u00bb, a nast\u0119pnie przecinamy wynik (czyli robimy AND) z polem \u00abterrace\u00bb oraz z polem \u00abreservations\u00bb. A na ko\u0144cu uzyskujemy ostateczny wynik.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/8d66c6d68019c2297b6c15b700f06a3a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBardzo mam nadziej\u0119, \u017ce w nieodleg\u0142ej przysz\u0142o\u015bci w systemach baz danych takich jak MySQL i PostgreSQL pojawi si\u0119 ten nowy typ indeks\u00f3w \u2014 indeksy bitmapowe.<br \/>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/7a8e33d576c7fb6376a173ee038b4206.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Podsumowanie<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Indeksy bitmapowe w Go: b\u0142yskawiczne wyszukiwanie\" src=\"\/wp-content\/uploads\/2019\/05\/c62caa9ad6f2d96056c80326f4fa9a0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJe\u015bli jeszcze nie zasn\u0105\u0142e\u015b, dzi\u0119kuj\u0119. Musia\u0142em poruszy\u0107 wiele temat\u00f3w w zwi\u0105zku z ograniczonym czasem, ale mam nadziej\u0119, \u017ce prezentacja by\u0142a u\u017cyteczna, a mo\u017ce nawet motywuj\u0105ca.<\/p>\n<p>Warto zna\u0107 indeksy bitmapowe, nawet je\u015bli nie s\u0105 ci teraz potrzebne. Niech b\u0119d\u0105 jednym z narz\u0119dzi w twoim zestawie.<\/p>\n<p>Rozeznali\u015bmy si\u0119 w r\u00f3\u017cnych sztuczkach poprawiaj\u0105cych wydajno\u015b\u0107 dla Go oraz w rzeczach, z kt\u00f3rymi kompilator Go nadal sobie nie radzi. To naprawd\u0119 co\u015b, co ka\u017cdy programista Go powinien wiedzie\u0107.<\/p>\n<p>To wszystko, co chcia\u0142em powiedzie\u0107. Dzi\u0119kuj\u0119!<br \/>\n<br \/>\u0179r\u00f3d\u0142o: <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\/pl\/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=\"pl_PL\" \/>\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\/pl\/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\udd47Indeksy bitmapowe w Go: poszukiwanie z osza\u0142amiaj\u0105c\u0105 pr\u0119dko\u015bci\u0105 | ProHoster","description":"Wst\u0119pne s\u0142owo Wyst\u0105pi\u0142em z.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","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\/pl\/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\/pl\/wp-json\/wp\/v2\/posts\/33793","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=33793"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/33793\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/25469"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=33793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=33793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=33793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}