Bit Vectors and my first steps into assembly

https://blog.smidt.dev/posts/0004/

by thunderbong • 2 years ago

114 43 2 years ago

blog.smidt.dev

ajross• 2 years ago

Since go doesn’t inline assembly i decided to include the search loop into the assembly itself and to return the index of the non matching character. Sadly i didn’t get it to work fully because i’m missing tools to actually debug the assembly itself.

Um... "gdb <my_binary>", "break <my_function>", "run", just like any other tool.

Then "disassemble" to see the instructions around the PC, "stepi" to execute one instruction. "info register" to get current state (or use registers in an expression as e.g. "print $rax" or "print $r11").

And that's it. Debuggers are actually natively tools operating at the level of machine instructions. The language syntax support is a level on top.

xyzzy_plugh• 2 years ago

Assembly is one of those things that is feared by so many engineers, but is actually incredibly accessible. Whenever I find an excuse to drop down to assembly my colleagues have looked at me like I'm a wizard with 3 heads.

The tooling to debug, dump or inspect, or to link or otherwise glue bits of assembly together has existed for decades. It's all right there!

RicoElectrico• 2 years ago

It's one of these areas LLMs really help to get started. Not much invention needed, but quite involved setup if you don't know what you're precisely looking for. Having them spit out boilerplate and needed invocations lowers the barrier substantially.

dist1ll• 2 years ago

I agree it's unnecessarily feared. At its core, it lacks a lot of complexity.

But actually writing asm is an experience straight from the 80s. Compared to modern languages, the tooling is simply antiquated. I noticed this once I started writing larger sections of asm at a time. It's "fine" in the same sense that writing makefiles is "fine" - it becomes a PITA after a certain size.

I think there's lots to improve on the current state of asm, but it's just too niche. The only power users I know are hobbyists working on operating systems and games for retro hardware.

pm215• 2 years ago

I also like "disp /3i $pc", which tells gdb to disassemble the next three instructions whenever it stops (including after stepi). Though I'm sure you can configure it to give you more sophisticated disassembly display and context, especially with the tui interface, this is usually "good enough" for me when I run into something I want to step through at the assembly level in the middle of debugging a program that's primarily C.

purplesyringa3• 2 years ago

On a related note, https://hugsy.github.io/gef/ provides a TUI interface like that.

MobiusHorizons2• 2 years ago

I’m surprised he didn’t use a switch statement, as that is the canonical way to ask the compiler to make the jump table for you.

rep_lodsb• 2 years ago

Without SIMD, that would probably the optimal way to implement it. And this bit vector idea really isn't doing SIMD at all, it's just (ab)using the vector registers to store 128 bits.

I think the Zig code would also compile to better output, and be a lot simpler, if it was using an array of u1, instead of doing the bit shifting manually.

MobiusHorizons2• 2 years ago

The bit vector does give a nice compression compared to the jump table. But I believe the main thing to do for speeding up string parsing is to consume more than one character at a time. I personally found the techniques in https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in... very helpful to explain these issues.

EDIT: I especially like this statement from the conclusion:

The good thing about the switch statement in C is that it is maybe the highest level statement in the language: the compiler can get really creative in how its code is generated. It's not uncommon for it to generate jump tables or even binary searches.

dragontamer6• 2 years ago

Bit processing is always SIMD.

A 64-bit register being processed 64-bits at a time is, from a mental and programmers perspective, a 64-wide SIMD computer over 1-bit AND, OR, and NOT instructions.

If you aren't using SIMD / parallel programming concepts while thinking about 64-parallel bits (or even in this case, parallel processing of 8-bit bytes or 7-bits of ASCII), then you are making life much harder for yourself.

-------

I believe in the 90s, some people called 32-bit parallelism as SIMD Within A Register (SWAR). Some guy wrote 3DES encryption with 64-bit AND/OR/NOTs and progressed bit-by-bit (but in parallel), achieving absurdly efficient encryption back in the day.

And of course, Chess Programmers with all their 64-bit boards for their 8x8 game constantly think in terms of SIMD inside of 64-bits.

