Hacker News new | ask | show | jobs
by explodingwaffle 607 days ago
The more and more bit-hacks I see, the more convinced I am that they should be handled by a cleverer compiler. Some intrinsic(s) where you say “do x, y, to these bits” and it just figures out the optimum way of doing it for whatever platform you compile for.
3 comments
jsheard 607 days ago
This tool is handy if you want a specific bit shuffle:

https://programming.sirrida.de/calcperm.php

It doesn't always find the optimal solution but it usually gets close.

link
PhilipRoman 607 days ago
That's a really cool side. Sad that it doesn't allow duplicate indices. I tried implementing the same thing but with support for duplicates and it was definitely a humbling exercise. I'm curious if there is any formal mathematical theory for this (shifted-off bits would probably make it less elegant than pure rotation)
link
explodingwaffle 607 days ago
that page + the book Hacker's Delight are a big part of the reason I am so convinced of this :)

If compilers/languages/standard libraries provided these bit permutations, and it was just something ~everyone had learned, it would be a lot easier to work with bits without needing to come up with the bitwise ops (or use that generator). In addition it would probably make better use of the hardware: sure, people like to pretend that we’re still programming C for PDP11, but modern hardware supports more operations than C has operators for (RISC-V B extension and co have the right idea <3)

Modern compilers are probably pretty good? but I doubt they are perfect at turning code like that in OP into the best instructions. It is probably a bit late for C/C++ though. maaaybe possible to get it into LLVM and Rust.

link
sumtechguy 607 days ago
I always wanted to see stuff like this website put into the compiler. https://graphics.stanford.edu/~seander/bithacks.html

The very tough problem is recognizing to emit the correct code.

link
sixthDot 607 days ago
Well it is already the case, for example things like ROR or ROL are generated by optimizers[1] from certain patterns of bitops.

[1]: https://godbolt.org/z/eE1cx9GT4

link
jsheard 607 days ago
That's more like the opposite, OP wants to tell the compiler what transform to do and have it figure out a solution, but in your example you give the compiler a solution and it works backwards to figure out the intent and rewrite it to a completely different solution.

Most languages do have intrinsics for ROL/ROR at least, which you should generally use instead of relying on optimizer magic. I've certainly run into cases where those magic patterns don't get optimized (looking at you MSVC) but intrinsics always work.

link