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

51–60 of 232 posts

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

#51

Post by cross_wiber »

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.

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.

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

#52

Post by nikanj »

shantly wrote: post #21
savingGrace wrote: post #14

Earlier quoted context omitted.

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

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

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

#53

Post by masklinn »

Etheryte wrote: post #49
masklinn wrote: post #43

Earlier quoted context omitted.

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…

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.

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

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

#54

Post by masklinn »

cogman10 wrote: post #42
masklinn wrote: post #32

Earlier quoted context omitted.

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.

The one benefit of n^2 is it is really easy to do without any additional memory or data structure requirements. To make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc. I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "…

That still makes no sense. The GP is literally just talking about switching from an association list to a hashmap:

> Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.

You're not tracking more things (just tracking a hashmap instead of a list), you're not generating anything different, you don't have any new concept to track.

All I'm asking is where the apparently significant loss of elegance would come from.

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

#55

Post by jandrese »

adzm wrote: post #20
retrovm wrote: post #15

Earlier quoted context omitted.

POSIX threads can be individually named. They inherit the name of their creator if you don't set one.

They can be named in Windows as well, and this author has made pleas for developers to do so.

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.

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

#57

Post by AaronFriel »

jedberg wrote: post #37

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?

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

[1] - See this self-described eulogy by @SwiftOnSecurity: https://twitter.com/SwiftOnSecurity/status/85185740489147187...

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

#58

Post by rcthompson »

masklinn wrote: post #45
marcosdumay wrote: post #40

Earlier quoted context omitted.

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

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"?

It's a function of the language. If you're working a Lisp, association lists are very much the "default" for mappings, and the style of code built around them is very clear as a result (in most lisp-like languages, at least). For example, there's no special constructor for an alist: you just create a list, which can be done using the lisp syntax itself. Whereas for something like a hash table, you likely have to call a constructor or something. It's all just a consequence of lisp's syntax and structure being largely built around list manipulation.

In contrast, languages like Perl or Python have literals and syntax support for both lists and mapping-type data structures (hashes in Perl, dicts in Python), so using either one is roughly equally elegant, and you are more free to choose one or the other based on performance concerns.

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

#59

Post by jtolmar »

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.

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.

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

#60

Post by JonathonW »

ComputerGuru wrote: post #39
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.

'winmgmt.exe /verifyrepository', the tool with the O(n^2) behavior, is a diagnostic tool-- it verifies the consistency of the WMI repository.
Post reply on HN