15 ms·

O(n^2), again, now in Windows Management Instrumentation

501 points by harikb 7y ago

harikb 7y ago
A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there
- rcthompson 7y ago
  I think the other reason O(n^2) is a "sweet spot" is that it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. Very often it's ultimately because the inner O(n) algorithm should have been implemented as O(1), but nobody bothered because it was never intended to be called in a loop.
  - cross_wiber 7y ago
    That's a good point. It explains why you can very often unintentionally end up with an O(n^2) algorithm in the first place, and Dawson's law then explains why no one bothers to fix it until it's too late.
    - brucedawson 7y ago
      Hey, it's Dawson's first law of computing. I have more planned, and it's important to distinguish them.
  - crankylinuxuser 7y ago
    This is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being able to identify and detect resource usage is what is nice about waterfall. Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days.
    - ComputerGuru 7y ago
      > Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. Which has led to the ridiculous software bloat we have today. This always MVP, break fast, break often garbage needs to die.
      - chousuke 7y ago
        I feel like the concept of an MVP is often abused. It shouldn't be a thing that somehow works with bubblegum and luck; it should still be "solid". The point ought to be to leave out features, not quality.
        NateEag 7y ago
        When you leave out features and quality, you have a proof of concept. Those are valuable things to build, IMO. Just make sure you leave out enough features that it cannot be pushed into production once someone else sees it running.
    - TimTheTinker 7y ago
      Waterfall refers more to the fact that further work (development, testing, or deployment) has to wait for someone else to finish something else first. Multiply that by how many “steps” something has to go through before being released. This implies everyone is taking work in large chunks instead of small iterations, and that too much is being planned too early instead of learning as you go. Taking things iteratively, small iterations, delaying decisions, learning as you go — that’s what agile development is. And all the stuff you mention above is possible when developing with agility.
    - pjc50 7y ago
      > Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days. If you've worked out which API calls are happening and how often, you've already written most of the application. It's just that it might be on paper or in pseudocode. Waterfall was abandoned because getting to that level of detail takes far too long for management to accept and it's easier - sometimes orders of magnitude faster - to write the thing as actual code, try it, and then see what needs improving. And see what was wrong with the requirements.
  - ludamad 7y ago
    Right, if we consider O(n) "ideal" (for many domains, this is true), we can consider processing per item as a more convenient metric. If you go above, say, O(log n) processing per item, you're in trouble proportionate to the unintended success of this portion of the code. Very easy to write a sloppy utility with a nice API, only for it to be 'the perfect fit' for someone else's tight deadline, become an idiom in the code, finally see a 10,000 entry example much later
  - leetcrew 7y ago
    sometimes it was correct to choose O(n) instead of O(1). if you know you're only going to have very few elements, linear search on a vector can be faster than a hashtable lookup or rb-tree traversal and use less memory for the data structure. later on some clown decides to expose your private function for their own convenience and starts calling it with thousands of elements.
    - mrec 7y ago
      You're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense. For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to people reading the code later.
      - cogman10 7y ago
        Depends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c < d) or (a < b and d == b)". Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial. When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".
        mehrdadn 7y ago
        > where the keys looks something like "if (a > b and c < d) or (a < b and d == b)" Confused, what do you mean when you say the key is an "if" statement?
        z92 7y ago
        He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.
  - savingGrace 7y ago
    I often see O(n^2) algorithms that can be reduced to O(2n) at the very least. One of the best things I gained from school was the red flag that fires off in my mind any time I see a loop nested in a loop.
    - TravHatesMe 7y ago
      O(2n) = O(n)
    - shantly 7y ago
      A little experience gets you that same red flag instinct in a hurry, too. [EDIT] it also makes you hesitate & second-guess and worry and experiment a bunch when contemplating using a recursive algorithm, which is deeply counterproductive in interviews where the expected behavior is so often "apply recursion, instantly and without hesitation" :-)
      - deleted 7y ago
        [deleted]
      - nikanj 7y ago
        Unfortunately interviews seem to be all about dogma, and if you even mention performance you will get dinged for premature optimization. It’s like a postmodern religion where premature optimization is the cardinal sin, and you are supposed to burn as many cycles as possible to demonstrate that you are of good faith
        WorldMaker 7y ago
        On the flipside, I've met different sorts of interviewers that ding someone for writing something intentionally unoptimized in the spirit of avoiding premature optimization for algorithmic clarity, because don't they have rote knowledge that "x is faster". Dogma on every side of the fence. (Also, continuing proof that technical interviews will never be objective evaluations of skill.)
    - stevefan1999 7y ago
  - Tade0 7y ago
    Or those two should have been combined into O(nlogn) via sorting.
    - 52-6F-62 7y ago
      Or if you've already made allowances for the memory usage, you can also check to see if you can write your O(n^2) nested loops as O(n) + O(n) depending on the shape of your data.
  - masklinn 7y ago
    > it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. https://accidentallyquadratic.tumblr.com https://accidentallyquadratic.tumblr.com was / is pretty much an entire blog dedicated to this.
  - jtolmar 7y ago
    Programming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, but you have to go out of your way and do something a bit weird to get an exponential run time.
    - kortilla 7y ago
      What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
      - esotericn 7y ago
        That's n^2.
      - reggieband 7y ago
        That is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time https://stackoverflow.com/questions/4317414/polynomial-time-...
        justincredible 7y ago
        whoops is O(2^n)
      - _wldu 7y ago
        Two for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).
      - a1369209993 7y ago
        Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
        trehalose 7y ago
  - lmm 7y ago
    I don't think that's a real insight. You could equally say that O(n^3) should be a sweet spot because you can nest a loop 3 deep, and so on for n^4, n^5 and so on. But we don't see these cases making it out into the wild because they're caught in testing.
  - wesammikhail 7y ago
    A useful heuristic from my CS professor: always treat every tab (indentation / complexity) to be equivalent to a cart that you are attaching your horse. Add enough carts (complexity) and you will soon be asking yourself why your horse isnt a nuclear reactor instead?
- mehrdadn 7y ago
  Speaking of O(n^2) algorithms (if it's OK for me to promote my own writing on this recently?): I recently illustrated how they can even occur as a result of algorithms being slow by a constant factor. I thought it might be useful for others, so I posted it here: https://news.ycombinator.com/item?id=21745911 https://news.ycombinator.com/item?id=21745911
lousken 7y ago
seems like building chrome is a loyal pain in the ass, so many bugs found in windows because of that :)
- techntoke 7y ago
  It's actually pretty easy and there are package manifest in Arch that shows you how.
  - ComputerGuru 7y ago
    That’s just because someone went through that pain for you and scripted and packaged the entire procedure and rolled up most of the dependencies and their bills systems. I’ve done it from the official build directions without containers or prebuilt dependencies and “royal pain in the ass” is an understatement.
    - techntoke 7y ago
      Firefox is a nightmare to package that way.
      - ComputerGuru 7y ago
        That’s one nice side effect from the push to convert dependencies/components to pure rust, one at a time. Even if it doesn’t go all the way, each step hugely simplifies the build process and minimizes the list of (recursive) dependencies.
