5 ms·

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

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.

JoeAltmaier 7y ago
That could be underestimating the truly catastrophic nature of O(n^2). Blows up very very fast. From milliseconds to seconds to days to decades. Pretty much anything that grows at all, must not be subject to the terrible power of O(n^2)
btilly 7y ago
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.
loeg 7y ago
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.
- brucedawson 7y ago
  Well, it doesn't block all other processes, but it sure did block a lot of them. I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.
  - acqq 7y ago
    > I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. Exactly. It's 1.9 GB on your machine, whereas on a plain home-use computer it's less than 50 MB, i.e 40 times smaller. Something produces all that data there, what is that, and what's that that's being stored?
ComputerGuru 7y ago
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.
- JonathonW 7y ago
  'winmgmt.exe /verifyrepository', the tool with the O(n^2) behavior, is a diagnostic tool-- it verifies the consistency of the WMI repository.
  - Someone1234 7y ago
    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.
    - tedunangst 7y ago
      It sure sounded like they had a scheduled task to run it manually every hour. "Until then our IT department has promised to stop running the /verifyrepository command every hour, which should avoid the worst symptoms."
    - brucedawson 7y ago
      I believe that the repo gets verified automatically as a daily thing, but our IT department was verifying it hourly. They have stopped. I think that the hourly verification was put in to try to diagnose some problems that were actually or suspected to be related to WMI corruption. Even daily verification is going to cause problems, they are just less likely to be noticed, until they get to the 30+ minutes level.
  - ComputerGuru 7y ago
    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.
jandrese 7y ago
That's the part that seemed insane to me. Dial it back so it only runs at 4AM every day and nobody would have noticed. Running it every hour seems like outright paranoia by the IT staff.
deleted 7y ago
[deleted]

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.

JoeAltmaier 7y ago

That could be underestimating the truly catastrophic nature of O(n^2). Blows up very very fast. From milliseconds to seconds to days to decades. Pretty much anything that grows at all, must not be subject to the terrible power of O(n^2)

btilly 7y ago

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.

loeg 7y ago

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.

brucedawson 7y ago
Well, it doesn't block all other processes, but it sure did block a lot of them. I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.
- acqq 7y ago
  > I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. Exactly. It's 1.9 GB on your machine, whereas on a plain home-use computer it's less than 50 MB, i.e 40 times smaller. Something produces all that data there, what is that, and what's that that's being stored?

ComputerGuru 7y ago

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.

JonathonW 7y ago
'winmgmt.exe /verifyrepository', the tool with the O(n^2) behavior, is a diagnostic tool-- it verifies the consistency of the WMI repository.
- Someone1234 7y ago
  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.
  - tedunangst 7y ago
    It sure sounded like they had a scheduled task to run it manually every hour. "Until then our IT department has promised to stop running the /verifyrepository command every hour, which should avoid the worst symptoms."
  - brucedawson 7y ago
    I believe that the repo gets verified automatically as a daily thing, but our IT department was verifying it hourly. They have stopped. I think that the hourly verification was put in to try to diagnose some problems that were actually or suspected to be related to WMI corruption. Even daily verification is going to cause problems, they are just less likely to be noticed, until they get to the 30+ minutes level.
- ComputerGuru 7y ago
  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.

jandrese 7y ago

That's the part that seemed insane to me. Dial it back so it only runs at 4AM every day and nobody would have noticed. Running it every hour seems like outright paranoia by the IT staff.

deleted 7y ago

[deleted]