PROPOSAL: Binary Literals

[Derek Foster]

Comments inline.

-----Original Message-----
>From: Reinier Zwitserloot <reinier at zwitserloot.com>
>Sent: Mar 25, 2009 11:46 PM
>To: Derek Foster <vapor1 at teleport.com>
>Cc: coin-dev at openjdk.java.net
>Subject: Re: PROPOSAL: Binary Literals
>
>In regards to j2me: j2me is on its way out, and will not be receiving  
>many updates regardless, because sun can't exactly update the java  
>version on the billions of phones out there.

You seem to be under the impression that j2me is solely for phones. It is actually for "embedded systems" and "mobile devices" of which phones are only an important subset. A device like a Kindle, or a PalmPilot, or an iPod Touch, or even headless devices like the JavaRing or various kinds of network appliances could conceivably use J2ME.

Note that phones get replaced every few years on average as people upgrade for better features or change service providers, so the fact that Sun can't update the existing ones is pretty much irrelevant.

In any case, I am not currently using J2ME. I just mentioned it because it has similar constraints to the sort of programming I have been dealing with recently: a system which allowed hundreds of tiny Java programs to be compiled to native code to run together on a single massively parallel processor chip with hundreds of cores, each of which has only a tiny amount of memory. Oddly enough, that kind of severely resource-constrained environment is far more similar to writing a J2ME app to run on a cell phone than it is to writing an app to run on a webserver, and a lot of the same techniques and concerns apply.

>On performance: I don't understand. The result of a library call is a  
>byte primitive, which you can then assign to a private static final  
>byte constant. From there on out, that will be as fast as a code  
>literal. Unless you were planning on using a few million binary  
>literals in your code, there shouldn't be a performance impact; just  
>an annoyance that you have to constantize every literal you use in a  
>time sensitive area instead of using Byte.of("01000100") directly in  
>your method body.

You are not considering the impact of constant folding on compiler optimizations.

Not all constants are created equal. Constants whose values can be determined at compile time can be inlined by the compiler, and arithmetic expressions involving them can often therefore be simplified at compile time. This process is known as "constant folding". The resulting code need not reference the original variable to get the constant at all -- it can just use the inlined result of evaluating the expression. Additional compiler optimizations may then be performed on the basis of these folded constants. For instance, a compiler might decide to compile this code:

private static const final int FOO = 0x42;
private static const final int BAR = FOO + 3;
private static const final int BAZ = 0x46;
private int func(int x) {
    return x * (BAZ - BAR);
}

as if it had been written like this:

int func() {
    return x;
}

Note that there is now no need to even allocate space to hold FOO, BAR, and BAZ, since all references to them were removed as part of the constant folding process.

However, if I had instead declared the variable FOO as:

static const final int FOO = Integer.decode("0x42");

then the compiler cannot determine its value at compile time, and must generate code to actually call the parseInt function at static initialization time and stow its result in the FOO variable, then calculate BAR, and so forth, eventually compiling the 'func' function as written, with an unnecessary and time-consuming multiply operation in it.

The situation gets even more complex when constant folding is combined with method inlining, so that entire methods which perform bitwise or other operations may be simplified to omit certain operations in some call sites but not others depending on what arguments are passed and whether or not some of those can be determined to be compile-time-constant expressions.

In general, these kinds of optimizations can't be done for expressions involving a call to a library method, because the compiler does not know at compile time what value that method will return when it is executed.

I suggest some research into the justifications given for why the hexadecimal notation for floating point numbers was added to the language (despite its ugliness and the limited domain in which it is used), and why libraries were not judged an adequate solution in that case. Basically the same arguments apply here.

>The odds that "0b01000100", where you've added a zero too many (or  
>left one out) is going to result in a compile time error seems odd.  
>Why would that cause a compile time error, exactly?

for the same reason that this:

byte x = 900000000000;

is a compile-time error. The compiler checks the numeric ranges at compile time, and knows that the value declared won't fit into a byte. It won't detect leading zeroes, of course.

>Evidently that wasn't clear, but my reference to "real programmers  
>think in hex since they are A years old" was intended as a joke. I  
>apologize if that wasn't obvious.

I took it as a joke, although I started to wonder after later postings of yours seemed basically to be arguing from that perspective. For the record, my comments about front panel switches to program core memory were also a joke. (Real Programmers actually program core memory by reaching into it with a magnet.)

>How many bits are set in 0x4EC6? 8. I was able to count that about as  
>quickly as with 0b0100111011000110. Shame we didn't bet on it.

Even if you personally can genuinely do it that fast, I very much doubt that most Java programmers can.

>Quick: How many nibbles are in 0b0100111011000110? How many bits are  
>set in the upper byte?

This example only illustrates that a program that needed to answer questions like that would probably best written to use hexadecimal notation. My point was not that hexadecimal notation should be removed from the language or deprecated in some way -- just that some problems are better understood in binary, and it would be useful to have binary notation available for use on those problems.