JonathonW 7y ago
Honestly, O(n^2) is probably okay for a diagnostic tool that's only meant to be run occasionally-- I'd like to know why Google's IT department felt the need to schedule it to run so frequently.
- JoeAltmaier 7y ago
  That could be underestimating the truly catastrophic nature of O(n^2). Blows up very very fast. From milliseconds to seconds to days to decades. Pretty much anything that grows at all, must not be subject to the terrible power of O(n^2)
- btilly 7y ago
  The problem is that available disk space is growing exponentially over the years with a current doubling time of around 18 months for flash drives. And therefore repository size has been as well. What today are 1 GB repositories fairly predictably will be 10+ GB repositories in 5 years. And 100+ GB in 10 years. Which means that the period of locking your computer predictably will go from minutes to hours to days in the same time period. What is kinda OK today is going to definitely not be OK going forward. This algorithm has to get fixed.
- loeg 7y ago
  It's sort of unclear why 3 billion bytes needs to be processed in an O(N^2) algorithm in the first place, but seems especially egregious in that it also blocks other processes from running. One other aspect of the issue is that it's unclear why that database is now so large. It seemed like different machines had different sized databases — perhaps one angle of the solution is trimming and vacuuming.
  - brucedawson 7y ago
    Well, it doesn't block all other processes, but it sure did block a lot of them. I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.
peter_d_sherman 7y ago
Excerpt: "I decided that the interactions were too complex to be worth analyzing in detail, especially without any thread names to give clues about what the 25 different threads in svchost.exe (3024) were doing." Future OS/Compiler Programming Note: It would be nice if threads could be individually named and those thread names shown/slowed/stopped/debugged in whatever tool implements Task Manager like functionality...
- retrovm 7y ago
  POSIX threads can be individually named. They inherit the name of their creator if you don't set one.
  - adzm 7y ago
    They can be named in Windows as well, and this author has made pleas for developers to do so.
    - jandrese 7y ago
      The caveat being the developers who are careful enough to name their threads and implement good debug hooks aren't the ones you get called on to fix their code.
  - the-rc 7y ago
    As an aside, POSIX/Linux thread names have a limit of 16 bytes, which means 15 characters plus NULL. Speaking from experience, this can and will bite you when you need the names the most, if e.g. they are long, have just one or a handful of common prefixes and their creation is not entirely under your control.
- colatkinson 7y ago
  Already possible in Windows [0]. [0]: https://docs.microsoft.com/en-us/windows/win32/api/processthreadsapi/nf-processthreadsapi-setthreaddescription https://docs.microsoft.com/en-us/windows/win32/api/processth...
- 7y ago
rwmj 7y ago
I have my own O(n^2) blow-up story. Back in the day I wrote some Google AdWords analysis software in a functional language. Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. Anyway these were only used to load the analysis inputs which was written in an Excel spreadsheet (the customer insisted on this!), exported to a CSV and loaded into the software. The spreadsheet was only perhaps 5 rows so, whatever. One day I got a call from the customer that his analysis was taking 6 hours to run, for a program that should have finished in a fraction of a second. It turned out the customer had tried to load a 30,000 row spreadsheet of input. The program would on every loop iterate over the input association list, resulting in classic O(n^2) performance overall. After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.
- masklinn 7y ago
  Why would the code be "nowhere near as elegant"? Lack of a functional / persistent map? Because I'd expect all maps to provide roughly similar interfaces whether they're assoc lists, hashmaps, btrees, HAMT, …: iterate all entries, presence of a key, get value for key, insert (key, value), remove key (and value), possibly some other niceties on top (e.g. update value in-place, merge maps, …) but those are extras.
  - marcosdumay 7y ago
    On my experience, moving away from a list of pairs add a parsing stage that one may be able to omit otherwise.
    - masklinn 7y ago
      I don't understand how or why. What's the "parsing stage"? You have an associative array, a key, a value, and a function to associate the k, v pair to the array. You're moving from let m' = (k, v) : m to let m' = insert k v m What there would make the code "nowhere near as elegant"?
stevefan1999 7y ago
Well, now this show how polynomial time isn't necessarily any better than O(2^n), or exponential time in reality. Once the k grew bigger in O(n^k), our modern machine will still struggle to run it.
- loeg 7y ago
  O(N^2) is strictly better than O(2^N). Per the article, this algorithm fell over at 3 billion bytes of data, but wasn't especially noticeable at 300 million bytes of data.
  - saagarjha 7y ago
    Better from an theoretical perspective. Depending on n and any constant factors, one or the other may end up winning in reality.
    - loeg 7y ago
      In practice, not really either. Unless "N" isn't actually variable and is basically zero.
- read_if_gay_ 7y ago
  The point where polynomial time becomes impractical is far beyond the point where exponential becomes impractical. It's like for n=10 your smartphone can run an exponential algorithm instantly but for n=20 the fastest supercomputer on earth will take forever. Not true for polynomial.
- actuator 7y ago
  Not really. The n is huge, there is an enormous difference between an exponential complexity like O(2^n). Many algorithms are O(N^2) and are perfect for their use case. To see the difference. - 100^2 -> 10^4, 2^100 -> 10^10 - 1000^2 -> 10^6, 2^1000 -> 10^100 Look at the difference in order of growth. Just to give a very simplified comparison, your individual processor core can run about 10^9 simple instructions in a second.
