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

71–80 of 232 posts

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

#71

Post by Tyr42 »

stevefan1999 wrote: post #30
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.

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)

Yet, we understand exactly what he means. Sometimes it's useful to show an un-reduced intermediate step to facilitate understanding, even if you could reduce it further.

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

#72

Post by 52-6F-62 »

Tade0 wrote: post #19
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.

Or those two should have been combined into O(nlogn) via sorting.

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.

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

#73

Post by [deleted] »

zackmorris wrote: post #48

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

[deleted]

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

#74

Post by aflag »

protomikron wrote: post #69
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.

> Eh, you're technically correct [...] The best kind of correct. Calling it O(n) then is the best way to express the performance improvement - I think that's the whole point of Big-O notation. However I agree that for smaller n one should not underestimate the constant factor impact.

The point was that you can often convert nested loops into two loops that are not nested. O(2n) conveys that, O(n) does not.

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

#75

Post by vecter »

ihaveajob wrote: post #67

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.

Could you explain more? As the other commenter pointed out, 2^2^9 = 2^512 which is an astronomically large number (far more than the number of atoms of ordinary matter in the observable universe). Something doesn't seem right.

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

#77

Post by bobbyi_settv »

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

That would help, but I think the root problem here (of the debugging difficulty, not the actual perf problem) is the Windows approach of having lots of unrelated services running together in a single process (svchost)

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

#79

Post by ww520 »

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.

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

#80

Post by Someone1234 »

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.

He used that to manually reproduce, but the original behaviour wasn't caused by manually calling the winmgmt executable with the /verifyrepository switch.

Instead the repo was being verified as a side effect of another WMI operation.

Post reply on HN