 |
|
Computer programmer's questionWhat is the most efficient way to determine the sum of the set bits in a large array of 16-bit values? This is a standard question to the computer scientist's knowledge, which even Google has already asked its job applicants.[1][2] AnswerI thought I would have some fun and investigating it too, based on my knowledge as a senior computer science engineer. The result is a Visual Studio solution (source code) with many comments, in which the optimization steps are shown and the speeds are measured. If you are interested, you can download the complete solution or just the program executable on any Windows machine and run it on your own machine. In the following I show which optimization steps that can be taken. The starting point is an array named 'array' filled with a large amount of 16-bit integer values. In my solution it's a million, but you can change it in the program. A first, naive and straightforward programmed solution:
Let's start optimizing that. The inner loop can be written with Shift instead of divisions:
To avoid the Modulo operator '%' (combination of division and subtraction), you can work with AND ('&'):
The comparison "unequal 0" is also a bit faster than a comparison with 'probeBit', because 0 is a constant and the processor already has a hardware instruction for it. Anyone who has been in the IT business for some time knows this for example under the name 'BEQ' (Branch if equal). But the question is whether the IL implements that at all. Now you can see that 'bitCount' and 'probeBit' are executed once for each array element. These are COM operations. Of course they will notice the 2nd time that the variable already exists, but they will still have to look it up each time (you can check this out by declaring a new variable during a break in the debugger). In general, you can always move iteration variables up and outside of a loop. But you also lose some checks which the compiler does for you, to assure that the variables are not accessed outside its planned scope. But in our case this is completely irrelevant. The loop is overseeable and what we want is speed.
We can now also do without 'elementBits' and directly increase 'count':
Doesn't bring much, but still a little bit. The test for the lowest bit in C# is a bit complicated. In other programming languages there is often a function 'Odd(x)' which can do this. But this function is missing in C#. If you think outside the box you can see that the sign is also represented by a bit. This way you can easily test the highest bit instead of the lowest bit:
Now you would think there is nothing more to simplify. But far from it. Already in the year 1960 Peter A. Wegner found an even simpler method to count the bits in one word. This method looks like this:
Wait, a minus one combined with an AND, how should that work? It's not so easy to understand. My analysis shows the following:
Conclusion: In both cases, even or odd, exactly one 1 is cleared. And in both cases it's the most right one. So we can increase the 'count' at each iteration until the value goes to 0. The last method to consider is whether the use of volatile might bring something. This modifier only exists in the newer C# versions. It tells the compiler to keep a variable in a register instead of storing it in memory. But I suspect it won't help much, because the compiler itself is already equipped with a clever logic that usually notices such things itself. But now we're really done with optimizing. You can't go any further with this approach. After all, these measures have brought us already a factor of 9.3 compared to the straightforward programmed version. We would gain a lot if we could get rid of the loop that counts the bits in a word. This would be done by precalculating the bits of a 16-bit value and storing the result in a lookup table. First, you can be a bit conservative and make the table only for 8 bits, that saves some space:
Filling can be done by a recursive method. The task "Fill a table for x+1 bits" can be split into "Fill the lower half with the sums where the bit is 0" and "Fill the upper half with the sums where the bit is 1 and therefore is added". For fast execution, it is also important to ensure that arrays are always dimensioned to their full size right from the start. Otherwise, it may happen that an array is enlarged in several steps and thereby copied. This would waste a lot of computing power. The counting method based on such an array is very simple and therefore very efficient:
The measurements show that filling the table takes almost no time. The larger the array is that is to be calculated, the more worthwhile it is to create a table. In my example with 1 million values the table creation takes 3 thousands of a percent of the array calculation time. For an array with only 10'000 values it is still only 3 thousands. It is therefore worthwhile in any case to build up such a lookup table. But have we now won something with it? Yes, an enormous amount. The method with Lookup-Table is 25 times faster than the straightforward-programmed version. What can we improve here afterall? Well, using the BitConverter class smells like effort. Let's do it ourselves, it's not a piece of witchcraft:
Right! Not only at mom's the homemade stuff tastes better, it's the same in computer science. It is almost 4 times faster. If that has brought so much, why not precalculate all 65536 values at once? Nowadays a computer has gigabytes of memory. Such a table needs only 64 kB because in a 16-bit value there can be a maximum of 16 bits. So it can be coded with 5 bits. If needed it could even be stored in a compact form of 40'960 bytes. That poses no problem, if we don't want to integrate it into a microcontroller. But we have to bypass a small obstacle here, namely that the array contains integer values, and they can be negative. As a consequence the counting method looks like this:
Now we have already reached the factor 30. That has paid off extremely well. Can we still tune this a bit? The comparison with if can be simplified by making the 'value' positive beforehand:
But it brings only an insignificant gain, the factor is still stable around 30. Any operation within the loop should be avoided. How about telling the compiler to treat the integer as an unsigned integer? We can then also get rid of the variable inside the loop:
Yep. The measurement shows, we are now about 100 times faster than the straight-forward programmed solution. Now we could dedicate ourself to the table creation. Why always create a table that is constant? Wouldn't it be faster to just load the table? Therefore we simply save it to a file and embed it into the resources of the executable. If necessary we can then just load it. The measurement shows that it is about 1% faster to load such a table than to calculate it:
If we want to save some space, we can compress the lookup table. The numbers in it are limited to the range 0..16, where 0 only occurs once at the beginning and 16 only once at the end. If we hardcode these two values, the number range shrinks to 1..15 and we only need 4 bits per number. So we can shrink the table to half:
When loading, we unpack it like this:
The measurement shows that this is about as fast as the uncompressed version, but we reduce the program size by 32 kB. Let's go back to the calculation method based on such a table. What does it look like if we also place everything in a block of unchecked? There could be a few overflow tests falling away, right? No, unfortunately the measurements show hardly any difference. But maybe we can tickle more optimizations out of the compiler. There is also the Reflection attribute "[MethodImpl(MethodImplOptions.AggressiveInlining)]". But unfortunately here, too, no success. All this hardly brings a speeding up. One more idea: How about not loading the table, but programming it directly into the code? Here C# is unfortunately not as well equipped as C. In C there is a sophisticated preprocessor which supports - in analogy to programming languages - methods that can even have parameters. With this at hand it would be easy to generate the table recursively. In contrast, only a few rudimentary commands are available in the C# preprocessor and certainly no methods with parameters. So you have to do it another way. For example, you could use the T4 mechanism (Text Templates) to generate code. Although I have worked with it intensively, for this study it was too much to take on. I only implemented a very simple method: The solution contains a few routines that generate source code using a StringBuilder and copies it to the clipboard. From there I pasted it into the source code. The measurements show that such an approach is slower than the 16-bit lookup array. You lose a little above a factor of 3 in speed. "Just one more thing" [Steve Jobs]: The following idea is based on my C knowledge: In C, the compiler converts a large switch statement to a lookup table. Very good idea of the creators. If this would also be the case with C#, you could code the table in the form of a switch statement. This attempt is contained in the source "LookupTables.cs". The counting method based on such an 8-bit-switch would then look like this:
Sadly you lose a factor of 10 with this. The assumption that the compiler implements the switch as a table is therefore falsified for C#. This approach doesn't work. I tried also to implement a 16-bit switch, but a switch with 65536 lines overwhelmed the compiler. Funny enough, it freezes during compilation. Would be something for an entry in a hypothetical page "How to drive a C# compiler nuts". The Visual Studio text editor also has a lot of problems with the statement, it hangs several seconds or sometimes minutes. So we could actually also drive this one nuts (:-)
Measurement resultsLet's come to the hard facts. These are the measurements of the processing if the compiler is not optimizing the code (checkbox in the properties of the project). The displayed times are in ticks (1 tick = 100 nanoseconds). Click on image to enlarge:
|
||
|
|
||
| |
||
| © 2018 Andres Rohr. Dieses Thema stammt vom Autor selbst. Es ist nicht einfach vom Internet runterkopiert.
|
||