radicalbyte 7y ago
Ten years ago the hash-map implementation in Internet Explorer was also O(n2). I had to inject javascript into some vendor code to avoid this after our production environment died. I ended up replacing the underlying hash-map into multiple smaller maps based on a hash of the items. So I'd have 50 maps of 1000 items instead of one map of 50000 items.
- Etheryte 7y ago
  I'm interested to know, what practical application did you load 50.000 items into the frontend for 10 years ago?
  - masklinn 7y ago
    10 years ago is 2009. Large web applications had been breaking out of intranets (where they'd lived for quite some time at that point) for years at that point. GMail was launched in 2004, Google Maps in 2005 (that's also the year "AJAX" was coined) the JS library war was done and over with (jquery, prototype, mochikit, mootools, dojo, YUI, … were all released between 2005 and 2006). IE7 was 3 years old, Google Chrome was reaching its first year, IE8 was just released.
    - Etheryte 7y ago
      You seem to be missing the crux of the issue I was trying to address — even today, loading 50.000 items into a frontend application would be a very, very niche edge case. 10 years ago even more so. Tacking on arbitrary reference points from Wikipedia doesn't change any of that.
      - masklinn 7y ago
        > You seem to be missing the crux of the issue I was trying to address — even today, loading 50.000 items into a frontend application would be a very, very niche edge case. It's a medium-sized inventory, if you need fast / offline access then loading it to the client makes a lot of sense. I'm sure there are plenty other things of which you can easily reach 50k, and that you'd want to index or cross-reference somehow.
aneutron 7y ago
Reminds me of the time we found out a team was running O(n^2) code, but in terms of SQL Queries, that is to say, not O(n^2) of comparisons or anything, and were trying to blame the other team when a client sent a request that never ended. And they tried blaming them for migrating data to a new server with an SSD that shaved 20 minutes from their processing time. And if you're wondering, they refused to fix it because "it would need too many sprints" and "maybe we'll talk about it in a workshop". It's still not fixed.
- 72deluxe 7y ago
  Funny that you used the word "team" when the outcome is anything but teamwork.
jedberg 7y ago
The thing that impresses me most about this writeup is how much instrumentation there is on Windows now. I stopped using Windows about 15 years ago, but I don't think this kind of analysis was possible back then. Or maybe I just didn't know the tools well enough?
- AaronFriel 7y ago
  15 years ago? You might have just missed it. Event Tracing for Windows gained a lot of functionality in Windows Vista, which some[1] have described as the most forward-looking and instrumental release in Windows history. Vista had a lot of flaws, but it introduced almost everything fundamental to Windows 7 to Windows 10, save perhaps the more recent developments in virtualization and containerization. From differential application-consistent full backups, to transparent full disk encryption, to the use of a TPM to verify boot integrity. Vista was a massive release, but also much maligned so maybe you didn't miss much leaving when you did. The tooling has certainly gotten a lot better since then, and so has Windows. Rather more recently, Windows has gained dtrace support: https://techcommunity.microsoft.com/t5/Windows-Kernel-Internals/DTrace-on-Windows/ba-p/362902 https://techcommunity.microsoft.com/t5/Windows-Kernel-Intern... [1] - See this self-described eulogy by @SwiftOnSecurity: https://twitter.com/SwiftOnSecurity/status/851857404891471872 https://twitter.com/SwiftOnSecurity/status/85185740489147187...
  - jedberg 7y ago
    I never used Vista. My last Windows was XP. Vista is only 14 years old. :)
  - sedatk 7y ago
    Vista's importance in Windows history can't be overstated. It's regarded as a failure in the end but it provided a great baseline for the releases following it. Windows 10 has a much better networking stack, update mechanism, device driver model, GUI etc, all thanks to Vista.
- mixmastamyk 7y ago
  Same here. WMI and perf counters have been around a long time though. I recently used Win10 for work and was amazed at the combination of awe-inspiring tech and plain awe-full complexity. Just the control panel goes four layers deep attempting to make things easier but in practice is several times harder to find options than it was in Win2k. If there were a distribution with all the corporate goals stripped out I'd jump on it.
