Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Common Systems Programming Optimizations and Tricks

paulcavallaro.com

Post reply on HN
Print view View original

31–40 of 98 posts

Re: Common Systems Programming Optimizations and Tricks

#31

Post by astrobe_ »

eschneider wrote: post #6
legulere wrote: post #3

Instead of repurposing top bits you can also repurpose the Bits beyond alignment. E.g 32 bit integers are aligned to 4 bytes, so you can use the lower two bits of pointers to them instead.

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.

I'm curious, when does it fail?

Re: Common Systems Programming Optimizations and Tricks

#32

Post by muricula »

kabdib wrote: 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…

Armv8 has an opt-in feature you can turn on to ignore the top byte: https://en.wikichip.org/wiki/arm/tbi This is also where the pointer authentication code goes for arm pointer authentication: https://lwn.net/Articles/718888/

On x86_64 and arm without those features enabled, the top bits of the pointer must be sign extended. This means that x86_64 by default gives you the top two bytes to play with as long as you don't use the values 0xffff or 0x0000. Attempting to access a pointer whose top 16 bits aren't a sign extension of bit 48 will fault. You can still safely play this game as long as you fix up the pointer before dereferencing it.

Re: Common Systems Programming Optimizations and Tricks

#33

Post by hinkley »

dbcurtis wrote: post #2

Good article. Basics that everyone can benefit from knowing. Just one nit/warning... breaking coarse locks into fine-grained locks can be taken too far. There is a point of diminishing returns where you end up spending increased time acquiring/releasing/waiting-for locks. At some point you want to clump together under a single lock resources that tend to often be used together, even if you often end up locking an ext…

Not just performance, but the moment there are two locks required for any task, you may have the Dining Philosophers problem.

Re: Common Systems Programming Optimizations and Tricks

#34

Post by CJefferson »

kabdib wrote: 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…

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 happens.

Re: Common Systems Programming Optimizations and Tricks

#35

Post by hinkley »

dbcurtis wrote: post #14
jacobush wrote: post #4

Earlier quoted context omitted.

Taken to the extreme, ONE lock in Python. :)

Ha Ha! Yes. The gillectomy project collected some interesting data on that a couple of years ago, creating very fine-grained locks and measuring. Not unexpectedly, with a zillion locks performance suffered. The reason though, had much to do with how much it thrashed the cache on a modern CPU. Lots of cache invalidation traffic back and forth between cores. The C-Python implementation is architected around the GIL, an…

75% correct is not a bad ratio.

Re: Common Systems Programming Optimizations and Tricks

#36

Post by hinkley »

notacoward wrote: post #11
jcelerier wrote: post #7

Earlier 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. That's why you hide the trick behind a zero-cost abstraction which checks at compile-time if the platform supports this

One of my favorite system programming tricks is to never believe that a "zero cost abstraction" lives up to the name.

Sometimes programmer advice needs disclaimers like prescription medicines.

† Offer only valid in the contiguous United States. Offer cannot be used in combination with any other offers. See stores for details.

‡ When not in use, return Happy Fun Ball™ to its protective lead case.

Re: Common Systems Programming Optimizations and Tricks

#37

Post by jnwatson »

muricula wrote: post #32
kabdib wrote: 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…

Armv8 has an opt-in feature you can turn on to ignore the top byte: https://en.wikichip.org/wiki/arm/tbi This is also where the pointer authentication code goes for arm pointer authentication: https://lwn.net/Articles/718888/ On x86_64 and arm without those features enabled, the top bits of the pointer must be sign extended. This means that x86_64 by default gives you the top two bytes to play with as long as you don…

"Attempting to access a pointer whose top 16 bits aren't a sign extension of bit 48 will fault."

Currently. Coming soon to an Intel chip near you is 57-bit virtual addressing and 5-level page tables [1]. It would be quite a bug that would only crash on new Intel hardware on probably quite full memory maps where your pointer fix up code wouldn't restore bits 48-57 correctly.

[1] https://www.phoronix.com/scan.php?page=news_item&px=Linux-De...

Re: Common Systems Programming Optimizations and Tricks

#38

Post by vardump »

jnwatson wrote: post #37
muricula wrote: post #32

Earlier quoted context omitted.

Armv8 has an opt-in feature you can turn on to ignore the top byte: https://en.wikichip.org/wiki/arm/tbi This is also where the pointer authentication code goes for arm pointer authentication: https://lwn.net/Articles/718888/ On x86_64 and arm without those features enabled, the top bits of the pointer must be sign extended. This means that x86_64 by default gives you the top two bytes to play with as long as you don…

"Attempting to access a pointer whose top 16 bits aren't a sign extension of bit 48 will fault." Currently. Coming soon to an Intel chip near you is 57-bit virtual addressing and 5-level page tables [1]. It would be quite a bug that would only crash on new Intel hardware on probably quite full memory maps where your pointer fix up code wouldn't restore bits 48-57 correctly. [1] https://www.phoronix.com/scan.php?page=…

It'll probably be quite a while before operating systems rush to turn on extra level of page walk fun, increasing TLB miss penalty even more.

If only x86 could have 64 kB pages...

Of course you're right it's not a great idea to use those bits. Eventually they will be in use, although it's probably 10+ years.

Re: Common Systems Programming Optimizations and Tricks

#39

Post by hinkley »

vardump wrote: post #16
notacoward wrote: post #11

Earlier quoted context omitted.

One of my favorite system programming tricks is to never believe that a "zero cost abstraction" lives up to the name.

Yeah, don't believe in dogmas, measure. Zero cost abstractions sometimes are anything but.

And sometimes the surprises can be in the other direction.

Cache thrashing is a thing. And perf analysis tools have bookkeeping errors.

Re: Common Systems Programming Optimizations and Tricks

#40

Post by kabdib »

CJefferson wrote: post #34
kabdib wrote: 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…

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 several ways).

"We know this is wrong, but we'll deal with it when it happens" is a demonstrably expensive road. I can't think of many clearer cases of refusal to learn from history in computing.

Post reply on HN