Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)
-
(Why do neither of these onebox?)New community features for Google Chat and an update on Currents
.png)
Note: This blog post outlines upcoming changes to Google Currents for Workspace users. For information on the previous deprecation of Googl...
Representative stack trace:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 40 at java.util.TimSort.pushRun(TimSort.java:413) at java.util.TimSort.sort(TimSort.java:240) at java.util.Arrays.sort(Arrays.java:1438) at TestTimSort.main(TestTimSort.java:18)
-
https://plus.google.com/u/0/109093485030374661399/posts/aDT2bEQbMfS
(Why do neither of these onebox?)
-
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.
...
As to the reasons, why our solution has not been adopted, we can only speculate: perhaps the JDK maintainers did not bother to read our report in detail, and therefore don’t trust and understand our fix. After all, Open Java is a community effort, largely driven by volunteers with limited time.
, 
-
That's a huge pixel.
-
https://twitter.com/dgryski/status/570256114803212290
, The four packages listed on that page:
This one uses 256 as its default buffer size and also has the ability to resize its buffer, so it'll never have any problems. Also, it's apparently not used by anything, so there aren't any problems there either.
GitHub - psilva261/timsort: go implementation of timsort
go implementation of timsort. Contribute to psilva261/timsort development by creating an account on GitHub.
This one is a link to the other one. It's not a library. It's just a link.
GitHub - pgmmpk/timsort: timsort has moved to psilva261/timsort
timsort has moved to psilva261/timsort. Contribute to pgmmpk/timsort development by creating an account on GitHub.
This one looks like a straight port of a Java library, so it's already fucked before it starts.
golucene/core/util/sort.go at master · ironsweet/golucene
Go (Golang) port of Apache Lucene. Contribute to ironsweet/golucene development by creating an account on GitHub.
This one doesn't support timsort. It says it might in the future, but it doesn't support timsort.
GitHub - zephyrtronium/sort: Faster and broader sorting in Go
Faster and broader sorting in Go. Contribute to zephyrtronium/sort development by creating an account on GitHub.
-
at java.util.TimSort.sort(TimSort.java:240)
I see the problem here. It was quite the poor design decision to have a sort only for Tims. What if I have an array of Bens or @accalias? Just goes to show how much of a
Java is and has always been.
-
Things I hate: Sites where middle click doesn't open the link in a new tab.
-
In 10 years no one will middle-click, this thing is built FOR THE FEWCHUR.
-
it may not have generated a notification, but...
i like it!@accalias
huh. so ­ works to preserve mentions.
-
Not that I think this isn't happening, but the example code they're using to break Java's
Arrays.sortseems unnecessarily complicated.I mean, wasn't it @Yamikuronue who pointed out just recently that unit tests should test the smallest possible scenario in order to make sure you're actually testing what you think you're testing?
-
Not that I think this isn't happening, but the example code they're using to break Java's Arrays.sort seems unnecessarily complicated.
Considering people have been using it for decades and nobody detected the bug, it's pretty damned subtle/obscure.
-
I was intentionally trying not to summon you.
-
I was intentionally trying not to summon you.
Why? i read the entire forum anyway.
But to be on topic that is one hell of a bug. Glad we finally found it.
-
Things I hate: Sites where middle click doesn't open the link in a new tab.
The weird thing is, the links in their nav bar work properly with middle click. Did Jeff make their site or what?
-
Because reasons.
Also staying on topic, Java has many other bugs which have been around for a long time that you are more likely to encounter.
One that caused me problems recently (SO warning):
Introspector getBeanInfo on bean with generic implemented method
Good day everyone. I'm using Vaadin and got a problem with BeanItemContainer. I have a generic interface and a bean implementing that interface package ru.package.testpackage; public class SomeTe...
And it doesn't just happen with generics. Using the Introspector on any parent-child class pair may return the parent implementation of a method instead of the child, which completely breaks the reflection API.
-
huh. so works to preserve mentions.
That's how I summoned @Kuro in the Discopædia ;)
@IngenieurLogiciel said:Using the Introspector on any parent-child class pair may return the parent implementation of a method instead of the child, which completely breaks the reflection API.
Times like these I'm glad I don't Java
-
Times like these I'm glad I don't Java
I have to keep telling myself, "At least it's not PHP!" and oh how I long for the days when I waxed eloquent in C#.
-
That's how I summoned @Kuro in the Discopædia
And I thought you were just ­ to talk to me
Filed Under: oh well
-
Also staying on topic, Java has many other bugs which have been around for a long time that you are more likely to encounter.
Of course. Like this one:
http://bugs.java.com/view_bug.do?bug_id=4787931
\2002. Ensures every single Java GUI program on Windows is fucking broken-by-default, right out the gate.
There's no way to write just "2002." at the start of a line without Dipshit turning it into a list. HEY GUYZ I LOVE ME SOME MARKDOWN HUUUUURRDEEEERRRUUUUR
-
Fixed in JDK 8
-
It's a trick!
-
That's still a long time.
-
I agree
-
They even... they even used SHGetSpecialFolderLocation!? This is outrageous. What am I going to bitch about now!?
EDIT: oh wait, it's still wrong. In at least two different ways:
! * Home directory/
! *
! * We first look under a standard registry key. If that fails we
! * fall back on using a SHELL32.DLL API. If that fails we use a
! * default value.Wrong. Stupidly, they'd be more correct if they'd simply not written the Registry query.
/*! * Home directory
*
* The normal result is that for a given user name XXX:
* On multi-user NT, user.home gets set to c:\winnt\profiles\XXX.
* On multi-user Win95, user.home gets set to c:\windows\profiles\XXX.
* On single-user Win95, user.home gets set to c:\windows.
*/
{
! WCHAR *homep = getHomeFromShell32();
if (homep == NULL) {
homep = L"C:\";
}
! sprops.user_home = homep;Wrong. As we've discussed before, Windows does not have and has never had a concept of a "user home directory". That's a *nix thing.
-
>echo %USERPROFILE%
-
What am I going to bitch about now!?
I'm sure you'll find something. It doesn't normally seem to be a problem
Oh... there we go...
Windows does not have and has never had a concept of a "user home directory"
Clearly not.
-
Windows does not have and has never had a concept of a "user home directory"
Yes it does; on Vista/7/8/8.1, it'sC:\Users\[username]
-
Holy Hanzo Batman!
-
We've gone over this again and again and again and again and again. I'm sick of explaining it.
The concept of the "home" directory is only there for Windows' benefit. And its primary use is to define where new named folders get created if an application asks for them and they didn't previously exist.
NO APPLICATIONS SHOULD EVER USE THAT VALUE. NOR EVER STORE FILES THERE. OR EVEN ASK FOR IT.
And even if the value should be used by applications (and it shouldn't), querying the Registry for it instead of using the correct API is utterly wrong as well.
So Java's still buggy here.
-
Holy Hanzo Batman!
Yeah, it's like a stampede of idiot incompetent developers racing to be wrong all at once. I should have anticipated this particular idiocy.
-
And its primary use is to define where new named folders get created if an application asks for them and they didn't previously exist.
@blakeyrat said:NO APPLICATIONS SHOULD EVER USE THAT VALUE. NOR EVER STORE FILES THERE.
So… apps can create folders there, but not files?
Excuse me while I drop a phat
-
The concept of the "home" directory is only there for Windows' benefit. And its primary use is to define where new named folders get created if an application asks for them and they didn't previously exist.
NO APPLICATIONS SHOULD EVER USE THAT VALUE. NOR EVER STORE FILES THERE. OR EVEN ASK FOR IT.
Bullshit. If I want VirtualBox to save some settings specific to me why shouldn't they go under %USERPROFILE%\VirtualBox ?
-
The Win32 answer is that it should be storing those in %APPDATA%\VirtualBox AFAIK
-
Maybe but VirtualBox doesn't for the VMs, and either way, its still under the home directory.
edit: Same applies to OneDrive or DropBox. Under the home directory.
-
Every time I am forced to use Google+ (like just now when I clicked on that link) I think "I'm so glad this thing is failing despite all of Google's attempts". I want to think that they'll finally give up one day and close it after wasting millions to keep it afloat for so many years. Because fuck Google.
-
So… apps can create folders there, but not files?
The OS can. The OS is responsible for creating named folders on-demand, and uses its own permissions to do so.
Applications? There is a chance they can, but a good chance they can't. There's certainly no contract stating they can, which is one of the major reasons applications shouldn't be using that path.
Bullshit. If I want VirtualBox to save some settings specific to me why shouldn't they go under %USERPROFILE%\VirtualBox ?
You can put them where you want, I'm not your dictator and neither is Windows.
But VirtualBox shouldn't use that path by default, because there's a very good chance it'll fail on a particular Windows install. By default it should be using Documents/VirtualBox, or AppData/VirtualBox (or RoamingAppData, but we won't get into that), depending on whether the user is expected to interact with the files or not.
Maybe but VirtualBox doesn't for the VMs, and either way, its still under the home directory.
Ok? So their product is buggy. What do you want?
edit: Same applies to OneDrive or DropBox. Under the home directory.
Then those products are buggy, too.
I'm telling you how to write working, correct software for Windows. The fact that a ton of Windows software isn't correct and only works by accident (as opposed to following the OS contracts) is irrelevant.
-
The fact that OneDrive a
ton of Windows softwareMicrosoft product isn't correct and only works by accident (as opposed to following the OS contracts) is irrelevant.
-
I'm telling you how to write working, correct software for Windows. The fact that a ton of Windows software isn't correct and only works by accident
Even when, like OneDrive, it's written by the people to also wrote the OS?
By default it should be using Documents/VirtualBox
Fine, maybe, but it still needs to know where %USERPROFILE% is to work out where %USERPROFILE%\Documents is.
-
Even when, like OneDrive, it's written by the people to also wrote the OS?
The Office team doesn't follow MS's own guidelines; why would any other team?
-
Fine, maybe, but it still needs to know where %USERPROFILE% is to work out where %USERPROFILE%\Documents is.
Actually, Documents is a library for Win 7+ so there's no guarantee %USERPROFILE%/Documents is part of that library. I assume there's an API to get the folder directory.
Also Hazno'ed again
-
Even when, like OneDrive, it's written by the people to also wrote the OS?
News to me.
I thought it was written by the Office team after they absorbed the old Windows Live Mesh product. And I've said from day one that Windows Live products are shitty pieces of junk.
Fine, maybe, but it still needs to know where %USERPROFILE% is to work out where %USERPROFILE%\Documents is.
No it doesn't, and doing so would be a bug.
Documents isn't even necessarily on the same drive as %USERPROFILE%. Hell, it's not even necessarily on the same server.
If VirtualBox wants to know where Documents is, the one and only correct way of finding that is by asking the OS where Documents is. Via the API, not scrounging around in the Registry.
-
The Office team doesn't follow MS's own guidelines; why would any other team?
I like to think that you guys, instead of just using this as a cheap shot towards me, are instead starting to adopt my philosophy that almost all software is broken, buggy, trash. Because it is. This is a good example.
The only thing that keeps the software industry going, even big players like Microsoft and Adobe, is programs that work-by-accident (instead of strictly following the OS contract) and lazy-ass users who don't give a shit about software quality.
-
Even when, like OneDrive, it's written by the people to also wrote the OS?
Do I have to post that comic again?
-
No it doesn't, and doing so would be a bug.
Documents isn't even necessarily on the same drive as %USERPROFILE%. Hell, it's not even necessarily on the same server.
If VirtualBox wants to know where Documents is, the one and only correct way of finding that is by asking the OS where Documents is. Via the API, not scrounging around in the Registry.
Fair enough. Previous points retracted.
-
Do I have to post that comic again?
Apparently, because there's still idiots like Loopback out there that thinks Microsoft is based in a garage and has like 6 employees. (And therefore that the same people who make Windows make Office.) If you've ever been to Microsoft's campus, you'd realize how utterly insane and idiotic that belief is.
That's like saying, "well of course the menu music in the Playstation Vita is good, it's made by Alice in Chains. Because both the Playstation products and Alice in Chains have the Sony brand name attached to them." It's insane gibberish.
-
And therefore that the same people who make Windows make Office.
You sound like the people whom you berate when they rationalize bad software. The users don't care. They just see the Microsoft label.
-
There's no way to write just "2002." at the start of a line without Dipshit turning it into a list.
2002. Some text...
Yeah, I had to hack around MarkBbHtmlDownCode:
2002\. Some text...But at least the \ isn't visible in the end result.
-
You sound like the people whom you berate when they rationalize bad software. The users don't care. They just see the Microsoft label.
Right; I get that. What I don't get is why people don't do that with, say, Disney or Sony but do with Microsoft.
-
What I don't get is why people don't do that with, say, Disney or Sony but do with Microsoft.
I'm trying to figure out what that would mean and I'm failing. Possibly because different things are different.
-
What I don't get is why people don't do that with, say, Disney or Sony but do with Microsoft.
People do do that with Sony; I've seen plenty around the Net where people have said they'll never buy a VAIO or a PlayStation because of Sony BMG's spyware shenanigans.
