4 ms·

> Laying out icons on a grid should be an inherently linear operation, but somehow it was written as quadratic and was executed even when the icons were not bei

> Laying out icons on a grid should be an inherently linear operation, but somehow it was written as quadratic and was executed even when the icons were not being displayed. I could sort of understand this sloppiness if it was some random app from a hot startup, but this is a Windows issue affecting, presumably, all Windows users... Somehow this gets past code review and QA and into production, where it remains broken and nobody has fixed it. Depressing. I would argue part of the problem is that the majority of developers are computer science illiterate. They just hack things together, gluing libraries on top of frameworks, with very little understanding about what goes on underneath. Even when you point out a problem like this, people seem to be unwilling or incapable of understanding it. I have a personal experience where I raised doubts about an unoptimized algorithm (the time complexity was something like O(n^2 log n) where typical case n was supposed to be 10^6). I'm paraphrasing, but the response I got was roughly "don't worry, we can just run it on a powerful VM" and also the classic "developer time is more valuable than CPU time". When people realized this problem can't be solved by throwing money at it, the next suggestion was to artificially constrain n to be small enough that the program completes. Again I was raising doubts that this doesn't make sense, but everybody else thought it's fine. So I spent time running a series of experiments to demonstrate that the results we're getting are nonsense. It was at this point that I optimized the algorithm so it ran in O(n log n) or something similar. Something that we should have done from the start.

hoseja 6y ago
Well it's probably there since Windows 3.0 or so.
- forgotmypw17 6y ago
  not 3.0, but 95 or ie4 active desktop easily. i experienced this slowdown back then, and learned not to store many icons or files in the desktop folder.
adrianN 6y ago
I would argue that the majority of developers are juggling half a dozen tasks that need to be done ASAP and a simple quadratic solution was fast enough for the use case they had in mind and there definitely was no time to optimize for the case of invisible icons.
- baobabKoodaa 6y ago
  From the perspective of an individual developer that may be the case, but it's inexcusable for Microsoft as an organization.
  - hhjj 6y ago
    There are still a lot of bugs, features not working at all in windows. So a feature that works but slowly in extraordinary (for most users) conditions is not prioritized. If you want a bug-free os, you'll pay an extreme price in features or in dollars.
    - baobabKoodaa 6y ago
      > There are still a lot of bugs, features not working at all in windows. So a feature that works but slowly in extraordinary (for most users) conditions is not prioritized. Please don't pretend like Microsoft has rationally prioritized the feature/bug work on Windows. Microsoft is spending resources pushing ridiculously niche use cases like "3D Objects". Microsoft is also doing a bunch of duplicate work, for example, maintaining 2 different UIs for Control Panel even though the old one was fine. Maybe it's time for Microsoft to stop the endless re-designs just for the sake of "new is better", and maybe focus on fixing bugs?
      - tom_ 6y ago
        You may be correct in the larger sense, but there will be multiple teams working on Windows, with non-interchangeable staff. Assuming anybody found this bug before, somebody on the Explorer team almost certainly will have rationally prioritized it.
MontyCarloHall 6y ago
Couldn’t agree more. I’m saving this post to send to the next person who expresses disapproval that I ask computational complexity questions during my interviews.
- alisonkisk 6y ago
  How has that person not gotten in trouble for writing terribly slow software at work yet?
  - hansvm 6y ago
    I've met some developers with a good intuitive understanding of fast vs slow code and who simply don't have the vocabulary (Big-O and whatnot) to perform well in that kind of an interview. If a person really couldn't write fast code though, they could also just never have been assigned anything performance critical, the issues could have been addressed before they had any impact (e.g., in code review), or there could be a host of organizational reasons why despite pushing excessively slow code to production the consequences to any one developer are minor, especially in the short term (I've seen all of the above). Mildly off-topic, most of the accidentally quadratic code I've seen has arisen by building on top of something that wasn't designed to support it via some kind of miscommunication or leaky abstraction (and the rest from building the algorithm never imagining N could grow large enough to matter). E.g., somebody designed a type which could be instantiated with sorted data and then passed to other places with demanding enough performance guarantees to need sorted data, and the type checker would ensure that an unsorted array wasn't accidentally being passed places it shouldn't be. Somebody else saw a sorted data type providing an Add() method and thought that was perfect -- without any exotic performance needs they just blissfully assumed any of the many well-known average-case logarithmic algorithms was used for the implementation. Fast forward a little bit, and suddenly the instantiation of a large sorted data type is taking way too long because...drumroll please...it's bubble sorting! That isn't to say that nobody was blameless per se, but lack of comp sci knowledge wasn't the culprit; it was some combination of poor communication, ambiguous type names, leaky abstractions, not performance testing, not verifying the behavior of the components you're building on, etc....
