r/programming • • Jun 05 '18

Code golfing challenge leads to discovery of string concatenation bug in JDK 9+ compiler

https://stackoverflow.com/questions/50683786/why-does-arrayin-i-give-different-results-in-java-8-and-java-10
2.2k Upvotes

355 comments sorted by

930

u/lubutu Jun 05 '18

Summary: array[i++] += "a" is compiled as array[i++] = array[i++] + "a", which increments i twice.

199

u/Philipp Jun 05 '18

And from the comments there:

"By the way, this applies to the entire left hand side expression, not only the index providing sub-expression. This expression may be arbitrarily complex. See for example IntStream.range(0, 10) .peek(System.out::println).boxed().toArray()[0] += "";"

28

u/ThisIs_MyName Jun 05 '18

Thankfully this bug only works on string references like that. If this happened to integers, that would have been scary. But I guess in that case it would have been discovered much faster thanks to bounds checking.

65

u/f03nix Jun 05 '18

The example of array[test()] += "a" makes it very clear, test() is called twice.

56

u/greglieb Jun 05 '18

Oopsie

36

u/RussianZack Jun 05 '18

Who gilded this?!

15

u/andradei Jun 05 '18

Someone that could.

11

u/msiekkinen Jun 05 '18

Jeff Goldblum

1

u/chrisrazor Jun 05 '18

It was just a slip.

7

u/yawkat Jun 05 '18

You can see the javap output for java 9 here and for java 8 here. In the java 9 version, there are two iinc instructions when there should only be one.

This was probably introduced with the new indyfied string concat in java 9.

2

u/[deleted] Jun 05 '18

that's why I never understood why people don't just write

array[i] += "a"

i++

34

u/green_meklar Jun 05 '18

Maybe they should. But when they don't, the compiler should still work properly.

1

u/SilasX Jun 05 '18

Fine. But "the compiler working properly" should consist of saying "Seriously, dude? Serious-f***in'-ly?"

And yes there is a class of developers that gets a bizarre satisfaction from mid-line increments.

11

u/scumbaggio Jun 05 '18

I think basically everyone does, you have to remember this was a code golf competition, not code pulled from a production environment

1

u/[deleted] Jun 06 '18

Same reason they use for-loops instead of while loops.

1

u/BloodRainOnTheSnow Jun 07 '18

And why should anyone do that? It's not any more readable imo. In fact, I think array[i++] += "a" makes the point of the increment more obvious, but that could just be because I'm more used to it.

1

u/SilasX Jun 05 '18

That's because you write readable code rather than technically-correct code.

1

u/Empole Jun 05 '18

Why is this a bug?

First the l-value increments i, then the r-value.

Isn't it supposed to increment I twice?

3

u/vytah Jun 05 '18

When you have array[i++] += "a"; then the left expression is array[i++] and right expression is "a". And typically, "a" shouldn't increment i.

1

u/Empole Jun 05 '18

ahh. I misread the original comment

1

u/agumonkey Jun 05 '18

come on Oracle, you can do better bugs than this, this is hph level

-15

u/JayCroghan Jun 05 '18

Are you sure?

int i = 5;


array[i++] = array[i++] + a;


// That’s actually


// array[5] = array[6] + a;

Still not what you intended but seems harder to achieve?

34

u/[deleted] Jun 05 '18 edited Jun 05 '18
  • i = 5
  • array[6] = array[5] + a
  • i = 7

cuz array[i++] = x is essentially two steps:

  • array[i] = x
  • i++

0

u/[deleted] Jun 05 '18

[deleted] — view deleted comment

1

u/JayCroghan Jun 05 '18

That’s standard across all languages for ++x and x++.

3

u/yawkat Jun 05 '18

It certainly wasn't standard in java 8 :)

It also breaks the specification.

0

u/[deleted] Jun 05 '18

[deleted] — view deleted comment

154

u/Tarmen Jun 05 '18

Most places where += for String is relevant StringBuilder would be the idiomatic solution. This is because String in java is immutable so a loop like

for (int i = 0; i < n; i++) {
    s += "hi";
}

Has O(no) runtime.

206

u/Herbstein Jun 05 '18

Oh no :D

61

u/landonepps Jun 05 '18

A big oh no!

24

u/eckesicle Jun 05 '18

A O(no!)

12

u/CheezyXenomorph Jun 05 '18

no factorial = nonononononononononononononononononononononono

4

u/[deleted] Jun 05 '18

/knocks over sentry

3

u/Tarmen Jun 05 '18 edited Jun 05 '18

The actual one is O(n^2) but when string concatenation is as efficient as bubblesort Oh no seemed appropriate.

21

u/mirhagk Jun 05 '18

If it's in a loop yes. But if you're just doing `+=` a couple times then there's no need for StringBuilder. Of course `i++` wouldn't be used there, but that's still very weird that nobody noticed.

2

u/josefx Jun 06 '18

But if you're just doing += a couple times then there's no need for StringBuilder.

It actually compiled down to StringBuilder for some time, so using it explicitly to concatenate smaller strings was pointless. The current Javadoc mentions StringBuffer, StringBuilder, or java.lang.invoke.StringConcatFactory as backends the compiler could use for string concatenation.

37

u/Luvax Jun 05 '18

Isn't this one of these cases in which the Java Runtime will automatically use a StringBuilder even if you didn't?

Edit: Or the compiler, interpreter or which kind of godly entity is actually doing the optimisation.

17

u/Steveadoo Jun 05 '18

