O(N^2) in CreateProcess(randomascii.wordpress.com)
randomascii.wordpress.com
O(N^2) in CreateProcess
https://randomascii.wordpress.com/2019/04/21/on2-in-createprocess/
9 comments
Scheme requests for implementation often have this specified, soo for example 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).
It specifies it for every procedure (the preface says that procedures that don't specify asymptotic performance run in O(n).
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?)
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).
To put names to what you're asking for: best-case, average-case and worst-case analysis. All are valid ways to characterize algorithms.
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.
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.
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. 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.
I'm co-author on a paper which does that: 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.
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.
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.
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.
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.
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.
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.
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 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%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.
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 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%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.
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.
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.
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.
If I need a combination, I can always check for small N and call a different implementation.
I absolutely love this series
Update: Microsoft has built a fix for the issue.
https://twitter.com/mamyun/status/1120878048620892166
Pretty quick work - two days after the blog post.
https://twitter.com/mamyun/status/1120878048620892166
Pretty quick work - two days after the blog post.
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...
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...
It is caused by Control Flow Guard introduced in 8.1, so there's no point testing other versions.
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/contr...
[1] https://docs.microsoft.com/en-us/windows/desktop/secbp/contr...
Seeing how many O(n^2) he found, I think you could've stopped your sentence at tested.
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/4e41d621c3f413eb31da2...
https://github.com/google/guava/commit/4e41d621c3f413eb31da2...
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)?
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.
Sounds like it might work much better to only have as many processes as there are logical cores.
Most build processes are going to run at least the compiler once per code file. Plus or minus a linker and preprocessor and whatever else. Nobody said all 70,000 quoted processes were run simultaneously.
You could presumably write a compiler that didn't do the traditional start - read - process - output - quit cycle to avoid paying startup costs, but it is generally assumed that startup cost is small relative to processing, and that avoiding complexity is worth the cost; if your OS makes startup really expensive, maybe that's not a reasonable assumption.
You could presumably write a compiler that didn't do the traditional start - read - process - output - quit cycle to avoid paying startup costs, but it is generally assumed that startup cost is small relative to processing, and that avoiding complexity is worth the cost; if your OS makes startup really expensive, maybe that's not a reasonable assumption.
We avoid having more processes that cores running at a time. But we run a separate compiler instance for each file we compile, 'cause why not? So, 70,000 processes over the length of the build.
Compilers generally instantiate one process per input file. (.cpp or .c files, but not .h) Because the compiler writer can generally be assured that the process is very short lived, compilers are typically written to never use free(). When the object file is created, the process exits, and the memory is freed by the OS. This is generally a significant speedup.
Unit tests. When a unit test crashes, that crash needs to be logged, and it can't interrupt the other tests. The good way to do this is by creating a new process per unit test.
Some web servers in certain configurations will start one process per connection. If you have 1000 simultaneous connections, you have 1000 processes. https://httpd.apache.org/docs/2.4/mod/mpm_winnt.html
That's 3 examples. There are others.
Unit tests. When a unit test crashes, that crash needs to be logged, and it can't interrupt the other tests. The good way to do this is by creating a new process per unit test.
Some web servers in certain configurations will start one process per connection. If you have 1000 simultaneous connections, you have 1000 processes. https://httpd.apache.org/docs/2.4/mod/mpm_winnt.html
That's 3 examples. There are others.
The article literally answers that. It's very common for unit tests and building infra, especially when ported from POSIX systems.
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.
As a workaround for perf issues like the article, you might choose to reuse the same process more instead, but it's a tradeoff.
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
I would argue that O(n^2) algorithms are really only acceptable if n is known to be bounded well ahead of time. In large integer libraries like GMP, O(n^2) multiplication is switched out for asymptotically better and better algorithms as n gets too large: https://gmplib.org/manual/Multiplication-Algorithms.html
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.
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.
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.
Off course it is. The n is fixed.
Also as a side note, n^2 is not the lowest order algorithm for multiplication.
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.
What's the runtime of 75^4096 mod 236?
That sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".
a^n mod m requires O(log(n)) iterations in the outer loop. If m fits in one machine word, each iteration is O(1). If m is large, each iteration is O((log m)^2).
For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup.
https://godbolt.org/z/KNX4pi
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...
For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup.
https://godbolt.org/z/KNX4pi
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...
O(1) - constant time. The answer is 29. I just happen to know that.
I think you need an 'n' in there before it is meaningful to ask about the runtime.
I think you need an 'n' in there before it is meaningful to ask about the runtime.
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.
It would be bad to have the OS cover this use case by default.
You don't think an OS/kernel should be expected to perform the most basic of kernel tasks well?
Also creating a lot of processes to run your tests is a perfectly normal use case. In this case they're running 10 per process, but creating 1 process/test (so as to not leave any corrupt memory/state behind after a failed one) would also be perfectly reasonable.
Also creating a lot of processes to run your tests is a perfectly normal use case. In this case they're running 10 per process, but creating 1 process/test (so as to not leave any corrupt memory/state behind after a failed one) would also be perfectly reasonable.
Am I misunderstanding this;
there are 1000 instances of a process stemming from a 120Mb executable, and initializing it 1000 times is kind off slow unless you chose to turn off some branching integrity check.
I don't think other OSs have this much trouble, but I haven't performed my own testing, so take this statement with a grain of salt.
Dunno. But reading the test readme it seems like gLinux (GNU/Linux? RS' new angle?) has other problems that need dehacking.
I mean running test like this is fine who cares. But it's probably bad architecture for the unit test that makes it take time rather than the OSes. And that's fine because it's not production code. But not ground for a condescending snarky blog post.
https://www.chromium.org/developers/testing/running-tests
'Run tests 5x faster on gLinux Browser tests on gLinux start up extremely slowly due to idiosyncratic NSS configurations. If you need to regularly run browser tests on gLinux, consider using the run_with_dummy_home.py helper script:
I mean running test like this is fine who cares. But it's probably bad architecture for the unit test that makes it take time rather than the OSes. And that's fine because it's not production code. But not ground for a condescending snarky blog post.
https://www.chromium.org/developers/testing/running-tests
'Run tests 5x faster on gLinux Browser tests on gLinux start up extremely slowly due to idiosyncratic NSS configurations. If you need to regularly run browser tests on gLinux, consider using the run_with_dummy_home.py helper script:
testing/run_with_dummy_home.py testing/xvfb.py out/Default/browser_tests
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...)
(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...)
This OS performance bug does not add 10 seconds to boot time. That would only be the case if those startup processes were enormous .exe files, which they generally are not. The O(n^2) chart in the blog post shows that the cost of this issue is modest for most executables.
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.
That's not the same thing as it's slow to add normal sized processes.
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.
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.
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.
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.
I have been told that moving the meat of unit_tests.exe to a DLL would avoid the repeated CFG initialization costs (they would be paid on the first CreateProcess call and then the CFG data would be shared). This wouldn't speed up the tests "more" than my change did (it would speed up the tests slightly less, actually), but it would be a possible fix.
But, such a change would be more work. And, honestly, it shouldn't be necessary. Windows could avoid this problem by using an O(n) algorithm for the initialization, or by sharing the CFG data between .exe files as well as .dll files. I am content with my current workaround and I'll consider reverting it when the underlying OS issue is fixed.
Note that the chrome executable on Linux contains all of the code so it is 50-100 MB. It is only an accident of history that chrome.exe on Windows puts all the code in chrome.dll/chrome_child.dll
But, such a change would be more work. And, honestly, it shouldn't be necessary. Windows could avoid this problem by using an O(n) algorithm for the initialization, or by sharing the CFG data between .exe files as well as .dll files. I am content with my current workaround and I'll consider reverting it when the underlying OS issue is fixed.
Note that the chrome executable on Linux contains all of the code so it is 50-100 MB. It is only an accident of history that chrome.exe on Windows puts all the code in chrome.dll/chrome_child.dll
I have a sneaky suspicion you're right, windows generally assumes any 'shared' code will be in DLLs and is optimized around ensuring they are shared as much as possible in memory. It's likely that if the tests were in a DLL vs. the EXE then windows would just share the CFG page for that DLL read only between all the processes and call it done.
The size of the executable doesn't really matter after the first load as subsequent loads share the mapped section so it doesn't need to be loaded from disk again. Loading an executable multiple times after the first time really shouldn't take all that long from an OS perspective...just some mapping of shared pages.
> The size of the executable doesn't really matter
> after the first load
shouldn't really matter. If you have CFG enabled then it does. If they fix CFG's initialization then it will go back to not mattering, and even this huge process will be created in just a few ms.
shouldn't really matter. If you have CFG enabled then it does. If they fix CFG's initialization then it will go back to not mattering, and even this huge process will be created in just a few ms.
[deleted]
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.