-------

Once you learn to think in SIMD, you can extend these concepts out to 128-bits (SSE), 256-bits (AVX) or 512-bit (AVX512) or beyond (GPU 1024-bits and greater).

boris-smidt9• 2 years ago

I just tried the switch statement ``` func BenchmarkSwitch(b *testing.B) { for i := 0; i < b.N; i++ { for i := 0; i < len(randomBytes); i++ { loop: for i, x := range randomBytes[i:] { switch x { case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9': result = i != 0 break loop case 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z': result = i != 0 break loop case 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'Y', 'Z': result = i != 0 break loop } } } } } ```

It isn't any faster than the || compare, so i suspect the go compiler doesn't really treat it like a special case.

madflame991• 2 years ago

In certain conditions gcc will actually generate instructions that use this same bitvector described: https://godbolt.org/z/6Gfjv6PGd (notice the funny 130159 value in there)

The only thing I did was to adjust the range of characters so that the bitvector fits 64 bits. Sadly, I do not this it would work for the author's bigger range.

dan-robertson• 2 years ago

Another trick for classifying bytes is to use pshufb. That instruction works like:

  fn pshufb(a: [i8; 16], b: [i8; 16]) -> [i8; 16] {
    result = [0; 16]
    for j in 0, 1, …, 15 {
      if b[j] >= 0 {
        result[j] = a[b[j] & 15];
      }
    }
    return result;
  }

So you can often construct values m1, m2, and compute:

  a = pshufb(m1, input & 0xf)
  b = pshufb(m2, (unsigned_input) >> 4)
  x = f(a,b)

Where f is something like bit wise AND. Roughly, m1 and m2 assign sets of 8 potential properties based on the high or low order bits of each byte, and then we and together the sets of properties to make sure the upper and lower bits ‘agree’.

This technique can sometimes be used to mark a few special characters.

dragontamer6• 2 years ago

Pshufb is an old trick. An oldie but a goodie from SSE2 days.

All hail modern improvements!! pdep, pext, vpcompressb, vpexpandb, and especially vpermi2v.

Forget about 16 byte lookup table with pshufb. Try a 128-byte lookup with vpermi2v AVX512.

--------

I find that pext/pdep for 64-bits and vpcompressb/vpexpandb for 512-bits is also more flexible than pshufb (!!!!) in practice, if a bit slower as it is over multiple instructions.

Supercomputer programs are written with a gather-conpute-scatter pattern. Gather your data, compute on the data, and finally place the data where needed.

Pext and vpcompressb are gather operations.

Pdep and vpexpandb are scatter.

Pshufb is only a gather and thus fails to match the supercomputer pattern. GPUs provide a bpermute (backwards-permute) that scatters results back to a table and is really the missing link IMO.

Hopefully Intel will provide bpermute of their own eventually....

teo_zero2• 2 years ago

So you can often construct values m1, m2, and compute:

And what would m1 and m2 be for the specific problem¹ described in TFA?

¹ Namely, to find out if the input belongs to [0-9A-Za-z]

dragontamer6• 2 years ago

The original poster got lucky and m1 and m2 can in fact be constructed.

But your overall post and skepticism is warranted. It's definitely wrong in the general case the original post made.

To solve this easily, you truly need the 128-byte table from vpermi2v / AVX512 (note that ASCII is a 7-bit code and thus all functions of ASCII fit inside of a 128-table).

The reason the original post got lucky is that the top 2 bits of ASCII determine special vs numbers vs lowercase vs uppercase.

The bottom 5 bits determine the specific character. ASCII is a table of tables.

0x30-0x39 are '0' - '9' respectively. So 0x3 in the 'top' table proves you have a number.

0x40 is uppercase and 0x60 is lower case letters.

Bottom table is harder to construct but we don't actually need to know the top bits. We just need 0x0-0x9 (valid for numbers) vs 0x1-0xF (valid for 0x4 and 0x6, as 0x40 and 0x60 are invalid letters), and finally 0x0-0x1A (aka p-z, valid for top half of alphabets in ASCII).

