5 ms·

From the article: The reaction of the Java developer community to our report is somewhat disappointing: instead of using our fixed (and verified!) version of me

by mkesper 12y ago

From the article: The reaction of the Java developer community to our report is somewhat disappointing: instead of using our fixed (and verified!) version of mergeCollapse(), they opted to increase the allocated runLen “sufficiently”. As we showed, this is not necessary. In consequence, whoever uses java.utils.Collection.sort() is forced to over allocate space. Given the astronomical number of program runs that such a central routine is used in, this leads to a considerable waste of energy.

tveita 12y ago
It looks like the Python version that's good for 2^49 items uses 1360 bytes for this array, allocated on the stack. I wouldn't worry about an extra couple of bytes nearly as much as I would worry about changing the behaviour of a function used in an "astronomical number of program", so this looks like a pretty reasonable and conservative choice, at least for an immediate patch.
- deleted 12y ago
  [deleted]
- krick 12y ago
  Does it "change behavior"? As far as I understand, the only change is that this test wouldn't crash anymore. Which certainly is "changing the behavior", but allocating more memory is as well. If so, I don't see any reason not to use formally verified version. Not that it is really important, but quite reasonable.
xamuel 12y ago
Java: Turning "reasonable data, should fit in RAM" into "Big Data (tm)" since 1995
- collyw 12y ago
  I thought it was nodejs evangelists that did that.
  - TeMPOraL 12y ago
    Java did that with data. Node.js did it with your file system (NPM, I'm looking at you).
- fforw 12y ago
  It is widely known that every corporate developer has endless time for his work. Mundane aspects like costs of development should have no impact on our code, the pureness of which is a goal in itself.
bsdetector 12y ago
Which costs more, doubling the number of runLength comparisons or allocating more memory? Without knowing that answer it's hard to say which is the better solution (assuming more memory actually fixes the bug).
- marcosdumay 12y ago
  Exchanging memory usage for equality comparations is an almost universal no brainer. The number of comparations must increase hundreds of times for compensating doubling the memory usage... and that's just for performance, for energy savings you'll need more.
  - stingraycharles 12y ago
    Where do you base these numbers on? If it still fits inside the L1 cache, I assume that increasing the comparisons will have a relatively bigger impact?
    - marcosdumay 12y ago
      Yes, that's right. The thing is that nearly all of the times you want to order arrays that fit inside the L1 cache, neither execution time nor allocation size are a problem.
  - tedunangst 12y ago
    Sounds like the amount of memory involved is quite small. Below a certain threshold, doubling is practically free. And IIUC even over-allocating memory doesn't necessarily mean it uses all of the memory, only for the the inputs that cause the bug. The extra comparison however would be performed for all inputs.
    - rozim 12y ago
      Below what threshold though? L1 cache size? O(64 bytes), no?
muyuu 12y ago
Really symptomatic of the way the JDC works.
pron 12y ago
They fixed it. The question of whether or not it was the "proper" fix (out of the two proposed solutions) is complicated. The maximum working array length was changed from 40 (ints) to 49. The difference in this case means that even an additional cache line won't be necessary, and if it is -- only for arrays 120K long. This may have been judged to be better than adding more branches to each iteration (and the code lengthened) which will need to run no matter the input size. My guess is that they ran a JMH benchmark with each proposed fixed, and picked the better one. In either case, I doubt that makes much difference.

by mkesper 12y ago

tveita 12y ago

It looks like the Python version that's good for 2^49 items uses 1360 bytes for this array, allocated on the stack. I wouldn't worry about an extra couple of bytes nearly as much as I would worry about changing the behaviour of a function used in an "astronomical number of program", so this looks like a pretty reasonable and conservative choice, at least for an immediate patch.

deleted 12y ago
[deleted]
krick 12y ago
Does it "change behavior"? As far as I understand, the only change is that this test wouldn't crash anymore. Which certainly is "changing the behavior", but allocating more memory is as well. If so, I don't see any reason not to use formally verified version. Not that it is really important, but quite reasonable.

xamuel 12y ago

Java: Turning "reasonable data, should fit in RAM" into "Big Data (tm)" since 1995

collyw 12y ago
I thought it was nodejs evangelists that did that.
- TeMPOraL 12y ago
  Java did that with data. Node.js did it with your file system (NPM, I'm looking at you).
fforw 12y ago
It is widely known that every corporate developer has endless time for his work. Mundane aspects like costs of development should have no impact on our code, the pureness of which is a goal in itself.

bsdetector 12y ago

Which costs more, doubling the number of runLength comparisons or allocating more memory? Without knowing that answer it's hard to say which is the better solution (assuming more memory actually fixes the bug).

marcosdumay 12y ago
Exchanging memory usage for equality comparations is an almost universal no brainer. The number of comparations must increase hundreds of times for compensating doubling the memory usage... and that's just for performance, for energy savings you'll need more.
- stingraycharles 12y ago
  Where do you base these numbers on? If it still fits inside the L1 cache, I assume that increasing the comparisons will have a relatively bigger impact?
  - marcosdumay 12y ago
    Yes, that's right. The thing is that nearly all of the times you want to order arrays that fit inside the L1 cache, neither execution time nor allocation size are a problem.
- tedunangst 12y ago
  Sounds like the amount of memory involved is quite small. Below a certain threshold, doubling is practically free. And IIUC even over-allocating memory doesn't necessarily mean it uses all of the memory, only for the the inputs that cause the bug. The extra comparison however would be performed for all inputs.
  - rozim 12y ago
    Below what threshold though? L1 cache size? O(64 bytes), no?

muyuu 12y ago

Really symptomatic of the way the JDC works.

pron 12y ago

They fixed it. The question of whether or not it was the "proper" fix (out of the two proposed solutions) is complicated. The maximum working array length was changed from 40 (ints) to 49. The difference in this case means that even an additional cache line won't be necessary, and if it is -- only for arrays 120K long. This may have been judged to be better than adding more branches to each iteration (and the code lengthened) which will need to run no matter the input size. My guess is that they ran a JMH benchmark with each proposed fixed, and picked the better one. In either case, I doubt that makes much difference.