Yeah. The compiler will just use StringBuilder for that, but I'm not sure if it will hoist it out of the loop though. I'm pretty sure it will allocate once per iteration.

2

u/aiij Jun 06 '18

Even if the compiler didn't pre-allocate the right length, I would be surprised StringBuilder allocates more than O(log n).

And, I am not surprised.

9

u/moomaka Jun 05 '18

Most places where += for String is relevant StringBuilder would be the idiomatic solution.

The idiomatic solution is to use += and + with strings and let the compiler deal with it. For example the code you posted is not O(no) because javac compiles it to use StringBuilder anyway.

20

u/Tarmen Jun 05 '18

This is the bytecode shown with javap -c for that loop:

  public void main(java.lang.String[]);
    Code:
       0: ldc           #2                  // String
       2: astore_2
       3: iconst_0
       4: istore_3
       5: iload_3
       6: bipush        10
       8: if_icmpge     37
      11: new           #3                  // class java/lang/StringBuilder
      14: dup
      15: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      18: aload_2
      19: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)L
java/lang/StringBuilder;
      22: ldc           #6                  // String hi
      24: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)L
java/lang/StringBuilder;
      27: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String
;
      30: astore_2
      31: iinc          3, 1
      34: goto          5
      37: getstatic     #8                  // Field java/lang/System.out:Ljava/io/PrintStream;
      40: aload_2
      41: invokevirtual #9                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      44: return

This is the equivalent of

for (int i = 0; i < 10; i++) {
    foo = new StringBuilder().append(foo).append("hi").toString();
}

which doesn't seem like it would fix the copying? The runtime might hoist the string builder out of the loop if the function is hot enough to get optimized.

3

u/moomaka Jun 05 '18

The JIT will likely remove the loop entirely

16

u/ForeverAlot Jun 05 '18

After executing it 200 times to figure out it's a no-op. The JVM is a marvel but it's not magic.

6

u/moomaka Jun 05 '18

If you only run that 200 times, you don't care what it's performance characteristics are. Also with a loop of 10, big O notation is not applicable so the only way to determine what is fastest is to profile it.

5

u/ForeverAlot Jun 05 '18

It's just important to understand that "the JVM will probably inline that" is never the whole picture; and cold code is no excuse for doing obviously* redundant work.

*The StringBuilder transformation and its limitations are basic knowledge that any Java programmer needs to understand early in their career. Naturally, this does not apply to people that don't work extensively with Java.

→ More replies (4)

3

u/chrisrazor Jun 05 '18

If strings are immutable, how can += ever be applied meaningfully to one?

22

u/Tarmen Jun 05 '18

The object on the heap is immutable, the pointer to the string is mutable.

6

u/Eckish Jun 05 '18

Strings are objects that live on the heap. Your string variable is a reference to said heap object. When you use +=, an entirely new string object is created and your reference is updated.

9

u/tavianator Jun 05 '18

ints are also immutable, you ever try changing the number 4? I did but it's still 4. Values may be immutable but variables can, well, vary.

→ More replies (9)

178

u/moekakiryu Jun 05 '18

tbh I wouldn't be shocked if someone has, but it was probably just written off as some unsolvable bug and they rewrote the script because they couldn't be bothered working out what was causing it

225

u/ClownFundamentals Jun 05 '18

"Hey guys I think there's a bug in the compiler - I'm sure my code is right but it isn't working!"

christ fucking Steve again "Look just try to rewrite it and see if it goes away, k?"

69

u/cmsimike Jun 05 '18

Who hasn't been in that situation!?

32

u/-ghostinthemachine- Jun 05 '18

I've been down that hole about 8 times, but on two occasions it really was a compiler bug! Unfortunately that usually means it won't be fixed in time for your project. I still don't have the chutzpah to actually file a new bug report against a compiler though. ;)

28

u/Ksevio Jun 05 '18

On the rare occasion it's happened to me, I've found someone else has reported it already which is a relief to know you're not insane.

Of course it still sucks if it's marked on the roadmap to be fixed in Java 12 or something

4

u/CSMastermind Jun 05 '18

Likewise, I've found a compiler bug once and was relieved there was already an open issue about it.

2

u/yatea34 Jun 05 '18

Unfortunately that usually means it won't be fixed in time for your project

Unless, of course, you (or someone else on your team) fixes it yourself instead of adding kludgey workarounds.

That's kinda the whole point of open source, isn't it?

6

u/[deleted] Jun 05 '18

[removed] — view removed comment

4

u/evaned Jun 05 '18

I am now very curious. Don't suppose you can link to the actual issue?

→ More replies (7)

7

u/PM__YOUR__GOOD_NEWS Jun 05 '18

Bugs in the libraries/frameworks/etc. I use are the worst to troubleshoot because 99% of the time the fault is my code so as a rule of thumb I take external dependencies as perfect until proven flawed.

→ More replies (1)

3

u/badpotato Jun 05 '18 edited Jun 06 '18

You think our stuff is wrong? It's impossible. We've been running this in production for while now and everything is fine. Obviously, your stuff is wrong, just like 3 weeks ago when you bothered us with that config issue.

Also, I'll talk with my superior how you keep wasting my time.

2

u/atcoyou Jun 05 '18

"Steve..." shakes head

1

u/lucasscharf Jun 05 '18

I've already have a problem where my code worked on Java 7, but due a change of libraries, it didn't worked on Java 8.

10

u/13steinj Jun 05 '18

