1. 29

    I don’t own any macs, but I think it is worth considering the flipside of this article - that Linux in 2019 is actually very good at hardware compatibility. I run the Wayland/wlroots window manager Sway on my laptop (a Dell XPS), and recently had cause to connect it to a Samsung TV. I expected to have to poke around with the Sway config and perhaps with drivers to get things working nicely but to my pleasant surprise, the display worked instantly as soon as I plugged it in. I am very grateful to the hard-working devs who have toiled over the subsystems which allow this sort of seamless, stress-free computing. Those of us who use libre software must be cognisant that these sorts of usability victories represent a lot of hard and often thankless work.

    1. 8

      It’s a lot of hard work by a lot of people, including the people who make hardware standards. Moving from everything connecting via serial port and needing low-level device support to things connecting over USB and HDMI has been a big step up. That isn’t a panacea, and it still represents a lot of work done by software developers to support these new hardware standards, but more of the work can be done once, and improved, instead of having to be done multiple times over. (Plus, of course, there’s also the hardware that’s simply died, like Winmodems and Zip drives. Especially Winmodems, which by-and-large never worked on Linux.)

      1. 6

        Especially Winmodems

        I had an Amiga so, not only could I not use a Winmodem, I couldn’t even use an internal modem. True external modems were often twice the price of an internal modem, and three times the price of a Winmodem…it hurt.

      2. 7

        that Linux in 2019 is actually very good at hardware compatibility.

        Within the past year:

        I bought a Lenovo IdeaPad and tried to install Linux on it. It failed with a kernel panic. The ACPI tables in the BIOS were incorrect but in a way that Windows didn’t mind. Disabling ACPI via kernel parameters got the system to boot (though obviously this was not preferable), but then the graphics card was unsupported and I got a side-by-side mirroring effect on the internal display.

        I bought an Acer laptop. Linux didn’t support the sound card.

        I bring these up not to say that Linux sucks but to say that I was genuinely surprised that these things happened. It was the first time in maybe a decade that Linux didn’t support everything out-of-the-box.

        (Except for printers. I have a PoS HP home printer that supposedly has Linux support but it’s hit or miss whether it shows up on the network, can print, will finish a print job, or print the right thing when asked. This is also not a Linux problem: printers have always sucked.)

        1. 8

          IIRC from my conversations with FreeBSD kernel devs: Microsoft has a broken implementation of ACPI, and hardware manufacturers cater to that. Open source projects implement ACPI as defined by the spec, but then run into bugs.

        2. 6

          I had the same experience with the same setup (Sway + XPS), everything worked out of the box with the Dell Adapter and HDMI. Very smooth experience!

          1. 3

            I built a plex server earlier this year and got some sort of no-name chinese 7” LCD display so I could avoid having to SSH into it all the time if I wanted to do some small tasks. I plugged it in, it worked. The same thing happened with a knockoff TV I have for my guest room that I initially was using with it. I remember fighting with linux distros for weeks at a time over the dumbest issues when I first got into it (late 90s), but it’s so streamlined now.

          1. 43

            I would guess that a very substantial proportion of the people who read Lobsters have heard of Timsort.

            1. 22

              That, and TimSort really only makes sense in certain situations:

              • Comparisons have to be extremely expensive. Think dynamic dispatch. This is because TimSort itself performs a bunch of branches and integer comparisons to keep track of galloping scores and the stack invariant.

              • You need a stable sort. If you don’t need a stable sort, pattern defeating quicksort will probably do better.

              1. 11

                Quicksort is the Achilles of sorting algorithms: unbeatably fast, easy to implement, in-place; but with the vulnerable heel of bad worst-case performance (the worst case being pre-sorted data in the naïve implementation) and instability.

                1. 5

                  There’s a fairly easy fix to that, called introsort: start with quicksort, but bail out to a guaranteed O(n log n) sort like heapsort if it takes too long. In the bail-out case, you lose constant-factor performance compared to if you had used heapsort in the first place, but you avoid quicksort’s O(n^2) worst case, while still getting its good performance in non-pathological cases. It’s used in practice in .NET and some C++ STL implementations.

                  1. 3

                    Quicksort -> Heapsort is method I used. It worked fine in practice. I love solutions like that. Another, unrelated one was sklogic’s trick of using a fast, dumb parser first to see if it’s correct. If it wasn’t, he switched to one that made error messages easier.

                    I bet there’s more of this stuff waiting to be found for situations where people are shoving every case into one algorithm.

                2. 4

                  Comparisons have to be extremely expensive. Think dynamic dispatch.

                  That explains why Python uses it as it’s standard sort.

                  1. 9

                    Yeah. That’s exactly why Python uses TimSort.

                    More tellingly, where Rust uses an algorithm that’s related to TimSort for its stable sorting algorithm, they didn’t implement “galloping” because it’s not worth it. https://github.com/rust-lang/rust/blob/7130fc54e05e247f93c7ecc2d10f56b314c97831/src/liballoc/slice.rs#L917

                3. 10

                  I consider myself relatively knowledgeable about many different topics of CS and had not heard of Timsort until this article. What’s the point of your comment? That the article is not worth posting as you presume that it is widely known?

                  1. 4

                    The point is that the title of the article, and of this submission, is inaccurate. I would call the title clickbait because for most readers, the article doesn’t deliver what it promises – a sorting algorithm “you’ve” never heard of. I think the article itself is fine; it’s just the title that is a lie.

                    1. 5

                      That seems to be a really low-value comment. For whom is the remark actually intended? For other crustaceans to look at, nod and agree, thinking, “yes, I too possess the superior knowledge”? Does every submission with a title that invokes “you” need to be correct and ‘deliver on its promise’ for all possible “you”s? C’mon.

                      1. 4

                        Yes, I suppose jgb could have been more explicit in why they brought up their guess. (I wrote an explanation of my interpretation of the comment, not the original comment.)

                        Does every submission with a title that invokes “you” need to be correct and ‘deliver on its promise’ for all possible “you”s?

                        I think every article with a title that invokes “you” needs to be correct and ‘deliver on its promise’ for the majority of possible “you”s in its audience. If a title says “you’ll love this” and most readers don’t love it, the title was wrong, and it wasted people’s time by getting them to open the article on false pretenses. It is up to article authors to adhere to that principle or not.

                        As for titles of submissions of articles with clickbait titles, there can be a conflict between submission titles that reflect the author’s intent and titles that accurately describe the article. I don’t have a simple answer as to when submission titles should differ from the article title.

                        1. 3

                          I think every article with a title that invokes “you” needs to be correct and ‘deliver on its promise’ for the majority of possible “you”s in its audience.

                          I think I agree with this, and I think my concern comes down to disagreeing instead with the notion that the majority(/“a very substantial proportion”) of Lobsters readers have heard of Timsort. Short of a poll there’s not an actual answer to that; I just felt particularly rankled because I hadn’t, and presumably if I had I wouldn’t have bothered or thought to comment myself.

                          I err on the side of preserving the article title in the submission, which I think is pretty common. Accordingly, I think most Lobsters are primed to see submission titles that aren’t necessarily addressing them as Lobsters readers, but in some context that might be quite removed.

                  2. 2

                    I thought it played a pretty big role in the Oracle vs. Google lawsuit too, making it one of the more famous algorihtms.

                    However see “rangeCheck” mentioned a lot, which is a trivial part of TimSort.


                    Here it seems to cite TimSort. But for some reason I can’t find a lot of sources that talk about TimSort and the lawsuit, even though at the time I remember it being a prominent thing.


                    edit: here’s another one mentioning TimSort and the lawsuit.


                    Googling “rangeCheck timsort lawsuit” digs up some results.

                  1. 3

                    Pointless nitpick, but I feel the need to mention that an oil company has a lot of relevance to MotoGP. After all, those bikes do have engines, and engines need oil…

                    1. 14

                      “Congressman, I don’t have all the answers to your very technical questions…”

                      That’s not something you hear everyday. Who is this Riggleman guy?

                      1. 7
                        1. 2

                          It’s interesting because he sounds decently familiar with GitHub. I wonder how many Congresspersons have GitHub accounts, if any?

                          1. 5

                            Perhaps your expectations of congressman is so low that the ability and initiative to use a website to do research is the more surprising part, because it doesn’t take a lot of familiarity with Github to perform a search. He did sound familiar with programming on more than a surface level, however.

                            1. 7

                              He was able to talk confidently about nightly toolchain builds though, which takes a fair amount of technical understanding.

                              1. 12

                                His mention of DoD practice leads me to think he picked this up as an intelligence officer. You don’t have to be an experienced developer to recognize high-level risks. Extrapolating from a single point of experience working for a former I.O. for several years, they have a keen skill for picking through details.

                                1. 1

                                  He was also an NSA contractor.

                                  1. 1

                                    I think he did indeed mention he had a background in intelligence.

                                2. 4

                                  What jgb said. He talked like a programmer or project manager, not someone vaguely familiar with it.

                                  1. -5

                                    It’s not so much low expectations it’s just the average age of a congressperson is 57, so it’s kind of new to see folks who would be familiar with something like Git.

                                    1. 29

                                      About half my computer science lecturers at university were older than that, and they were all familiar with git. My dad’s about that age, and he’s familiar with git.

                                      57 isn’t actually particularly old. Many of the pioneers of computer science have died of old age at this point. We’re well past the point where programming or computer science is a ‘young man’s game’ in any reasonable sense.

                                      1. 5

                                        The number of programmers doubled roughly every 5 years for a long period of time. Possibly from the beginning up until recently. This suggests that there are 64 times more 25 years old programmers than there are 55 years old programmers. Yes, all the pioneers are now old. But they were exactly that: few pioneers.

                                        Programming has never been a young man’s game, but this exponential growth skews the numbers like crazy, and make it appear like a young man’s game. After all, if the only thing you know about someone is their age, the older they are, the less likely they are to have learned programming.

                                        1. 2

                                          there was definitely a dip in the rate of CS enrollment after the dotcom bust in 2000, but then numbers of both major and nonmajor CS exposure has seen a massive surge since 2005

                                          1. 1

                                            Very well explained, thank you!

                                          2. 8

                                            Linus Torvalds himself turns 50 this year.

                                            1. 4

                                              57 and working in computer science is different from the average 57 year old who may not have an in-depth exposure to computer science.

                                              1. 20

                                                I wouldn’t expect that the average 57 year old has a better or worse idea of git than the average 21 year old. People often claim that young people are better with technology. In my experience, they tend to not be at all.

                                                1. 4

                                                  In my experience, they tend to not be at all.

                                                  Young people work for cheap and are more easily taken advantage of.

                                                  Why do you think so much of advertising is aimed at people in their twenties? Some disposable income and not as much life experience.

                                                  1. 3

                                                    Yeah, the average 21 year old also has no exposure to computer science either. I agree it’s a pointless comparison.

                                                2. 2

                                                  Good point! My bias is showing (growing up where I did, the only people I knew who knew about computers were my age). This makes me hopeful that I can still be programming well into retirement age :)