gameswithgo 7y ago
In the world of database backed web apps a related pattern is asking the database for some rows for a table, and then asking the database from some more rows, based on each row you just got. Rather than joining it together into one query. Makes it into production but falls down eventually!
- kbenson 7y ago
  There are sometimes reasons why you don't want to join, such as large data parent row sizes that get repeated a lot in if there's a lot of child relations. But that should be two queries. One for all the parents, and one to get the children with a sub-select (or at worst a manually generated parent id list), and then you can join them manually (if actually needed and you can't just use the data sets as they are).
  - somurzakov 7y ago
    you are right, APIs often use o(n) algorithms in an individual API call that is meant to execute once. what happens, is that API users start executing that endpoint N times and here it becomes O(n^2). people should remember that APIs are for CRUD calls. If you want batch reports - call a separate reporting endpoints that process data in large batches.
- toast0 7y ago
  I've actually had a lot of success going the other way. A database query with a join takes down production, so do a client side join, query one: get a bunch of ids from table A, query two: get a bunch of rows from table B, often as get one row from table B UNION get next row from table B etc. You can try using IN on the second query, but usually if that was going to work in a reasonable amount of time, your join would have also worked in a reasonable amount of time. The real problem people run into with the client side join is making it query one get a bunch of ids from table A, query two through N, get one row from B, with each query requiring a round trip. Even a pretty small client to server roundtrip of 1 ms gets nasty quick with repeated queries.
  - 7y ago
zackmorris 7y ago
If you're building a library or framework, then just assume that worst-case performance will be encountered by your users, because you can't predict their use cases. So for example, I almost always use associative arrays (maps) instead of lists. I actually really wish there a MAPP language because I view the map as a potentially better abstraction than the list in LISP, but I digress. I also tend to use atomic operations instead of locks. Some good starting points for that are understanding how compare-and-swap (CAS) works, and also how functional programming with higher order functions and immutable variables works because that mindset greatly simplifies threading with no shared mutable state for the Actor model. Lazy evaluation is another good one. Also vector languages like Gnu Octave and MATLAB are good because they favor a level of abstraction above the bare-hands programming of C-style languages like C++ and Javascript so you tend to see that most algorithms are embarrassingly parallel at some level (especially the things we tend to think of as computationally expensive like multimedia processing). Also (this may be controversial) but I think that poor performance can be politically motivated. For example, I run Safari with Javascript disabled so I can have thousands of tabs open (it's disabled as I write this). But when I disable Javascript in Chrome, performance grinds to a halt. You can try it right now on the Mac by force quitting Chrome with a bunch of tabs open and relaunching it from Terminal.app with: open -a "Google Chrome" --args --disable-javascript Or manually with: https://www.computerhope.com/issues/ch000891.htm https://www.computerhope.com/issues/ch000891.htm I don't know what causes it, but my guess is that Google either wrote some of the loops under the assumption that Javascript would always be on, or they had a blind spot in their implementation because so much of their business model depends on ads having dynamic behavior. So when you're in a meeting and someone shouts down your concern about edge case performance because they don't see that as a priority, graciously humor them and then write your code the right way because you know that it doesn't take any longer than doing it the wrong way. You might catch some flack during code review so have a good excuse handy, something about trying it the other way but running into problems. Often I'll write the easy imperative solution in a comment above the simple functional solution or even put both solutions under a preprocessor directive or feature flag to leave it up to the team lead/project manager and have our keisters covered if/when something melts down.
- deleted 7y ago
  [deleted]
equalunique 7y ago
(not) discussed previously: https://news.ycombinator.com/item?id=21740589 https://news.ycombinator.com/item?id=21740589
rcthompson 7y ago
Probably the most important thing I learned about algorithmic complexity analysis in grad school was that N is not constant, but rather it grows over time (probably at an exponential rate). That is, as our computing power increases, we continue to aspire to analyze larger and larger data sets. So anything beyond O(n*log(n)) that works right now is more or less guaranteed to blow up in the not-so-distant future, if it remains in use that long.
ihaveajob 7y ago
This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.
- Google234 7y ago
  2^2^9 is 1.340781e+154
  - mathgladiator 7y ago
    In this format, exponents are evaluated left to right, so this is 4^9 which is 262144 and is reasonable.
    - vecter 7y ago
      That's certainly not the standard. If anything, exponentiation is usually performed right to left, with some exceptions [0]. However, the fact that we even have carets in this conversation isn't because the GP wanted to adopt a left-to-right convention, but due to limitations in the richness of HN's text editor. If you write a tower of 2^2^9 on a whiteboard and ask 1000 mathematicians and computer scientists to evaluate it, I'm sure 999 or 1000 of them would evaluate it as 2^(2^9). [0] https://en.wikipedia.org/wiki/Order_of_operations#Serial_exponentiation https://en.wikipedia.org/wiki/Order_of_operations#Serial_exp...
      - mathgladiator 7y ago
        I'm a mathematician and a computer scientist, so I must be one in a thousand. The link even indicates that ambiguity exists in wild, and I think clear notation would help. In this case, the absurdity of the number suggests a more realistic number.
        7y ago
fourseventy 7y ago
I love this guys blog. Been reading it for a while. He is a beast.
vortico 7y ago
Batch scripts themselves are O(n^2) because the shell closes and reopens them after each line (even comments or even blank lines), and the scan to get to line `n` takes O(n) time and disk bandwidth.
- concerned_user 7y ago
  That is just plain incorrect, local variables would not work in scripts if that were the case.
  - vortico 7y ago
    I definitely remember both reading about and experiencing this years ago, but I can't seem to find a source and it's driving me crazy (will search more later). I imagine variables would persist in the shell's memory. I'm talking about an implementation detail of the batch shell script parser/runner. I recall that some people would put GOTO statements to jump across large comment blocks in the days where reading a few KB was noticeable.
    - concerned_user 7y ago
      It can be correct if you are talking about subprocesses/subshells of another batch script/command then yes, separate shell process will be spawned in each iteration.
      - vortico 7y ago
        No, I recall reading that the batch processor closes/re-opens the file, scans for n carriage returns where n is the current line number, executes that line, and repeats. These are the sources I found. http://xset.tripod.com/tip3.htm http://xset.tripod.com/tip3.htm "COMMAND.COM reads and executes batch files one line at a time; that means that it reads one line, execute it and rereads the file from the beginning to the next line." Perhaps this is a really old version of COMMAND.COM? Perhaps it's poorly stated but actually meant that it "rereads the file from the beginning of the next line to the next line". https://docs.microsoft.com/en-us/windows/win32/fileio/local-caching https://docs.microsoft.com/en-us/windows/win32/fileio/local-... "Command processors read and execute a batch file one line at a time. For each line, the command processor opens the file, searches to the beginning of the line, reads as much as it needs, closes the file, then executes the line." This also seems to agree with my original claim. I tested this with a batch script generated by print("@echo off") for i in range(1000): for j in range(1000): print("rem hello world") print(f"echo {i}") and ran it using COMMAND.COM in a Windows 95's VM. It appears to run in linear time. Either COMMAND.COM was fixed, or both sources are incorrect.
ww520 7y ago
Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N, to get the job done quickly and simple enough to ensure correctness. Plus I could replace it later if needed. So it's done and forgotten. Things were working fine and performance was good. Then one day Windows Explorer suddenly hung with 100% CPU for couple seconds. This was one of the worst kind of bugs. There's no crash to pinpoint the problem. Things still work most of the times, just slowed down intermittently. Luckily I was able to catch a slowdown and deliberately crashed the process in time. The call trace stopped in the bubble sort function. I immediately kicked myself - it's the classic case of O(n^2) blowup. The cache entries had been scaled up to couple thousands items and the exponential O(n^2) blowup to tens of million of iterations was having a real impact. I switched to merge sort and performance was back to normal. Edit: I picked merge sort because the worst case was O(n log n), unlike quick sort whose worst case was O(n^2). Once burnt, needed to be extra careful with edge cases.
- vecter 7y ago
  n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
  - ww520 7y ago
    You're correct n^2 is polynomial, not exponential. It was just an exaggerated figure of speech. BTW, O(n) and O(n log n) are also polynomial; it just doesn't have the punch to it.
    - paulddraper 7y ago
      So the more precise term would be quadratic. "Exponential" is indeed misused. Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.
kortilla 7y ago
Sounds like they’ll have to increase their leetcode requirements in the interviewing process. This is one of the “obvious fundamentals” that leetcode challenges screen for, right? /s
wakatime 7y ago
That's why latency is always measured in p99: https://stackoverflow.com/questions/12808934/what-is-p99-latency https://stackoverflow.com/questions/12808934/what-is-p99-lat...
tinus_hn 7y ago
Then again, your disk space, processing power and memory is cheap for Microsoft.
mark-r 7y ago
Any time I hear of an O(n^2) problem I remember Shlemiel the painter. https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/
hnick 7y ago
At work we had a daily script that took about 30 minutes to run, and about 3 hours on the weekend due to more data. One day we got a report that a downstream service was missing SLA because the script wasn't finishing. I'd come onto the team late so wasn't aware this was abnormal. It turns out it was now taking about 1-2 hours daily and 6-12 hours on the weekend depending on data size. This had been going on for months but gradually getting worse as the data grew, to the point it was unbearable so finally reported. A senior programmer had removed the shell call to sort on an indexed text file and written their own ad-hoc sorter through every fresh programmer's favourite (you guessed it) bubble sort. To make things worse, this was perl which has a perfectly functional sort itself if you really have to do it that way. I still have no idea why this was done, I don't think asking would have been productive in that place at that time.
codetrotter 7y ago
I have over a 100,000 images on my iPhone and some apps used to be really really really slow when I selected browse album in them. One of the apps that used to be maddeningly slow was Instagram, but Instagram has gotten better lately. No idea why though.
bokjack 7y ago
holly molly

501 points by harikb 7y ago

A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there

rcthompson 7y ago
I think the other reason O(n^2) is a "sweet spot" is that it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. Very often it's ultimately because the inner O(n) algorithm should have been implemented as O(1), but nobody bothered because it was never intended to be called in a loop.
- cross_wiber 7y ago
  That's a good point. It explains why you can very often unintentionally end up with an O(n^2) algorithm in the first place, and Dawson's law then explains why no one bothers to fix it until it's too late.
  - brucedawson 7y ago
    Hey, it's Dawson's first law of computing. I have more planned, and it's important to distinguish them.
- crankylinuxuser 7y ago
  This is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being able to identify and detect resource usage is what is nice about waterfall. Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days.
  - ComputerGuru 7y ago
    > Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. Which has led to the ridiculous software bloat we have today. This always MVP, break fast, break often garbage needs to die.
    - chousuke 7y ago
      I feel like the concept of an MVP is often abused. It shouldn't be a thing that somehow works with bubblegum and luck; it should still be "solid". The point ought to be to leave out features, not quality.
      - NateEag 7y ago
        When you leave out features and quality, you have a proof of concept. Those are valuable things to build, IMO. Just make sure you leave out enough features that it cannot be pushed into production once someone else sees it running.
  - TimTheTinker 7y ago
    Waterfall refers more to the fact that further work (development, testing, or deployment) has to wait for someone else to finish something else first. Multiply that by how many “steps” something has to go through before being released. This implies everyone is taking work in large chunks instead of small iterations, and that too much is being planned too early instead of learning as you go. Taking things iteratively, small iterations, delaying decisions, learning as you go — that’s what agile development is. And all the stuff you mention above is possible when developing with agility.
  - pjc50 7y ago
    > Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days. If you've worked out which API calls are happening and how often, you've already written most of the application. It's just that it might be on paper or in pseudocode. Waterfall was abandoned because getting to that level of detail takes far too long for management to accept and it's easier - sometimes orders of magnitude faster - to write the thing as actual code, try it, and then see what needs improving. And see what was wrong with the requirements.
- ludamad 7y ago
  Right, if we consider O(n) "ideal" (for many domains, this is true), we can consider processing per item as a more convenient metric. If you go above, say, O(log n) processing per item, you're in trouble proportionate to the unintended success of this portion of the code. Very easy to write a sloppy utility with a nice API, only for it to be 'the perfect fit' for someone else's tight deadline, become an idiom in the code, finally see a 10,000 entry example much later
- leetcrew 7y ago
  sometimes it was correct to choose O(n) instead of O(1). if you know you're only going to have very few elements, linear search on a vector can be faster than a hashtable lookup or rb-tree traversal and use less memory for the data structure. later on some clown decides to expose your private function for their own convenience and starts calling it with thousands of elements.
  - mrec 7y ago
    You're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense. For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to people reading the code later.
    - cogman10 7y ago
      Depends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c < d) or (a < b and d == b)". Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial. When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".
      - mehrdadn 7y ago
        > where the keys looks something like "if (a > b and c < d) or (a < b and d == b)" Confused, what do you mean when you say the key is an "if" statement?
        z92 7y ago
        He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.
- savingGrace 7y ago
  I often see O(n^2) algorithms that can be reduced to O(2n) at the very least. One of the best things I gained from school was the red flag that fires off in my mind any time I see a loop nested in a loop.
  - TravHatesMe 7y ago
    O(2n) = O(n)
  - shantly 7y ago
    A little experience gets you that same red flag instinct in a hurry, too. [EDIT] it also makes you hesitate & second-guess and worry and experiment a bunch when contemplating using a recursive algorithm, which is deeply counterproductive in interviews where the expected behavior is so often "apply recursion, instantly and without hesitation" :-)
    - deleted 7y ago
      [deleted]
    - nikanj 7y ago
      Unfortunately interviews seem to be all about dogma, and if you even mention performance you will get dinged for premature optimization. It’s like a postmodern religion where premature optimization is the cardinal sin, and you are supposed to burn as many cycles as possible to demonstrate that you are of good faith
      - WorldMaker 7y ago
        On the flipside, I've met different sorts of interviewers that ding someone for writing something intentionally unoptimized in the spirit of avoiding premature optimization for algorithmic clarity, because don't they have rote knowledge that "x is faster". Dogma on every side of the fence. (Also, continuing proof that technical interviews will never be objective evaluations of skill.)
  - stevefan1999 7y ago