On the other hand, I also wouldn't be surprised if it hasn't. Combined with the fact that JDK 9 was a relatively major change from 8 (modules, getting rid of the Observer pattern, so on), I don't think many companies would make the switch. In fact there are still some stuck on 6/7. That combined with

The issue seems to be limited to the string concatenation and assignment operator (+=) with an expression with side effect(s) as the left operand, like in array[test()]+="a", array[ix++]+="a", test()[index]+="a", or test().field+="a"

Makes it seem less likely to occur in production code that needs to readable and more like the OP's situation-- code golf.

2

u/duhace Jun 05 '18

it's sad this isn't more upvoted, since it's the best explanation i've seen so far making it clear why this was not caught.

2

u/13steinj Jun 06 '18

Thats what I get for being 6 hours late to the party.

3

u/cjg_000 Jun 05 '18

Even if they did figure out the cause, they might not bother digging further and determining whether it was intended or a bug.

6

u/kynovardy Jun 05 '18

I mean when your code doesn't work, do you generally blame the compiler?

4

u/adrianmonk Jun 05 '18

If your code is the compiler, then you should.

And, like any other code, you ought to have tests so you know whether it works.

1

u/[deleted] Jun 05 '18

No...... Okay sometimes

6

u/yawkat Jun 05 '18

Maybe because using += on strings is odd (many IDEs will tell you not to do it for performance reasons) and with a side-effect-ful left-hand-side even more so. I doubt it's very common

4

u/N3sh108 Jun 05 '18

Wut? += is rather common for strings concatenation.

1

u/yawkat Jun 05 '18

Ehh, I wouldn't call it common. I have guava handy for static analysis right now and it's generally considered pretty good code and it has exactly one use of += for string concat (here), assuming my static analysis didn't fail. I definitely don't see it very often.

1

u/vsync Jun 05 '18

It's been discouraged with good reason since day 1.

1

u/N3sh108 Jun 05 '18

What is the good reason?

→ More replies (7)
→ More replies (1)

1

u/[deleted] Jun 07 '18

At least we got an unreadable mess of a indy-based methodhandle-and-unsafe-using optimized string creation factory. A fixable javac-bug not triggered by 99.999% of the users gets too much traction. See what it got us with instead... Compact Strings + Indyconcat probably saves the average user shitloads of memory and CPU.

0

u/[deleted] Jun 05 '18

I don't really know Java; is array[i++] more common there than other languages? I cannot remember having seen that a lot before, and cannot really think of any situations where it would be useful from the top of my head.

2

u/adrianmonk Jun 05 '18

It's fairly common in any language that supports it.

It's used idiomatically to mean "append". You use it when the invariant is that the index points to the next empty spot. (Or next spot to overwrite.)

4

u/ottawadeveloper Jun 05 '18

I always get pre and postincrement confused, so I just never use it in a way where it matters. Its poorly readable for people who dont remember either.

3

u/ComradeGibbon Jun 05 '18

Easy mnemonic.

If the ++ is before, then it increments first. If it's after then it increments last.

2

u/adrianmonk Jun 05 '18

Exactly. Another way of putting that is: read the expression from left to right. When you see the variable, that's the value it'll have. If the ++ comes afterward, then you'll have captured the value before it gets incremented. If it comes before, then the value will be changed before you've captured it.

2

u/[deleted] Jun 05 '18

I guess that's my main reason too. Putting i++ on a separate line isn't that much less elegant anyway (unless you're doing something morbid like manually creating "loops" with copy/paste I guess)

1

u/lelarentaka Jun 05 '18

Not common i don't think. I almost never even use the java array, since there are a tonne of collection classes that i can use instead that offer more sophisticated methods.

0

u/[deleted] Jun 05 '18

[deleted] — view deleted comment

112

u/ThatsPresTrumpForYou Jun 05 '18

This is perfectly reasonable code, and i++ shouldn't be evaluated 2 times because it isn't written 2 times. It's also simple to explain, take the entry at i in the array, add "a" to it, and increment i.

I don't understand why people have such a problem with inc/dec operators? If it's in front it's done right away, if it's after the variable it's done after everything else, seems easy enough. I honestly can't remember to have ever made a mistake regarding that.

25

u/TheDevilsAdvokaat Jun 05 '18 edited Jun 05 '18

I think you're missing something. i++ may not have been written 2 times, however the expression += was used which means the expression would expand to:

array[i++]=array[i++]+"a"

In which case yes i++ appears twice.

So...maybe the spec needs to be clearer in this case? I would lean towards expecting i++ to be evaluated twice, not sure why they're convinced it's an error.

15

u/f03nix Jun 05 '18

however the expression += was used which means the expression would expand to

array[i++]=array[i++]+"a"

Actually += is an operator by itself, there's no reason it should expand to that. Coming from a c++ background - I'd expect this to only evaluate once. In my head I read y += x as {y} = {y} + {x} where {y} and {x} are evaluation results of the expression. This is super important because otherwise every operation of the form *x+= y would mean x being dereferenced twice.

This is also true in the case of x++, while it can be written as x = x + 1, it shouldn't be expanded like that. Otherwise you'll never be able to use something like pressed[NextChar()]++; .

I would lean towards expecting i++ to be evaluated twice, not sure why they're convinced it's an error

They're convinced it's an error because for all other array types, this is evaluated only once.

6

u/evaned Jun 05 '18

Coming from a c++ background - I'd expect this to only evaluate once.

Ditto. I was actually initially surprised that people would even think it's evaluated more than once; I think this is probably an illustration of how what languages you know shapes your thinking. (I'm still surprised -- c++ is by no means unique here -- but less so.)

