16 ms·

O(N^2) in CreateProcess

154 points by nikbackm 7y ago

magicalhippo 7y ago
One thing I really miss in a lot of library documentation is performance guarantees similar to that of the C++ standard library. Yes yes, this method lets me find the index of an element, but is it O(log N) or O(N)? I need to know, otherwise I might inadvertently create O(N^2) code.
- rightbyte 7y ago
  Yes that would be nice but the O(...) notation is not very useful for choosing algorithms unless you also compare how eg. a O(n) algorithm compares to a O(n^2) given a certain amount of nodes to compute.
  - fluffything 7y ago
    Complexity bounds do not answer the question of how fast an algorithm or a particular implementation of it is. I don't think anybody claimed that, and that was actually not the problem here. The problem here is that the implementation exploded when passed an input Nx larger in production than what the implementation was tested with. Complexity bounds would have prevented that problem because "maybe process creating shouldn't be O(N^2)". So sure, choose an O(N^2) algorithm if its faster than an O(N) one for small enough N, there is nothing wrong with that. But don't do that if the size of the input does not depend on you (or fall back to a O(N) algo for very large inputs). People doing this is why DDoS are a thing: my O(N^3) server was very fast for 100 connections, who would have thought that someone would DDoS it with 1000 connections - yeah, who would have thought about that, 1000 connections isn't even a real DoS, but whatever.
    - rightbyte 7y ago
      Yes I agree. What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects like cache misses (cache size) etc is not taken into consideration and further more the range of n:s for which each algorithm is fastest is often ignored. Some dummy numbers: T1 = 0.0000001 n^2 + n T2 = 100000000 n Would yield: O1(n^2) O2(n) Long before n is big enough for a hypothetical server running the O(n^2) algorithm to be slower than the O(n) other effects might cap it. The best way to find out is empirical testing.
      - jnurmine 7y ago
        Isn't the point the order of growth...? If you double the input size, O(N) will run twice as long, whereas O(N^2) four times as long.
        rightbyte 7y ago
        No, that's only true at the limit as n goes towards infinity. And even if you see it as a approximation of growth for big n:s, you need to know "twice what" and "four times what" and "what's a big n" to have any use from it. For the example with multiplication of 2 n-digit numbers: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm It's O(n^1.585). Need about 1000 digits before it's actually faster than "School book" O(n^2) multiplication. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... It's O(n log n log log n). In practice faster than Karatsuba at 10,000 to 40,000 decimal digits. Then there is the newest and hottest O(n log n) version, that's not practical at all.
        brucedawson 7y ago
        Sure, there are some cases where O() can be misleading, but those are the exceptions. You can work in software for a long time without being affected significantly by them, whereas using O(n^2) when you could use O(n) can make your code 1,000 times slower than usable, and it does this frequently. I have fixed hundreds of O(n^2) algorithms over the years, made them O(n) or O(n log(n)), and made the product dramatically better. The fact that an O(n) algorithm can sometimes be slower than an O(n^2) feels more like pedantry than useful information in this context.
  - magicalhippo 7y ago
    The point is that for most cases I'm dealing with things that are not extremely performance sensitive (ie every ms doesn't count), but which should handle arbitrary user input without grinding to a halt. If I need a combination, I can always check for small N and call a different implementation.
- consp 7y ago
  I'm more interested in the lower, "average" (random input), sequential and empty set bounds as they tend get close, in certain instances (e.g. large memory space required, only efficient on ordered data etc), to the upper bound. If your algorithm for function is O(n^2) in theory but has an lower average bound of O(N log N) which almost always is used on your input data, it might be a good thing to sanitize the input and use it anyways (looking at you quicksort).
  - scott_s 7y ago
    To put names to what you're asking for: best-case, average-case and worst-case analysis. All are valid ways to characterize algorithms.
    - kadoban 7y ago
      Average-case can be quite an odd beast. You have to be careful what you are averaging over -- what distribution you're assuming in the analysis. For example for quicksort, if you implement it such that it always pivots on the first element of the range to be sorted, that could be average-case O(n lg n) if I consider all possible orderings of the inputs of the given size, but if I usually call it with an almost sorted array, that's not the average behavior I'm going to see by any means. So in most cases it ends up being a pretty leaky and dangerous contract that your function is providing, with average-case analysis. You have to know deep details of how it's working. An often better way to go, when it's possible, is to use expected-time. So again using quicksort as an example, this would mean the algorithm randomly chooses a pivot in the given range. The difference now is, the worst-case is still O(n^2), but there's no input I can give it (accidentally or intentionally) that will trigger that behavior, I'd have to get insanely unlucky for that to happen on a large input.
      - scott_s 7y ago
        I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distributions: when you're doing analysis of a particular operation being called a bunch of times, versus once. In such cases, average-case can yield amortized analysis which still makes no assumption of the input distribution. I'm co-author on a paper which does that: https://www.scott-a-s.com/files/debs2017_daba.pdf https://www.scott-a-s.com/files/debs2017_daba.pdf. In that work, we present a sliding window aggregation algorithm for worst-case constant time, but we compare against ones that are average-case constant time. The average-case constant algorithms are better on throughput, but worst-case constant is better on latency.