- Tade0 7y ago
  Or those two should have been combined into O(nlogn) via sorting.
  - 52-6F-62 7y ago
    Or if you've already made allowances for the memory usage, you can also check to see if you can write your O(n^2) nested loops as O(n) + O(n) depending on the shape of your data.
- masklinn 7y ago
  > it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. https://accidentallyquadratic.tumblr.com https://accidentallyquadratic.tumblr.com was / is pretty much an entire blog dedicated to this.
- jtolmar 7y ago
  Programming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, but you have to go out of your way and do something a bit weird to get an exponential run time.
  - kortilla 7y ago
    What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
    - esotericn 7y ago
      That's n^2.
    - reggieband 7y ago
      That is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time https://stackoverflow.com/questions/4317414/polynomial-time-...
      - justincredible 7y ago
        whoops is O(2^n)
    - _wldu 7y ago
      Two for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).
    - a1369209993 7y ago
      Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
      - trehalose 7y ago
- lmm 7y ago
  I don't think that's a real insight. You could equally say that O(n^3) should be a sweet spot because you can nest a loop 3 deep, and so on for n^4, n^5 and so on. But we don't see these cases making it out into the wild because they're caught in testing.
- wesammikhail 7y ago
  A useful heuristic from my CS professor: always treat every tab (indentation / complexity) to be equivalent to a cart that you are attaching your horse. Add enough carts (complexity) and you will soon be asking yourself why your horse isnt a nuclear reactor instead?
mehrdadn 7y ago
Speaking of O(n^2) algorithms (if it's OK for me to promote my own writing on this recently?): I recently illustrated how they can even occur as a result of algorithms being slow by a constant factor. I thought it might be useful for others, so I posted it here: https://news.ycombinator.com/item?id=21745911 https://news.ycombinator.com/item?id=21745911

lousken 7y ago

seems like building chrome is a loyal pain in the ass, so many bugs found in windows because of that :)