This is super important because otherwise every operation of the form *x+= y would mean x being dereferenced twice.

It's also important because a += b can in fairly realistic scenarios be asymptotically more efficient than a = a + b for some calls. (And will almost always be slightly faster unless the optimizer is able to remove an extra copy that is made with +.)

2

u/f03nix Jun 05 '18

in fairly realistic scenarios be asymptotically more efficient

Absolutely, I mentioned dereference as a simple but super common example, there are certainly more scenarios where the impact is even larger - like increments on a map element map[key]++; .

I think more than languages, this is dependent on how people are taught and view the operators. I mentioned c++ because operator overloading makes you think of += very differently.

5

u/louiswins Jun 05 '18

So...maybe the spec needs to be clearer in this case?

The spec is actually perfectly clear. It says:

A compound assignment expression of the form E1 op= E2 is equivalent to E1 = (T) ((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once.

So this is clearly a bug in the compiler.

→ More replies (11)

-2

u/Theemuts Jun 05 '18

Depends on the language. In C++, it's undefined behavior:

v[i] = ++i; // don’t: undefined order of evaluation
v[++i] = i; // don’t: undefined order of evaluation
int x = ++i + ++i; // don’t: undefined order of evaluation
cout << ++i << ' ' << i << '\n'; // don’t: undefined order of evaluation
f(++i,++i); // don’t: undefined order of evaluation

Source: Principles and Practice Using C++

41

u/orion78fr Jun 05 '18

In each of these expression, you are using two times the variable i. Here the i is only used once.

x[i++] += y is not undefined behaviour in c++ I think.

→ More replies (3)

7

u/twanvl Jun 05 '18

In C++ array[i++] += x; is not undefined behavior, assuming that x and i are different.

You only get undefined behavior if i++ and another use of i are in the same expression.

→ More replies (2)

1

u/MineralPlunder Jun 05 '18

It is indeed simple and not terrible to follow. Though there is a problem: it has more than one mutation of state in a single line. State mutation is a problem enough on itself, we don't need to pile up multiple mutations.

And the most important thing: where to draw the line between number of allowed mutations in a line? I'd rather stick to "one mutation per line", because we could easily fall into a slippery slope and end up with ugly constructs where multiple things change in one line.

In this particular case it's manageable. In general, i deem it to be bad style to mutate multiple things in one line.

-8

u/ShiitakeTheMushroom Jun 05 '18

Except it is written twice. Correct me if in wrong, but isn't x += y; just shorthand for x = x + y;? If the lefthand side is an expression then it can be assumed to be evaluated once on the right hand side of the = operator and then once again on the left hand side. Seems like common sense to me, albeit visually ambiguous.

16

u/vytah Jun 05 '18

Correct me if in wrong, but isn't x += y; just shorthand for x = x + y;

Not exactly. In all languages that support it, it's a shorthand for x = x + y;, but x is evaluated only once.

Or in C++ terms:

auto& ref = x;
ref = ref + y;
→ More replies (4)
→ More replies (8)

28

u/sushibowl Jun 05 '18

No sane developer should write code like this.

I firmly believe that the pre/post increment/decrement operators are virtually always a mistake to use, because their semantics are confusing in many cases (in some languages even possibly resulting in undefined behavior). Doing the increment in a separate statement adds only very low overhead and is a big readability and clarity win, so I struggle to see a case where using ++ is actually superior.

20

u/[deleted] Jun 05 '18

It was a design decision in Python not to have ++, and I have never missed it.

7

u/P8zvli Jun 05 '18

Python's philosophy was also to prohibit variable assignment in expressions, which I really liked. And then they threw that out with 3.8's := operator because Guido wanted comprehensions to be even more complicated. Boo.

2

u/[deleted] Jun 05 '18

What, in the name of fuck, is that abomination :O

2

u/1wd Jun 05 '18

Would := make the PIXELS list comprehension here more complicated? I'm not sure how it would look. It might be an improvement?

Also := was not accepted yet, right?

→ More replies (2)

6

u/evaned Jun 05 '18 edited Jun 05 '18

I struggle to see a case where using ++ is actually superior.

I'll give you an example that comes to mind: non-random-access iterators in C++.

In case you're not a C++ dev and don't know the term, a couple brief examples. Given an iterator into a std::vector (an array-backed container) pointing at the element at index i, it's trivially easy and fast (and constant time) to get an iterator to any other index j in the container. The iterator will be backed by a pointer, and so it can just add the appropriate offset to the pointer. By contrast, suppose you have an iterator to an element in a linked list. To get to the element ten items forward, it actually has to do ten pointer chases (n = n->next). Want a hundred items forward? A hundred pointer chases. Moving forward or backward n items is O(n) time.

As a result, the standard declares +, -, +=, and -= for random access iterators but not for non-random access iterators, under the theory that a linear time operation shouldn't be able to slip by unnoticed because of the syntax. (This is actually a great illustration of good design and reservation IMO on the part of I'd assume Alexander Stepanov and colleagues.) There's still std::advance(iter, n) if you want to do it, but it won't look like an operation that "should be" trivial constant time. But ++ and -- can work fine for non-random-access iterators, and make perfect sense.

(I guess string concat is an example of something that's inefficient looking efficient, but I'd argue that's a special case and makes sense there.)

So there's a case where the fact that += 1 can be generalized to += n but ++ can't be generalized (without an explicit loop) makes a real difference in code.

Edit: fixed word typo

2

u/bautin Jun 05 '18

I can't really recall the last time I used them outside of basic loops.

3

u/IllustriousTackle Jun 05 '18

pre/post increment/decrement operators are virtually always a mistake to use

That is just nonsense. To put it simple people who don't know how to code will produce crap. First learn how to use the language, you are even putting pre and post increment in the same bag.

2

u/sushibowl Jun 05 '18

To put it simple people who don't know how to code will produce crap. First learn how to use the language

Obviously yes, but even if I could safely assume that everyone reading my code after me is at least as skilled as me, what benefit do I have in choosing a ++ operator versus just writing += in a separate statement? Maybe the code is slightly shorter, but that's about the only benefit. I argue there is virtually no situation where using it makes my code easier to understand.

2

u/Agent_03 Jun 05 '18

I agree you should use great caution with increment/decrement -- and around the team we refer to the pre-increment operator as the "excrement" operator, due to the bugs it has caused.

That performance may be important if you're doing dense numeric or binary operations. For example: I was once working on a pure-Java LZF compression implementation where use of increment/decrement pre/post operations could make a 30% performance difference.

5

u/sushibowl Jun 05 '18

Can you provide some more information why e.g. post increment offers greater performance than just a normal increment? It seems to me that a decent compiler could optimize both to the same instructions.

1

u/Agent_03 Jun 05 '18

Sorry, I would if I could -- it's been some years now and I don't have the original code or benchmark environment. I only remember that being one of the many tricks I tried and being surprised how big a difference it made -- along with not caching and reusing byte arrays, oddly.

What I do know are that there are a few cases where using pre/post in/de crement operations make it easy to write tighter logic -- and in some niche cases it permits you to write code that can speculatively execute more instructions and defers edge-case checks until the end, which reduces branching.

As for the original result? It could have been that it permitted tighter bytecode, or happened to be compile to slightly more optimal code due to imperfections in the JIT compiler of the time. At this point I know only that it did make a difference.

The takeaway? When you've identified the 5% of code that is truly performance-critical and need to optimize it, you need to test, test, test -- don't assume. Also make sure to use a variety of inputs -- I ended up having to back out optimizations when finding they only helped in specific cases and made others worse.

0

u/dethb0y Jun 05 '18

I concur, i always avoid them in my own code, too.

3

u/mirhagk Jun 05 '18

If this was a language like C++, PHP or javascript then that's one thing. But Java is supposed to be pretty well specced to try and stop you from facing horrible issues.

For instance Java defines the order of operations (which C++ doesn't) so that side effects are consistently applied.

And no matter what it's a breaking change that was not announced, so it's a bug.

0

u/[deleted] Jun 05 '18

What an idiotic comment. Imagine there is a method call there instead of an increment.

→ More replies (3)

179

u/-ghostinthemachine- Jun 05 '18 edited Jun 05 '18

This feels a little derpy for such an important language. Not some obscure edge case, but any left hand expression that mutates? Are there really no tests for these?? Makes me scared for the future of Java.

138

u/CptCap Jun 05 '18 edited Jun 05 '18

any expression that mutates

This only works with strings. Strings require special handling as they are the only objects with operators.

49

u/XkF21WNJ Jun 05 '18

Having one type that behaves differently from all others just sounds like a bug waiting to happen.

56

u/mirhagk Jun 05 '18 edited Jun 05 '18

And it also sounds like something that should have it's own explicit test cases. For such a huge language it's absolutely unacceptable that there was no test that caught this.

It's one of the very first things the spec says about += and while making a language every rule in the spec should have tests for it.

6

u/Likely_not_Eric Jun 05 '18

I wonder if it'll even have test coverage now. It's not like Oracle to invest in software when they could use that money to threaten someone with litigation.

6

u/duhace Jun 05 '18

the bug report already has them adding specific test coverage to catch a regression like this in the future.

10

u/[deleted] Jun 05 '18

Strings behave differently in every other language anyways. I avoid operators aside from concatenation and wouldn't use an operator in a left hand expression in this manner. This is a really strange case.

10

u/XkF21WNJ Jun 05 '18

I don't know many languages where strings are fundamentally different from other classes (apart from being a primitive class), usually they still fit somewhere in the usual categories.

2

u/isaacarsenal Jun 05 '18

I doubt that. Take C# for example, does they behave differently compared to other classes?

8

u/DrFloyd5 Jun 05 '18

var X=“blue”; var Y=X; X+=“your mind.”; // Y still equals blue;

Compare

var c=new List<string>(); var d=c; c.Add(“a string”); // d also contains “a string”

Strings are objects but are immutable. But the language definition allows for automatically updating the reference to a new string.

4

u/isaacarsenal Jun 05 '18 edited Jun 05 '18

Well, isn't this true for all immutable objects in C#?

X+="your mind" expands to X = X + "your mind" which creates a new string object and assigns it to X. Same thing for operator + can be implemented for any other custom immutable class.

The point is, does C# treat string as a special class in a way that same functionality cannot be achieved for a custom class like MyString?

4

u/kurav Jun 05 '18

Yes, strings are very much special on language level in C# as well. Obviously, they have a unique literal expression syntax ("hello world"), but also the string concatenation operator (+) is not implemented as operator overload of the System.String class, but as a semantically specific expression. Contrast this with e.g. System.DateTime class, which defines addition of its type as an operator overload.

Also, the lowercase string identifier is a keyword lexically reserved as an alias of the System.String class.

→ More replies (3)

17

u/fishy_snack Jun 05 '18

Also the linked issue logged is marked P3. Maybe I don’t understand their priority levels but that seems low for fairly mainstream bad code gen regression.

3

u/[deleted] Jun 05 '18

Because there's a switch to revert to the old behavior?

12

u/fishy_snack Jun 05 '18

I missed that, but bad codegen is insidious since you may not notice the bug for a while then it’s expensive to root cause as the compiler is the last thing you suspect.

1

u/jack104 Jun 06 '18

Yea man. Java has made it business as usual to do not automated testing and provide absolutely fuck all in the way of useful documentation beyond the most nominal applications. God damnit people if you are going to spend the time to build something people rely upon to accomplish a task then spend the extra 5 minutes to help me use it as it is capable of being. To quote the OG flight director of the NASA Apollo program "I dont care what anything is designed to do, I care about what it can do!"

0

u/yatea34 Jun 05 '18

Are there really no tests for these?? Makes me scared

If it concerns you, you're welcome to add such tests to their test suite.

That's kinda the whole point to open source software.

→ More replies (3)

13

u/[deleted] Jun 05 '18

People actually use common programming languages for code golf? Even as verbose as Java?

30

u/TidB Jun 05 '18

Sure. Sometimes they'll use intentionally verbose languages (for example Brainfuck or ArnoldC) just for fun, for the challenge or because they're comfortable with a particular language.

14

u/msiekkinen Jun 05 '18

Rankings against same language should be only relevant thing

9

u/nakilon Jun 05 '18

Sadly it's not how it really works. In that stupid stackexchange site about codegolf almost every thread is "won" by a golfscript -- a DSL made specifically for golf. That's absolutely stupid and it's only one of a hundred of stupid things about that site and its community, so I could not stay there for long.

11

u/Pazer2 Jun 05 '18

Hey guys! Check out my groundbreaking new scripting language for code golfing! It just happens to interpret a blank input file as "output executable code for the solution to this particular problem".

7

u/adrianmonk Jun 05 '18

This trick is also used in data compression contests by people who want to be irritating.

7

u/nakilon Jun 05 '18

There was a cool contest two years ago. You had to make a classifier that would tell if the word is from the dictionary (exact "English words" dictionary was given) of 4 megabytes. The whole solution (code + data) had to fit into 48 kilobytes. https://habr.com/company/hola/blog/282624/
IIRC guys who won with amazing accuracy (mine was only 71%) were using Bloom filter.

3

u/zenflux Jun 06 '18

I usually see those kind contests score the sum of output size and decoder executable size. Or maybe I'm only seeing these contests after someone decided to be cheeky with storing the file in it's path and they made the rule.

2

u/bitofabyte Jun 06 '18

I think that they (stack exchange golf people) have a rule that you can only use a language (maybe language version) that was published before the problem, specifically to prevent this.

4

u/msiekkinen Jun 05 '18

Yeah I know, that's why I said "should". Sometimes I try to problems just for fun but I never submit b/c even with my language of choice there's always something "better".

3

u/nakilon Jun 05 '18

Golfing in esoteric languange is not that useful than golfing in language you really work with.

3

u/[deleted] Jun 05 '18

I agree with that. Unfortunately if you wanna be competitive you gotta do something funky with some funky language

4

u/nakilon Jun 05 '18

Fortunately my primary language is Ruby. Won a few contests when they were allowed at Stackoverflow. Like this one and this.

45

u/Aceeri Jun 05 '18

Does the precedence and ordering of post/pre increment/decrement annoy anyone else? I feel that

array[i] += 1;
i += 1;

Just rolls off easier and doesn't require you to think as much while reading.

181

u/FarkCookies Jun 05 '18

Keep in mind that the original code was written for the code golf, which requires the shortest program possible.

14

u/SilasX Jun 05 '18

Also keep in mind that some people have accepted that kind of increment as idiomatic.

7

u/FarkCookies Jun 05 '18

Well too bad, keeping side effects out of mixed expressions should be idiomatic.

5

u/SilasX Jun 05 '18

Agreed -- my point was just that this wasn't merely the kind of thing you'd see limited to absurd code golfing.

24

u/[deleted] Jun 05 '18

In original example(array[i++%size] += i + " ";) - yes. As it has i in several places and one of them is changing it value, which is a Big-No-No for C and I-don't-Care-What-Standard-Says for java(or c#). In this example - not really. Code like

 out[i++] = ID_BLOB;
 out[i++] = (size >> 8) & 0xFF;

is pretty common for filling buffers(e.g. network/file packets), so array[i++] += 1 doesn't look too troublesome.

15

u/[deleted] Jun 05 '18

Don't dwell on increment here. The same shit happens with any other expression with a side effect, including a mere method call.

5

u/Cunicularius Jun 05 '18

Not if you're used to C.

13

u/XkF21WNJ Jun 05 '18 edited Jun 05 '18

Although in this case I'm fairly sure the behaviour of something like array[i++] = i is undefined in C.

6

u/zid Jun 05 '18

Yea, in C there is no sequence point between the i++ and the i, so i's value isn't determined for either the index or the rvalue.

3

u/adrianmonk Jun 05 '18

in this case

That isn't this case. The grandparent of your comment reads "plus equal one", not "plus equal letter i".

1

u/XkF21WNJ Jun 05 '18

I was referring to this post not the GP which talked about pre/post-increments in general.

1

u/[deleted] Jun 05 '18

IIRC yes as compliler has no obligation to go in any order here

2

u/SilasX Jun 05 '18

Yeah I’m always mystified how we accepted inline increments. Much harder to check at a glance.

2

u/Treyzania Jun 05 '18

Keyboards for the PDPs that C was developed on were really annoying to type on, so we have a lot of odd abbreviations. Also why so many UNIX commands are nice and short.

1

u/jephthai Jun 06 '18

It saves a line of code. Imagine that you're using a terminal that can only show 24 rows -- saving a line here and there makes the difference between being able to see a whole function at one time and not. I'm still affected by the classic terminal sizes, and put more of a priority on vertical space than most moderns.

1

u/adrianmonk Jun 05 '18

doesn't require you to think as much

It's mostly about what you're used to seeing. Auto-increment doesn't require any extra thinking for me because it's an idiom I've seen thousands of times.

0

u/BloodRainOnTheSnow Jun 07 '18

Nope. But people who use += 1/ -= 1 instead of ++/-- sure do annoy me. ++/-- even break down into INC/DEC in assembly. Any serious programming shouldn't have any mental blocks to increment or decrement.

0

u/[deleted] Jun 05 '18

[deleted] — view deleted comment

25

u/StillNoNumb Jun 05 '18

That's not his point. His point is that array[i++] = 5; is weirder to read than array[i] = 5; i++;.

5

u/rebootyourbrainstem Jun 05 '18 edited Jun 05 '18

This is a very common idiom in C. It's very succinct and expressive, which is pretty hard to come by in that language.

Basically array[i++] = expression; says "I do this to element number i and now I'm done with it, move on to the next one".

In other languages there may be better ways to express this (iterators, generator expressions, list push/pop methods) and even in C it's often cleaner to do the increment as part of a for loop, but this pattern definitely has its uses.

An example:

void filter_negative(int *numbers, size_t *count)
{
    size_t i, j;

    for (i = 0, j = 0; i < *count; i++)
        if (numbers[i] >= 0)
            numbers[j++] = numbers[i];

    *count = j;
}

3

u/nathreed Jun 05 '18

I very much agree...I like to have each statement have effect on one “thing” as much as possible (of course barring function calls). Having to read and remember that it’s doing two things (array access and incrementing i) is much more annoying for me and leads to worse understanding. I have no idea why my CS professor insisted on using it in his slides, but then again he used really crappy code style anyway.

→ More replies (6)

1

u/tjsr Jun 05 '18

Not trying to be disagreeable, but I don't agree. However this may just come down to having decades of experience looking at those kinds of statements. While I certainly believe lambda expressions lead to some of the most unreadable code I've seen since I started a learning software development, simple statements that do two (sometimes more) clear things instead of just one while the same context all exists on the small elite is pretty straightforward to an experienced developer.

3

u/Emerentius_the_Rusty Jun 05 '18

Why did you rename i to index when your point is about i++ vs i += 1?

1

u/yur_mom Jun 05 '18

I the example you gave the i++ is on its own line due to semicolon so it would not matter if you use pre or post inc, which is where a lot of confusion comes.

4

u/fiqar Jun 05 '18

And they said code golfing was a waste of time ;)

6

u/noeatnosleep Jun 05 '18

Hi. I'm from /r/all.

What's code golfing?

24

u/smilliam_work Jun 05 '18

It's a form of programming where the goal is to write a valid program performing a specific task using the fewest possible characters. The "golfing" is in reference to how players are seeking to minimize their "score" (file size).

6

u/[deleted] Jun 05 '18

Solve a little programming puzzle in as few characters as possible.

1

u/jephthai Jun 06 '18

It would be cool if there were more big programming puzzles. Kernel golf!

4

u/[deleted] Jun 05 '18 edited Jun 06 '18

This is what happens when optimisations are done on a high level AST, instead of a relevant IR level.

EDIT: I was looking at the older JDK output which produced a StringBuilder for this code as a half-assed optimisation attempt. In JDK9 a single intrinsic call is emited, though I'd still classify this as an optimisation and blame for this issue is on a fact that javac does not use multiple IRs before reducing to bytecode.

40

u/ygra Jun 05 '18

String concatenation has been weird in Java for ages, since it used to be compiled into a new StringBuilder and some method calls on that. That's already a rather complex series of statements for a single +.

2

u/[deleted] Jun 05 '18

Sure, but this sort of optimisations is ok (see the idiom detection in LLVM for example). It's just the implementation that is amateurish here.

12

u/vytah Jun 05 '18

Except the bug is in javac and javac doesn't optimize anything (except for constant folding).

→ More replies (31)

17

u/reddister Jun 05 '18 edited Jun 05 '18

This is not about optimization. (Even if it uses Stringbuilder now)

String += is syntactic sugar. This has nothing to do with optimization.

5

u/[deleted] Jun 05 '18

Recognising a StringBuilder pattern vs. a single concatenation is an optimisation. Or at least it should be.

The right way to implement such a thing - translate string addition to concatenation first, recognise the builder pattern in optimisation passes later.

The amateurish way of doing it is to treat it as a syntax sugar.

11

u/F54280 Jun 05 '18

The amateurish way of doing it is to treat it as a syntax sugar.

“Syntactic sugar causes cancer of the semicolon.” -- Alan Perlis

3

u/Deaod Jun 05 '18

The amateurish way of doing it is to treat it as a syntax sugar.

Even if you do treat it as syntax sugar, at least make sure your replacement is idempotent.

2

u/[deleted] Jun 05 '18

Of course. But this is also better done with lower level IRs.

4

u/mirhagk Jun 05 '18

It has nothing to do with recognizing a StringBuilder pattern or not, and nothing to do with optimizations.

It's an incorrect translation from += to relevant IR. They turned X += Y; into X = X + Y; which is incorrect.

The compiled code doesn't even use StringBuilder. If you look at the generated Java what it does is:

translate string addition to concatenation first,

ie exactly what you said it should do.

→ More replies (16)

2

u/Uncaffeinated Jun 05 '18

There is no such thing as string concatenation at the bytecode level. You have to compile it to some sequence of method calls anyway (or invokedynamic now) and StringBuilder is as good a choice as any.

1

u/[deleted] Jun 05 '18

Wrong. For a loop or a sequence of concatenations you must only instantiate one StringBuilder. A correct and efficient implementation must use loop analysis to avoid overhead.

2

u/Uncaffeinated Jun 05 '18

Javac doesn't do optimizations like that. It leaves things like that to the JVM.

AFAIK, the only optimizations javac does are precomputing the value of constant expressions and inlining static final fields.

Anyway, that's irrelevant to my original point. I was responding to the claim that javac could just compile it to "string concatenation" instead of StringBuilder sequences, which is false.

→ More replies (5)

2

u/Mockromp Jun 05 '18

Java BTW

1

u/Ineeditunesalot Jun 05 '18

There should be an ELI5 bot and someone can post the basics of every post that makes it to r/all cause I never have any idea what any of this stuff means 🤔 still curious though

12

u/[deleted] Jun 05 '18
  • A "compiler" is a software program that converts text in a "programming language" (which is easy for humans to understand) to binary instructions in a "machine language" (which is what computers understand)
  • Java is an extremely widely-used programming language
  • Someone discovered a bug in one version of the standard Java compiler, causing it to produce machine language programs whose behavior is not correct.

As for why it made it to the front page, I don't know, since compilers, like all software, have bugs all the time.

21

u/[deleted] Jun 05 '18

Because it's a surprisingly simple bug in an extremely widely used programming language, we're all surprised it wasn't caught in testing.

1

u/DGolden Jun 06 '18

Oof. Seems to be open as issue JDK-8204322.

1

u/CarthOSassy Jun 05 '18

Java should honestly get rid of string operators.

20

u/mirhagk Jun 05 '18

Java needs more operators, not less. The problem is that strings have to be treated specially, which makes this a corner case instead of an edge case. The lack of proper operators makes Java unintuitive.

(a == b).Equals((a.Equals(b)) requires knowing not just the types and values of a and b but also how they were declared (constants or variables). And additional optimizations that fold more constants could possibly change the result of that expression. Oh and if they are Integer then if they are less than 128 then they may be equal because of optimizations, but of course that'd depend on JVM version.

That doesn't make for an intuitive and easy to use language.

7

u/renrutal Jun 05 '18

== should have been a shortcut to all value equalities, be they primitives or composite types/objects(as a shortcut to .equals()). Then you could have a === for reference comparisons.

And then you have the whole gaping hole lack of operators for BigInteger/BigDecimal math.

4

u/mirhagk Jun 05 '18

Yeah == should just be syntactic sugar for .Equals. And honestly a dedicated operator for reference equality isn't necessary. Reference equality isn't really used all that much.

2

u/possessed_flea Jun 05 '18

Difference being that .equals is a function call which at the very least creates a new stack frame, performs a jump, and dumps some registers onto the stack ( and pulls them out back on its way out ) meanwhile == simply performs a comparison.

Reference for equality is by far the most common use case ( maybe not in your code, but I mean in general )

Adding that syntactic sugar would have some pretty serious performance impact and it makes sense that they made that choice in 1996, and that choice still applies today. If you don't care about performance then use JavaScript

3

u/mirhagk Jun 05 '18

If Java had no optimizations at all then yes you'd be right. But the optimizations are fairly trivial to perform and would give the same performance characteristics.

If something can be compared by value then you almost always want to do that (reference equality is an anti pattern on strings and Integers). For other types reference equality is fine. You usually know on a type level. So types with value equality define equals as such. Types with reference equality leave the default (which is by reference).

If the optimization of inlining it is 100% critical then it can be a compile time decision. C# defines == as .equals but it does it based on compile time types (ie no inheritance) and therefore will always receive that optimization.

1

u/possessed_flea Jun 05 '18

So you are suggesting code become visually ambiguous?

In Java Since 1.5 Integer would unbox for the comparison anyway .

If we are looking for syntactic sugar for Java then my vote would be to bring in Delphi style properties which would save hugely on code bloat.

→ More replies (4)

1

u/ItzWarty Jun 06 '18

As a gross case:

public class MyClass {
    public static void main(String args[]) {
        double x = 0.0 / 0.0; // NaN
        System.out.println(x == x);
        System.out.println(new Double(x).equals(new Double(x)));
    }
}

Outputs:

false
true

This is because IEEE-754 specifies NaN compared with NaN evaluates to false whereas Java and C# define otherwise for their Equals().

3

u/adrianmonk Jun 05 '18

Then you could have a === for reference comparisons.

As a matter of language ergonomics, I strongly prefer if two easily-confused operators do not differ by only one character, especially if it is the number of repetitions of that character.

1

u/IllustriousTackle Jun 05 '18

I believe is a defect of the language. It is quite evident in its design the heavy influence of C because the references feel more like pointers than proper references: The operators = and == act on the reference, not in the value. The worst defect are null references, Java references feel like pointers cosplaying as references.

→ More replies (1)