This harder bottom table is solvable with 3 bits of the 8, meaning we have 5 spare bits for future extensions.

So valid for numbers is bit 0x1. Valid for lower-half alphabet is 0x2 and valid for upper-half alphabet is 0x4.

Locations like 5 are valid for all three (0x7) while locations like 0 are only valid for numbers and upper half alphabet (aka 0x5).

----------

In the general case, the [0-9a-zA-Z] language is a regular language (even in an arbitrary non-ASCII code in binary), which means it can always be solved with a state transition table and a finite automata. And yes, pshufb can be a very useful tool for making such a table (and a bigger table like vpermi2v is even better).

But it's not clear that the pshufb sequence in the original post would always work for an arbitrary jump table. Indeed, for best results you likely need to use pext and other complex bit instructions to efficiently extract the most info out of the bits available.

Or you know.... Use the 128-tanle from vpermi2v.

------

Note: FPGAs are composed of 4-LUTs which share many similarities with these 4-bit / 16-byte tables. One can argue that an FPGA is nothing more than a whole bunch of parallel pshufb units.

But that doesn't mean that two such tables solves all problems lol. It's often surprising how some problems blow up in your face and suddenly eat up thousands of LUTs.

boris-smidt9• 2 years ago

I'll try it in the follow up post and probably include some graphics to make it clear what it does. Its indeed the real simd way of comparing multiple characters in 1 iteration instead of 1 character per iteration.

dragontamer6• 2 years ago

purplesyringa's post below is ~7 assembly instructions without any need of lookup tables.

And the instructions purplesyringa uses are Add, AND, OR, and Compare. Modern CPUs can execute ~4 ADD/AND/OR instructions per clock tick (even if they are SIMD or even AVX512 instructions), so you're looking at under 4ish clock cycles to purplesyringa's solution.

Its likely the best solution in the whole thread. The main advantage of pshufb is its extreme flexibility due to the lookup table, so there's advantages in learning that methodology.

But in general, sequences of simpler instructions are much faster.

---------

The "hard part" of purplesyringa's code is that its branchless.

Learning to write branchless (especially using the pcmpeq* line of instructions) is a bit of a hassle and worth practicing for sure. AVX512 added explicit mask registers that do it better but 128-bit SSE / 256-bit AVX is still more widespread today.

purplesyringa3• 2 years ago

This article is kind of fine overall but gets so many specifics wrong. I guess this is to be expected from someone just beginning to verse in assembly, but still.

    if '0' <= x && x <= '9' || 'a' <= x && x <= 'z' || 'A' <= x && x <= 'Z' {
 ...
    }

Go is garbage, but GCC and LLVM compile this to branchless code. If the goal was to redo the book in Zig and Rust, perhaps it would've been a good idea to profile the implementations under Zig and Rust.

If you really want to optimize code like `a <= x && x <= b` by hand, you can rewrite it to `x - a <= b - a`, where the comparison is unsigned; GCC and LLVM do that for you. Next, you can optimize the case-insensitive check by masking out the case bit:

    void f();
    void test(char x) {
        if ((unsigned char)(x - '0') < 10 || (unsigned char)((x & 0x5f) - 'A') < 26) {
            f();
        }
    }

compiles to just

    lea     eax, [rdi - 48]
    cmp     al, 10
    jb      f
    and     dil, 95
    add     dil, -65
    cmp     dil, 25
    jbe     f
    ret

This is still not as fast as a memory read, but IMO this should've been the first thing to try. However, a) GCC and LLVM can autovectorize this, whereas memory reads can't be (although I admit the resulting codegen makes me uneasy), b) you can go on and vectorize this by hand, parsing an identifier in just one iteration of a loop, which you can't do with a LUT. I might have made a bug, but something along the lines of

    unsigned short test(__m128i x) {
        return _mm_movemask_epi8(_mm_or_si128(
            _mm_cmplt_epi8(_mm_sub_epi8(x, _mm_set1_epi8(0xb0)), _mm_set1_epi8(0x8a)),
            _mm_cmplt_epi8(_mm_sub_epi8(_mm_and_si128(x, _mm_set1_epi8(0x5f)), _mm_set1_epi8(0xc1)), _mm_set1_epi8(0x9a))
        ));
    }

