stub.go with function headers to bridge the two worlds: Go and assembly.\n<\/li>\n<\/ul>\n\n
First, let's look at the scalar versions.
Unfortunately, we cannot force the compiler to inline our functions written in assembly. The Go compiler does not currently have this capability, although there has been a request to add it for quite some time.<\/p>\n
That is why it is impossible to gain any advantages from small functions in assembly. We either have to write large functions, use the new math\/bits package, or avoid assembly altogether.<\/p>\n
Now let\u2019s take a look at the vectorized versions of our functions.
The second innovation is that I decided to use an optimization called loop unrolling, which means performing eight loop iterations manually before jumping back to the start of the loop. This optimization reduces the number of branches in the code, and it is limited by the number of free registers available.
Issues with bitmap indexes<\/h2>\n \nNow that we have examined the simple implementation of a bitmap index in Go and a much more performant one in assembly, let\u2019s finally discuss why bitmap indexes are so rarely used.
The High Cardinality Problem<\/h2>\n \nSo, we are told that bitmap indexes are suitable only for fields with low cardinality, meaning those with few values (such as gender or eye color). The reason is that the usual representation of such fields (one bit per value) will take up too much space in cases of high cardinality, and moreover, these bitmap indexes will be sparsely (rarely) populated.
You can find roaring bitmaps in some of the most popular applications. There are already a huge number of implementations for a variety of programming languages, including more than three implementations for Go.
Thus, we can group similar values into bins within 1 cm.<\/p>\n
And if we also know that very few people have a height less than 50 cm and greater than 250 cm, we can essentially turn a field with infinite cardinality into a field with cardinality of about 200 values.<\/p>\n
Of course, if needed, we can perform additional filtering later.<\/p>\n
The issue of high bandwidth<\/h2>\n \nThe next issue with bitmap indexes is that updating them can be very costly.<\/p>\n
Databases must allow for updating data at the moment when potentially hundreds of other queries are searching through that data. We need locks to avoid problems with concurrent data access or other concurrency issues. And where there is one big lock, there is a problem \u2014 lock contention, when that lock becomes a bottleneck.
Sharding is simple and well-known. You can shard a bitmap index just as you would shard any other data. Instead of one large lock, you obtain many smaller locks and thus eliminate lock contention.<\/p>\n
The second way to solve the problem is by using versioned indexes. You may have one copy of the index that you use for searching or reading, and another for writing or updating. And every so often (e.g., every 100 ms or 500 ms), you duplicate them and switch them. Of course, this approach is applicable only when your application can work with a slightly outdated search index.<\/p>\n
These two approaches can be used simultaneously: you may have a sharded versioned index.<\/p>\n
More complex queries<\/h2>\n The last problem with bitmap indexes is that, as we are told, they are poorly suited for more complex types of queries, such as range queries.<\/p>\n
Indeed, if you think about it, bitwise operations like AND, OR, etc., are not very suitable for queries like \"Show me hotels with room rates from $200 to $300 per night.\"
But the problem is easily solved by using a representation specifically created for this type of query. In academic papers, it is called range-encoded bitmaps.
Using this representation, we can respond to this type of search query by scanning the index only twice. First, we get a list of hotels where the room cost is less than 300 dollars, and then we filter out those where the cost is below 199 dollars. Done.
Ready-made solutions<\/h2>\n \nI hope I have piqued your interest a bit and you now have another useful tool in your arsenal. If you ever need to do something similar, you'll know where to look.<\/p>\n
However, not everyone has the time, patience, and resources to create bitmap indexes from scratch. Especially more advanced ones, using SIMD, for example.<\/p>\n
Fortunately, there are several ready-made solutions that can help you.
Roaring bitmaps<\/h2>\n \nFirst, there\u2019s the roaring bitmaps library that I mentioned earlier. It contains all the necessary containers and bitwise operations you will need to create a full-fledged bitmap index.
Pilosa<\/h2>\n \nAnother product that can help you is the Pilosa DB, which essentially only has bitmap indexes. It is a relatively new solution but is quickly winning hearts.
Let\u2019s quickly take a look at an example of using Pilosa to answer a question you're already familiar with.
After that, we use NOT on the field 'expensive', then intersect the result (or AND it) with the field 'terrace' and the field 'reservations'. And finally, we get the final result.
Conclusion<\/h2>\n \n
It's good to know about bitmap indexes, even if you don't need them right now. Let them be one more tool in your toolbox.<\/p>\n
We reviewed various tricks to enhance performance for Go and the issues that the Go compiler is still not handling very well. This is certainly useful knowledge for every Go programmer.<\/p>\n
That's all I wanted to share. Thank you!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](\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\")