I will echo what others have said: a better algorithm is going to win in terms of performance gains. That said, I work in image processing, which as a problem domain can be stickier. For example, many years ago I had a chunk of code that looked like this: void FlipBuffer(unsigned char *start, unsigned char … Read more
See “Hacker’s Delight”, multiword division (pages 140-145). The basic concept (going back to Knuth) is to think of your problem in base-65536 terms. Then you have a 4 digit by 2 digit division problem, with 2/1 digit division as a primitive. The C code is here: https://github.com/hcs0/Hackers-Delight/blob/master/divmnu.c.txt
4×4 matrix multiplication is 64 multiplications and 48 additions. Using SSE this can be reduced to 16 multiplications and 12 additions (and 16 broadcasts). The following code will do this for you. It only requires SSE (#include <xmmintrin.h>). The arrays A, B, and C need to be 16 byte aligned. Using horizontal instructions such as … Read more
There appears to be a related bug report, Bug 59659 – large zero-initialized std::array compile time excessive. It was considered “fixed” for 4.9.0, so I consider this testcase either a regression or an edgecase not covered by the patch. For what it’s worth, two of the bug report’s test cases1, 2 exhibit symptoms for me … Read more
Cache coherence. When you scan horizontally, your data will be closer together in memory, so you will have less cache misses and thus performance will be faster. For a small enough rectangle, this won’t matter.
Interestingly, using -fdata-sections can make the literal pools of your functions, and thus your functions themselves larger. I’ve noticed this on ARM in particular, but it’s likely to be true elsewhere. The binary I was testing only grew by a quarter of a percent, but it did grow. Looking at the disassembly of the changed … Read more
This answer is obsolete : the dropDups option was removed in MongoDB 3.0, so a different approach will be required in most cases. For example, you could use aggregation as suggested on: MongoDB duplicate documents even after adding unique key. If you are certain that the source_references.key identifies duplicate records, you can ensure a unique index … Read more
Is there any faster way of doing this in Java? Yes. Scanner is fairly slow (at least according to my experience). If you don’t need to validate the input, I suggest you just wrap the stream in a BufferedInputStream and use something like String.split / Integer.parseInt. A small comparison: Reading 17 megabytes (4233600 numbers) using … Read more
Here’s a proof that, in the absence of the anomalous jumps mentioned by harold in the comments, the “start small” algorithm is optimal: First, let’s establish that “start small” always produces a feasible solution — that is, one that doesn’t contain any short encoding of a too-long jump. The algorithm essentially amounts to repeatedly asking … Read more
UPDATE: this post answered is now superseded by this new one (which take into account the updates of the question) providing an even faster code based on a different approach. Step 1: better algorithm First of all, building a k-d tree runs in O(n log n) time and doing a query runs in O(log n) … Read more