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

81–90 of 232 posts

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

#81

Post by baddox »

TravHatesMe wrote: post #66
vanderZwan wrote: post #61

Earlier quoted context omitted.

Eh, you're technically correct but when used as a point of relative comparison to an O(n²) algorithm I think there's some merit to it, because it actually gives some sense of constant overhead within the context.

What if the constant were massive? Then the coefficient might not be significant in practise. O(2n) might be worse than O(n+99999999), they both reduce to O(n) though. It is a classification. Personally I would prefer to use different semantics to express that. It seems big O notation often carries a separate meaning in parlance. I thought big O notation was about classifying function growth irrespective of the coeff…

If constant factors are significant in practice and the size of the input is not significant, then big O notation is not the right tool for the analysis, and that's perfectly fine. For instance, we generally don't talk about big O notation when comparing the performance of SSDs and spinning HDs.

Big O notation is for describing how the performance of an algorithm changes as the size of its input changes. If the size of the input is not a significant concern, then it's totally fine to not use big O notation for analyzing the problem.

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

#83

Post by laszlokorte »

Etheryte wrote: post #29
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?

Almost 10 years ago (2010) I built a virtual table scroller in javascript for editing spreadsheet of 100 columns by 10.000 rows in the browser.

I learned that just replacing the whole page's innerHTML by a concatinated string on each frame/mousewheel event is way faster then updating the cells content and position individually, and resuls in butter smooth scrolling.

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

#84

Post by somurzakov »

kbenson wrote: post #50
gameswithgo wrote: post #46

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!

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

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.

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

#85

Post by marcosdumay »

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

I don't get the downvoting for not understanding.

But well. In Haskell assotiation lists are also the default, as they don't impose any stictness and are very fast to iterate. So that is what you get from libraries.

If you need a map, you will have to first construct it, then run your code. But of course, if you are the one creating the lists, it does change very little.

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

#87

Post by jedberg »

AaronFriel wrote: post #57
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 differenti…

I never used Vista. My last Windows was XP. Vista is only 14 years old. :)

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

#88

Post by kortilla »

jtolmar wrote: post #59
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.

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.

What? It’s trivial to go exponential.

  for i in n:
      for j in n:
          whoops(i, j)

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

#89

Post by ComputerGuru »

JonathonW wrote: post #60
ComputerGuru wrote: post #39

Earlier quoted context omitted.

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.

That’s just a manifestation of the issue and not necessarily the only symptom. Dawson used it to explicitly illustrate the wbem size to slowdown effect.

The reason I’m hating on developers that use WMI when alternatives are available is because WMI is dog slow and everyone that does low-level Windows development knows it.

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

#90

Post by aflag »

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.

50k items seems actually quite small. Front loading data can make your app look a lot snappier at the cost of a slightly longer load time. It may be worth it in many situations.
Post reply on HN