techntoke 7y ago
It's actually pretty easy and there are package manifest in Arch that shows you how.
- ComputerGuru 7y ago
  That’s just because someone went through that pain for you and scripted and packaged the entire procedure and rolled up most of the dependencies and their bills systems. I’ve done it from the official build directions without containers or prebuilt dependencies and “royal pain in the ass” is an understatement.
  - techntoke 7y ago
    Firefox is a nightmare to package that way.
    - ComputerGuru 7y ago
      That’s one nice side effect from the push to convert dependencies/components to pure rust, one at a time. Even if it doesn’t go all the way, each step hugely simplifies the build process and minimizes the list of (recursive) dependencies.

JonathonW 7y ago

Honestly, O(n^2) is probably okay for a diagnostic tool that's only meant to be run occasionally-- I'd like to know why Google's IT department felt the need to schedule it to run so frequently.

JoeAltmaier 7y ago
That could be underestimating the truly catastrophic nature of O(n^2). Blows up very very fast. From milliseconds to seconds to days to decades. Pretty much anything that grows at all, must not be subject to the terrible power of O(n^2)
btilly 7y ago
The problem is that available disk space is growing exponentially over the years with a current doubling time of around 18 months for flash drives. And therefore repository size has been as well. What today are 1 GB repositories fairly predictably will be 10+ GB repositories in 5 years. And 100+ GB in 10 years. Which means that the period of locking your computer predictably will go from minutes to hours to days in the same time period. What is kinda OK today is going to definitely not be OK going forward. This algorithm has to get fixed.
loeg 7y ago
It's sort of unclear why 3 billion bytes needs to be processed in an O(N^2) algorithm in the first place, but seems especially egregious in that it also blocks other processes from running. One other aspect of the issue is that it's unclear why that database is now so large. It seemed like different machines had different sized databases — perhaps one angle of the solution is trimming and vacuuming.
- brucedawson 7y ago
  Well, it doesn't block all other processes, but it sure did block a lot of them. I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.

peter_d_sherman 7y ago

Excerpt: "I decided that the interactions were too complex to be worth analyzing in detail, especially without any thread names to give clues about what the 25 different threads in svchost.exe (3024) were doing." Future OS/Compiler Programming Note: It would be nice if threads could be individually named and those thread names shown/slowed/stopped/debugged in whatever tool implements Task Manager like functionality...

retrovm 7y ago
POSIX threads can be individually named. They inherit the name of their creator if you don't set one.
- adzm 7y ago
  They can be named in Windows as well, and this author has made pleas for developers to do so.
  - jandrese 7y ago
    The caveat being the developers who are careful enough to name their threads and implement good debug hooks aren't the ones you get called on to fix their code.
- the-rc 7y ago
  As an aside, POSIX/Linux thread names have a limit of 16 bytes, which means 15 characters plus NULL. Speaking from experience, this can and will bite you when you need the names the most, if e.g. they are long, have just one or a handful of common prefixes and their creation is not entirely under your control.
colatkinson 7y ago
Already possible in Windows [0]. [0]: https://docs.microsoft.com/en-us/windows/win32/api/processthreadsapi/nf-processthreadsapi-setthreaddescription https://docs.microsoft.com/en-us/windows/win32/api/processth...
7y ago

rwmj 7y ago

I have my own O(n^2) blow-up story. Back in the day I wrote some Google AdWords analysis software in a functional language. Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. Anyway these were only used to load the analysis inputs which was written in an Excel spreadsheet (the customer insisted on this!), exported to a CSV and loaded into the software. The spreadsheet was only perhaps 5 rows so, whatever. One day I got a call from the customer that his analysis was taking 6 hours to run, for a program that should have finished in a fraction of a second. It turned out the customer had tried to load a 30,000 row spreadsheet of input. The program would on every loop iterate over the input association list, resulting in classic O(n^2) performance overall. After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.

masklinn 7y ago
Why would the code be "nowhere near as elegant"? Lack of a functional / persistent map? Because I'd expect all maps to provide roughly similar interfaces whether they're assoc lists, hashmaps, btrees, HAMT, …: iterate all entries, presence of a key, get value for key, insert (key, value), remove key (and value), possibly some other niceties on top (e.g. update value in-place, merge maps, …) but those are extras.
- marcosdumay 7y ago
  On my experience, moving away from a list of pairs add a parsing stage that one may be able to omit otherwise.
  - masklinn 7y ago
    I don't understand how or why. What's the "parsing stage"? You have an associative array, a key, a value, and a function to associate the k, v pair to the array. You're moving from let m' = (k, v) : m to let m' = insert k v m What there would make the code "nowhere near as elegant"?

stevefan1999 7y ago

Well, now this show how polynomial time isn't necessarily any better than O(2^n), or exponential time in reality. Once the k grew bigger in O(n^k), our modern machine will still struggle to run it.

loeg 7y ago
O(N^2) is strictly better than O(2^N). Per the article, this algorithm fell over at 3 billion bytes of data, but wasn't especially noticeable at 300 million bytes of data.
- saagarjha 7y ago
  Better from an theoretical perspective. Depending on n and any constant factors, one or the other may end up winning in reality.
  - loeg 7y ago
    In practice, not really either. Unless "N" isn't actually variable and is basically zero.
read_if_gay_ 7y ago
The point where polynomial time becomes impractical is far beyond the point where exponential becomes impractical. It's like for n=10 your smartphone can run an exponential algorithm instantly but for n=20 the fastest supercomputer on earth will take forever. Not true for polynomial.
actuator 7y ago
Not really. The n is huge, there is an enormous difference between an exponential complexity like O(2^n). Many algorithms are O(N^2) and are perfect for their use case. To see the difference. - 100^2 -> 10^4, 2^100 -> 10^10 - 1000^2 -> 10^6, 2^1000 -> 10^100 Look at the difference in order of growth. Just to give a very simplified comparison, your individual processor core can run about 10^9 simple instructions in a second.

radicalbyte 7y ago

Ten years ago the hash-map implementation in Internet Explorer was also O(n2). I had to inject javascript into some vendor code to avoid this after our production environment died. I ended up replacing the underlying hash-map into multiple smaller maps based on a hash of the items. So I'd have 50 maps of 1000 items instead of one map of 50000 items.

