<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Engineering @ Factual - Medium]]></title>
        <description><![CDATA[Factual’s engineers on problems they are solving, projects they are working on, and anything else they find particularly interesting. - Medium]]></description>
        <link>https://medium.com/engineering-factual?source=rss----eecb94d220cc---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Engineering @ Factual - Medium</title>
            <link>https://medium.com/engineering-factual?source=rss----eecb94d220cc---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:30:14 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/engineering-factual" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Data pipeline performance (part 1)]]></title>
            <link>https://medium.com/engineering-factual/data-pipeline-performance-part-1-23965908e345?source=rss----eecb94d220cc---4</link>
            <guid isPermaLink="false">https://medium.com/p/23965908e345</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[perl]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data]]></category>
            <dc:creator><![CDATA[Factual Team]]></dc:creator>
            <pubDate>Tue, 04 Apr 2017 21:05:12 GMT</pubDate>
            <atom:updated>2018-02-14T19:15:38.986Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*06w37VDkT0m9KKRbOwkX1A.png" /></figure><p>If data scientists had their way, we would buy petabytes of memory and never think about IO performance or serialization ever again. Such is the influence of accountants, however, that few companies have realized this otherwise brilliant strategy; instead, whether the workflow is written in Hadoop or in bash, it usually amounts to “stream data in, process a little bit, stream data out.” And this means that performance isn’t purely a matter of profiling code; it’s going to depend on stuff we don’t control like gzip and grep.</p><p>This post is about some experiments I ran to build a better intuition about pipeline performance, and which later informed the design of <a href="https://github.com/spencertipping/ni">ni</a> and other tools I use at Factual.</p><h3>Before we get going: some UNIX measurement tools</h3><p>Two common and absolutely essential utilities are <a href="http://www.catonmat.net/blog/unix-utilities-pipe-viewer/">pv</a> and <a href="https://www.gnu.org/software/units/">units</a>.</p><p>pv is cat, but it gives you a live indicator of how fast data is moving, and your progress/ETA if you use it on a file. For example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EUAoJDRpeSZb3Xpiv5bfJA.png" /></figure><p>This functionality is so useful that I’ve written it into every pipeline constructor I use: nfu has <a href="https://github.com/spencertipping/nfu/blob/master/humongous-survival-guide.md#progress-reporting">a throughput monitor</a>, and its successor ni takes the concept further with <a href="https://github.com/spencertipping/ni/blob/master/doc/monitor.md#monitors">throughput and data pressure</a>.</p><p>units is a command-line calculator that can do unit conversions (like <a href="http://revealingerrors.com/google_miscalculator">the ones Google supports</a>). For instance:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wC6fT0RigzK9F-nxAWCa1w.png" /></figure><p>These tools are great because they make it easy to think about units of throughput, rather than just time — and that’s exactly the type of intuition required when you’re working on large datasets.</p><h3>When time and throughput are different: fast and slow languages</h3><p>A “slow language” usually means a language with a high interpreter overhead — Ruby and Perl sink to the bottom of the <a href="http://benchmarksgame.alioth.debian.org/">benchmarks game</a> for this reason. But that doesn’t mean these languages will be slow for text-processing or similar use cases; <a href="https://github.com/spencertipping/ni">ni</a>, for example, is written in Perl and can process text at 800MB/s with multithreading; Ruby could easily do the same. The key is that these languages provide specialized, efficient vectorized operations that outperform obvious native implementations.</p><p>For example, I wrote three line counting programs, one in C and two in Perl:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JA1Fz7mE473CjxtUwXbZrQ.png" /></figure><p>Here’s wcl1.pl, the obvious version:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZGv7tK7vrCwjZUFAmnLXSw.png" /></figure><p>And here’s wcl2.pl, which doesn&#39;t reallocate any memory:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PxZGWCfMPonAnYWkQBF_QA.png" /></figure><p>I then benchmarked their throughput using a high-speed data source:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Rz5TUSBuBjzKrFoNQuxNtg.png" /></figure><p>There’s nothing up my sleeve here: if you run the above programs, you should see Perl count lines about 3.5x as fast as C. gcc mostly fixes the CPU bottleneck when you compile with -O3, now outperforming Perl as we&#39;d expect:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ac7eezytxV-bhvSWet4dTw.png" /></figure><p>And, of course, the real wc -l is faster still, saturating the data source:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pfyEEKn-1So4vg0WcElw_g.png" /></figure><h3>What’s going on here</h3><p>C is a “fast language” in that it has no interpreter overhead, but the CPU can move data only so quickly itself. Taking a look at the assembly for wcl.c compiled at the default and -O3:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*thxnTrDICbwhVmlOXZQ3tw.png" /></figure><p>It makes sense that this would run slowly: each byte of input data becomes 12 CPU instructions. To get the data rate we observed of ~320MB/sec, the CPU’s throughput would have to be about 3.5Ginsns/sec — about right, given that modern CPUs have some instructions that amortize to 1/2 or 1/3 of a clock cycle. When we compile with -O3, the picture changes completely. gcc unrolls the loop by a factor of 16 and uses SSE instructions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b6hmIUJ7oYIMsR0Fu0fDjQ.png" /></figure><p>This implementation uses 38 instructions for 16 bytes, which is about six times as efficient as before.</p><p>Ok, but what’s going on with wc -l? <a href="http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob;f=src/wc.c;h=94cbaff9ad6d8fbadff74ebb1ad4a1101438e8bd;hb=HEAD#l295">The source</a> provides a hint:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*750W2Mde--W83qOmY-RoYQ.png" /></figure><p>Intuitively this makes sense: function call overhead would dictate that the more work memchr can do internally, the faster this will go. But memchr itself is still outperforming the -O3 byte loop by more than 2x. Here&#39;s how <a href="https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=ca9fd99f2105003d0b56285ff3f41ba10dad8685;hb=HEAD#l100">it works</a>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*s-9_IxtlK0F3Uk1K8tIFmQ.png" /></figure><p>Like -O3, it&#39;s also vectorizing; but this version, although more efficient for long lines, is optimized for cases where most of the time is spent searching (i.e. a hit on any given byte is unlikely). All of wc -l&#39;s advantage is data-dependent, which becomes evident if we feed it just a bunch of newlines:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZfbRyXyqF-qwd5tapEom8g.png" /></figure><p>memchr is why Perl ends up being faster than the original C version: most of the data is being pushed through the very high-throughput inner loop, and only a few bytes have to go the slow route through the Perl interpreter itself. Other aspects of overhead, like copying lines into $_ and updating various internal variables, made it unable to compete with -O3 even for long lines.</p><h3>The Takeaway</h3><p>In a throughput-bound world, what’s the right tool for the job? I haven’t found a particularly good way to predict it aside from understanding how things work and testing on specific data. The complicating factors are that (1) many tools have been optimized for a specific use case (e.g. Perl and text processing), and (2) many of the fastest algorithms are data-dependent and aren’t worst-case optimal. <a href="http://www.agner.org/optimize/">Agner Fog’s optimization guides</a> illustrate the subtleties of even the hardware itself; as the infrastructure increases in complexity, optimization becomes an increasingly vertical pursuit.</p><p>In part 2 I’ll go into some lower-level aspects like input encoding and garbage collection, and part 3 will be an unbelievably smashing wrap-up of some kind. Stay tuned.</p><p>- Spencer Tipping, Software Engineer</p><p><em>Enjoy this read?</em></p><ul><li><em>Please click the heart icon to recommend it to others.</em></li><li><em>You can read more Factual Engineering posts at our </em><a href="https://www.factual.com/category/engineering/"><em>blog</em></a><em>.</em></li><li><em>You may be interested in working at Factual! </em><a href="https://www.factual.com/jobs#openings"><em>See our openings</em></a><em>.</em></li></ul><p><em>Originally published at </em><a href="http://www.factual.com/blog/Data-Pipeline-Performance"><em>http://www.factual.com/blog/Data-Pipeline-Performance</em></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=23965908e345" width="1" height="1" alt=""><hr><p><a href="https://medium.com/engineering-factual/data-pipeline-performance-part-1-23965908e345">Data pipeline performance (part 1)</a> was originally published in <a href="https://medium.com/engineering-factual">Engineering @ Factual</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Category Considerations: Assigning Categories to Factual’s Global Places]]></title>
            <link>https://medium.com/engineering-factual/category-considerations-assigning-categories-to-factuals-global-places-719f6614e69c?source=rss----eecb94d220cc---4</link>
            <guid isPermaLink="false">https://medium.com/p/719f6614e69c</guid>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Ross Israel]]></dc:creator>
            <pubDate>Wed, 13 Jul 2016 23:46:21 GMT</pubDate>
            <atom:updated>2016-07-14T17:12:12.136Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3-apQbxvZb_pg7mHY2nMxw.png" /></figure><p>One of the hardest attributes to pin down in our <a href="https://www.factual.com/products/global">Global Places data</a> is our Category Labels field. This is where we describe what a place is or what service it provides. It’s what tells you that <a href="https://www.factual.com/1946c2b0-73ee-4e01-9c56-1f1f342681ef">LaRocco’s Pizzeria</a> is a Pizza Restaurant, whereas <a href="https://www.factual.com/27f1de92-f4c0-481f-8501-517c7da8cfdb">Rocco’s Tavern</a>, a mere 200 feet down the street, is both a Sports Bar and a Pizza Restaurant.</p><p>While the process of building data is complex in and of itself, it is exacerbated by a number of issues that impact categories specifically. Categorizing a business is often a subjective endeavor and it can be extremely difficult to guess what category a place may be from any location or name-based cues. For example, it is difficult to know that <a href="https://www.factual.com/6644cf15-2b20-4473-b95a-1f30556a3eed">Public School 310</a> is a restaurant, as opposed to a school, solely by looking at the name.</p><p>We work hard to build high quality data, so our customers receive correct information about the places they care about. Having said that, when you provide data for over 90 million places across 50 countries, there will be some warts. Since categorization poses such a thorny problem, some of these imperfections rise to the surface from time to time. With that in mind, we decided to show some of these challenges, explain why they arise, and describe how we address them so that our data is always of the highest quality.</p><h3>Where Categories Come From</h3><p>In order to understand where challenges in categorization come from, it’s important to first understand how categories are assigned to places. We build data by gathering information from multiple <em>sources</em> (feedback from different partner apps, <a href="https://www.factual.com/blog/factuals-trusted-data-contributor-program-adds-13-new-partners">trusted data contributors</a>, data from the web, etc.). Pieces of information about the same place are called <em>inputs</em>, and a key part of our process is determining which value is correct if inputs from different sources have conflicting values.</p><p>For categories, every source has their own taxonomy, or way of defining how a business or point of interest fits in the world. Likewise, we have our own <a href="http://developer.factual.com/working-with-categories/">taxonomy</a> at Factual. So, a preliminary, essential part of our category process is <em>mapping</em> all of those source taxonomies onto ours. For example, in our taxonomy, pizza restaurants fall under Social &gt; Food and Dining &gt; Restaurants &gt; Pizza. But this can be expressed in a seemingly limitless number of ways by other sources, such as: <em>restaurants — pizza, pizza restaurants, pizzerias, pizza places, pizza-restaurants</em>, etc., all of which must point to the correct node in our taxonomy. We have 466 categories in our taxonomy and other sources can have even more than that, and we are constantly gathering information from new sources; so this mapping must be continually maintained to include as accurate and up-to-date information as possible. We keep our mappings up to date both by adding specific taxonomy mappings one at a time, and via a machine learning-based approach that can add thousands of mappings at a time (developed with one of our former interns, <a href="https://www.factual.com/blog/ask-an-intern-sarah-krasnik-data-summer-2015">Sarah Krasnik</a>).</p><p>The next step in the process is analyzing the data gathered from all of our millions of unique sources to build our places dataset. Once we have identified the many data points that refer to a single place, we then algorithmically determine the most factual representation of that place. To select which categories get assigned to our places, we systematically consider the category information from all of the inputs associated with each place to discover what category or set of categories is most likely correct. Since places can often be represented by more than one category (think bar + restaurant) we surface up to three categories per record. We also keep a small list of categories that can co-occur together, (one place can be labeled both a gas station and a convenience store, for example), so that we don’t end up with bizarre groupings like Pharmacy + Museum (a place can be either a pharmacy or a <a href="https://www.factual.com/09d9cd72-df34-4201-a35a-9baab61ba610">museum</a>, not both).</p><h3>Category Confusions</h3><p>Here are a few examples of particularly tricky place categorizations that we have seen in our data and how we caught and fixed them.</p><h4>Bethsaida Seventh Day Church</h4><p>One of the obvious problems associated with categories is simply not having one. Some location services will fill in the blanks when they are unsure of what a place is with a non-informative category label such as “local business” or “establishment.” We prefer to leave the label off all together if we cannot provide a meaningful one (it’s worth noting that this is rare; over 97% of our places in the US have a category assigned). This can happen when we either can’t get reliable information about what a place is, or if the description of the place has not been mapped to our taxonomy yet. When <a href="https://www.factual.com/b2071dac-bdb2-4555-bae3-8d56ed71d4bb">Bethsaida Seventh Day Church</a> first surfaced in our data, it was a case of the former problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ayPAFV9BCVyw58KSyZyG-g.png" /></figure><h4>Explanation</h4><p>You might be thinking: “Why don’t you just look at the name? You can plainly see that it’s a church!” It turns out that trying to assign categories strictly based off of business names is an unreliable approach. While it’s true that “church” often shows up in the names of churches, it also shows up in the names of other things, such as the radio station <a href="https://www.factual.com/c1e6fc31-b561-43ce-ba30-40e439c72ce0">Wxmc-1310 Am-New Jerusalem Church Lines</a>. So, categorizing based on the word “church” would get that wrong. Now you might be thinking something along the lines of: “But it will work if Church is the first or last word, you could use regular expressions, right?” However, even when you restrict the search with these types of rules you’ll still run into things like <a href="https://www.factual.com/42bc4d46-6a3c-4ed9-b3dd-4eb2ddc40c26">Church &amp; Dwight Co.</a>, which manufactures cleaning products or <a href="https://www.factual.com/4ca52108-c3b5-4a2c-89ae-c2a4a7099bc1">Thomas Carton Church</a>, an ophthalmologist.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b00HdmnXoomAvRVbXFYQTA.png" /></figure><p>When businesses without categories pop up in our data, they typically get categories assigned quickly since we have a dynamic categorization system in place that allows us to make changes at any time to rectify any problems. We add new taxonomy mappings every month, which leads to both adding new categories and correcting existing errors. On top of that, we’re constantly adding new sources to continually improve the quality of our places data. With new data and new category mappings, we assign meaningful categories to Factual places on an ongoing basis.</p><h4>Vape Star</h4><p>The recent increasing popularity of vaping has lead to a rise in vape-associated businesses, e.g. retail stores and vape bars, where people can gather to vape together. One such establishment, <a href="https://www.factual.com/9a346e84-49ba-495f-8850-c66a00b275e6">Vape Star</a>, was initially mislabeled as providing home improvement services.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_Xzy39Aix_ycoNeUCRfPeQ.png" /></figure><h4>Explanation</h4><p>As mentioned above, one of the challenges in assigning categories is mapping the components of our sources’ taxonomies onto our own. The problem for Vape Star is that one of the sources provided a category of “pipe and smoker”, which we had incorrectly mapped to our home improvement node. This happened because in lots of instances, “pipe” legitimately shows up in descriptions of home improvement businesses. For example, businesses like <a href="https://www.factual.com/2cc01f7a-25a5-4302-940e-a96f92c7d506">Southland Pipe</a> and <a href="https://www.factual.com/045466df-426f-4668-b027-7b15761a2cbb">Star Pipe Products</a> that sell supplies for pipe-specific construction are often described using just the words “pipe” or “pipes”. So you can see how “pipe and smoker” could be grouped with those other descriptions. In cases like this, we simply update that mapping in our system, and any businesses with this description get automatically assigned to the appropriate Factual category.</p><h3>Conclusion</h3><p>Assigning the correct categories to places is deceptively tricky, but it is exactly the type of problem that our engineers love to take on at Factual. We embrace the challenge and allot a considerable amount of time and resources towards ensuring that our Global Places data continue to have the most accurate and comprehensive category coverage possible.</p><p>- Ross Israel, Data Engineer</p><p><em>Enjoy this read?</em></p><ul><li><em>Please click the heart icon to recommend it to others.</em></li><li><em>You can read more Factual Engineering posts at our </em><a href="https://www.factual.com/blog/category/engineering"><em>blog</em></a><em>.</em></li><li><em>You may be interested in working at Factual! </em><a href="https://www.factual.com/jobs#openings"><em>See our openings</em></a><em>.</em></li></ul><p><em>Originally published at </em><a href="https://www.factual.com/blog/category-considerations-assigning-categories-to-factual-places"><em>https://www.factual.com/blog/category-considerations-assigning-categories-to-factual-places</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=719f6614e69c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/engineering-factual/category-considerations-assigning-categories-to-factuals-global-places-719f6614e69c">Category Considerations: Assigning Categories to Factual’s Global Places</a> was originally published in <a href="https://medium.com/engineering-factual">Engineering @ Factual</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fast Indirect Sorting in Java]]></title>
            <link>https://medium.com/engineering-factual/fast-indirect-sorting-in-java-87a640d6b55f?source=rss----eecb94d220cc---4</link>
            <guid isPermaLink="false">https://medium.com/p/87a640d6b55f</guid>
            <category><![CDATA[java]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Spencer Tipping]]></dc:creator>
            <pubDate>Tue, 28 Jun 2016 02:25:22 GMT</pubDate>
            <atom:updated>2016-07-20T17:50:06.137Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jbtGC5nyNDJo5ytFZeheOQ.png" /></figure><p>I was recently writing some performance-sensitive code in which I had a double array of distances (one per element), and I wanted to get a list of elements sorted by distance:</p><pre>double[] distances = { d1, d2, ..., dN }; <br>Element[] elements = { e1, e2, ..., eN };<br>// do something here to sort elements[] by distances[]</pre><p>Java provides Arrays.sort for direct sorting; that is, it’s easy to ask it to sort distances or elements by its natural ordering. But in this situation, the two arrays are tied together only by indexes, which would require a comparator to maintain a reverse lookup from Element to either its index, or to its distance. That’s a lot of overhead — particularly because the map would require generic boxing of either type of value.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/713/1*aIfKoUK6qpaKz7dj5InU2A.png" /><figcaption>credit: xkcd <a href="https://xkcd.com/license.html">https://xkcd.com/license.html</a></figcaption></figure><p>Luckily there’s an interesting way to solve this problem that meets the following requirements:</p><ol><li><a href="http://stackoverflow.com/questions/23587314/how-to-sort-an-array-and-keep-track-of-the-index-in-java">No extra memory is allocated</a>, aside from the two arrays above, each of which is allowed to be clobbered</li><li>We do not write any sorting code; we just use standard APIs</li><li>We end up being able to access the distance-sorted Elements each in constant time</li></ol><p>I should also mention that the resulting ordering isn’t exact, but it is very close.</p><p>Before I go into how I solved it (which took a while to think of), you should see what you come up with. It’s a fun problem.</p><h4>The Solution</h4><p>First in code:</p><pre>int largest = distances.length - 1;<br>long mask = -1l;<br>while ((~mask &amp; largest) != largest) mask &lt;&lt;= 1;<br>for (int i = 0; i &lt; distances.length; ++i)<br> distances[i] = Double.longBitsToDouble(<br>      Double.doubleToLongBits(distances[i]) &amp; mask | i);<br>Arrays.sort(distances);</pre><p>Now distances[] is sorted such that the distance of elements[(int) (Double.doubleToLongBits(distances[i]) &amp; ~mask)] is ascending for ascending values of i.</p><h4>How It Works</h4><p>Each distance is encoded as a double-precision float, which internally looks like this:</p><pre>+--- sign<br>|<br>| +- exponent<br>| |<br>S EEEEEEEEE MMMM ... MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM<br>            |---------------52 mantissa bits--------------------|</pre><p>The mantissa for all but the smallest numbers is <em>normal</em>, meaning that it’s interpreted as though there were a leading 1 in a 53rd bit. This puts an upper bound on the significance of low-order mantissa bits, which is what we need for the code above to work.</p><p>Depending on how the distances are distributed, we can make a probabilistic argument about how much the ordering will change as we lose precision in the mantissa; specifically, suppose we’ve got two distances a and b and we lose 24 bits:</p><pre>A = S EEEEEEEEE MMMM ... MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM <br>B = S EEEEEEEEE MMMM ... MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM <br>                |---------------| |------------------------|<br>               keeping these bits               losing these</pre><p>The probability of changing the ordering between these two points is the same as the probability that the bits we’re keeping are all identical between them. <a href="https://en.wikipedia.org/wiki/Benford&#39;s_law">Benford’s law</a> converges rapidly to a uniform distribution for subsequent digits and the leading 1 is implied, so in practical terms P(reordering) is very nearly 2^-k, where <em>k</em> is the number of bits being kept.</p><p>If we can lose some precision without causing problems (which for my use case was true), then we can arbitrarily reassign low-order mantissa bits to store information. In this case I’m storing the original array index for each distance in its low-order bits. Here’s the code above, piece by piece:</p><pre>// The largest index is distances.length - 1; when we encode stuff, // we need to reserve enough bits to represent this quantity. </pre><pre>int largest = distances.length - 1;</pre><pre>// Now construct a mask that selects the bits we&#39;re keeping in the // double. -1<br>// has all bits set, and each left-shift clears one from the right. The test <br>// &quot;(~mask &amp; largest) != largest&quot; will fail and end the loop when the bits we&#39;re <br>// keeping are disjoint from the ones we&#39;ll use to store the indexes. </pre><pre>long mask = -1l;<br>while ((~mask &amp; largest) != largest) mask &lt;&lt;= 1;</pre><p>Then we tag each distance this way (here I’m assuming we’ve got between 219and 220elements, so we reserve 20 bits):</p><pre>d[i] S EEEEEEEEE MMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM <br>       |-----------------original bits----------------||-----tag space--| <br>&amp; mask 1 111111111 1111 11111111 11111111 11111111 11110000<br> 00000000 00000000<br>| i     0 000000000 0000 00000000 00000000 00000000 0000IIII IIIIIIII IIIIIIII </pre><pre>=       S EEEEEEEEE MMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMIIII IIIIIIII IIIIIIII</pre><pre><br>// Store the original index into each double using the strategy described above </pre><pre>for (int i = 0; i &lt; distances.length; ++i) <br>  distances[i] = Double.longBitsToDouble(<br>    Double.doubleToLongBits(distances[i]) &amp; mask | i);</pre><p>At this point Arrays.sort() will be none the wiser and will sort the array normally (and, importantly, very quickly).</p><p>Now we can read the tags back to recover the ordering, which looks like this:</p><pre>  mask  1 111111111 1111 11111111 11111111 11111111 11110000<br> 00000000 00000000 <br> ~mask  0 000000000 0000 00000000 00000000 00000000 00001111 <br> 11111111 11111111 </pre><pre>  d[i]  S EEEEEEEEE MMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMIIII<br> IIIIIIII IIIIIIII <br>&amp; ~mask 0 000000000 0000 00000000 00000000 00000000 0000IIII<br> IIIIIIII IIIIIIII <br>(int)                                      00000000 0000IIII<br> IIIIIIII IIIIIIII</pre><pre>// Do the mask inversion up front rather than inside each iteration; now it <br>// selects the tag bits. </pre><pre>mask = ~mask; </pre><pre>// Collect the elements using the original positions as an indirect index. </pre><pre>List&lt;Element&gt; sorted = new ArrayList&lt;&gt;(elements.length);<br>for (double d : distances) <br>  sorted.add(elements[(int) (Double.doubleToLongBits(d) &amp; mask)]);</pre><h4>Other Languages</h4><p>You can use this hack in any language to similar effect, though you lose most of the performance advantages if the language doesn’t have bitwise access to doubles. Even a well-optimized sorting function that doesn’t have the Java indirection problem will benefit if you can store the data in the floats directly, since the array will be smaller in memory and you’re doing O(n log n) element-copy operations.</p><p>It is possible to simulate bitwise access using floating point arithmetic and int casting (which <a href="https://github.com/spencertipping/flotsam/blob/master/js/flotsam.js#L81">flotsam does in Javascript</a>), but it requires some care — particularly in this case, when any rounding error will cause data loss within the indexes. It’s also a lot slower than the bitwise solution above, possibly enough to outweigh any performance benefits in the sorting logic itself.</p><h4>When This Kind of Thing Doesn’t Work</h4><p>Distances are ideal for this type of hack because they tend to be spread over a wide range of magnitudes, and even when they aren’t, you don’t tend to care much whether the points are exactly ordered (i.e. the parts-per-trillion error we’re introducing doesn’t really pose a problem most of the time). Not all distributions are so robust to bit-twiddling, though. In particular, if you had a case where the variance were many orders of magnitude smaller than the average — e.g. 1,000,000,000 ±0.003 — then there’s a good chance the small bits would matter. It’s important to figure out the probability of a false reordering before losing bits of precision.</p><p><em>Enjoy this read?</em></p><ul><li><em>Please click the heart icon to recommend it to others.</em></li><li><em>You can read more Factual Engineering posts at our </em><a href="https://www.factual.com/blog/category/engineering"><em>blog</em></a><em>.</em></li><li><em>You may be interested in working at Factual! </em><a href="https://www.factual.com/jobs#openings"><em>See our openings</em></a><em>.</em></li></ul><p><em>Originally published at </em><a href="https://www.factual.com/blog/fast-indirect-sorting-in-java"><em>https://www.factual.com/blog/fast-indirect-sorting-in-java</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=87a640d6b55f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/engineering-factual/fast-indirect-sorting-in-java-87a640d6b55f">Fast Indirect Sorting in Java</a> was originally published in <a href="https://medium.com/engineering-factual">Engineering @ Factual</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>