>There are a select few questions that are just easier when written out  
>in binary, even if that results in a massive amount of digits, such as  
>finding contiguous sequences of bits (the packing into nibbles gets in  
>the way for that kind of thing). Which is why I said that  
>Byte.of("01000100") is a good idea.

That method basically already exists (Byte.parseByte("01000100", 2)), and I use it in code where appropriate. However, my prior comments about library methods still apply. Besides the issues I mentioned before about disabling the compiler's support for constant folding, note that the compiler also won't issue any warnings or errors at compile time for any of the following:

Byte.parseByte("0100100 ", 2);
Byte.parseByte("010O100", 2);
Byte.parseByte("0101l00", 2);
Byte.parseByte("Slartibartfast", 2);
Byte.parseByte("010010001001001001010", 2);

It will therefore be left up to unit tests (assuming someone has time to write them, and when executed, they cover the particular code path in question) to find problems like these. This is a Bad Thing. Finding problems at compile time is much more reliable than finding them at runtime.

>The theory of 'those who don't care can just ignore it' has a  
>fundamental flaw: It leads to readable-only-by-author code. Grab some  
>perl example code and try to ascertain what it's trying to do. I wish  
>you good luck!

You appear to be assuming that people will choose to use this new feature primarily in ways that will be abusive and will decrease the readability of code, rather than choosing to use it in the places where it makes code clearer, and using hex, decimal, or octal in the cases where those make code clearer. I don't understand why you hold this belief.

Yes, people can choose to be malicious or stupid in their coding, but most programmers won't be. If that argument were truly persuasive, then we should remove (or should never have added) most of the other existing features from Java as well, as well as pretty much everything currently being discussed in Project Coin, on the grounds that a malicious or incompetent programmer could use them to write horrible code.

I've seen things done with nothing more than 'if' statements and 'for' loops that would turn your stomach, but I don't consider that a good reason to remove these features from the language. I just consider them a good reason to remove the programmer that wrote such atrocities from my project, or remove myself from the company that hires such incompetent programmers.

A bad programmer will write horrible code no matter what language features are available. Lack of language features can't prevent that. However, language features can enable good programmers to write better code, and can even encourage (although not force) average programmers to do so.

Most programmers want to be able to code in a way that clearly expresses the intent of their design. Putting barriers in their way to that goal does not appear to me to be a good idea, since if they are not allowed to do things in an easy, straightforward way, they will be forced to choose between a variety of less-than-optimal alternatives. Consider that if the language does not support binary literals, and someone wants to get the effect of using them anyway, that the most likely approach (in my experience, anyway, having looked at a lot of people's code) is to write their own custom binary-to-integer translator, and call it all over the place. (I've seen this done before.) Do you think this makes the code easier to read? I don't.

>Optimally speaking, every language feature is at least somewhat  
>familiar to every programmer of that language. Java is a few steps  
>beyond that already (see the Java Puzzlers for proof), but that  
>doesn't mean we should no longer care about that tenet anymore. Such a  
>feature should introduce extremely significant improvements in a niche  
>area, and/or allow you to things that you just can't do now. This  
>clearly isn't the case.

I think there is actually quite a bit of disagreement about what exactly the criteria should be for what features are included, and whether the ones you list are the only ones applicable. In any case, I don't see how this feature satisfies your criteria any less than, for instance, enhanced for loops, static import, or boxing. It's trivially easy to use, and explaining it to a new programmer takes all of two seconds ("binary constants look like 0b000101"), in contrast to having to explain, say, the Iterable interface or how "int x = y;" might now trigger a NullPointerException.

I spend significant time programming in a niche that you apparently don't (based on your statement that bitmasks are "seldomly used" which has not been my experience at all in the Java programming domains where I have been spending time for the last few years). This feature would be a significant benefit to me. I would not have bothered to write up a proposal for this feature, and spend time researching that proposal as well as I have, if the lack of this feature was not a significant and frequent irritation to me.

>Speaking of 'things that you just can't do now', for bit wrangling and  
>performance, I'd love to see a Math.* library that foregoes exact spec  
>precision and trades it for raw speed. Right now java Math.* can't use  
>the gfx pipelines because those don't use quite the same floating  
>point spec that java docs say they should. Just to give an example of  
>a change that I would wholeheartedly support even if it is extremely  
>niche.

That's a change that would affect me basically not at all (I almost never even find myself using floating point in Java, at least for on-the-job programming, and in the circumstances where I do use floating point, I am much more concerned with accuracy than speed), but I wouldn't oppose such a change. While it's not my programming niche, it is somebody else's, and we are both consumers of the Java platform and it needs to meet multiple users' needs.

Derek

