3-bit Waymarking

(a.k.a. Son of Use-Diet)

Gabor Greif
Weekend LLVM-hobbyist

<picture : array of Uses embedded/pointered in User> Use has 4 pointers

• drop pointer to User
• allocate Uses before User in memory
• make Prev pointer tagged (2-bits, since always 4-byte aligned)
• seen 12% space savings on big C++ programs
• landed in the LLVM codebase: May 2008

Employ a framed serial code in consecutive Uses

• S → full stop
• s → stop
• 0, 1 → binary digits

Read off binary digits to obtain distance to User

:-)

2.5% runtime increase

(but it was worth it!)

When two feet permit just so much speed, then you have to upgrade to three feet!

I really did not mean to do something cruel as this!

But no earthly life-form provides this feature, so...

Clearly I was in need of some alien technology!

...then I took a page from the book of space exploration and found this gem:

Alien tricks from Mars! :-)

On today's predominantly 64-bit platforms, pointers are 8-byte aligned

We have 8 distinct tags for disposal

• double digits: 00, 01, 10, 11
• 3 stop tags: q, r, s (always in this order)
• full stop: S

Originally modelled in Haskell (+QuickCheck)

Now in LLVM repo (on a branch), with automatic algorithm selection

• stop tags allow longer hops while hunting down the framed digits
• any stop tag encodes the distance to the framed payload
• harvesting 2-bits at a time

• unroll tag initialisation loops
• distance relative to stopped frame (microoptimization)
• rol (rotate) instructions with condition flags
• examining resultant assembly (on all archs!)

Credits:

• NASA (image)
• Wikipedia (image)
• W3C Slidy