[HN Gopher] SIMD in Pure Python
___________________________________________________________________
SIMD in Pure Python
Author : dmarto
Score : 243 points
Date : 2024-01-05 02:09 UTC (20 hours ago)
(HTM) web link (www.da.vidbuchanan.co.uk)
(TXT) w3m dump (www.da.vidbuchanan.co.uk)
| dinkleberg wrote:
| This is great, nice work!
|
| I just recently started going through a performance programming
| course (https://computerenhance.com/) and have learned about SIMD
| and other techniques and it is awesome to see something out in
| the wild.
| ashvardanian wrote:
| This is a nice exercise!
|
| There is also a very different "write SIMD assembly in Python"
| approach available through the PeachPy library, one of the least
| known gems between Python and HPC worlds:
| https://github.com/Maratyszcza/PeachPy
|
| This is what a dot-product would look like in PeachPy:
| https://unum-cloud.github.io/usearch/python/index.html#id4
|
| PS: Cppyy and Numba are also fun to use in such projects :)
| brrrrrm wrote:
| PeachPy is awesome - it's really a great way to play with
| assembly-level performance programming and not have to deal
| with assembler toolchains
| eigenket wrote:
| > This is what a dot-product would look like in PeachPy
|
| Is it just me (I'm far from an expert here) or is this code
| really weird? Why does ymm_one appear to contain the number
| zero? Why do we subtract what looks like it should be the inner
| product we want from ymm_one at the end?
| eigenket wrote:
| I can't edit my previous comment for some reason but it looks
| like the code # Negate the values, to go
| from "similarity" to "distance" VSUBPS(ymm_c,
| ymm_one, ymm_c)
|
| Is actually just subtracting zero from ymm_c for no reason I
| understand.
| Retr0id wrote:
| I believe the argument order is "a = b - c", so it's
| effectively `ymm_c = 0 - ymm_c`. (And yes, ymm_one does
| seem to be initialized to zero, I'm not sure why they
| picked that name for it...)
| eigenket wrote:
| That makes slightly more sense, but then why the heck do
| you end up needing to negate something while computing a
| dot product?
| redskyluan wrote:
| Just stumbled upon this blog it's absolutely intriguing! As a
| Python enthusiast, it's like finding a hidden treasure that
| challenges the usual norms of Python's capabilities. Thinks of
| writing a Pure python implementation of some ml algos in learning
| SIMD~
| jxy wrote:
| tl;dr
|
| > The general term for this concept is SWAR, which stands for
| SIMD Within A Register. But here, rather than using a machine
| register, we're using an arbitrarily long Python integer. I'm
| calling this variant SWAB: SIMD Within A Bigint.
|
| Thanks to Peano and Godel, it's safe to say we may encode any
| compute with operations on natural numbers. So if anything is
| slow in Python for you, you may always encode it in Bigint and
| hope for the best.
| jvans wrote:
| Exercises like this really make you a better programmer. Someone
| should collect these types of examples in a git repo somewhere.
| justinl33 wrote:
| Genius!
|
| >* the state of the cells is being stored in a big array,
| accessed via the get_cell and set_cell helper functions. What if
| instead of using an array, we stored the whole state in one very
| long integer, and used SWAB arithmetic to process the whole thing
| at once?*
|
| I'm really curious as to how the unpacking of this long integer
| into pixels on the screen doesn't add more overhead than it
| saves. I guess I'll have to wait for your next one on the
| compressed gzip stream hack.
| nneonneo wrote:
| If I had to guess, it's a matter of setting up the Huffman
| tables such that every code ends up with a length of four bits,
| and then prepending that precomputed Huffman table onto the
| "compressed" stream. Then you can abuse the zlib library as a
| decompressor mapping the 4-bit "Huffman" codes to regular
| bytes.
|
| Of course, this won't be anywhere near as efficient as just
| implementing the decoder in C, as Huffman decoding needs to be
| much more general than just unpacking fixed-width chunks. But
| it will definitely be an improvement over naive loops.
|
| I wonder whether .hex() could be pressed into service as a very
| scuffed 4-bit unpacker? Maybe something like
| .hex().encode().translate() to get an arbitrary palette
| mapping?
| Retr0id wrote:
| Yup, that's pretty much exactly it.
|
| .hex() is a good idea, and probably has a decent chance of
| beating gzip, assuming .translate() is fast enough.
|
| The fastest approach for the bitsliced AES impl ended up
| being pretty cursed:
| https://github.com/DavidBuchanan314/python-bitsliced-
| aes/blo...
| nneonneo wrote:
| Neat trick! I implemented a similar bitpacking approach for
| solving matrix equations in GF(2), which can be used for things
| like forging CRC hashes (faster than bruteforce) and solving
| certain cryptography problems. Code is here:
| https://github.com/nneonneo/pwn-stuff/blob/master/math/gf2.p....
| Retr0id wrote:
| Ha! As it happens, I've recently written near identical code,
| and was considering writing about it in a future article - I
| originally had leaking internal states of xorshift128+ in mind
| :)
| akasakahakada wrote:
| np.array([ BigInt list ], dtype=object)
|
| then you can apply this bit parallelism to a tensor.
___________________________________________________________________
(page generated 2024-01-05 23:02 UTC)