fingerlocks 6y ago
I applied for a job at Microsoft recently. I had to take an online test which consisted of two medium and one hard leetcode problems. In one hour. It took nearly 15 minutes to just read the problems and make a game plan. That left 15 minutes solve and code all of them up. Have you ever done a hard leetcode problem? In 15 minutes? If that’s the bar at Microsoft, I doubt their developers are computer science illiterate. That test was harder than any of the other FAANG tests I’ve done, online or in person. Clearly the icon code was delegated to some intern or perhaps a child of one of the developers, because the bar is stupid high there just to have a conversation with a hiring manager. And they don’t even pay that well.
- baobabKoodaa 6y ago
  > Have you ever done a hard leetcode problem? Yes. I used to compete on CodeForces regularly. > Clearly the icon code was delegated to some intern or perhaps a child of one of the developers, because the bar is stupid high there just to have a conversation with a hiring manager. You're implying that the developers of Microsoft can't be computer science illiterate, because a computer science illiterate couldn't possibly pass through the recruitment funnel that you experienced. But we know this code exists. Somebody wrote it. Somebody reviewed it. Somebody tested it. Everybody involved in this process thought "yeah, this is good enough", when it's clearly not good enough. Anyone with as little as CS101 experience would not write crap like this in the first place, so it's really hard to argue that the developers at Microsoft are computer science literate.
  - fingerlocks 6y ago
    The code was likely written in the early 90s when the barrier to entry was much lower. It was a time when thousands of icons on your desktop wasn’t a use case worth considering, much less testable. That seems more plausible than all the developers being illiterate.
    - baobabKoodaa 6y ago
      > The code was likely written in the early 90s when the barrier to entry was much lower. You're probably right about that. > That seems more plausible than all the developers being illiterate. I'm not saying all developers are CS illiterate, but most are.
bigiain 6y ago
> I would argue part of the problem is that the majority of developers are computer science illiterate. While I wouldn’t argue against that... Sometimes people who do know what they’re doing choose slow algorithms knowingly. I implemented a way finding algorithm that works in O(n^4) a while back. Because I knew the specific use case we needed it for had a max of around 200 for n, and that I could run a brute force of all possible routes for that in less than a minute in unoptimised Python on my laptop, so that I could then cache all the results and just do a very fast lookup from a ~40,000 row database table in production. I was very very clear to everybody concerned that this solution was not a scalable general solution, but it worked like magic for what our customer needed.
- sitkack 6y ago
  You applied global optimization, which I wish we could do more often. Part of the type system should encode how long the fn call is allowed to take.