- bjoli 7y ago
  Scheme requests for implementation often have this specified, soo for example https://srfi.schemers.org/srfi-140/srfi-140.html https://srfi.schemers.org/srfi-140/srfi-140.html It specifies it for every procedure (the preface says that procedures that don't specify asymptotic performance run in O(n).
- JoeAltmaier 7y ago
  I'd like a lot more than that! Including memory promises (who frees associated buffers/handles), critical-sections involved in the call, and where it can be called from (user space? kernel? interrupt routine/driver? callback? hyperthread affinity?)
rightbyte 7y ago
Maybe he should have split his 120Mb executable into more executables ... or using a sane number of processes. It would be bad to have the OS cover this use case by default.
- deleted 7y ago
  [deleted]
- AstralStorm 7y ago
  You do understand that windows creates about 1000 processes on boot alone? A clean start? (Of those about 100 survive as services.) In short this fail adds as much as 10 seconds to boot time? (Sort of hidden on most hardware by parallelism, but if you have something not super recent, well...)
  - rightbyte 7y ago
    Yes, but he creates 1000 processes of the same executable with different arguments to run different tests as I understand it. With a really big executable. That's not the same thing as it's slow to add normal sized processes.
    - mort96 7y ago
      That's not out of the ordinary though? Any time you compile C or C++ code, you're creating a process from the same GCC/Clang/whatever executable but with different arguments for each source file. For a big project, it's not uncommon for there to be thousands or tens of thousands of small source files. Creating and maintaining processes is the core responsibility of an operating system.
      - rightbyte 7y ago
        gcc is like 1Mb. It would be interesting if he did the same test on Debian or something with default options. I would personally link in the tests as a shared lib or something. chrome.exe on my laptop is around 1Mb. That would probably speed up his tests more than his hacks to the validation routine.
nonsince 7y ago
I absolutely love this series
w8rbt 7y ago
O(n^2) is polynomial and perfectly acceptable for many use cases. Basic multiplication is O(n^2), as are many other operations. for i = 1 -> n: for j = 1 -> n: do something Although, if the outside n differs in size from the inside n, it should be written O(nm).
- Sharlin 7y ago
  In this case it doesn't seem to be. Although admittedly executables as large as in the article are rare, process creation on Windows is slow enough as it is, without extra inefficiencies. As an aside, basic multiplication is O(n^2) only if your number type is arbitrarily wide. Standard 32-bit or 64-bit multiplication as implemented in hardware is constant time.
  - w8rbt 7y ago
    Right, it's a pity RSA does not use 32 or 64 bit ints.
    - BubRoss 7y ago
      What does that have to do with anything? The original thread was about performance guarantees of API functions.
  - rightbyte 7y ago
    It's tautological to state that for a fixed number of nodes, mutliplication is constant time. Off course it is. The n is fixed. Also as a side note, n^2 is not the lowest order algorithm for multiplication.
    - enedil 7y ago
      No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.
      - 7y ago
varelaz 7y ago
Why someone needs 1000 created processes on one server? I worked with IO and CPU bound tasks and never needed more than ~50 processes, even on very big servers. Is there any practical reason for this (besides pure interest)?
- seba_dos1 7y ago
  The article literally answers that. It's very common for unit tests and building infra, especially when ported from POSIX systems.
  - MaulingMonkey 7y ago
    And as for why you might want to spawn processes in these cases - it helps isolate memory corruption, other unrecoverable process failures, or even just issues like memory fragmentation to a specific unit test / file build - so that issues building/testing X don't show up as intermitent failures that get misattributed to building/testing Y. As a workaround for perf issues like the article, you might choose to reuse the same process more instead, but it's a tradeoff.
  - varelaz 7y ago
    Sorry, I thought problem is with thousands parallel processes execution. There problem is with some remainings from previous process runs.
    - seba_dos1 7y ago
      ...or with the fact that they're constantly being created and destroyed as some tests/build tasks finish and the new ones are spawned.