Etheryte 7y ago
I'm interested to know, what practical application did you load 50.000 items into the frontend for 10 years ago?
- masklinn 7y ago
  10 years ago is 2009. Large web applications had been breaking out of intranets (where they'd lived for quite some time at that point) for years at that point. GMail was launched in 2004, Google Maps in 2005 (that's also the year "AJAX" was coined) the JS library war was done and over with (jquery, prototype, mochikit, mootools, dojo, YUI, … were all released between 2005 and 2006). IE7 was 3 years old, Google Chrome was reaching its first year, IE8 was just released.
  - Etheryte 7y ago
    You seem to be missing the crux of the issue I was trying to address — even today, loading 50.000 items into a frontend application would be a very, very niche edge case. 10 years ago even more so. Tacking on arbitrary reference points from Wikipedia doesn't change any of that.
    - masklinn 7y ago
      > You seem to be missing the crux of the issue I was trying to address — even today, loading 50.000 items into a frontend application would be a very, very niche edge case. It's a medium-sized inventory, if you need fast / offline access then loading it to the client makes a lot of sense. I'm sure there are plenty other things of which you can easily reach 50k, and that you'd want to index or cross-reference somehow.

aneutron 7y ago

Reminds me of the time we found out a team was running O(n^2) code, but in terms of SQL Queries, that is to say, not O(n^2) of comparisons or anything, and were trying to blame the other team when a client sent a request that never ended. And they tried blaming them for migrating data to a new server with an SSD that shaved 20 minutes from their processing time. And if you're wondering, they refused to fix it because "it would need too many sprints" and "maybe we'll talk about it in a workshop". It's still not fixed.

72deluxe 7y ago
Funny that you used the word "team" when the outcome is anything but teamwork.

jedberg 7y ago

The thing that impresses me most about this writeup is how much instrumentation there is on Windows now. I stopped using Windows about 15 years ago, but I don't think this kind of analysis was possible back then. Or maybe I just didn't know the tools well enough?

AaronFriel 7y ago
15 years ago? You might have just missed it. Event Tracing for Windows gained a lot of functionality in Windows Vista, which some[1] have described as the most forward-looking and instrumental release in Windows history. Vista had a lot of flaws, but it introduced almost everything fundamental to Windows 7 to Windows 10, save perhaps the more recent developments in virtualization and containerization. From differential application-consistent full backups, to transparent full disk encryption, to the use of a TPM to verify boot integrity. Vista was a massive release, but also much maligned so maybe you didn't miss much leaving when you did. The tooling has certainly gotten a lot better since then, and so has Windows. Rather more recently, Windows has gained dtrace support: https://techcommunity.microsoft.com/t5/Windows-Kernel-Internals/DTrace-on-Windows/ba-p/362902 https://techcommunity.microsoft.com/t5/Windows-Kernel-Intern... [1] - See this self-described eulogy by @SwiftOnSecurity: https://twitter.com/SwiftOnSecurity/status/851857404891471872 https://twitter.com/SwiftOnSecurity/status/85185740489147187...
- jedberg 7y ago
  I never used Vista. My last Windows was XP. Vista is only 14 years old. :)
- sedatk 7y ago
  Vista's importance in Windows history can't be overstated. It's regarded as a failure in the end but it provided a great baseline for the releases following it. Windows 10 has a much better networking stack, update mechanism, device driver model, GUI etc, all thanks to Vista.
mixmastamyk 7y ago
Same here. WMI and perf counters have been around a long time though. I recently used Win10 for work and was amazed at the combination of awe-inspiring tech and plain awe-full complexity. Just the control panel goes four layers deep attempting to make things easier but in practice is several times harder to find options than it was in Win2k. If there were a distribution with all the corporate goals stripped out I'd jump on it.

gameswithgo 7y ago

In the world of database backed web apps a related pattern is asking the database for some rows for a table, and then asking the database from some more rows, based on each row you just got. Rather than joining it together into one query. Makes it into production but falls down eventually!

