Hi there,

when running the attached program "spawn_test.c" on my machine (see end
of this mail), I get the following results (as measured with
"/usr/bin/time"):

cycles | elapsed time
---------------------

  2000  | 0:01.69
  4000  | 0:04.04
  8000  | 0:10.72
16000  | 0:32.51
32000  | 1:46.85

, indicating that the runtime increases non-linearly. An "strace" for the
program shows that single "execve/wait" calls are requiring more and more
time, when the total memory usage for the program goes up.
Note how the processes don't run in parallel, but are started one after
the other in the single "cycles"...
By setting the define USE_EXECUTE to "0", one can confirm that it's indeed
the wait call (and not the execlp) that grows in time.
As you can see in the source file, I also used "ptrace" to find out whether
it's the number of actual instructions that increases:

cycles | instructions
---------------------

  4000  |  806848773
  8000  | 1613697249

So the number of machine instructions scales linearly, hence it appears 
to be
more of a timing/locking/scheduling problem to me.
During my runs, the total process never consumed more than 10% of the
available RAM in the system. That's why I'm currently not looking in
the area of memory management (fragmentation?).

I tried to understand the code of "do_wait" in kernel/exit.c
(v3.2.0 sources), but am a bit lost as to where and how to continue my
debugging.

Here are my questions:

- Can someone reproduce my results on his side?
- What's the reason for this behaviour, is it known already or even
   expected?
- Are there any kernel parameters/settings that influence it, and could
   possibly be tweaked? How can the time performance be improved?
- Are the timing outputs of "strace" reliable under the given
   circumstances, or do I have to debug this differently?

Thanks a lot in advance for your answers. Please CC me directly, I'm
not subscribed to this list.
I'd really appreciate any pointers on how to debug this further,
where to look in the sources, what additional docs to read...or anything
else I could try. It'd be even more awesome if a kernel developer, with
the necessary experience under his belt, could take it from here and
find out what's going on.

ad STFW: I searched the LKML archives, http://lwn.net/Kernel/Index and
the web for keywords like "exec, wait, performance, futex, hash, table"
(in various combinations) and found the discussion at
https://lkml.org/lkml/2013/11/23/15.
I also tried to grasp the source of "futex.c", but I don't know enough
about the kernel to tell whether the above problem is related to futexes
or not.
I couldn't find any reports or discussions about performance problems
related to exec*/wait, combined with growing memory usage.


Best regards,

Dirk Baechle


P.S.: This is not a toy project. What's actually behind it are my
profilings for the build system SCons (www.scons.org)...please visit
http://scons.org/wiki/WhySconsIsNotSlow to find out more.
I'm trying to improve its performance, for which the
above problem seems to be the key.

P.P.S.: Some data about my machine...

OS       = Ubuntu 12.04.4 LTS
CPU      = 2x Intel(R) Core(TM)2 Duo CPU E8300 @ 2.83GHz
RAM      = 2GB
uname -a = Linux ubuntu 3.2.0-58-generic #88-Ubuntu SMP
            Tue Dec 3 17:37:58 UTC 2013
            x86_64 x86_64 x86_64 GNU/Linux