3 ms·
I'm looking at a lot of these... and it seems like coding of these "tables" needs to be discussed. The most obvious decision-table encoding is the humble bitse
by dragontamer 6y ago
I'm looking at a lot of these... and it seems like coding of these "tables" needs to be discussed.
The most obvious decision-table encoding is the humble bitset. For example:
A B C | T/F
---------
0 0 0 | T
0 0 1 | F
0 1 0 | T
0 1 1 | T
1 0 0 | T
1 0 1 | F
1 1 0 | F
1 1 1 | T
Which would be represented as: 0x9D (10011101-binary), a simple 8-bit number (one byte).
Unfortunately, this table grows exponentially: 11-variable tables require 2048-bits, but this is still a 256-byte value that can be manipulated in a single-clock tick on AVX2 systems (Zen and Skylake). AVX2 supports AND, OR, NOT, XOR in a single clocktick (heck: Skylake supports 3 256-bit boolean instructions per clocktick. Zen2 supports 4 per clocktick)
---------------
While 2048-bit (11 variable) tables maximize memory bandwidth through SIMD instructions, the real "rich" instructions exist in the 64-bit world. I don't feel like making this post much larger, so I'll just note a brief summary now.
* Popcnt -- Provides a "Select Count( * ) from table", so to speak. 1-clock tick on Skylake, 4-per-clock tick on AMD Zen.
* PEXT -- Parallel-Extract, a bitwise gather command. 1-clocktick on Skylake (unfortunately slow on Zen: 18 clocks). This is your "Select" statement. Take the 8-bit (3-column) table 0x9D as an example (10011101-binary). PEXT (10011101b, 10101010b) == 1010, which so happens to be equivalent to "Select A,B from table where C=True".
Some other examples:
PEXT (table, 01010101b) is "Select ... where C=False".
PEXT (table, 11001100b) is "Select ... where B=True".
PEXT (table, 11110000b) is "Select ... where A=True".
PEXT (table, 00001111b) is "Select ... where A=False".
* PDEP -- Parallel Deposit, a bitwise scatter command. This is the exact opposite of PEXT. If you're building a larger table from a smaller one, getting ready for a "join" operation, this is useful. Ex: "Expanding" a hypothetical "AB" table into a "ABC" Table (making room for the new "C" column) can use the PDEP instruction.
* Summary: PEXT "Reads many column in parallel", while PDEP "writes many columns in parallel".
* Where PEXT and PDEP are inefficient (ie: everything outside of Intel chips), a careful mix of bitshift-and-AND operations can implement the above operations with reasonable speed.
* BLSR -- Reset lowest bit. The 0x9D table is converted into 0x9C, a useful operator for "iterator++" in C++ terms. For example, 0x9D across repeated BLSR commands changes as follows: 10011101, 10011100, 10011000, 10010000, 10000000, and finally 00000000. See TZCNT for more info.
* TZCNT -- Trailing Zero Count. A useful operator for "*iterator" in C++ terms. For example, the TZCNT(10011101) == 0, TZCNT(10011100) == 2, TZCNT(10011000) == 3. To convert fully into ABC column form, simply write out the index in binary. For example, "TZCNT(10011000) == 3", or 011 in binary (A=false, b=true, c=true).
"TZCNT(10010000) == 4" becomes 100 in binary (A=true, b=false, c=false).
------
64-bit Popcnt, BLSR, TZCNT are all implemented in GPUs by the way. PDEP / PEXT is an Intel CPU-only trick, but its definitely one of the coolest operators I've seen.
Given that all of these instructions can be implemented in 1-clock tick on most hardware (except PDEP / PEXT), it seems important to learn how to use these instructions. Especially if you're manipulating logic tables in the form described in the blogpost.
-------
This area of super-optimized bitmask based programming wraps full-round to Relational Algebra and SQL. Its a very intriguing corner of Comp. Sci for me.
Arguably, the classic "Table form" that typical SQL-databases use are simply the sparse-matrix form of these bitmasks I described above. Otherwise, the operators are identical in concept.
It also should be noted that hardware exists that executes these bitmask-tables extremely efficiently. Its called an FPGA (which these days, are primarily composed of 6-LUTs, or 6-column look up tables, aka 64-bit numbers). Manipulation of these tables alone is Turing complete!