- brucedawson 7y ago
  When building Chrome from source code our build system creates about 70,000 processes. This is enough that, even without CFG issues, process-creation time is a factor in the minimum build time.
charleslmunger 7y ago
It's very easy to accidentally create O(n^2) code. For example, take a look at the test case added here: https://github.com/google/guava/commit/4e41d621c3f413eb31da2d31b6c9d9713cd851f6 https://github.com/google/guava/commit/4e41d621c3f413eb31da2...
peter_d_sherman 7y ago
It looks like the author of this article tested with Windows 7 and Windows 10. What would be really interesting is if the same tests could be performed with all of the other, older versions of Windows... why? Well, then you'd know the version of Windows in which this phenomena first appears (it could not possibly have existed in Windows 1.0 and probably didn't exist until several subsequent versions later). So that knowledge of where it first appears could be interesting... That is, I'd love a Raymond Chen deep-dive explanation for the Microsoft "why" of this phenomenon...
- garaetjjte 7y ago
  It is caused by Control Flow Guard introduced in 8.1, so there's no point testing other versions.
kristianp 7y ago
This article is about the Control Flow Guard [1] security feature introduced in Win 8.1. The same blog has a few articles about it. Seems that it wasn't performance tested against large binaries in its original development. [1] https://docs.microsoft.com/en-us/windows/desktop/secbp/control-flow-guard https://docs.microsoft.com/en-us/windows/desktop/secbp/contr...
- aneutron 7y ago
  Seeing how many O(n^2) he found, I think you could've stopped your sentence at tested.
brucedawson 7y ago
Update: Microsoft has built a fix for the issue. https://twitter.com/mamyun/status/1120878048620892166 https://twitter.com/mamyun/status/1120878048620892166 Pretty quick work - two days after the blog post.

154 points by nikbackm 7y ago

One thing I really miss in a lot of library documentation is performance guarantees similar to that of the C++ standard library. Yes yes, this method lets me find the index of an element, but is it O(log N) or O(N)? I need to know, otherwise I might inadvertently create O(N^2) code.

rightbyte 7y ago
Yes that would be nice but the O(...) notation is not very useful for choosing algorithms unless you also compare how eg. a O(n) algorithm compares to a O(n^2) given a certain amount of nodes to compute.
- fluffything 7y ago
  Complexity bounds do not answer the question of how fast an algorithm or a particular implementation of it is. I don't think anybody claimed that, and that was actually not the problem here. The problem here is that the implementation exploded when passed an input Nx larger in production than what the implementation was tested with. Complexity bounds would have prevented that problem because "maybe process creating shouldn't be O(N^2)". So sure, choose an O(N^2) algorithm if its faster than an O(N) one for small enough N, there is nothing wrong with that. But don't do that if the size of the input does not depend on you (or fall back to a O(N) algo for very large inputs). People doing this is why DDoS are a thing: my O(N^3) server was very fast for 100 connections, who would have thought that someone would DDoS it with 1000 connections - yeah, who would have thought about that, 1000 connections isn't even a real DoS, but whatever.
  - rightbyte 7y ago
    Yes I agree. What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects like cache misses (cache size) etc is not taken into consideration and further more the range of n:s for which each algorithm is fastest is often ignored. Some dummy numbers: T1 = 0.0000001 n^2 + n T2 = 100000000 n Would yield: O1(n^2) O2(n) Long before n is big enough for a hypothetical server running the O(n^2) algorithm to be slower than the O(n) other effects might cap it. The best way to find out is empirical testing.
    - jnurmine 7y ago
      Isn't the point the order of growth...? If you double the input size, O(N) will run twice as long, whereas O(N^2) four times as long.
      - rightbyte 7y ago
        No, that's only true at the limit as n goes towards infinity. And even if you see it as a approximation of growth for big n:s, you need to know "twice what" and "four times what" and "what's a big n" to have any use from it. For the example with multiplication of 2 n-digit numbers: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm It's O(n^1.585). Need about 1000 digits before it's actually faster than "School book" O(n^2) multiplication. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... It's O(n log n log log n). In practice faster than Karatsuba at 10,000 to 40,000 decimal digits. Then there is the newest and hottest O(n log n) version, that's not practical at all.
        brucedawson 7y ago
        Sure, there are some cases where O() can be misleading, but those are the exceptions. You can work in software for a long time without being affected significantly by them, whereas using O(n^2) when you could use O(n) can make your code 1,000 times slower than usable, and it does this frequently. I have fixed hundreds of O(n^2) algorithms over the years, made them O(n) or O(n log(n)), and made the product dramatically better. The fact that an O(n) algorithm can sometimes be slower than an O(n^2) feels more like pedantry than useful information in this context.
