Noelle and I made a couple pumpkins each for Halloween. I made a photojournal of them.
When I was a boy growing up in rural Wisconsin, I built my share of tree houses — probably about a half dozen. Some even had doors and windows. When I take a walk along the pipeline here, I see a few simple ones that make me wonder how I would build one today, if I were so inclined.
I keep thinking about structures that are suspended between multiple trees or perhaps the branches of a large deciduous tree. The chief benefits of such a design are that it the levelness of the floor would be resistant to tree growth and it might add stability to the supporting trees. There are self-leveling picavets for stabilizing cameras in kite aerial photography that might be scaled-up with heavy cable and pulleys to support a tree fort. Would it be too scary to be in a rock-a-by tree house? Or would people become nauseous from motion sickness in high winds? An over-engineered version might have servos and accelerometers to counteract movement (or amplify it for added fun).
In response to Paul Messmer's email, I revised the operation counting methodology on my bithacks page to not count large constants as operations. It probably takes more time to load the value from a variable than a large immediate, even when multiple instructions are required to load it, because fetching values from memory has grow slower with faster CPUs clockrates. Since I don't count variables as operations, I decided not to count constants. My initial policy was due to the small number of registers on the popular x86 CPUs and the mulitple instructions required for loading large immediates on MIPS CPUs.
He also recommeded that I count the length of computational dependency chains rather than total operations. For example, in the following, x should take less time to compute than y:
x = a + b + c + d + e + f;While (a+b) is added, a modern superscalar processor could add (c+d) and (e+f) simultaneously. Unfortunately IA32 processors are limited in the number of registers they can use, and compilers for them typically don't bother to emit instructions that can be executed in parallel. I tested this with g++ 3.4 on a Pentium III, an Athlon XP, and an Athlon 64. Only after I tweeked the assembly output for the Athlon 64 (with it running in 64-bit mode) could I get the expected 40% speed-up.
y = ((((a + b) | c) + d) | e) + f;
So before updating the bithacks page to reflect the length of the computational dependency chains, I'll wait until at least half of the CPUs sold are capable of x86-64 (or EM64T, as Intel puts it), and people are typically running them in 64-bit mode (on Windows 64 or Linux 64), and compilers are capable of emitting code that can be executed in parallel.
/* The following uses the Gnu Assembler (gas) syntax, which has the destination register last */
/* Compiler's a+b+c+d+e+f: */
addl %esi, %edi
addl %edx, %edi
addl %ecx, %edi
addl %r8d, %edi
leal (%rdi,%r9), %eax
/* My hand-tweaked a+b+c+d+e+f: */
addl %esi, %edi
addl %ecx, %r8d
addl %edx, %r9d
addl %edi, %r8d
leal (%r8,%r9), %eax
/* Compiler's ((((a+b)|c)+d)|e)+f: */
addl %esi, %edi
orl %edx, %edi
addl %ecx, %edi
orl %r8d, %edi
leal (%rdi,%r9), %eax
Paul Messmer sent me an improvement to my bithack for determining if a word has a zero byte. It performs a quick pretest, which produces false positives on the rare occasions that the first byte is 0x80. All positives are checked using the more reliable method. Because it only takes 3 operations for the fast pretest, it runs faster.
bool mayHaveZeroByte = ((v + 0x7efefeff) ^ ~v) & 0x81010100;
if (mayHaveZeroByte) // or may just have 0x80 in the high byte
{
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}
// Return bits from x in even positions and bits from y in the odd
unsigned short
InterleaveBitsFromBytes(unsigned char const x, unsigned char const y)
{
return ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 49) & 0x5555 |
((y * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 48) & 0xAAAA;
}
This technique works by using two instances of the same basic pattern transformation, which spreads the bits of x and y out, requiring only an OR operation. The spreading is described below.We want bit pattern abcdefgh to become a0b0c0d0e0f0g0h
abcdefgh
* 0000000100000001000000010000000100000001000000010000000100000001 = 0x0101010101010101ULL
==================================================================
abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
& 1000000001000000001000000001000000001000000001000000001000000001 = 0x8040201008040201ULL
==================================================================
a00000000b00000000c00000000d00000000e00000000f00000000g00000000h
* 0000000100000010000001000000100000010000001000000100000010000001 = 0x0102040810204081ULL
------------------------------------------------------------------
a00000000b00000000c00000000d00000000e00000000f00000000g00000000h
+ 00b00000000c00000000d00000000e00000000f00000000g00000000h0000000
+ 0000c00000000d00000000e00000000f00000000g00000000h00000000000000
+ 000000d00000000e00000000f00000000g00000000h000000000000000000000
+ 00000000e00000000f00000000g00000000h0000000000000000000000000000
+ 0e00000000f00000000g00000000h00000000000000000000000000000000000
+ 000f00000000g00000000h000000000000000000000000000000000000000000
+ 00000g00000000h0000000000000000000000000000000000000000000000000
+ 0000000h00000000000000000000000000000000000000000000000000000000
==================================================================
aebfcgdhebfcgdhe0fcgdhe0f00dhe0f0g0he0f0g0h00f0g0h0000g0h000000h
>>1001001 = 49
==================================================================
?????????????????????????????????????????????????aebfcgdhebfcgdh
& 0000000000000000000000000000000000000000000000000101010101010101 = 0x5555
==================================================================
0000000000000000000000000000000000000000000000000a0b0c0d0e0f0g0h
Posted by seander at 03:27 PM
| Comments (0)
On Saturday, October 2nd, I hiked to Hidden Lake Lookout with Dan Crouse, John Mason (Dan's old boss), and Lisa (John's wife). The weather was perfect. The fire lookout was built in the early 1900's by a man who hauled up the materials by mule or foot. I made a photojournal and a panorama of the view from the top. The hike was 8 miles round-trip and the elevation gain was 3500 feet.