Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

randomascii.wordpress.com

Post reply on HN
Print view View original

31–40 of 232 posts

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

#31

Post by masklinn »

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

They can. Dawson specifically notes that there are no thread names here because he regularly harps on that subject e.g. https://randomascii.wordpress.com/2015/10/26/thread-naming-i... and https://randomascii.wordpress.com/2019/10/20/63-cores-blocke... ("plea for thread names" in the conclusion)

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

#32

Post by masklinn »

rwmj wrote: post #23

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

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.

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

#33

Post by aneutron »

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.

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

#34

Post by TravHatesMe »

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.

O(2n) = O(n)

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

#35

Post by ComputerGuru »

crankylinuxuser wrote: post #4
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.

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

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

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

#36

Post by loeg »

stevefan1999 wrote: post #26

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.

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.

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

#37

Post by jedberg »

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?

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

#38

Post by loeg »

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.

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.

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

#39

Post by ComputerGuru »

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.

WMI is not a diagnostic tool. It’s an abstraction/API and lots of developers unfortunately the build over it rather than directly against the underlying WIN32 APIs.

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

#40

Post by marcosdumay »

masklinn wrote: post #32
rwmj wrote: post #23

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

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.

On my experience, moving away from a list of pairs add a parsing stage that one may be able to omit otherwise.
Post reply on HN