> The Magic Power of 2: Division Is Slowaloo
Is LLVM not smart enough to optimize this?
Common Systems Programming Optimizations and Tricks
61–70 of 98 posts
Re: Common Systems Programming Optimizations and Tricks
#62Earlier 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.
Right, because the quality of every lesson one learns about programming practice should be evaluated by the market cap of the firm where it was learned.
The parent post mentioned those companies and the corporate 'cost' of recovering from this mistake. Take it up with him.
Re: Common Systems Programming Optimizations and Tricks
#63"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…
Interesting history, thanks. Sorry if this is a silly question but is the "upper" in these examples the most significant bit end of the address then?
The most significant bits, yes.
(The world numbers these from 0 to N, least significant to most significant. IBM numbers them from 1 to 32, with 1 being most significant. I guess that made sense to accountants).
Re: Common Systems Programming Optimizations and Tricks
#64> The Magic Power of 2: Division Is Slowaloo Is LLVM not smart enough to optimize this?
Yes, for constant divisors.
However, for signed division, the C semantics (round towards zero) are different than the semantics when you apply an arithmetic shift (round towards negative infinity).
If you are fine with the latter behavior explicit shifts remove several extraneous instructions dealing with the difference.
Re: Common Systems Programming Optimizations and Tricks
#65Earlier quoted context omitted.
As someone who's worked on old Macs and has also done lots of 32 -> 64-bit porting, this is the sort of trick that works wonderfully...until it doesn't. And then you've got a nightmare on your hands. I'm not saying never do that (ok, maybe I am...) But definitely think long and hard about how long your code will be around before you do it.
> As someone who's worked on old Macs and has also done lots of 32 -> 64-bit porting, this is the sort of trick that works wonderfully...until it doesn't. And then you've got a nightmare on your hands. That's why you hide the trick behind a zero-cost abstraction which checks at compile-time if the platform supports this
Those failures were all about top bits, not low bits though weren't they?
What problems did lower bit use cause? You always had to mask it away even on the old boxes, no?
Re: Common Systems Programming Optimizations and Tricks
#66Earlier quoted context omitted.
Honestly, you may as well use the bits if they are available, because as you say too many will break and will break backwards compatibility. With x86_64, the top bits have to be all 0, or all 1. You can still reuse them as long as you clear them before actually using them as pointers. Of course that might break at a later date is memory spaces increase in size and they are used, but I'll deal with that when it happen…
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.
Re: Common Systems Programming Optimizations and Tricks
#67Last 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 discovering a low-contention locking protocol.
Readers should note that packing spare bits into the bottom bits of suitably aligned pointers is more portable than using high bits. Any page-aligned pointer has at least 12 bits free at the bottom, and any malloc'd pointer has at least 2, more often 4.
Ring buffer counters into a power-of-2 sized buffer can be incremented without bound, enabling use of ordinary arithmetic on them, and high bits masked off cheaply on each use. [But use 64 bits!]
Probably the most neglected primitive data structure is the bitmapped set. A `uint32_t` gives you a universe of 32 elements; a byte is enough for the days of the week. The popcount native instruction is very valuable here, usually expressed as `__builtin_popcount` in source code. C++98's `std::bitset` provides Standard, portable access to it, but C++20 offers `std::popcount` directly.
[I add here that storing things in high bits of addresses is very likely to fail on systems with ASLR, and that I have learned MSVC bitsets have a very slow popcount.]
Re: Common Systems Programming Optimizations and Tricks
#68> Now, to support multiple processors on a single machine reading and writing from the same memory in a coherent way, only one processor on a machine can have exclusive access to a given cache line. Does this also apply when multiple processors are only reading memory?
"Exclusive access" means writing. But the reader doesn't know when it might change. Sometimes that's exactly what you want.
Re: Common Systems Programming Optimizations and Tricks
#69Earlier 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…
This is majestic. Is your current work anywhere near as interesting? :P
It was pretty cool. The company was founded by MIT folks, so I guess they weren't afraid of mixing C & scripting languages. :-) I was just a junior developer, so I barely understood what was going on. The company tried to build an open source version, but it suffered a lot from second-system effect IMO.
I don't often get to do work as cool as that, but I've really enjoyed pursuing more researchy things in my spare time. Right now I'm working on adding SQL:2011 temporal features to Postgres, so I guess I'm still getting my C fix from somewhere. :-)
Re: Common Systems Programming Optimizations and Tricks
#70"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…
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.