kbenson 7y ago
There are sometimes reasons why you don't want to join, such as large data parent row sizes that get repeated a lot in if there's a lot of child relations. But that should be two queries. One for all the parents, and one to get the children with a sub-select (or at worst a manually generated parent id list), and then you can join them manually (if actually needed and you can't just use the data sets as they are).
- somurzakov 7y ago
  you are right, APIs often use o(n) algorithms in an individual API call that is meant to execute once. what happens, is that API users start executing that endpoint N times and here it becomes O(n^2). people should remember that APIs are for CRUD calls. If you want batch reports - call a separate reporting endpoints that process data in large batches.
toast0 7y ago
I've actually had a lot of success going the other way. A database query with a join takes down production, so do a client side join, query one: get a bunch of ids from table A, query two: get a bunch of rows from table B, often as get one row from table B UNION get next row from table B etc. You can try using IN on the second query, but usually if that was going to work in a reasonable amount of time, your join would have also worked in a reasonable amount of time. The real problem people run into with the client side join is making it query one get a bunch of ids from table A, query two through N, get one row from B, with each query requiring a round trip. Even a pretty small client to server roundtrip of 1 ms gets nasty quick with repeated queries.
- 7y ago

zackmorris 7y ago

If you're building a library or framework, then just assume that worst-case performance will be encountered by your users, because you can't predict their use cases. So for example, I almost always use associative arrays (maps) instead of lists. I actually really wish there a MAPP language because I view the map as a potentially better abstraction than the list in LISP, but I digress. I also tend to use atomic operations instead of locks. Some good starting points for that are understanding how compare-and-swap (CAS) works, and also how functional programming with higher order functions and immutable variables works because that mindset greatly simplifies threading with no shared mutable state for the Actor model. Lazy evaluation is another good one. Also vector languages like Gnu Octave and MATLAB are good because they favor a level of abstraction above the bare-hands programming of C-style languages like C++ and Javascript so you tend to see that most algorithms are embarrassingly parallel at some level (especially the things we tend to think of as computationally expensive like multimedia processing). Also (this may be controversial) but I think that poor performance can be politically motivated. For example, I run Safari with Javascript disabled so I can have thousands of tabs open (it's disabled as I write this). But when I disable Javascript in Chrome, performance grinds to a halt. You can try it right now on the Mac by force quitting Chrome with a bunch of tabs open and relaunching it from Terminal.app with: open -a "Google Chrome" --args --disable-javascript Or manually with: https://www.computerhope.com/issues/ch000891.htm https://www.computerhope.com/issues/ch000891.htm I don't know what causes it, but my guess is that Google either wrote some of the loops under the assumption that Javascript would always be on, or they had a blind spot in their implementation because so much of their business model depends on ads having dynamic behavior. So when you're in a meeting and someone shouts down your concern about edge case performance because they don't see that as a priority, graciously humor them and then write your code the right way because you know that it doesn't take any longer than doing it the wrong way. You might catch some flack during code review so have a good excuse handy, something about trying it the other way but running into problems. Often I'll write the easy imperative solution in a comment above the simple functional solution or even put both solutions under a preprocessor directive or feature flag to leave it up to the team lead/project manager and have our keisters covered if/when something melts down.

deleted 7y ago
[deleted]

equalunique 7y ago

(not) discussed previously: https://news.ycombinator.com/item?id=21740589 https://news.ycombinator.com/item?id=21740589

rcthompson 7y ago

Probably the most important thing I learned about algorithmic complexity analysis in grad school was that N is not constant, but rather it grows over time (probably at an exponential rate). That is, as our computing power increases, we continue to aspire to analyze larger and larger data sets. So anything beyond O(n*log(n)) that works right now is more or less guaranteed to blow up in the not-so-distant future, if it remains in use that long.

ihaveajob 7y ago

This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.

Google234 7y ago
2^2^9 is 1.340781e+154
- mathgladiator 7y ago
  In this format, exponents are evaluated left to right, so this is 4^9 which is 262144 and is reasonable.
  - vecter 7y ago
    That's certainly not the standard. If anything, exponentiation is usually performed right to left, with some exceptions [0]. However, the fact that we even have carets in this conversation isn't because the GP wanted to adopt a left-to-right convention, but due to limitations in the richness of HN's text editor. If you write a tower of 2^2^9 on a whiteboard and ask 1000 mathematicians and computer scientists to evaluate it, I'm sure 999 or 1000 of them would evaluate it as 2^(2^9). [0] https://en.wikipedia.org/wiki/Order_of_operations#Serial_exponentiation https://en.wikipedia.org/wiki/Order_of_operations#Serial_exp...
    - mathgladiator 7y ago
      I'm a mathematician and a computer scientist, so I must be one in a thousand. The link even indicates that ambiguity exists in wild, and I think clear notation would help. In this case, the absurdity of the number suggests a more realistic number.
      - 7y ago

fourseventy 7y ago

I love this guys blog. Been reading it for a while. He is a beast.

vortico 7y ago

Batch scripts themselves are O(n^2) because the shell closes and reopens them after each line (even comments or even blank lines), and the scan to get to line `n` takes O(n) time and disk bandwidth.

concerned_user 7y ago
That is just plain incorrect, local variables would not work in scripts if that were the case.
- vortico 7y ago
  I definitely remember both reading about and experiencing this years ago, but I can't seem to find a source and it's driving me crazy (will search more later). I imagine variables would persist in the shell's memory. I'm talking about an implementation detail of the batch shell script parser/runner. I recall that some people would put GOTO statements to jump across large comment blocks in the days where reading a few KB was noticeable.
  - concerned_user 7y ago
    It can be correct if you are talking about subprocesses/subshells of another batch script/command then yes, separate shell process will be spawned in each iteration.
    - vortico 7y ago
      No, I recall reading that the batch processor closes/re-opens the file, scans for n carriage returns where n is the current line number, executes that line, and repeats. These are the sources I found. http://xset.tripod.com/tip3.htm http://xset.tripod.com/tip3.htm "COMMAND.COM reads and executes batch files one line at a time; that means that it reads one line, execute it and rereads the file from the beginning to the next line." Perhaps this is a really old version of COMMAND.COM? Perhaps it's poorly stated but actually meant that it "rereads the file from the beginning of the next line to the next line". https://docs.microsoft.com/en-us/windows/win32/fileio/local-caching https://docs.microsoft.com/en-us/windows/win32/fileio/local-... "Command processors read and execute a batch file one line at a time. For each line, the command processor opens the file, searches to the beginning of the line, reads as much as it needs, closes the file, then executes the line." This also seems to agree with my original claim. I tested this with a batch script generated by print("@echo off") for i in range(1000): for j in range(1000): print("rem hello world") print(f"echo {i}") and ran it using COMMAND.COM in a Windows 95's VM. It appears to run in linear time. Either COMMAND.COM was fixed, or both sources are incorrect.

ww520 7y ago

Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N, to get the job done quickly and simple enough to ensure correctness. Plus I could replace it later if needed. So it's done and forgotten. Things were working fine and performance was good. Then one day Windows Explorer suddenly hung with 100% CPU for couple seconds. This was one of the worst kind of bugs. There's no crash to pinpoint the problem. Things still work most of the times, just slowed down intermittently. Luckily I was able to catch a slowdown and deliberately crashed the process in time. The call trace stopped in the bubble sort function. I immediately kicked myself - it's the classic case of O(n^2) blowup. The cache entries had been scaled up to couple thousands items and the exponential O(n^2) blowup to tens of million of iterations was having a real impact. I switched to merge sort and performance was back to normal. Edit: I picked merge sort because the worst case was O(n log n), unlike quick sort whose worst case was O(n^2). Once burnt, needed to be extra careful with edge cases.

vecter 7y ago
n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
- ww520 7y ago
  You're correct n^2 is polynomial, not exponential. It was just an exaggerated figure of speech. BTW, O(n) and O(n log n) are also polynomial; it just doesn't have the punch to it.
  - paulddraper 7y ago
    So the more precise term would be quadratic. "Exponential" is indeed misused. Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.

kortilla 7y ago

Sounds like they’ll have to increase their leetcode requirements in the interviewing process. This is one of the “obvious fundamentals” that leetcode challenges screen for, right? /s

wakatime 7y ago

That's why latency is always measured in p99: https://stackoverflow.com/questions/12808934/what-is-p99-latency https://stackoverflow.com/questions/12808934/what-is-p99-lat...

tinus_hn 7y ago

Then again, your disk space, processing power and memory is cheap for Microsoft.

mark-r 7y ago

Any time I hear of an O(n^2) problem I remember Shlemiel the painter. https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/

hnick 7y ago

At work we had a daily script that took about 30 minutes to run, and about 3 hours on the weekend due to more data. One day we got a report that a downstream service was missing SLA because the script wasn't finishing. I'd come onto the team late so wasn't aware this was abnormal. It turns out it was now taking about 1-2 hours daily and 6-12 hours on the weekend depending on data size. This had been going on for months but gradually getting worse as the data grew, to the point it was unbearable so finally reported. A senior programmer had removed the shell call to sort on an indexed text file and written their own ad-hoc sorter through every fresh programmer's favourite (you guessed it) bubble sort. To make things worse, this was perl which has a perfectly functional sort itself if you really have to do it that way. I still have no idea why this was done, I don't think asking would have been productive in that place at that time.

codetrotter 7y ago

I have over a 100,000 images on my iPhone and some apps used to be really really really slow when I selected browse album in them. One of the apps that used to be maddeningly slow was Instagram, but Instagram has gotten better lately. No idea why though.

bokjack 7y ago

holly molly