9 ms·
EABitTricks.h
- flohofwoe 4y agoSeeing the project name EAStdC I thought for a moment this would be the C counterpart to EASTL (e.g. a modern replacement for the C standard library), but alas, it's all written in C++ and intended to be used from C++ (e.g. no C interfaces). For anyone interested in this sort of stuff and isn't yet aware of the 'bit twiddling hacks' collection: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html Also regarding the bit counting function: inline int CountBits(uint32_t x) // Branchless version { #if defined(EASTDC_SSE_POPCNT) return _mm_popcnt_u32(x); #else x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; return (int)((x * 0x01010101) >> 24); #endif } Some compilers go as far as detecting the 'bit twiddling' version and replace that with a popcnt instruction: https://www.godbolt.org/z/bExMvfzEx https://www.godbolt.org/z/bExMvfzEx
- sreekotay 4y agoMy contribution: http://sree.kotay.com/2007/04/shift-registers-and-de-bruijn-sequences_10.html?m=1 http://sree.kotay.com/2007/04/shift-registers-and-de-bruijn-...
- maximilianburke 4y ago(disclaimer: I used to work on these EA* libraries) The intention of EAStdC wasn't really to replace the platform libc but to augment it with portable implementations that had consistent behavior across the different platforms, as well as have some opt-in performance improvements (like a memcpy that used VMX), while also not polluting the global (C) namespace.
- djmips 4y agoWow! That's quite surprising to me (the godbolt link). Very cool!
- vodou 4y agoModified BSD License (3-Clause BSD license), so it is permissive. Not apparent from header file only.
- AdmiralAsshat 4y agoAre any of these still needed, though? I kinda assumed they would be like Duff's Device and be a nifty historical relic, but firmly in the "Let the compiler do this for you" category in modern C.
- TonyTrapp 4y agoMany of those are not standard functions (or were not, until very recently). You have to implement it somehow, so having a ready-made collection that also performs well is very nice to have.
- jesse__ 4y agoWhen you're working on Frostbite you definitely need these. Optimizers are smart, but aren't smart enough yet
- anonymoushn 4y agoHow do you let the compiler do these things for you?
- saagarjha 4y agoBy having someone write the optimization passes to detect these :)
- KMnO4 4y agoCompile with optimizations enabled.
- anonymoushn 4y agoWhat code specifically do you write instead of the code in TFA, in order to have the optimizer generate the code in TFA? In general compiling with optimizations enabled has not produced particularly good code in my experience.
- mywittyname 4y agoinline uint32_t Log2(uint32_t x) { const union { float f; uint32_t i; } converter = { (float)x }; return (converter.i >> 23) - 127; } This is interesting. It looks like it's returning the (biased corrected) value of mantissa. I'm surprised that there isn't a function supplied by the compilers or in the processor that takes an int and returns the mantissa. After all, every int -> float conversion requires this step.
- electroly 4y agoTake a look at the C header <ieee754.h>. It's not on all systems but it provides a union for type punning between a double and its decomposed parts. IEEE754_DOUBLE_BIAS is provided for bias correction. The same are available for floats. (Unfortunately, the "not on all systems" part is why I don't use it, but instead copy the union and the constant verbatim into the project if I need it.)
- asveikau 4y agoI thought that type punning via union is against the standard. I personally do not think it should be ... It's a very handy tool.
- electroly 4y agoI think it may be a GNU extension to explicitly allow it, but I'm no language lawyer. This header is from glibc; it may explain why it's not available on some platforms.
- ot 4y agoMy favorite so far /// GetNextWithEqualBitCount /// How to get the next higher integer with the same number of bits set. /// This function is supposed (claim by original author) to be able to /// wrap around and continue properly, but testing indicates otherwise. /// Do not call this with x = 0; as that causes a divide by 0. /// Doesn't work for an input of all bits set. /// Do not assign the result of this to a type of less size than the input argument. /// This function has certain real-world applications. /// This function has been called 'snoob' by some.
- Centigonal 4y agosnoob - I want to know why
- smcl 4y agoFull marks for honesty, IMO. It'd be tempting to delete this before making it publicly visisble.
- rosywoozlechan 4y agoI wonder what the real-world applications for this are
- CGamesPlay 4y agoIt can be used to enumerate all subsets of size N from a set of size M. Start with 1 << N - 1, and then repeatedly call this function until the value is larger than 1 << M. Every subset of size N will be visited, in order.
- ladberg 4y agoI wonder how many of these have actually been used vs someone thought of a cool bitwise trick for a problem that doesn't exist. Can anyone think of a use-case for TurnOffLowestContiguousBits?
- dansalvato 4y agoI'm working on a game written in m68k Assembly. In cases where I'm trying to make every CPU cycle count, these kinds of novel bitwise operations really catch my interest. TurnOffLowestBit seems useful for an effect I've had in mind for a while: A graphic gets "erased" one pixel at a time from right to left, but with some random variance for each horizontal line. Reliably turning off the lowest bit might be a good solution. Maybe throwing in TurnOffLowestContiguousBits would help to introduce some variance in a visually interesting way. Or maybe it wouldn't. But in order for me to consider these operations as potential solutions to a problem, I have to know they exist. Even if they beckon for me to invent a problem they can solve, I'm totally open to that kind of creative inspiration. "Check out this neat bitwise thing you can do in only 12 CPU cycles!" That's definitely the jam of Assembly and/or demoscene coders, haha.
- deleted 4y ago[deleted]
- thomasahle 4y agoFunny they didn't just extend the 32 bit reverse algorithm to 64 bits: https://github.com/electronicarts/EAStdC/blob/master/include/EAStdC/EABitTricks.h#L518 https://github.com/electronicarts/EAStdC/blob/master/include...
- chrchang523 4y agoYes, this library is of uneven quality, and would benefit from a few hours of focused attention from a specialist. E.g. the various HighestBit functions below what you've called out also look inefficient relative to something using one of the builtin_clz intrinsics, even though there's an earlier use of builtin_clz...
- asveikau 4y agoI think a lot of times the way a header like this comes into being is that someone has a narrow need for an operation that is deemed reusable and abstract. The 64 bit version of a 32 bit bit utility doesn't have a need at the time. Then somebody comes in later trying to fill out more stuff.
- rsaxvc 4y agoI haven't tested this, but on Arm32 platforms, this isn't a bad way to do it n some 32-bit machines. If the compiler recognizes the 32-bit approach and rbit is available, the 64-bit variant is usually 2 rbits with the registers swapped.
- thomasahle 4y agoIf the compiler can recognize the 32-bit version, it really should be able to recognize the 64-bit version too, no?
- rsaxvc 4y agoIdeally yes. Only last year did Clang 13 learn the 32-bit one. GCC doesn't understand either. I haven't checked clang for the 64-bit one.
- erksa 4y agoDoes anyone have any reading material on introduction to where bit-wise programming becomes important knowledge? Is it mostly just used in game-dev? They've always peaked my interest, but never personally had to work with it, and just don't know the use cases where these become important!
- ianlevesque 4y agoInteracting with hardware registers, such as in a device driver, is another common use case.
- woodrowbarlow 4y agoor implementing file formats / network protocols
- _0ffh 4y agoMost obvious use case I can think of is embedded programming, e.g. when you're setting control registers.
- thoughtFrame 4y agoI don't know of any formal introductions to the topic but you can see them in action in these places too * some of Daniel Lemire's work in high performance data structures * the blog posts related to solving board games on https://nullprogram.com https://nullprogram.com * the articles about board representations on the chess programming wiki https://www.chessprogramming.org/Main_Page https://www.chessprogramming.org/Main_Page * Any explanation of Quake III's fast inverse square root
- erksa 4y agoThanks for the resources, these are great! As an avid chess fan I've always played around with the idea of trying making a basic chess engine.. This might just be the push!!
- xxpor 4y agoWhen dealing with networking it's extremely common.
- danbruc 4y agoFor those interested in this kind of stuff, there is the FXT library [1] and the accompanying book [2] by Jörg Arndt. [1] https://www.jjj.de/fxt/ https://www.jjj.de/fxt/ [2] https://www.jjj.de/fxt/fxtbook.pdf https://www.jjj.de/fxt/fxtbook.pdf
- butz 4y agoJust imagine performance of modern software if developers took time to optimize it, like they did it in the old days.
- saagarjha 4y agoBit hacks are but a tangent to performance optimization, of course.
- turtledragonfly 4y agoI like this topic, so here are some more "bit hacks" links, from my collection: * http://aggregate.org/MAGIC/ * http://graphics.stanford.edu/~seander/bithacks.html * https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer/109025#109025 * https://github.com/bloomberg/bde/blob/main/groups/bdl/bdlb/bdlb_bitutil.h
- supermdguy 4y agoQuestion from a frontend dev: Why can't the compiler apply these tricks automatically? Are there assumptions they're making that don't necessarily hold?
- SideQuark 4y agoThe compiler cannot always detect all the uses.
- nibbleshifter 4y agoYou can't really trust the compiler to emit sensible code ever
- jonstewart 4y agoClang and GCC can do some amazing optimizations. However, these types of tricks often come into play as a result of clever data representation, i.e., instead of representing data as a bunch of objects in an array, you’ve figured out how to represent it, or a subset, in some cleverly packed bits and/or ints (and then can reap the benefit of these tricks). It’s trivial for a compiler to see (x / 2) and substitute (x >> 1) but it is much harder for a compiler to go from seeing that you have a bunch of Foo objects and realizing that they could be better represented as clever bit vectors.
- nibbleshifter 4y agoThere's this gem in EAProcess.h ```/// ExecuteShellCommand("su root\nrm /* -r");``` https://github.com/electronicarts/EAStdC/blob/master/include/EAStdC/EAProcess.h#L222 https://github.com/electronicarts/EAStdC/blob/master/include...
- moonchrome 4y agoNo -rf ?
- trap_goes_hot 4y agoObviously a very very gross generalization (might get called out on it too :P) - But I think the low hanging fruit for modern software is optimizing data layouts for fast processing. Optimizing code requires a lot of work, and requires skills that people usually learn from experience - therefore a rare and expensive skillset. Data-Oriented Design can be taught, and requires (IMO of course) a far less technical skillset.
- anonymoushn 4y agoThis is difficult because lots of tools don't let developers choose their data layouts. For example you cannot declare an array of structs in Java.
- physPop 4y agoThis is very true. The tower of template and OO class hierarchies typical in c++ codebases make the memory layout impossible. Polymorphism and vtables are so killer for performance. I think general programming can learn a lot of lessons from HPC and game engines.
- news_to_me 4y agoI just got a copy of Hacker's Delight, which seems to show the same sorts of tricks. I haven't read very much of it yet, but I wonder how many of these came from that book or a common source. It would be fun to read more about the history of these tricks. https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685/ https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0...
- djmips 4y agohttps://en.wikipedia.org/wiki/HAKMEM https://en.wikipedia.org/wiki/HAKMEM contains some early history but probably not complete. These type of things get re-invented a lot.
- efortis 4y agoAnother handy one: Bitwise Table Lookup /* Bits: selected, hovered */ const colors = [ grey, // 00 green, // 01 blueA, // 10 blueB // 11 ] const color = colors[selected << 1 | hovered] https://blog.uidrafter.com/bitwise-table-lookup https://blog.uidrafter.com/bitwise-table-lookup