- magicalhippo 7y ago
  The point is that for most cases I'm dealing with things that are not extremely performance sensitive (ie every ms doesn't count), but which should handle arbitrary user input without grinding to a halt. If I need a combination, I can always check for small N and call a different implementation.
consp 7y ago
I'm more interested in the lower, "average" (random input), sequential and empty set bounds as they tend get close, in certain instances (e.g. large memory space required, only efficient on ordered data etc), to the upper bound. If your algorithm for function is O(n^2) in theory but has an lower average bound of O(N log N) which almost always is used on your input data, it might be a good thing to sanitize the input and use it anyways (looking at you quicksort).
- scott_s 7y ago
  To put names to what you're asking for: best-case, average-case and worst-case analysis. All are valid ways to characterize algorithms.
  - kadoban 7y ago
    Average-case can be quite an odd beast. You have to be careful what you are averaging over -- what distribution you're assuming in the analysis. For example for quicksort, if you implement it such that it always pivots on the first element of the range to be sorted, that could be average-case O(n lg n) if I consider all possible orderings of the inputs of the given size, but if I usually call it with an almost sorted array, that's not the average behavior I'm going to see by any means. So in most cases it ends up being a pretty leaky and dangerous contract that your function is providing, with average-case analysis. You have to know deep details of how it's working. An often better way to go, when it's possible, is to use expected-time. So again using quicksort as an example, this would mean the algorithm randomly chooses a pivot in the given range. The difference now is, the worst-case is still O(n^2), but there's no input I can give it (accidentally or intentionally) that will trigger that behavior, I'd have to get insanely unlucky for that to happen on a large input.
    - scott_s 7y ago
      I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distributions: when you're doing analysis of a particular operation being called a bunch of times, versus once. In such cases, average-case can yield amortized analysis which still makes no assumption of the input distribution. I'm co-author on a paper which does that: https://www.scott-a-s.com/files/debs2017_daba.pdf https://www.scott-a-s.com/files/debs2017_daba.pdf. In that work, we present a sliding window aggregation algorithm for worst-case constant time, but we compare against ones that are average-case constant time. The average-case constant algorithms are better on throughput, but worst-case constant is better on latency.
bjoli 7y ago
Scheme requests for implementation often have this specified, soo for example https://srfi.schemers.org/srfi-140/srfi-140.html https://srfi.schemers.org/srfi-140/srfi-140.html It specifies it for every procedure (the preface says that procedures that don't specify asymptotic performance run in O(n).
JoeAltmaier 7y ago
I'd like a lot more than that! Including memory promises (who frees associated buffers/handles), critical-sections involved in the call, and where it can be called from (user space? kernel? interrupt routine/driver? callback? hyperthread affinity?)

rightbyte 7y ago

Maybe he should have split his 120Mb executable into more executables ... or using a sane number of processes. It would be bad to have the OS cover this use case by default.

deleted 7y ago
[deleted]
AstralStorm 7y ago
You do understand that windows creates about 1000 processes on boot alone? A clean start? (Of those about 100 survive as services.) In short this fail adds as much as 10 seconds to boot time? (Sort of hidden on most hardware by parallelism, but if you have something not super recent, well...)
- rightbyte 7y ago
  Yes, but he creates 1000 processes of the same executable with different arguments to run different tests as I understand it. With a really big executable. That's not the same thing as it's slow to add normal sized processes.
  - mort96 7y ago
    That's not out of the ordinary though? Any time you compile C or C++ code, you're creating a process from the same GCC/Clang/whatever executable but with different arguments for each source file. For a big project, it's not uncommon for there to be thousands or tens of thousands of small source files. Creating and maintaining processes is the core responsibility of an operating system.
    - rightbyte 7y ago
      gcc is like 1Mb. It would be interesting if he did the same test on Debian or something with default options. I would personally link in the tests as a shared lib or something. chrome.exe on my laptop is around 1Mb. That would probably speed up his tests more than his hacks to the validation routine.

