stub.go med funktionsoverskrifter for at forbinde de to verdener: Go og assembler.\n<\/li>\n<\/ul>\n\n
Lad os f\u00f8rst se p\u00e5 de skalar versioner.
Desv\u00e6rre kan vi ikke f\u00e5 kompilatoren til at inline vores funktioner, der er skrevet i assembler. Go-kompilatoren mangler i \u00f8jeblikket denne funktion, selv om der har v\u00e6ret en anmodning om at tilf\u00f8je den i lang tid.<\/p>\n
Netop derfor er det umuligt at f\u00e5 nogen som helst fordele ved sm\u00e5 funktioner i assembler. Vi m\u00e5 enten skrive store funktioner, eller ogs\u00e5 bruge det nye math\/bits bibliotek, eller undg\u00e5 assembler helt.<\/p>\n
Lad os nu se p\u00e5 de vektoriserede versioner af vores funktioner.
En anden nyhed er, at jeg har valgt at bruge en optimering kaldet loop unrolling, hvilket vil sige at udf\u00f8re otte loop-operationer manuelt, inden vi hopper tilbage til starten af loopet. Denne optimering reducerer antallet af brancher i koden og er begr\u00e6nset af antallet af ledige registre til r\u00e5dighed.
Problemer med bitmap-indekser<\/h2>\n \nNu hvor vi har gennemg\u00e5et en simpel implementering af bitmap-indeksen i Go og en langt mere effektiv i assembler, lad os endelig tale om, hvorfor bitmap-indekser s\u00e5 sj\u00e6ldent anvendes.
Problemet med h\u00f8j kardinalitet<\/h2>\n \nS\u00e5 vi f\u00e5r at vide, at bitmap-indekser kun er egnede til felter med lav kardinalitet, dvs. dem med f\u00e5 v\u00e6rdier (f.eks. k\u00f8n eller \u00f8jenfarve), og grunden til dette er, at den almindelige repr\u00e6sentation for s\u00e5danne felter (\u00e9n bit pr. v\u00e6rdi) ved h\u00f8j kardinalitet ville optage for meget plads, og desuden ville disse bitmap-indekser v\u00e6re svagt (sj\u00e6ldent) udfyldt.
Du kan finde roaring bitmapper i de mest popul\u00e6re applikationer. Der findes allerede et stort antal implementationer til mange forskellige programmeringssprog, inklusive mere end tre implementationer til Go.
S\u00e5 vi kan gruppere lignende v\u00e6rdier i grupper inden for 1 cm.<\/p>\n
Og hvis vi ogs\u00e5 ved, at der meget sj\u00e6ldent er mennesker, der er mindre end 50 cm h\u00f8je eller h\u00f8jere end 250 cm, kan vi i princippet omdanne et felt med uendelig kardinalitet til et felt med en kardinalitet p\u00e5 omtrent 200 v\u00e6rdier.<\/p>\n
Selvf\u00f8lgelig kan vi, hvis det er n\u00f8dvendigt, foretage yderligere filtrering efterf\u00f8lgende.<\/p>\n
Problemet med h\u00f8j b\u00e5ndbredde<\/h2>\n \nDet n\u00e6ste problem med bitmap-indekser er, at opdatering af dem kan v\u00e6re meget kostbart.<\/p>\n
Databaser skal give mulighed for at opdatere data i det \u00f8jeblik, hvor hundreder af andre foresp\u00f8rgsler potentielt s\u00f8ger p\u00e5 disse data. Vi har brug for l\u00e5se for at undg\u00e5 problemer med samtidig adgang til data eller andre problemer med delt adgang. Og hvor der er \u00e9n stor l\u00e5s, er der et problem \u2014 lock contention, n\u00e5r denne l\u00e5s bliver en flaskehals.
Sharding er enkelt og almengyldigt. Du kan shard bitmap-indekset, ligesom du ville shard andre data. I stedet for \u00e9n stor l\u00e5s f\u00e5r du mange sm\u00e5 l\u00e5se, og derved undg\u00e5r du lock contention.<\/p>\n
Den anden m\u00e5de at l\u00f8se problemet p\u00e5 er ved at bruge versionsindekser. Du kan have \u00e9n kopi af indekset, som du bruger til at s\u00f8ge eller l\u00e6se, og \u00e9n til skrivning eller opdatering. Og en gang imellem (f.eks. hvert 100 ms eller 500 ms) duplikerer du dem og bytter dem om. Selvf\u00f8lgelig er denne tilgang kun anvendelig i de tilf\u00e6lde, hvor din applikation kan arbejde med et let forsinket s\u00f8geindeks.<\/p>\n
Disse to tilgange kan bruges samtidigt: du kan have et sharded versionsindeks.<\/p>\n
Mere komplekse foresp\u00f8rgsler<\/h2>\n Det sidste problem med bitmap-indekser er, at de, som vi har f\u00e5et at vide, ikke passer godt til mere komplekse typer foresp\u00f8rgsler, s\u00e5som foresp\u00f8rgsler 'over intervallet'.<\/p>\n
Det er sandt, hvis man t\u00e6nker over det, at bitoperationer som AND, OR osv. ikke egner sig s\u00e6rlig godt til foresp\u00f8rgsler af typen 'Vis mig hoteller med en pris pr. nat mellem 200 og 300 dollars'.
Men problemet kan ogs\u00e5 nemt l\u00f8ses ved at bruge en repr\u00e6sentation, der er specielt designet til denne type foresp\u00f8rgsler. I videnskabelige arbejder kaldes det range-encoded bitmaps.
Ved at bruge denne repr\u00e6sentation kan vi svare p\u00e5 denne type s\u00f8geforesp\u00f8rgsel ved at g\u00e5 igennem indekset kun to gange. F\u00f8rst f\u00e5r vi en liste over hoteller, hvor v\u00e6relset koster mindre end 300 dollars, og derefter fjerner vi dem, hvor prisen p\u00e5 v\u00e6relset er mindre end 199 dollars. F\u00e6rdig.
F\u00e6rdige l\u00f8sninger<\/h2>\n \nJeg h\u00e5ber, jeg har fanget lidt af din interesse, og at du nu har et nyttigt v\u00e6rkt\u00f8j til din samling. Hvis du nogensinde skal lave noget lignende, vil du vide, hvilken retning du skal se i.<\/p>\n
Men ikke alle har tid, t\u00e5lmodighed og ressourcer til at oprette bitmap-indekser fra bunden. Is\u00e6r mere avancerede, ved hj\u00e6lp af SIMD, for eksempel.<\/p>\n
Heldigvis er der flere f\u00e6rdige l\u00f8sninger, der kan hj\u00e6lpe dig.
Roaring bitmaps<\/h2>\n \nFor det f\u00f8rste er der den n\u00e6vnte roaring bitmaps-bibliotek, som jeg allerede har talt om. Det indeholder alle de n\u00f8dvendige containere og bitoperationer, du har brug for for at lave et fuldt bitmap-indeks.
Pilosa<\/h2>\n \nEt andet produkt, der kan hj\u00e6lpe dig, er databasen Pilosa, som i bund og grund kun har bitmap-indekser. Det er en relativt ny l\u00f8sning, men den vinder hurtigt popularitet.
Lad os hurtigt tage et kig p\u00e5 et eksempel p\u00e5 brugen af Pilosa til at besvare et sp\u00f8rgsm\u00e5l, som du allerede kender.
Derefter bruger vi NOT p\u00e5 feltet \u00abexpensive\u00bb, krydser resultatet (eller AND-er) med feltet \u00abterrace\u00bb og med feltet \u00abreservations\u00bb. Og til sidst f\u00e5r vi det endelige resultat.
Konklusion<\/h2>\n \n
Det er godt at vide om bitmap-indekser, selvom de ikke er n\u00f8dvendige lige nu. Lad dem v\u00e6re et ekstra v\u00e6rkt\u00f8j i din v\u00e6rkt\u00f8jskasse.<\/p>\n
Vi har set p\u00e5 forskellige tricks til at \u00f8ge ydeevnen for Go og de ting, som Go-kompilatoren ikke helt h\u00e5ndterer godt endnu. Dette er bestemt nyttigt at vide for enhver Go-udvikler.<\/p>\n
Det var alt, hvad jeg ville sige. Tak!habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\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, […]<\/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\n\t
![\"Bitmap-indekser](\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\")