O(N^2) in CreateProcess

https://randomascii.wordpress.com/2019/04/21/on2-in-createprocess/

by nikbackm • 7 years ago

154 58 7 years ago

randomascii.wordpress.com

rightbyte9• 7 years 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.

AstralStorm• 7 years 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...)

rightbyte9• 7 years 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.

brucedawson8• 7 years ago

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.

chmod7752• 7 years ago

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.

rightbyte9• 7 years ago

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.

nonsince• 7 years ago

I absolutely love this series

magicalhippo2• 7 years 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.

rightbyte9• 7 years 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• 7 years 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.

magicalhippo2• 7 years 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• 7 years 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_s2• 7 years 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.

bjoli• 7 years ago

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

JoeAltmaier• 7 years 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?)

w8rbt3• 7 years 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• 7 years 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.

w8rbt3• 7 years ago

Right, it's a pity RSA does not use 32 or 64 bit ints.

rightbyte9• 7 years 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.

joppy• 7 years ago

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

varelaz2• 7 years 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_dos12• 7 years ago

The article literally answers that. It's very common for unit tests and building infra, especially when ported from POSIX systems.

MaulingMonkey• 7 years 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.

varelaz2• 7 years ago

Sorry, I thought problem is with thousands parallel processes execution. There problem is with some remainings from previous process runs.

brucedawson8• 7 years 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.

BubRoss2• 7 years ago

Sounds like it might work much better to only have as many processes as there are logical cores.

nwallin2• 7 years ago

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.

charleslmunger• 7 years 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/4e41d621c3f413eb31da2...

peter_d_sherman• 7 years 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• 7 years ago

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

kristianp• 7 years 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/contr...

aneutron• 7 years ago

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

brucedawson8• 7 years ago

Update: Microsoft has built a fix for the issue.

https://twitter.com/mamyun/status/1120878048620892166

Pretty quick work - two days after the blog post.

O(N^2) in CreateProcess

Related Stories