pretty flag
Conversation
Replying to
On the contrary, this aims at obtaining from GCC the constants that allow to implement these divisions as multiplications… in a context where the numbers to divide could have been represented as BCD, and then division would be trivial, but they weren't.
1
5
There's a great blog post on generating them yourself. We explored doing it in musl ldso to perform the % operation for hash lookups. I'll try to find link if you're interested.
2
3
There's an even faster way to do 32-bit mod, for cases like that hash example:
arxiv.org/pdf/1902.01961
github.com/lemire/fastmod
In github.com/GrapheneOS/har, I use libdivide for mapping the address of a slab allocation to the index of the slab metadata (github.com/GrapheneOS/har) and to find the slot of the slab allocation within the slab (github.com/GrapheneOS/har and github.com/GrapheneOS/har) for the bitmaps.
1
2
There's also the fancy approach to generating random numbers uniformly within a range without using a mod operation:
arxiv.org/pdf/1805.10941
I use that in github.com/GrapheneOS/har and it was a nice performance boost. I'll probably use these approaches elsewhere now too.
1
Show replies
It looks like it depends on __int128_t, which is a non-starter. The whole point is that 32-bit div/mod is a _function call_ on some archs; these certainly don't have 64x64->128 mul or full 128 mul.
2
1
That can be implemented fairly efficiently via 64-bit integer operations though. GCC / Clang provide a decent 64-bit int on 32-bit and 128-bit on 64-bit in software. It could be open coded too. It's going to make an even bigger difference if there's no hardware mod / div at all.
1
1
Show replies