<story><title>Why we didn&apos;t use a bloom filter</title><url>http://dr-josiah.blogspot.com/2012/03/why-we-didnt-use-bloom-filter.html</url></story><parent_chain></parent_chain><comment><author>TeMPOraL</author><text>&lt;i&gt;&quot;Have you ever used the STL? I did for about 6 months professionally, and I&apos;m glad that I could go back to C and Python. More seriously, object orientation in C++ doesn&apos;t come for free. Aside from the pain of the syntax of using C++ templates (and difficult to parse error messages), all of that object orientation hides the complexity of method dispatch in what are known as vtables. If your system has to call them to dispatch, you are wasting time in that processing when you could be doing something else.&quot;&lt;/i&gt;&lt;p&gt;This fragment made me WTF, so either I missed something in the C++ development of last few years, or...&lt;p&gt;a) How can you make standard-OOP-like method dispatch &lt;i&gt;faster&lt;/i&gt; than vtables?&lt;p&gt;b) Since when STL uses so much of virtual functions anyway? Last time I checked, it avoided any kind of polymorphism at all, for speed reasons. (and it doesn&apos;t really need to use much; C++ templates are nice tools that can make a pointer to function and a function object work in the same place &lt;i&gt;just because&lt;/i&gt; you can stick &quot;()&quot; to the right of the passed parameter and it will compile, no run-time work needed).&lt;p&gt;c) (it seems to be implied, though not explicitly stated). Going faster than STL... in Python?</text></comment>
<story><title>Why we didn&apos;t use a bloom filter</title><url>http://dr-josiah.blogspot.com/2012/03/why-we-didnt-use-bloom-filter.html</url></story><parent_chain></parent_chain><comment><author>ComputerGuru</author><text>Really an unfair article. The premise, title, and bulk have nothing to do with what actually happened.&lt;p&gt;With his &lt;i&gt;custom software&lt;/i&gt; he&apos;s solving a completely different problem with a different algorithm that was only possible based on observations unique to his dataset:&lt;p&gt;&lt;i&gt;I originally started with code very similar to the C++ STL set intersection code and was dissatisfied with the results. By observing that the longer sequences will skip more items than the shorter sequences, I wrote a 2-level loop that skips over items in the longer sequence before performing comparisons with the shorter sequence. That got me roughly a 2x performance advantage over the STL variant.&lt;/i&gt;&lt;p&gt;Let&apos;s call this apples. Then he talks about how using C++ STL wouldn&apos;t do the trick since he doesn&apos;t care about the data, only the count (oranges). And how bloom filters applied naïvely to the raw data would still take longer (zebras).&lt;p&gt;He&apos;s solving a completely different problem, and lambasting perfectly viable technologies for taking longer &lt;i&gt;to solve a completely different problem&lt;/i&gt;.&lt;p&gt;Now obviously there&apos;s a good blog post and moral in there: don&apos;t solve the wrong problem. Generic algorithms can&apos;t be both generic and special at once - they&apos;re not always going to give you what you&apos;re looking for and only what you&apos;re looking for, and that&apos;s a cost to be taken into consideration at any time that you&apos;re trying to choose a solution. But don&apos;t criticize them for being slow, and then in a postscript say &quot;and I don&apos;t need the actual results of this algorithm, anyway.&quot;</text></comment>