saagarjha 6y ago
> I would argue part of the problem is that the majority of developers are computer science illiterate. Sometimes, but it’s certainly only part of the problem. I’ve seen these kinds of bugs from people who would “know better”, who understand what O(n^2) is and are entirely willing and capable of fixing these things when you point them out…it’s just that they don’t see them when they are writing the code, or they mispredict the value of n that the code will be used under. And this seems to be prevalent no matter how “production grade” the software is; I’ve diagnosed these in my web browser, filesystem, text editor…in many of these cases I know who the developers are and they are exceptionally talented, and yet these kinds of bugs still exist. I don’t think we can solve these issues without some sort of concerted effort to uncover them, which I would argue is a strangely rare skill.
pezezin 6y ago
> When people realized this problem can't be solved by throwing money at it, the next suggestion was to artificially constrain n to be small enough that the program completes... It was at this point that I optimized the algorithm so it ran in O(n log n) or something similar. Something that we should have done from the start. I had the exact same situation at my previous job. Heck, the CEO even sold it as an advantage of our system, highlighting how few data we needed to get good results. Except our results were crap. I fixed that problem and many others, and left the job three years ago, but they are still selling their product the same way. Some times you really need a big amount of data to get good results.

hoseja 6y ago

Well it's probably there since Windows 3.0 or so.

forgotmypw17 6y ago
not 3.0, but 95 or ie4 active desktop easily. i experienced this slowdown back then, and learned not to store many icons or files in the desktop folder.

adrianN 6y ago

I would argue that the majority of developers are juggling half a dozen tasks that need to be done ASAP and a simple quadratic solution was fast enough for the use case they had in mind and there definitely was no time to optimize for the case of invisible icons.

baobabKoodaa 6y ago
From the perspective of an individual developer that may be the case, but it's inexcusable for Microsoft as an organization.
- hhjj 6y ago
  There are still a lot of bugs, features not working at all in windows. So a feature that works but slowly in extraordinary (for most users) conditions is not prioritized. If you want a bug-free os, you'll pay an extreme price in features or in dollars.
  - baobabKoodaa 6y ago
    > There are still a lot of bugs, features not working at all in windows. So a feature that works but slowly in extraordinary (for most users) conditions is not prioritized. Please don't pretend like Microsoft has rationally prioritized the feature/bug work on Windows. Microsoft is spending resources pushing ridiculously niche use cases like "3D Objects". Microsoft is also doing a bunch of duplicate work, for example, maintaining 2 different UIs for Control Panel even though the old one was fine. Maybe it's time for Microsoft to stop the endless re-designs just for the sake of "new is better", and maybe focus on fixing bugs?
    - tom_ 6y ago
      You may be correct in the larger sense, but there will be multiple teams working on Windows, with non-interchangeable staff. Assuming anybody found this bug before, somebody on the Explorer team almost certainly will have rationally prioritized it.

MontyCarloHall 6y ago

Couldn’t agree more. I’m saving this post to send to the next person who expresses disapproval that I ask computational complexity questions during my interviews.

alisonkisk 6y ago
How has that person not gotten in trouble for writing terribly slow software at work yet?
- hansvm 6y ago
  I've met some developers with a good intuitive understanding of fast vs slow code and who simply don't have the vocabulary (Big-O and whatnot) to perform well in that kind of an interview. If a person really couldn't write fast code though, they could also just never have been assigned anything performance critical, the issues could have been addressed before they had any impact (e.g., in code review), or there could be a host of organizational reasons why despite pushing excessively slow code to production the consequences to any one developer are minor, especially in the short term (I've seen all of the above). Mildly off-topic, most of the accidentally quadratic code I've seen has arisen by building on top of something that wasn't designed to support it via some kind of miscommunication or leaky abstraction (and the rest from building the algorithm never imagining N could grow large enough to matter). E.g., somebody designed a type which could be instantiated with sorted data and then passed to other places with demanding enough performance guarantees to need sorted data, and the type checker would ensure that an unsorted array wasn't accidentally being passed places it shouldn't be. Somebody else saw a sorted data type providing an Add() method and thought that was perfect -- without any exotic performance needs they just blissfully assumed any of the many well-known average-case logarithmic algorithms was used for the implementation. Fast forward a little bit, and suddenly the instantiation of a large sorted data type is taking way too long because...drumroll please...it's bubble sorting! That isn't to say that nobody was blameless per se, but lack of comp sci knowledge wasn't the culprit; it was some combination of poor communication, ambiguous type names, leaky abstractions, not performance testing, not verifying the behavior of the components you're building on, etc....

