## Hamming Code Optimization

From Joel.Becker@oracle.com Mon Jun 19 00:35:27 2006 Date: Mon, 19 Jun 2006 00:35:27 -0700 From: Joel Becker <Joel.Becker@oracle.com> To: martin.petersen@oracle.com, mark.fasheh@oracle.com, zach.brown@oracle.com Subject: A tale of optimization Message-ID: <20060619073527.GM29684@ca-server1.us.oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Burt-Line: Trees are cool. X-Red-Smith: Ninety feet between bases is perhaps as close as man has ever come to perfection. User-Agent: Mutt/1.5.11 Status: RO Content-Length: 5229 Lines: 108 [Ed note: I just realized I've typed out a long boring story. It may or may not be interesting, though it will help anyone trying to optimize this more to understand where I've been. Feel free to ignore if silly optimization results are boring when they take three pages.] Folks, Here's a fun story of optimization (as a fun story, you can feel free to ignore it for a while if you are busy :-). I was cooking up a Hamming Code algorithm for ECC in OCFS2. With Hamming Code parity, we can correct single-bit errors in 16bits of parity for a 4K block (less parity for smaller blocks). The standard method to calculate the parity is with matrix math. This quickly generates the code block (an interleaved bitstream of parity and data bits). However, the matrix has dimensions [total bits x data bits]. So, for our 4K blocksize, that's [32768 x 32784]. We can't do that in memory, not nicely :-) Lots of googling later, I understood enough to implement it mathematically. Details of the algorithm are handwaved here. The big problem is that parity is based on the offset in the code bitsream, not the data bitstream. In the code bitstream, all power-of-two bits are parity bits. Bits 1, 2, 4, ... are parity bits. The data bits are interleaved. So in the code bitstream, data bit 1 is code bit 3 (skipping past code bits 1 and 2, which are for parity). Any time you want to work on a bit, you have to know its code bitstream offset. Here's my original algorithm, the simple cut. I call it the "for" algoritm, for obvious reasons. In all the examples, 'i' is the data bit offset, 'b' is the code bit offset. I'm going to use 1-based arrays because that's what Hamming code uses. total_bits = total_data_bits + total_parity_bits; for (i = 1, b = 1; i < total_bits; i++, b++) while (is_power_of_two(b)) b++ if (test_bit(i)) for (j = 1; j < total_parity_bits; j++) if (b affects j) j ^= 1; I'm going to handwave right now how we determine whether bit b affects each parity bit, but it relies on b's number in the _code_ space, so we have to have that is_power_of_two() check. To sum up, the for loop runs through _every_bit_ and calls test_bit() on it. If the bit is set, it loops through each parity bit. That's a lot of looping. This naive implementation is slow. Surprise! My test program fills a blocksize buffer from /dev/urandom and runs N encodes. I have the same program do crc32 and similar. 10000 loops of a naive crc32 (the kernel's un-optimized fallback code) on my laptop take 0.300s. 10000 loops of zlib's optimized crc32 takes 0.030s. 10000 loops of our parity encode take 6s! The naive crc32 is an order of magnitude better! I wanted to find a way to move forward more than one bit at a time. Many algorithms (smarter crc32s, for example) work on words or larger chunks. But each bit affects different parity bits, so I'm not yet sure how to calculate more than one bit's parity in a single operation. I did realize that we skip 0 bits. Why can't we skip them faster? Instead of using the for loop to compute b's offset, I concocted a function that would take i and return b for any bit. I then changed the loop to use find_next_set. Let's call this the 'ffs' algorithm (handwaving around 1-based arrays): for (i = 1; (i = ocfs2_find_next_bit_set(data, total_bits, i)) < total_bits; i++) b = calc_code_bit(i); for (j = 1; j < total_parity_bits; j++) if (b affects j) j ^= 1; Here's the fun part. I figured that by skipping zero bits, we'd get some speedup. When I ran it, it was SLOWER! What? It ran 7s instead of 6s. So I profiled it. The 'for' algorithm's second biggest time consumer was ocfs2_test_bit(), with ~8m calls taking up 7s of profiled (slower) run time. The 'ffs' algorithm's ocfs2_find_next_bit_set() took 8s of profiled time with ~4m calls. Our naive ffs is *slow*. This is where I was when I started the email. I thought it was a fun outcome. But since then I've had some thoughts and success on the topic. This lead me to two conclusions. First, a fast find_next_bit(), like the kernel has in ASM, will be much faster. Second, half of our test_bits were returning true (4m ffs calls vs 8m test_bits). Of course they are, I'm using /dev/urandom. A real inode will have a ton of zeros, especially if it isn't fragmented. I changed the test buffer. It still reads from /dev/urandom, but then it zeros the tail of the inode, where it will likely be empty. The 'for' algorithm speeds up, as it has fewer loops through the parity checks, running about 2.5s. But the 'ffs' algorithm really shines. 1.3s for it's run of 10000. Assembly based ffs in-kernel will speed it up some more, but after that we'll have to do some tricks on the parity loop. I'm willing to call the code acceptible for now. Please, if anyone has more optimization ideas, have at. :-) Joel -- "Here's something to think about: How come you never see a headline like ``Psychic Wins Lottery''?" - Jay Leno Joel Becker Principal Software Developer Oracle E-mail: joel.becker@oracle.com Phone: (650) 506-8127