>  --Reinier Zwitserloot
>
>On Mar 26, 2009, at 03:55, Derek Foster wrote:
>
>> I am all for the addition of library methods to handle bit/byte/word/ 
>> whatever munging. I plan to submit proposals for a few myself once  
>> the opportunity arises.
>>
>> However, library methods only cover a small subset of the use cases  
>> my proposal was intended to address. In my proposal, I specifically  
>> discussed the use of a library method and explained why it was not  
>> an acceptable substitute. I pointed out the performance impact of  
>> library calls, and noted that in the cases where low-level  
>> programming is most needed (in severely resource-constrained  
>> devices, J2ME, and so forth) that having library calls all over the  
>> place just to translate numbers from a readable form poses an  
>> unacceptable overhead in terms of performance, code size, and  
>> maintainability, not to mention the fact that bugs end up appearing  
>> at runtime (if you happen to run the code in _just_ the right way)  
>> rather than at compile time. I also pointed out the impossibility of  
>> using 'switch' statements with such techniques.
>>
>> With regards to the issue of "real programmers think in hex", by the  
>> way, I should point out that I started writing assembly language  
>> programs starting in sixth grade, and that that was around thirty  
>> years ago. Apparently even though I've been doing both high-level  
>> (Java, etc.) and low-level (assembly and occasional hand-coded  
>> machine language) programming for most of my life, I'm not a 'real  
>> programmer' because I use decimal, hex, binary, and even on some  
>> rare occasions, octal in the circumstances where they seem  
>> appropriate, rather than sticking religiously to hex regardless of  
>> the circumstance. (This is ridiculous, of course: Real Programmers  
>> don't really use hex. They program core memory using front-panel  
>> switches, in binary. Or possibly using punched cards if they are  
>> feeling a need for luxury.)
>>
>> In my experience, *real* "Real Programmers" use the appropriate tool  
>> for the job they are doing at the moment. Hex is simply not the  
>> appropriate tool for all jobs. It's great to use when it is  
>> appropriate (like when data lines up nicely on four-bit boundaries,  
>> or when the specification you are working from states its important  
>> numbers in hex), but it is extremely inconvenient to use hex the  
>> situations where it's not appropriate. Having to translate back and  
>> forth between hex and binary all the time when what you really want  
>> to do are fundamental binary operations (which are easily and  
>> clearly expressed in binary, and easily checkable against the  
>> relevant specifications documents which specify them in binary), is  
>> a waste of time and a rich source of bugs.
>>
>> Quick: How many bits are set in the number 0x4EC6?
>>
>> If the number were written in binary, you would be able to answer it  
>> as fast as you can count to eight. I'll bet you can't do it half  
>> that fast when it's expressed in hex.
>>
>> Here's a few more to contemplate:
>>
>>
>> How many contiguous bit ranges exist in the number 0x5FF99C? What  
>> are their starting offsets?
>>
>> What will be the result of XORing together 0x4DE6 and 0x3837?
>>
>> Will 0x8567124 and 0x7218DB, ANDed together, be nonzero?
>>
>> What's the index of the fifth-highest set bit in the number 0x4687?
>>
>>
>> All of the above questions are easy and quick to answer in binary,  
>> but difficult and error-prone in hex. In fact, the most difficult  
>> part of answering them in hex isn't answering the problem -- it's  
>> translating the hex to binary so the problem can be solved! When I  
>> am doing code review, I don't want "difficult and error prone". I  
>> want simple, direct, and mapping as directly to the specification I  
>> am implementing as possible.
>>
>> For a recent job, I had to deal with writing a decompiler for a  
>> processor which had lots of bitfields that didn't fall on nice even  
>> nybble boundaries, but instead often straddled them and had strange  
>> widths (3 bits, 9 bits, etc.). Furthermore, there were often  
>> multiple noncontiguous ranges of bits that had to be merged into the  
>> same field. Using hex numbers for this kind of situation makes the  
>> code all but unreadable without close study, and basically required  
>> that the size of the code be doubled due to all the extra named  
>> hexadecimal constants (for shifting, bit masking, and so forth) plus  
>> the comments needed to explain what the heck the code was doing,  
>> since its structure no longer directly expressed the problem it was  
>> trying to solve as stated in the specification. In most cases, I  
>> ended up having to write the binary representations of the numbers  
>> as comments alongside the hex translations of them, and then  
>> manually check the two against each other, just so I could later a
>> lso manually check the binary numbers in my comments against the  
>> printed specification.
>>
>> Then I wrote and ran unit tests and found that even though I had  
>> manually verified the translations, I had still made a mistake. (Not  
>> too bad considering that I was translating a couple of hundred  
>> numbers in my head).
>>
>> I have recently had the occasion to do programming for  
>> microcontrollers in GCC, and was able to use the binary literal  
>> support provided by that compiler. It was so easy to use, and made  
>> the code so much clearer, that I found myself wondering again why I  
>> have to give up this feature when I move to the supposedly more  
>> convenient Java language.
>>
>> Why should programmers have to waste their time translating between  
>> hex and binary, when this is trivial for a compiler to do, and is  
>> considered a common enough need that multiple programming languages  
>> already support it?
>>
>> The effort to support this in a Java compiler is tiny, it fits well  
>> with the rest of the language and is similar to features in other  
>> languages. It won't break any existing code, and it is easy for  
>> those who don't want to use it to ignore it.
>>
>> Derek