fingerlocks 6y ago

I applied for a job at Microsoft recently. I had to take an online test which consisted of two medium and one hard leetcode problems. In one hour. It took nearly 15 minutes to just read the problems and make a game plan. That left 15 minutes solve and code all of them up. Have you ever done a hard leetcode problem? In 15 minutes? If that’s the bar at Microsoft, I doubt their developers are computer science illiterate. That test was harder than any of the other FAANG tests I’ve done, online or in person. Clearly the icon code was delegated to some intern or perhaps a child of one of the developers, because the bar is stupid high there just to have a conversation with a hiring manager. And they don’t even pay that well.

baobabKoodaa 6y ago
> Have you ever done a hard leetcode problem? Yes. I used to compete on CodeForces regularly. > Clearly the icon code was delegated to some intern or perhaps a child of one of the developers, because the bar is stupid high there just to have a conversation with a hiring manager. You're implying that the developers of Microsoft can't be computer science illiterate, because a computer science illiterate couldn't possibly pass through the recruitment funnel that you experienced. But we know this code exists. Somebody wrote it. Somebody reviewed it. Somebody tested it. Everybody involved in this process thought "yeah, this is good enough", when it's clearly not good enough. Anyone with as little as CS101 experience would not write crap like this in the first place, so it's really hard to argue that the developers at Microsoft are computer science literate.
- fingerlocks 6y ago
  The code was likely written in the early 90s when the barrier to entry was much lower. It was a time when thousands of icons on your desktop wasn’t a use case worth considering, much less testable. That seems more plausible than all the developers being illiterate.
  - baobabKoodaa 6y ago
    > The code was likely written in the early 90s when the barrier to entry was much lower. You're probably right about that. > That seems more plausible than all the developers being illiterate. I'm not saying all developers are CS illiterate, but most are.

bigiain 6y ago

> I would argue part of the problem is that the majority of developers are computer science illiterate. While I wouldn’t argue against that... Sometimes people who do know what they’re doing choose slow algorithms knowingly. I implemented a way finding algorithm that works in O(n^4) a while back. Because I knew the specific use case we needed it for had a max of around 200 for n, and that I could run a brute force of all possible routes for that in less than a minute in unoptimised Python on my laptop, so that I could then cache all the results and just do a very fast lookup from a ~40,000 row database table in production. I was very very clear to everybody concerned that this solution was not a scalable general solution, but it worked like magic for what our customer needed.

sitkack 6y ago
You applied global optimization, which I wish we could do more often. Part of the type system should encode how long the fn call is allowed to take.

saagarjha 6y ago

> I would argue part of the problem is that the majority of developers are computer science illiterate. Sometimes, but it’s certainly only part of the problem. I’ve seen these kinds of bugs from people who would “know better”, who understand what O(n^2) is and are entirely willing and capable of fixing these things when you point them out…it’s just that they don’t see them when they are writing the code, or they mispredict the value of n that the code will be used under. And this seems to be prevalent no matter how “production grade” the software is; I’ve diagnosed these in my web browser, filesystem, text editor…in many of these cases I know who the developers are and they are exceptionally talented, and yet these kinds of bugs still exist. I don’t think we can solve these issues without some sort of concerted effort to uncover them, which I would argue is a strangely rare skill.

pezezin 6y ago

> When people realized this problem can't be solved by throwing money at it, the next suggestion was to artificially constrain n to be small enough that the program completes... It was at this point that I optimized the algorithm so it ran in O(n log n) or something similar. Something that we should have done from the start. I had the exact same situation at my previous job. Heck, the CEO even sold it as an advantage of our system, highlighting how few data we needed to get good results. Except our results were crap. I fixed that problem and many others, and left the job three years ago, but they are still selling their product the same way. Some times you really need a big amount of data to get good results.