should work. This has 5x more throughput than a LUT and should have better branch prediction characteristics, although it consumes 16 bytes at a time, slightly limiting the applications.

The section about bitvectors is fine.

x86 processors don't have 128-bit MMX registers and 256-bit MMY registers. They have legacy 64-bit MMX registers, modern 128-bit XMM registers, and modern 256-bit YMM registers. This MMX/XMM duality sure does confuse people, so I don't blame the author. But come on, at least read the article before publishing; broken GitHub URLs without `blob/master` and broken ()[] Markdown syntax is not funny.

To those trying to make sense of Zig output, don't forget `-O ReleaseFast`. The codegen here is very simple, just a 128-bit integer simulated with two 64-bit ones.

jesse__• 2 years ago

Excellent nitpicks, hopefully the author reads this and does a follow up :)

selimthegrim3• 2 years ago

How good is Hacker’s Delight on this stuff?

boris-smidt9• 2 years ago

I'll have another try in Zig later on and indeed the XMM/MMX and MMY really is confusing, couldn't they just cal it V128, V256 and V512 ...

ww5203• 2 years ago

I know the post only uses SIMD as an attempt to do bitmask lookup for each byte, but a good alternative use of SIMD is for parallel data processing, i.e. operating on more than one character. Being able to identify a range of characters making up the identifier is much faster than checking one character at a time, especially for avoiding branching.

Did a bit of xmas hacking to come up with the function to find identifiers in parallel in 32-byte chunks. I used Zig since it makes vector/SIMD programming easy.

The code is in: https://github.com/williamw520/misc_zig/blob/main/identifier...

The generated code of the nextBitmask32() function has about 38 instructions. https://godbolt.org/z/7ME3sW55e

That's 38 instructions for processing every 32 bytes. With no branching!

ww5203• 2 years ago

Slightly optimized code to get down to 32 asm instructions.

https://godbolt.org/z/ccE3r1bjc

teo_zero2• 2 years ago

Godbolt shows 40 asm instructions, or am I misreading it?

boris-smidt9• 2 years ago

Hey i just discovered that my blog post was posted here i indeed have little experience with assembly and the idea was just could i use a 'larger register' like you would use a 64bit register to keep the table hot in the CPU. But sadly i failed and kinda gave up and made the post as is.

The good news is i will do a 'second' step into assembly programming where i will try to implement the algorithm of `dan-robertson`. There will also be a switch case and other tricks suggested in this thread.

With my experience i noticed that i'm missing breakpoints and unit tests to better understand what each assembly step does. Which things read from memory etc. What also doesn't help is that x86 feels a bit like an 'arbitrary patchwork of instructions' where some instructions exists for float and doubles but not int etc.

It seems a lot of implicit knowledge is needed to do assembly programming, for example `xor A A` to zero the register. So i probably have to read hackers delight from back to back.

The only assembly i have done in the past was AVR which is very limited and it was easy to understand. I could just put a JTAG debugger and see the registers directly.

Golang is used because it is a nice balance between high and low level, unlike the JVM/Python (JIT compilers) you can't disassemble and see the native code.

Ideally there would be a 'modern hackers delight' which would also include some simple simd tricks.

My goal is to eventually reimplement 'write a compiler/interpeter in go' in zig and rust to learn those languages. After 1h of trying it seems zig is 'quite' easy to include assembly as well and to do SIMD. But currently i'm on page 40 of 'write a compiler in go' so i'm still a long way off. For the zig/rust implementation i probably need to include a GC in this simple VM https://craftinginterpreters.com/garbage-collection.html so still a lot to learn.

Also one 'clever' idea i implemented in the lexer was to allow full UTF8 but only in string literal parsing mode. This avoids that you can use emoijs as variable and function names.

Bit Vectors and my first steps into assembly

Related Stories