4 ms·
Errors are highly domain specific. When I worked in finance, I would have very much agreed with your description. But then, the code I wrote was fairly trivial,
by marginalia_nu 5y ago
Errors are highly domain specific. When I worked in finance, I would have very much agreed with your description. But then, the code I wrote was fairly trivial, the challenge was communicating with the users and sometimes getting the users to understand what they were asking for wasn't what they wanted.
I, the same developer, spent a good hour recently trying to iron out the bugs in a piece of code that concatenated two integers bit-wise and calculated the offset point. That is, given two integers whose bits are
00000000,00000000,00000000,0PPPPPPP
00000000,000000QQ,QQQQQQQQ,QQQQQQQQ
The code should produce the shortest an array of bytes that looked like
ZZZZZZZZ,0000000P,PPPPPPQQ,QQQQQQQQ,QQQQQQQQ
Where Z in this case would be 18, the offset of P's bits. This is finicky in a way I've never encountered while I worked in finance. It's not exorbitantly difficult, but there are just a lot of potential logic errors to make.
The code, ultimately, looked like this (it's Java hence the extra awkward bit twiddling)
int pw = bitWidth(p);
int qw = bitWidth(q);
int pwr = (pw%8);
int totalSize = (pw + qw)/8 + (((pw+qw)%8)>0?1:0);
byte[] data = new byte[totalSize + 1];
int b = data.length - 1;
while (p > 0) {
data[b]=(byte)(p&0xFF);
p = p >>> 8;
if (p != 0) {
b--;
}
}
if (pwr != 0) {
while (q > 0) {
data[b--] |= ((byte) ((q << (pwr)) & 0xFF));
q = q >>> (8-pwr);
data[b] |= (byte) (q & 0xFF);
q = q >>> pwr;
}
}
else {
while (q > 0) {
data[--b] |= (byte)(q&0xFF);
q = q >>> 8;
}
}
data[0] = (byte) pw;
return data;
It's like 40 lines of code. It shouldn't be that hard. Yet it is. Bit-twiddling is error prone and hard to reason about and, dunno, maybe pwr isn't a great variable name, but the code really doesn't get particularly expressive even if you change it to pWidthRemainder or whatever. It's still basically a bunch of cthulhu fhtagn as far as I'm concerned.
- hiptobecubic 5y agoWhat on Earth required this? Is this part of some home grown compression scheme?
- marginalia_nu 5y agoIt is indeed, it's part of the compression scheme for the keyword lexicon for my search engine. It's a domain-specific compression that uses the fact that the keyword dictionary is a dictionary of keywords to compress N-grams into dense blobs using this function. Overall it achieves about 70% compression. The lexicon supports several billion entries entirely in memory, which requires a lot these eldritch coding tricks (since Java certainly wasn't built for that many objects, GC and header overhead extremely prohibitive so objects are entirely out of the question). Most of the data is kept in contiguous memory mapped byte arrays.
- Supermancho 5y agoThat's at least 5 functions of processing munged into one.
- marginalia_nu 5y agoYou're welcome to demonstrate that I'm wrong, but in my experience, Uncle Bobbing this type of code doesn't make it much clearer unless you introduce so many abstractions you see significant penalties. This is hot code with an invocation count in the billions, so among the requirements is that it shouldn't allocate objects while at the same time being thread safe. That's a tricky combo.
- Supermancho 5y agoRegardless of the language, the function is too complex. Every while could be it's own function and now you have a bunch of simple unit tests. Unit tests are literally the double accounting for the logic, which is the value. Any unit tests for that code is going to be horrendous to get decent coverage...and this is how it's easy to know it's too complex. Functions, especially if they are small, can be considered free, given the JVM inlines them into branches anyway....but I understand this is a hot path. If you want to avoid re-allocation, Java gets into your way. You could split up the function and use a singletonClass for holding the array, without having to pass the array by value and still being able to reference the singletonClass...blah blah blah. > Uncle Bobbing this type of code doesn't make it much clearer I get it and agree, while still recognizing the problem. Not you not the code not me. Java. It's really unfortunate that Java has damaged programming practices so subtly and completely by being unnecessarily byzantine AND pushing horrible solutions like Spring.
- marginalia_nu 5y agoI don't subscribe to the notion that every branch of every function needs to be tested. That just seems like anxious waste of time, not even considering the gargantuan pile of additional work it creates in maintenance of the tests.
- wruza 5y agoThis code would be less bullshit if C language (or C+ or any successor) enabled bit arrays and slices, just like byte arrays work. Bit-fiddling grows from the fact that there is no “addressable bit sequence” type in a language. I wonder how many bugs could be erased by simply allowing the following in such algorithms: bit data[length]; int width = 6; bit value[width] = random(64); for (i=0; i < lim; i += width) { int j = endof(i, width); data[i:j] = value; } or something like uint8_t c = 0xff; c[0..3] = 1; c[5..7] = 1; // c == 0x31
- jrockway 5y agoI recently wrote a microbenchmark where I convinced myself that doing operations to a [64]bool was equally fast as doing the same (bitwise) operations on an int64.
- dgunay 5y agoC++ has `std::bitset` for when the length is known ahead of time [0]. Otherwise, `std::vector<bool>` _may_ be specialized to occupy one bit per element [1]. [0]: https://en.cppreference.com/w/cpp/utility/bitset https://en.cppreference.com/w/cpp/utility/bitset [1]: https://en.cppreference.com/w/cpp/container/vector_bool https://en.cppreference.com/w/cpp/container/vector_bool
- wruza 5y agoBoth (and boost’s version too) can only address/assign one bit at a time, so it introduces the mirrored problem: how do you splice an n-bit integer into it without fiddling? Of course one can always abstract ops from my snippet away into some library, like setbits(ptr, offset, len, value), that’d be still valid, no need for fancy overloads even. But when batteries aren’t included, nobody cares enough to buy them separately. We know that from the situation with C strings.
- Const-me 5y agoI think it’s the language. Haven’t really tested but in C# that would be something like that, 8 lines of code instead of 40: public static byte[] func( uint p, uint q ) { int pw = 32 - BitOperations.LeadingZeroCount( p ); int qw = 32 - BitOperations.LeadingZeroCount( q ); Span<byte> buff = stackalloc byte[ 9 ]; ulong val = (ulong)q | (ulong)p << qw; BinaryPrimitives.WriteUInt64BigEndian( buff.Slice( 1 ), val ); int totalBytes = ( pw + qw + 7 ) / 8; buff[ 8 - totalBytes ] = (byte)qw; return buff.Slice( 8 - totalBytes ).ToArray(); } In C++ about the same, albeit you gonna need either C++/20 language version, or some non-standard compiler specific intrinsics for bit scan and byte swap.
- marginalia_nu 5y agoYeah, Java is almost certainly not the optimal language for low level programming. It's like C++ with oven mitts.
- CraigJPerry 5y agoI don’t know if it could help in your case (java) but there’s a machine instruction for count leading zeros on x86 platform - LZCNT https://en.m.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set https://en.m.wikipedia.org/wiki/X86_Bit_manipulation_instruc... - i found out about this randomly years ago when i was doing some interfacing with a microcontroller from python and my solution was horrifically slow. To exploit this i had to use cython from python to define a c function which used a gcc compiler intrinsic to allow me to write the asm instruction inline. It turned out about 7 lines of code so it wasn’t as bad as it sounds. In your case, you’d need to use JNI i suppose so it might not be any less code but it should at least be a lot faster if that matters.
- marginalia_nu 5y agoJava has Integer.numberOfLeadingZeros(), which I suspect exposes LZCNT where available.
- Const-me 5y agoYeah, and where not available Java probably uses BSR instruction which does the same thing but introduced in i386 (1985): https://www.felixcloutier.com/x86/bsr https://www.felixcloutier.com/x86/bsr
- twic 5y agoDoesn't this code actually put q in front of p? That is: ZZZZZZZZ,0000000Q,QQQQQQQQ,QQQQQQQQ,QPPPPPPP With Z still being the width of P?
- marginalia_nu 5y agoYeah, that's just me describing the requirements from memory :P
- twic 5y agoAlso, it seems to fail if either p or q is 32 bits long - you get zeroes instead of the bits of q. Here's my attempt, which is shorter, and i think quite a bit clearer: int pw = bitWidth(p); int qw = bitWidth(q); int qpw = qw + pw; long qp = Integer.toUnsignedLong(q) << pw | Integer.toUnsignedLong(p); int qpwBytes = ((qpw - 1) / Byte.SIZE) + 1; byte[] bytes = new byte[qpwBytes + 1]; bytes[0] = (byte) pw; for (int i = 1; i < bytes.length; i++) { bytes[i] = (byte) (qp >> (qpwBytes - i) * Byte.SIZE & 0xff); } return bytes; This did take me quite a bit of fiddling to get right - but it wasn't the bit-twiddling, it was the index arithmetic for copying the bytes into the array!
- marginalia_nu 5y agoYeah, the p and q are guaranteed to be positive, should be added. But that is indeed a more elegant solution.
- Someone 5y agoI think I would use BigInteger for that. You can create them from and convert them to arrays of bytes, count bits, shift them left and right, and add them, resizing storage where needed. https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html https://docs.oracle.com/javase/7/docs/api/java/math/BigInteg...