Live data from Hacker News

Common Systems Programming Optimizations and Tricks

paulcavallaro.com

71–80 of 98 posts

Re: Common Systems Programming Optimizations and Tricks

#71
post #28

"Repurposing Top Bits" - don't do that. Honest. The IBM 360 shipped with 32-bit addresses but only 24 bits decoded. "Hey, there's a whole byte up top that nobody's using today, let's put some stuff there!" When they wanted the address space IBM found themselves architecturally hamstrung, and the cost to dig out was significant. The 128K Macintosh used a 68000; it had 32-bit addresses but only 24 bits were decoded. "H…

Can't you just make sure that your allocator only uses the bottom x bits? (Of course you still need to be careful when interfacing with code that maps memory in some other fashion)

Re: Common Systems Programming Optimizations and Tricks

#72
post #70

Earlier quoted context omitted.

Apple’s market cap is $983B and IBM’s is $125B. So somehow they’ve survived this lowbrow hack. Seriously, with 64 bit addresses available on the iPhone I’m typing this into, this is an excellent trick, especially for applications. Even ARM’s TBI leaves 56 bits which is more address space than a data center’s DRAM. log2(16 billion * 100,000) is about 50 You have a point at 32. You’re just wrong at 64.

"You see, these guys hit this boulder , and they still ride their 60-ton battle tank! Why should I not try the same with my car?" See also: survivor bias.

That’s nice rhetoric but I didn’t pick the survivor examples.

Re: Common Systems Programming Optimizations and Tricks

#73
post #28

"Repurposing Top Bits" - don't do that. Honest. The IBM 360 shipped with 32-bit addresses but only 24 bits decoded. "Hey, there's a whole byte up top that nobody's using today, let's put some stuff there!" When they wanted the address space IBM found themselves architecturally hamstrung, and the cost to dig out was significant. The 128K Macintosh used a 68000; it had 32-bit addresses but only 24 bits were decoded. "H…

Back around 2001 I was part of a webdev shop that had its own proprietary application server. It pre-parsed HTML files for or and would run whatever you put there. We linked in slightly patched perl/python libraries so we didn't have to start a new interpreter every request. There were a couple in-house RPN languages too, and other comment-based markup for easy loops/interpolations. One design goal was to let you rou…

Was this https://openacs.org/ ?

Re: Common Systems Programming Optimizations and Tricks

#74
post #28

"Repurposing Top Bits" - don't do that. Honest. The IBM 360 shipped with 32-bit addresses but only 24 bits decoded. "Hey, there's a whole byte up top that nobody's using today, let's put some stuff there!" When they wanted the address space IBM found themselves architecturally hamstrung, and the cost to dig out was significant. The 128K Macintosh used a 68000; it had 32-bit addresses but only 24 bits were decoded. "H…

Can't you just make sure that your allocator only uses the bottom x bits? (Of course you still need to be careful when interfacing with code that maps memory in some other fashion)

If your allocator calls mmap or an equivalent, and the OS gives you back a pointer that uses all 64 bits (or more than 48, anyway) then what do you do? I guess the allocator has to retry and pray, or maybe just give up and fail. In any event your clever code is not going to work well, since you have made a choice that is non-portable.

I imagine that the guy on the MacOS team who stuffed some desk accessory bits into the high byte of a pointer parameter thought he was being clever. Four or five years down the line he was paying for it, and it took years to fix his original moment of convenience. He could have added a second parameter on the call in question, or allocated another byte in a struct, and the original system would have been slightly bigger but he wouldn't have hatched a nightmare. Go read about '32-bit clean' Mac applications if you don't believe me. It sucked real hard.

A bunch of companies with a bunch of smart people have made the decision to use "unused" high bits in pointers and have later regretted it, to the tune of a ton of expensive remedial engineering. I see a lot of talk here along the lines of "b-b-b-but we know what we're doing" and "oh, 48 bits is enough, and if it's not then we'll deal with it later" and I'm thinking, "This is precisely how the software industry just never learns."

I figure that I have about 20 years left in my career writing software. I've seen address spaces grow from 16 bits (and we used to think "wow, that's BIG") to 64 bits [okay, 48 bits if you're still in denial :-) ] and wow, that's big. But I'll bet I'll see 64 bits generally considered kind of tight before I retire, and I'll bet there are at least half a dozen people on the planet who are up against a 64-bit wall today. (High probability at least a couple of those folks are on HN. Any hands?).

Re: Common Systems Programming Optimizations and Tricks

#75
post #28

"Repurposing Top Bits" - don't do that. Honest. The IBM 360 shipped with 32-bit addresses but only 24 bits decoded. "Hey, there's a whole byte up top that nobody's using today, let's put some stuff there!" When they wanted the address space IBM found themselves architecturally hamstrung, and the cost to dig out was significant. The 128K Macintosh used a 68000; it had 32-bit addresses but only 24 bits were decoded. "H…

Meh, when you get to the point where you're exceeding your available address space, there's probably a million other refactorings you had to make to address all of the other architectural changes.

Re: Common Systems Programming Optimizations and Tricks

