Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)






  • 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.

    :trollface:

    :trollface:, :trolleybus:



  • That's a huge pixel.



  • @Buddy said:

    https://twitter.com/dgryski/status/570256114803212290

    :trollface:, :trolleybus:

    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.

    This one is a link to the other one. It's not a library. It's just a link.

    This one looks like a straight port of a Java library, so it's already fucked before it starts.

    This one doesn't support timsort. It says it might in the future, but it doesn't support timsort.



  • @ben_lubar said:

    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 :wtf: Java is and has always been.



  • Things I hate: Sites where middle click doesn't open the link in a new tab.


  • :belt_onion:

    In 10 years no one will middle-click, this thing is built FOR THE FEWCHUR.


  • sockdevs

    it may not have generated a notification, but... :smiley:
    i like it!

    @accalia­s

    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.sort seems 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?



  • @powerlord said:

    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.


  • sockdevs

    @IngenieurLogiciel said:

    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.



  • @JazzyJosh said:

    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):

    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.


  • sockdevs

    @accalia said:

    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.

    :wtf:

    Times like these I'm glad I don't Java :laughing:

    <!-- Emoji'd by MobileEmoji 0.2.0-->


  • @RaceProUK said:

    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#.


  • Winner of the 2016 Presidential Election

    @RaceProUK said:

    That's how I summoned @Kuro in the Discopædia

    And I thought you were just &shy; to talk to me

    Filed Under: oh well



  • @IngenieurLogiciel said:

    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:

    \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%



  • @blakeyrat said:

    What am I going to bitch about now!?

    I'm sure you'll find something. It doesn't normally seem to be a problem :laughing:

    Oh... there we go...

    @blakeyrat said:

    Windows does not have and has never had a concept of a "user home directory"

    Clearly not.


  • sockdevs

    @blakeyrat said:

    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's C:\Users\[username]

    <!-- Emoji'd by MobileEmoji 0.2.0-->


  • 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.



  • @JazzyJosh said:

    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.


  • sockdevs

    @blakeyrat said:

    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 :wtf:

    <!-- Emoji'd by MobileEmoji 0.2.0-->


  • @blakeyrat said:

    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.



  • @RaceProUK said:

    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.

    @loopback0 said:

    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.

    @loopback0 said:

    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?

    @loopback0 said:

    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.



  • @blakeyrat said:

    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.

    <!-- empty -->


  • @blakeyrat said:

    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?

    @blakeyrat said:

    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.


  • sockdevs

    @loopback0 said:

    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? :laughing:

    <!-- Emoji'd by MobileEmoji 0.2.0-->


  • @loopback0 said:

    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



  • @loopback0 said:

    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.

    @loopback0 said:

    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.



  • @RaceProUK said:

    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.



  • @loopback0 said:

    Even when, like OneDrive, it's written by the people to also wrote the OS?

    Do I have to post that comic again?



  • @blakeyrat said:

    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.



  • @anonymous234 said:

    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.



  • @blakeyrat said:

    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.



  • @blakeyrat said:

    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.



  • @boomzilla said:

    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.



  • @blakeyrat said:

    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.


  • sockdevs

    @blakeyrat said:

    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.

    <!-- Emoji'd by MobileEmoji 0.2.0-->

Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.