nonsince 7y ago

I absolutely love this series

w8rbt 7y ago

O(n^2) is polynomial and perfectly acceptable for many use cases. Basic multiplication is O(n^2), as are many other operations. for i = 1 -> n: for j = 1 -> n: do something Although, if the outside n differs in size from the inside n, it should be written O(nm).

Sharlin 7y ago
In this case it doesn't seem to be. Although admittedly executables as large as in the article are rare, process creation on Windows is slow enough as it is, without extra inefficiencies. As an aside, basic multiplication is O(n^2) only if your number type is arbitrarily wide. Standard 32-bit or 64-bit multiplication as implemented in hardware is constant time.
- w8rbt 7y ago
  Right, it's a pity RSA does not use 32 or 64 bit ints.
  - BubRoss 7y ago
    What does that have to do with anything? The original thread was about performance guarantees of API functions.
- rightbyte 7y ago
  It's tautological to state that for a fixed number of nodes, mutliplication is constant time. Off course it is. The n is fixed. Also as a side note, n^2 is not the lowest order algorithm for multiplication.
  - enedil 7y ago
    No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.
    - 7y ago

varelaz 7y ago

Why someone needs 1000 created processes on one server? I worked with IO and CPU bound tasks and never needed more than ~50 processes, even on very big servers. Is there any practical reason for this (besides pure interest)?

seba_dos1 7y ago
The article literally answers that. It's very common for unit tests and building infra, especially when ported from POSIX systems.
- MaulingMonkey 7y ago
  And as for why you might want to spawn processes in these cases - it helps isolate memory corruption, other unrecoverable process failures, or even just issues like memory fragmentation to a specific unit test / file build - so that issues building/testing X don't show up as intermitent failures that get misattributed to building/testing Y. As a workaround for perf issues like the article, you might choose to reuse the same process more instead, but it's a tradeoff.
- varelaz 7y ago
  Sorry, I thought problem is with thousands parallel processes execution. There problem is with some remainings from previous process runs.
  - seba_dos1 7y ago
    ...or with the fact that they're constantly being created and destroyed as some tests/build tasks finish and the new ones are spawned.
brucedawson 7y ago
When building Chrome from source code our build system creates about 70,000 processes. This is enough that, even without CFG issues, process-creation time is a factor in the minimum build time.

charleslmunger 7y ago

It's very easy to accidentally create O(n^2) code. For example, take a look at the test case added here: https://github.com/google/guava/commit/4e41d621c3f413eb31da2d31b6c9d9713cd851f6 https://github.com/google/guava/commit/4e41d621c3f413eb31da2...

peter_d_sherman 7y ago

It looks like the author of this article tested with Windows 7 and Windows 10. What would be really interesting is if the same tests could be performed with all of the other, older versions of Windows... why? Well, then you'd know the version of Windows in which this phenomena first appears (it could not possibly have existed in Windows 1.0 and probably didn't exist until several subsequent versions later). So that knowledge of where it first appears could be interesting... That is, I'd love a Raymond Chen deep-dive explanation for the Microsoft "why" of this phenomenon...

garaetjjte 7y ago
It is caused by Control Flow Guard introduced in 8.1, so there's no point testing other versions.

kristianp 7y ago

This article is about the Control Flow Guard [1] security feature introduced in Win 8.1. The same blog has a few articles about it. Seems that it wasn't performance tested against large binaries in its original development. [1] https://docs.microsoft.com/en-us/windows/desktop/secbp/control-flow-guard https://docs.microsoft.com/en-us/windows/desktop/secbp/contr...

aneutron 7y ago
Seeing how many O(n^2) he found, I think you could've stopped your sentence at tested.

brucedawson 7y ago

Update: Microsoft has built a fix for the issue. https://twitter.com/mamyun/status/1120878048620892166 https://twitter.com/mamyun/status/1120878048620892166 Pretty quick work - two days after the blog post.