O(n^2), again, now in Windows Management Instrumentation • Hacker News Board

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

#21

Post by shantly » Mon, Dec 09, 2019, 4:58 PM UTC

savingGrace wrote: post #14

rcthompson wrote: post #3

Earlier quoted context omitted.

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.

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.

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

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

#22

Post by albertzeyer » Mon, Dec 09, 2019, 4:58 PM UTC

muststopmyths wrote: post #18

peter_d_sherman wrote: post #12

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

This already exists. Windows had a janky way of naming threads before 10, but it has a supported API now. The problem is that svchost is a host that runs a thread pool with various services being invoked as needed. You'd have to rename each thread every time you ran a function for a service. That's probably more doable now with the supported API. The previous way involved raising an exception, so I can see why it was…

For reference, this was the old API: https://docs.microsoft.com/en-us/visualstudio/debugger/how-t...

This was well known, and many applications actually used that. Of course it was very ugly. I don't think it would have been a problem to also rename a given thread multiple times, but not sure.

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

#23

Post by rwmj » Mon, Dec 09, 2019, 4:59 PM UTC

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.

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

#24

Post by techntoke » Mon, Dec 09, 2019, 5:02 PM UTC

lousken wrote: post #6

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

It's actually pretty easy and there are package manifest in Arch that shows you how.

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

#25

Post by btilly » Mon, Dec 09, 2019, 5:11 PM UTC

JonathonW wrote: post #9

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.

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.

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

#26

Post by stevefan1999 » Mon, Dec 09, 2019, 5:20 PM UTC

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.

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

#27

Post by masklinn » Mon, Dec 09, 2019, 5:21 PM UTC

rcthompson wrote: post #3

harikb wrote: post #2

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

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.

> 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 was / is pretty much an entire blog dedicated to this.

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

#28

Post by radicalbyte » Mon, Dec 09, 2019, 5:22 PM UTC

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.

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

#29

Post by Etheryte » Mon, Dec 09, 2019, 5:24 PM UTC

radicalbyte wrote: post #28

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.

I'm interested to know, what practical application did you load 50.000 items into the frontend for 10 years ago?

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

#30

Post by stevefan1999 » Mon, Dec 09, 2019, 5:27 PM UTC

savingGrace wrote: post #14

rcthompson wrote: post #3

Earlier quoted context omitted.

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.

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.

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)