<story><title>Bitmap Indexes in Go: Search Speed (2019)</title><url>https://habr.com/en/company/badoo/blog/455608/</url></story><parent_chain></parent_chain><comment><author>todd8</author><text>This is an interesting article, and I&amp;#x27;ll probably take a look  at the go language profiling capabilities and built-in machine independent assembler.&lt;p&gt;The idea of using bitmaps for retrieval on multiple indexes isn&amp;#x27;t new. Not surprisingly Knuth has a good discussion of the technique [Knuth], it was explained very well with a nice illustration of using notched recipe cards that is worth taking a peek at.&lt;p&gt;-- straying off topic below this line --&lt;p&gt;One surprising note, Calvin N. Mooers invented zatocoding in 1947. This technique used the notched cards for information retrieval and cited by Knuth under the subsection &lt;i&gt;superimposed coding&lt;/i&gt;. Calvin N. Mooers went on to invent the &amp;quot;Reactive Typewriter&amp;quot; in the 1960s. This was an visionary implementation of how users might interact with computers using a terminal device (like a teletype). Mooers&amp;#x27; Reactive Typewriter was programmed using a language he invented named TRAC.&lt;p&gt;TRAC is a macro based language. It, like the roughly contemporaneous GPM of Christopher Strachey (1965), is a Turing complete language based on macros that can define other macros, etc. I learned about TRAC in the mid 1970s from Ted Nelson&amp;#x27;s book &lt;i&gt;Computer Lib&amp;#x2F;Dream Machines&lt;/i&gt; [Nelson]. It was one of three languages featured in that book. A fun little book, &lt;i&gt;Etudes for Programmers&lt;/i&gt;, which I bought in 1978 inspired me to implement a version of TRAC. It&amp;#x27;s a nice exercise.&lt;p&gt;Many years later (I believe it was 1991), during an Open Software Foundation meeting in Cambridge, Massachusetts, I got to meet Mooers in person, he was sitting in the front row during a presentation, and I got to speak with him briefly afterwards.&lt;p&gt;By the way, Christopher Strachey wrote the first paper on the concept of time-sharing in 1959 and in the 1970&amp;#x27;s with Dana Scott is credited with coming up with the important development in the theory of programming languages known as Denotational Semantics.&lt;p&gt;[Knuth] Donald Knuth. (1973).The Art of Computer Programming, Vol 3&amp;#x2F;Sorting and Searching. Section 6.5, Retrieval on Secondary Keys. Addison-Wesley.&lt;p&gt;[Nelson] Theodor H Nelson. (1974). Computer lib : you can and must understand computers now. ISBN 0893470023. OCLC 11182412. &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Computer_Lib&amp;#x2F;Dream_Machines&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Computer_Lib&amp;#x2F;Dream_Machines&lt;/a&gt;&lt;p&gt;[Strachey] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Christopher_Strachey#cite_note-21&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Christopher_Strachey#cite_note...&lt;/a&gt;&lt;p&gt;[Wetherell] Charles Wetherell, Etudes for Programmers,  Prentice Hall, 1977, &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.amazon.com&amp;#x2F;Etudes-Programmers-Charles-Wetherell&amp;#x2F;dp&amp;#x2F;0132918072&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.amazon.com&amp;#x2F;Etudes-Programmers-Charles-Wetherell&amp;#x2F;...&lt;/a&gt;</text></comment>
<story><title>Bitmap Indexes in Go: Search Speed (2019)</title><url>https://habr.com/en/company/badoo/blog/455608/</url></story><parent_chain></parent_chain><comment><author>manimino</author><text>Writing an object indexer is a fun project. My Python indexer, ducks [1], went through a lot of the same development stages, such as supporting only exact-value matches at first. I tried binning too, but ultimately using a BTree was simpler and performed well enough (500ns for a log-n tree traversal, vs 50ns hash).&lt;p&gt;Still looking for a way to apply bitmap indexing in ducks; it would surely speed up multi-index queries, but I haven&amp;#x27;t found an implementation that&amp;#x27;s worth the tradeoffs yet.&lt;p&gt;[1] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;ducks.readthedocs.io&amp;#x2F;en&amp;#x2F;latest&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;ducks.readthedocs.io&amp;#x2F;en&amp;#x2F;latest&amp;#x2F;&lt;/a&gt;</text></comment>