#76

Earlier quoted context omitted.

Back around 2001 I was part of a webdev shop that had its own proprietary application server. It pre-parsed HTML files for or and would run whatever you put there. We linked in slightly patched perl/python libraries so we didn't have to start a new interpreter every request. There were a couple in-house RPN languages too, and other comment-based markup for easy loops/interpolations. One design goal was to let you rou…

Was this https://openacs.org/ ?

No, but it looks like it's still around (at least the open source successor, which was not as nice or stable as the original): https://sourceforge.net/projects/integratis/

Re: Common Systems Programming Optimizations and Tricks

#77
post #70

Earlier quoted context omitted.

"You see, these guys hit this boulder , and they still ride their 60-ton battle tank! Why should I not try the same with my car?" See also: survivor bias.

That’s nice rhetoric but I didn’t pick the survivor examples.

You did, by mentioning the companies that are alive and kicking.

OTOH DEC placed a bet on new and cool Alpha architecture, and died switching (bought by HP).

Re: Common Systems Programming Optimizations and Tricks

#78
post #40

Earlier quoted context omitted.

You'll have to deal with APIs that do return full 64-bit pointers with real information in the top bits. You won't be able to play games with these bits. Stuff is going to break unless you are careful. If you are shipping a platform of some kind then you must also ensure that your customers cannot get into trouble (if you tell them "Hey, these upper bits are up for grabs" then you are doing them a disservice, in seve…

Nothing on x86_64 is returning "full 64 bit pointers", unless they are also playing games, as CPUs only support 48 bits of address space. Also, your suggestions are a bit strict, in my opinion. Every VM or interpreter I know about uses this kind of trick, usually to squish things like integers. Not doing this requires adding an extra allocation for every integer.

> Nothing on x86_64 is returning "full 64 bit pointers"

Well, I'm going from the processor reference manuals from Intel and AMD. Existing implementations are 48 bits, and future implementations WILL have more. I trust these folks to make good on their promise. (Similarly, the 68000 had 24 bits, and when the 68020 came out it had full 32 addressing, and an MMU, and badly written software broke).

There are pretty safe ways to do tagging; common techniques usually distinguish limited range integers and pointers with a low bit, and pointers often have extra bits since those are relatively safe to manipulate. I have not seen runtimes that use high-order bits for tags in quite some time, probably the late 80s; you haven't seen that software recently either, because it doesn't work anymore.

The x86 segmented architectures (which is all we had from Intel until the 386's flat address space came out) had several variations on pointers, basically a menu of terrible tradeoffs between fast and small code versus small and large address spaces. Far pointers were formed with a segment and an offset, and the game was all about making these multipart pointers efficient for things like comparison. In the face of pointer normalization, you mucked with high bits at your peril.

The one thing I'm sure of in this industry is that software is always going to be getting bigger. :-)

Re: Common Systems Programming Optimizations and Tricks

#79
post #67

Last time this came up ( https://news.ycombinator.com/item?id=20808778 ) and disappeared almost instantly, I wrote: A discussion of systems programming optimization that doesn't start with single-writer ring buffers starts on the wrong foot. Those other tricks are excellent, and I use all of them, in cases where they work at all. But, e.g., seeking a way not to need to take a lock at all should come before discoverin…

bitmapped set is one I don't remember at all. It have another name? A quick google not give me a clear idea of what is or how could be usefull...

Re: Common Systems Programming Optimizations and Tricks

#80
post #79
post #67

Last time this came up ( https://news.ycombinator.com/item?id=20808778 ) and disappeared almost instantly, I wrote: A discussion of systems programming optimization that doesn't start with single-writer ring buffers starts on the wrong foot. Those other tricks are excellent, and I use all of them, in cases where they work at all. But, e.g., seeking a way not to need to take a lock at all should come before discoverin…

bitmapped set is one I don't remember at all. It have another name? A quick google not give me a clear idea of what is or how could be usefull...

std::bitset is one. But you can just use an unsigned int, or array of them. In C++ or C, set intersection is &, union is |, complement is ~. Cardinality is __builtin_popcount, or std::bitset::count(). Membership test for m is (s & (1>5] & (1Bitsets are useful in more places than you might guess, because they can be used to filter out, with typically a single instruction, a majority of uninteresting cases in searches, leaving fewer cases to be examined with more precise and expensive operations. You record interesting properties of elements of a collection upon insertion as bits in a word stored alongside (or, better, in an index); and then first check the bits during any search. It is easy to speed up an amazing variety of programs by an order of magnitude, sometimes much more, with a tiny change.

For example, you can store an int value for each of a (possibly very large) collection of lines of text, representing the set of less-common letters that appear in the line. Searching for lines that contain a string, you first check it against the set for the string. Any line that doesn't have them all certainly doesn't have the string.

Leibniz (inventor of calculus) used this method very heavily in his own work. Before computers--and even into the 1960s--it was the most important way of automating data processing. Back then, you used cards that had a row of either holes or notches along one edge, and selected matching cards from a stack by inserting a rod through the stack at a selected spot, and lifting.

Post reply on HN